Morgan Stanley

Here are few puzzles asked in the Morgan Stanley's test yesterday:

1. i) Prove that Trace(A) = sum of eigen values.

ii) If Trace(A)=1, Trace(A^2)=3, Trace(A^3)=9, then find the value of det(A).

2. You have a square matrix of size N x N. From each block you can move to any of the 8 adjacent blocks. Moving to one particular block(zero cost direction) has a cost of zero. Moving to rest of the 7 blocks has cost 1. You have been given two points S and E. You have been also given the zero cost direction for each block. Give an efficient algorithm to find the optimal path from S to E.

3. You have been given [m(m-1)^2+1] points in a Cartesian plane. Each the these points is an integer point i.e. both x and y co-ordinates are integer. Prove that you can always find m points such that centroid of those m-points is also integer point.

4. Let A be a array of integers. Find the minimum of all k-consecutive elements in O(n) time.

Ex: if A=[2 3 5 1 3 5 6] and k=3 then your answer should be [2 1 1 1 3].