Morgan Stanley Quant Test

Morgan Stanley took a test for it's Quantitative Analyst profile. The test had 2 sections "Easy" and "Difficult" and total duration was about 2.5 hours.

Easy

1) Prove no square matrices A, B exists such that AB-BA = I. (Hint: use trace(X))

2) Each amoeba my transform to 0 amoeba (means that it's dead), 1 amoeba (stays itself) or 2 amoebas (reproduces a child). We initially have 1 amoeba. Find probability of the process up with 0 amoeba in the end.

3) Consider all strings composed of of {0, 1, 2}. Find number of strings such that no two 1s are consecutive in the string.

4) Given X, Y are Uniform(0,1) random variables. Find distribution of X^2 + Y^2.

5) Write algorithm to find lowest common ancestor of 2 nodes in a binary tree.

6) Solve the recurrence f(a, b) = f(a, b-1) + f(a-1, b-1) with base cases
    f(0, 0) = 1,
    f(0, k) = 0,
    f(k, 0) = 1. (Hint: Did you observe it's a Pascal Identity)



Difficult

1) Give an algorithm to find longest alternating subsequence in an array of numbers. The sequence need not be continuous. Alternating means that 1st term is greater than 2nd term, 2nd term is smaller than 3rd term and so on OR 1st term is smaller than 2nd term, 2nd term is greater than 3rd term and so on.

2) You are given a stream of numbers. Give an efficient data structure to find median of the numbers read so far from the stream in O(1) time.

3) You are given w white balls and b black balls initially in a box. Each time we randomly draw a ball from the box and remove it.We continue until no white ball is left in the box. Find the expected number of black balls in the box in the end.

4) Give a method to randomly choose any K-size subset from an N-size subset, however, N is not known to you.

5) Find all functions f, such that f(mA+nB) = mf(A) + nf(B), f(AB) = f(BA), where A, B are square matrices, find f in terms of a matrix M.