SDE - Intern

The avengers have the responsibility to save the world. To perform this task they have divided their responsibility such that each one takes the responsibility of one city. Mr. Stark aka Iron Man got the responsibility of the city Malibu. The only safe place in the city is the Stark tower. Now, Iron Man has to shift trapped people from different parts of the city to the Stark tower.

But he can only shift one person at a time. Due to less time he wants to take the shortest possible path. Help him to find the minimum distance that he had to cover to rescue all the trapped people.

Note:

1. Positions are represented by the cells in a 2D grid.
2. The positions of people don’t overlap.
3. Iron Man can move only up, down, left, and right to the adjacent cell.

You are given a string 'STR' containing lowercase English letters from a to z inclusive. Your task is to find all non-empty possible subsequences of 'STR'.

A Subsequence of a string is the one which is generated by deleting 0 or more letters from the string and keeping the rest of the letters in the same order.

You are the HR of the Ninja team and planning to hire ‘M’ candidates out of ‘N’ candidates to form a paid group. The candidates have been evaluated on the basis of their skills and have been asked for their minimum salary expectations. So, you are given two arrays, ‘SKILL’ and ‘EXPECTED_SALARY’, where ‘SKILL[i]’ and ‘EXPECTED_SALARY[i]’ represent the skill and minimum salary expectation of ‘i-th’ candidate, respectively. You have to consider the following two rules for hiring a group of ‘M’ candidates:

1) Every candidate in the paid group should be paid in the ratio of their skill compared to other candidates in the paid group.
2) The minimum salary expectation of every candidate in the paid group should be fulfilled.

You have to return the minimum amount of money required to hire ‘M’ candidates as per the above-mentioned rules.

Note:

Answers which are within the range 10^-6 of the correct answer will be considered correct.

You are given an array of size ‘N’. The elements of the array are in the range from 1 to ‘N’.

Ideally, the array should contain elements from 1 to ‘N’. But due to some miscalculations, there is a number R in the range [1, N] which appears in the array twice and another number M in the range [1, N] which is missing from the array.

Your task is to find the missing number (M) and the repeating number (R).

For example:

Consider an array of size six. The elements of the array are { 6, 4, 3, 5, 5, 1 }. 
The array should contain elements from one to six. Here, 2 is not present and 5 is occurring twice. Thus, 2 is the missing number (M) and 5 is the repeating number (R). 

Follow Up

Can you do this in linear time and constant additional space? 

You are given an array 'ARR' of 'N' positive integers. Your task is to find if we can partition the given array into two subsets such that the sum of elements in both subsets is equal.

For example, let’s say the given array is [2, 3, 3, 3, 4, 5], then the array can be partitioned as [2, 3, 5], and [3, 3, 4] with equal sum 10.

Follow Up:

Can you solve this using not more than O(S) extra space, where S is the sum of all elements of the given array?

You are given a binary tree consisting of ‘N’ nodes. Your task is to replace all the half nodes present in the binary tree with its child node. Half nodes are those nodes that have only one child.

For Example:

In this given binary tree, nodes 7, 5, and 9 are half nodes because they have only one child node. So we have to replace these nodes with their child. The inorder traversal of the updated binary tree is [1, 6, 11, 2, 4]. Hence, the answer is [1, 6, 11, 2, 4].

Example:

Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. 

The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

ACID Properties
SQL VS NO-SQL
Indexing and Its type
OSI Layers
How internet works

Design a HLD of Messaging App