Bloomberg - Nov 22, 2008

[Interview in person]

1. Given a list of numbers, describe an algorithm to find the maximum number on that list.

Sol: Compare the first two and record the maximum in a variable called MAX. Move on to the third one, compare it to MAX, and update MAX with the maximum between these two. Keep doing that as you run over the array of numbers. At the end MAX will have the maximum number of the list.

2. How about for finding the second largest number on that list?

Sol: Of course you could run twice over the array, but there's a better way to do it. Compare the first two and record the maximum in a variable called MAX1 and the other one in a variable called MAX2. Move on to the third one and compare it to MAX1. If it is larger than MAX1, then update MAX2 with the current value at MAX1, and MAX1 with the third number on the array. If it is not larger, then update MAX2 with the maximum between the current value at MAX2 and the third number. Continue doing this over the entire array and at the end MAX1 and MAX 2 will have the maximum and the second maximum of the list.

3. There are eight coins that look exactly the same, but one of them is heavier than the other seven. The other seven all weight the same. With a scale and two tries, how do you find the heaviest coin?

Sol: Divide the group into three groups of 3, 3 and 2. Weigh the two groups of 3. If they weigh the same, then the heaviest coin is in the group of 2 and one more use of the scale will give us the heaviest coin. If they don't, then you are left with one group of 3 containing the heaviest coin and one more use of the scale with two of those three coins will give you the heaviest coin.

4. There are five containers with pills. One of the containers has only contaminated pills and the other four have only non-contaminated pills. With one scale and one try, how would you find the container with the contaminated pills if a contaminated pills doesn't weigh the same as a non-contaminated pill?

Sol: I wasn't asked this question but heard people talking about it afterwards. I started thinking like if they were the coins of question 3., but that might take two tries. After a while I had no idea. I looked it up when I got home. I found it here (question #10) with way too many other riddles. I don't really like riddles (that I don't know know how to solve ;)).

Bloomberg - Nov 19, 2008

[Phone interview]

1. Suppose you have a loop where a variable of type double is being incremented by one with each iteration. What would happen if the condition in the loop is never satisfied?

Sol: I didn't know at the time of the interview. Now I have some idea. It never stops, even though a double variable has bounds. Why? I don't know. Something about the number of bits assigned to this variable in memory being reached. All I know is that when I coded it, by printing the current value of the variable, it reaches a value that the computer (or the compiler?) calls inf (as infinity) with arithmetic inf + 1 = inf. Funny business :)

2. Consider the Poisson equation in two dimensions on the square [0,1]x[0,1]. Explain how to use finite differences to solve numerically this problem.

Sol: Poisson equation in two dimensions is

u_xx + u_yy = f

The most common approximation scheme I know is by doing a centered approximation for each u_xx and u_yy as follows. First, for u_x:

u_x ~ (u(x+h/2,y) - u(x-h/2,y))/h

and so for u_xx:

u_xx ~ [(u(x+h,y) - u(x,y))/h - (u(x,y) - u(x-h,y))/h]/h
u_xx ~ [u(x+h,y) - 2u(x,y) + u(x-h,y)]/h^2 =: approx(u_xx)

Similarly with u_yy...

3. What's the accuracy of that approximation?

Sol: I never remember. Fortunately, it's not hard to deduce. Doing a Taylor expansion for u(x+h) and u(x-h), one gets...

u(x+h) = u(x,y) + hu_x(x,y) + 1/2(h^2)u_xx(x,y) + 1/6(h^3)u_xxx(x,y) + 1/24(h^4)u_xxxx(x,y) + ...
u(x-h) = u(x,y) - hu_x(x,y) + 1/2(h^2)u_xx(x,y) - 1/6(h^3)u_xxx(x,y) + 1/24(h^4)u_xxxx(x,y) + ...

Hence,

approx(u_xx) = u_xx(x,y) + 1/12(h^2)u_xxxx(x,y) + ...

and so the accuracy of this approximation is of order two.

4. What kind of problem you need to solve at the end to find the approximate solution? How would you solve it?

Sol: A linear problem. It's a system of linear equations. After both [0,1] in x and in y are subdivided into n sub-intervals we would have a system of (n-1)^2 unknowns with (n-1)^ equations. That is we would need to solve a linear system of the form Ax = b where A is a square matrix of size (n-1)^2. To solve that problem, if n is not big, I would use Gaussian elimination, but typically n is large. In that case I would use a gradient descend method to find the minimum of the function g(x):=1/2|| Ax-b||^2. The gradient of g is A^t(Ax-b), so the gradient descend iteration is of the form

x_{n+1} = x_n - a(A^t)(Ax-b)

where a is a small positive constant (that might change with n).

5. Is the function g a convex function?

Sol: Yes, since the Hessian of g is the matrix (A^t)A which is a positive semi-definite symmetric matrix.

6. What test would you use to discard outliers in a sample?

Sol: I have no idea. Read about it on wikipedia if you dont know... as I did :)

7. Suppose the probability of getting a head (H) in a coin is p. What is the expected number of tosses until you get the first H?

Sol: Interviewers seem to like this question. I gave the rigorous answer by considering the possible scenarios for the number of tosses together with their correspondent probabilities, and then calculate the expected value. They wanted to hear the solution using conditional expectation. It's pretty much like I did it here. The expected number of tosses until you get the first H is 1/p.

8. In C, what's a structure? Give an example of code using one.

Sol: I wrote on my resume I know C and very basic C++, so I guess that's why he asked me for C. Anyway, I should know in C++ what a structure (and a class) is and do examples. Read it all here... yes, on wikipedia.

9. Consider the Fibonacci sequence. Write a code for generating the n-th term in this sequence.

Sol: Do not write the code I did. I wrote a very inefficient recursive algorithm (and very bad for allocating memory). Check out this link with four different functions for doing that. Which one is the best? P.S> I wrote fibonacci1a for the interview... ups.

10. Consider the numbers {1,2,...,n}. I take one of them and I give you the other (n-1) numbers ordered in any way I want to. Find an efficient algorithm to get the number that is missing.

Sol: Nice question. I couldn't get it right, or rather I couldn't suggest anything of order less than nln(n). The interviewer said there was one of order n and I couldn't believe it. He was right. Here is a clever way of doing it (suggested by my housemate): The sum of all {1,2,...,n} is n(n+1)/2 (three operations). Add all the given numbers (for which you make n-2 operations) and substract the result from n(n+1)/2. The result is the missing number! (and you made n+2 operations!). Simple and cool.

11. In C, what's a static variable?

Sol: This is what it is. I can't explain it better.

Morgan Stanley - Nov 17, 2008

[Phone interview]

1. There are two children in a family and one of them is a boy. What's the probability that the other one is a girl?

Sol: A sample space for the event of a family with two children could be the set of touples {(B,B), (B,B), (G,B), (G,G)}. We are given that one of them is a boy, hence the conditional sample space would be {(B,B), (B,B), (G,B)} and thus the probability that the other child is a girl is 2/3.

2. What's the expected minimum number of tosses you need to get three consecutive heads in a row?

Sol: Tricky. A rigorous solution would be pretty long (I attempted it and couldn't finish it in the time given), but after the interview I found an easier one. Here it is. Let N be the expected minimum number of tosses you need to get three consecutive heads in a row and condition on the first three outcomes as follows:

1. If you get a T (tail), then the expected minimum number of tosses you need to get three consecutive heads in a row increases by one. The probability of having T is 1/2.
2. If you get a H (head) and then a T, then the expected minimum number of tosses you need to get three consecutive heads in a row increases by two. The probability of having HT is 1/4.
3. If you get HH in the first two toses and T in your third one, then the expected minimum number of tosses you need to get three consecutive heads in a row increases by three. The probability of having HHT is 1/8.
4. But if you get HHH, then you only took three tosses to get three consecutive heads in a row. The probability of having HHH is 1/8.

Thus,

N = (1/2)(N+1) + (1/4)(N+2) + (1/8)(N+3) + (1/8)(3)

which implies that N=14. (This solution assumes N is not infinity, and that's why a more rigorous solution is needed, although I am sure they are not looking for that on the phone)

3. There is a party and everybody shakes hands with everybody. There were 66 hand shakes. How many people were at the party?

Sol: If there are N people, let's line them up. Person 1 hand shakes with N-1 people to his right, Person 2 hand shakes with N-2 people to his right, and so on. Thus there are a total number of

(N-1) + (N-2) + (N-3) + ... + 2 + 1

hand shakes. There are N-1 terms above. Thus in total there are N(N-1)/2 hand shakes. If that number is 66, then N has to be 12.

4. It takes 1.5 people to drink 1 liter of vodka in 1.5 hours. How many people would be needed to drink 0.4 liters in 45 minutes?

Sol: The question, assuming constant rates and people drink at the same rate (etc, etc, etc), is the same as finding out how many people would be needed to drink 0.8 liters in 1.5 hours. Then the time information is not important anymore. So the question now is how many people would be needed to drink 0.8 liters given that 1.5 people drink 1 liter. A straightforward calculation says 1.2 people are needed. (I got very confused with this stupid question... it was so easy. I blew it)

Why this blog?

Because I decided to keep track of the questions (and some solutions) I am being asked during the process of interviewing to become a quant, for my own benefit. This might be helpful for someone else one day too. Feel free to comment if you you think I am wrong, or don't agree with any of my solutions, or have a more clever one.