1. Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree. Hint: Some kind of pointer handling with In Order Traversal

2. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.

3. Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?

Answer :

Consider 2 points A and B and a line L which is equidistant from both A and B.

if L does not intersect the line segment AB, then L must be parallel to AB.

if L does intersect AB, then L must pass through the midpoint of AB, also any line through the midpoint has this property.

So given A,B,C not all collinear, consider the midpoints X,Y,Z.

Pick any two points from X,Y,Z and consider the line joining them. It is equidistant from all three points.

Thus there are exactly three lines.

4. Classic - Egg Problem

You are given 2 eggs.You have access to a 100-storey building.

Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

5. There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

Hint:

1. Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
2. It should be done in O(n).

6. There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).

Answer :

Can be done easily in o(n) time and 2 *n extra space.

Arr1[n] and Arr2[n] are the two extra space arrays while Arr[n] is the original array

Arr1[i] = Arr[0] *Arr[1]* ... *Arr[i]
while
Arr2[i]= Arr[n-1]*Arr[n-2] ..Arr[i]

now final Arr[i] = Arr1[n] - ( (Arr[i]-1)*Arr1[i-1] *Arr2[i+1])

Handle Arr[0] and Arr[n] Separately like Arr[0] would be Arr2[1] while Arr[n] would be Arr1[n-1].

7. Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?