Morgan Stanley QED: Round1

Morgan Stanley organized a contest Q.E.D in 2012 to promote Mathematics in Finance among the students of IITB. It kicked off with a talk on Quantitative Finance by Ashwin Rao (Managing Director, Morgan Stanley India). For the contest, there were 3 elimination rounds. Round #1 had the following questions.

Objective Section

1) Let P be a projection, so P*P = P. Compute inverse of (I - cP) given c = 1/2, where I is the identity matrix.

2) Two creepers, C1 and C2, are both climbing up and round a cylinder. C1 twists clockwise and C2 anticlockwise, both start at the same point at the bottom. Before they reach the top of the cylinder C1 had made 5 complete twists and C2 had made 3 complete twists. Not counting the bottom and the top, how many times do their paths intersect?

3) Compute Σ ( i^5 / 1000^6 ) over i = 1 to 1000, approximately.

4) For strings of length m + n, with m 0's and n 1's. Find the expected number of switches from 0 to 1 (a switch can be thought of as presence of '01' in the given string).

5) Compute  ∫ (dt)^2.

6) Let I be an n*n identity matrix and J be an n*n matrix of all ones. Find the rank of I - (1/n)J.



Subjective Section

1) You have N cars that are all travelling the same direction on an infinitely long one-way highway. Unfortunately, they are all going different speeds, and cannot pass each other. Eventually the cars will clump up in one or more traffic jams. In terms of N, what is the expected number of clumps of cars?

2) Say a[1], a[2], a[3], ... a[N] be a permutation of first N natural numbers. a[i] is a maxima if a[i-1] < a[i] > a[i+1]. Find E[ number of maximas in a random permutation ].

3) Prove that E[x] = ∫ (1 - F(x)) dx over the range [0, ∞], where F is the cumulative distribution function.

Walmart Labs Test

Walmart Labs opened it's India division very recently. It has been on a hiring spree since then. The profile was Software engineering in the area of Machine Learning and Big Data.

It conducted a 1.5 hour test which consisted of 15 objective questions based on basic concepts in Networks, Data structures & Algorithms, some simple questions on Combinatorics.

There was a subjective section too, which had 2 questions to be coded on a piece of paper.



1) Given 2 additional members, node* prev, node* next in a binary tree node* struct. Initially prev and next are set to NULL. Populate these 2 pointers in the binary tree using inorder successor and predecessor of the respective node for all nodes in the tree.

2) BreakDown(K, S). Give an algorithm to calculate number of distinct ways in which you can break up amount K into denominations present in S, set of denominations. 

Pocket Gems Coding Test

Following coding questions were asked by Pocket Gems, a social gaming company based in San Francisco. Total duration was 1 hour.

1) Given an array of positive numbers. We can make any element of the array negative. We have to find the minimum positive sum after modifying numbers of array, by making some numbers negative.

2) Given an array of pairs of the form <a, b>. We have to find a sub-array such that the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible.

Source: Arun Chaudhary, DCE

Microsoft Internship Interview

It was August, 2011 and start of my 3rd year at IITB. It was internship season at IITB and I was desperately looking for a summer internship. Microsoft visited the campus and I was shortlisted (based on CPI) for interviews.

There were no personal interviews. Instead, every batch of 10 students was taken in a classroom and we were given to solve a couple of questions. We were asked the following questions and we had to write working-code on a piece of paper.

1) Coin-change problem. Given unlimited denominations of 1$, 2$, 5$, 10$; find the total number of ways to make change for amount 100$.

2) Given strings a, b, c. Replace all occurrences of string b in a with string c. Note that there is no restriction on lengths of a, b, c.

Somehow, I managed to code up the problems but not very neatly. I asked the interviewer to check my solutions. He stared at the code I had written for a couple of minutes and then asked me some questions and tried to confuse me. He then asked me about the complexity of my code and I was able to estimate it correctly. He then said that I was done with the process and could leave.

I thought that my interview performance was not up to the mark and didn't expect that I could get selected by Microsoft. However, later on, in the night I got a call saying that I had been selected by Microsoft for it's Summer Internship Program. Phew! I was relieved and my worries about getting an summer internship vanished all-together. :)


Key Takeaways

• You should be able to write neat code at one go. Practice writing actual code (C++/Java) on a piece of paper or white-board.
• Do some dry runs of your code for some test-cases and check whether it's doing what it's supposed to do.
• You need to cross-check your code twice and look out for small mistakes that you might commit due to interview pressure.