SDE - Intern

Euclid, Pythagoras, Pascal and Monte plan to play in a park. Pascal, Monte and Euclid enter the park first and stand at three different arbitrary positions. As Pythagoras is the last one to reach the park, he decides to stand in such a way that the four points form a parallelogram if joined with each other. The positions of Euclid and Monte form one of the two diagonals of the parallelogram.

Your task is to help Pythagoras determine the coordinates of the point where he must stand so that a parallelogram is formed.

A parallelogram is a simple quadrilateral with two pairs of parallel sides. The opposite or facing sides of a parallelogram are of equal length and the opposite angles of a parallelogram are of equal measure

For example, consider the scenario shown below. The coordinates of Euclid, Pascal, and Monte have been shown in the figure. 

Euclid and Monte are standing at the endpoints of a diagonal and Pascal is standing at one vertex of the other diagonal. Using the coordinates of Pascal, Euclid and Monte, figure out the coordinates of Pythagoras, which will be (10, 15).

Note:

The coordinates of Pythagoras will be unique for the unique values of the other three coordinates.

You have been given an undirected graph having ‘N’ nodes. A matrix ‘E’ of size 'M' x 2 is given which represents the ‘M’ edges such that there is an edge directed from node 'E[i][0]' to node 'E[i][1]'. You are supposed to return the size of the set of the minimum number of nodes from which all the other nodes are reachable (set of nodes/ vertices which contains at least one point of every edge in the given graph).

Example :

In the graph given below:

2 ---- 4 ---- 6
|      |
|      |
|      |
3 ---- 5

Here, the minimum vertex cover involves vertices 3 and 4. All the edges of the graphs are incident on either 3 or 4 vertex of the graph.

Note:

1. Nodes are numbered from 1 to 'N'.

2. Your solution will run on multiple test cases. If you are using global variables make sure to clear them.

A thief is robbing a store and can carry a maximum weight of ‘W’ into his knapsack. There are 'N' items available in the store and the weight and value of each item is known to the thief. Considering the constraints of the maximum weight that a knapsack can carry, you have to find the maximum profit that a thief can generate by stealing items.

Note: The thief is not allowed to break the items.

For example, N = 4, W = 10 and the weights and values of items are weights = [6, 1, 5, 3] and values = [3, 6, 1, 4]. Then the best way to fill the knapsack is to choose items with weight 6, 1 and 3. The total value of knapsack = 3 + 6 + 4 = 13.

Given a list of cities numbered from 0 to N-1 and a matrix 'DISTANCE' consisting of 'N' rows and 'N' columns denoting the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the starting city?

You are given an Integer ‘N’ you have to convert the integer to words.

For example you are given integer N = 2234 then you have to return the string “two thousand two hundred and thirty four”.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

1. Push(num): Push the given number in the stack.
2. Pop: Remove and return the top element from the stack if present, else return -1.
3. Top: return the top element of the stack if present, else return -1.
4. getMin: Returns minimum element of the stack if present, else return -1.

For Example:

For the following input: 
1
5
1 1
1 2
4
2
3

For the first two operations, we will just insert 1 and then 2 into the stack which was empty earlier. So now the stack is => [2,1]
In the third operation, we need to return the minimum element of the stack, i.e., 1. So now the stack is => [2,1]
For the fourth operation, we need to pop the topmost element of the stack, i.e., 2. Now the stack is => [1]
In the fifth operation, we return the top element of the stack, i.e. 1 as it has one element. Now the stack is => [1]

So, the final output will be: 
1 2 1

There are ‘N’ people at a party. Each person has been assigned a unique id between 0 to 'N' - 1(both inclusive). A celebrity is a person who is known to everyone but does not know anyone at the party.

Given a helper function ‘knows(A, B)’, It will returns "true" if the person having id ‘A’ know the person having id ‘B’ in the party, "false" otherwise. Your task is to find out the celebrity at the party. Print the id of the celebrity, if there is no celebrity at the party then print -1.

Note:

1. The helper function ‘knows’ is already implemented for you.
2. ‘knows(A, B)’ returns "false", if A doesn't know B.
3. You should not implement helper function ‘knows’, or speculate about its implementation.
4. You should minimize the number of calls to function ‘knows(A, B)’.
5. There are at least 2 people at the party.
6. At most one celebrity will exist.

You have been given a complete binary tree of ‘N’ nodes. The nodes are numbered 1 to ‘N’.

You need to find the ‘next’ node that is immediately right in the level order form for each node in the given tree.

Note :

1. A complete binary tree is a binary tree in which nodes at all levels except the last level have two children and nodes at the last level have 0 children.
2. Node ‘U’ is said to be the next node of ‘V’ if and only if  ‘U’ is just next to ‘V’ in tree representation.
3. Particularly root node and rightmost nodes have ‘next’ node equal to ‘Null’ 
4. Each node of the binary tree has three-pointers, ‘left’, ‘right’, and ‘next’. Here ‘left’ and ‘right’ are the children of node and ‘next’ is one extra pointer that we need to update.

For Example :

The‘next’ node for ‘1’ is ‘Null’, ‘2’ has ‘next’ node ‘6’, ‘5’ has ‘next’ node ‘3’, For the rest of the nodes check below.

You are given an 'N * N' matrix of integers where each row and each column is sorted in increasing order. You are given a target integer 'X'.

Find the position of 'X' in the matrix. If it exists then return the pair {i, j} where 'i' represents the row and 'j' represents the column of the array, otherwise return {-1,-1}

For example:

If the given matrix is:
[ [1, 2, 5],
  [3, 4, 9],
  [6, 7, 10]] 
We have to find the position of 4. We will return {1,1} since A[1][1] = 4.