Quantitative Interview questions and answers

[Matthew M]

4. (x_0 =1)
(x_n =1+\frac{2}{3x_{n-1}^2})
(x_1 = \frac{5}{3})
(x_2 = \frac{31}{25})
(x_3 = \frac{4133}{2883})

Can you find a closed form for (x_n)

This is the only one I can't figure out. I spent a good half hour on it, but it doesn't lend itself to any tricks I've seen before (it's not linear recursive, so I can't write down a linear operator and diagonalise it, it doesn't become more tractable if I write down (x_n) in terms of (x_{n-2}) or even earlier entries, I don't see an obvious way to do a "boomerang integration" type trick, and the pattern is not obvious enough that I can write down the answer and prove using induction).

Oh well.

 

[Andy Nguyen]

These are questions asked at some banks for front office or research quant position.

1.If a is a column vector, then how many non-zero eigenvalues does the matrix aa' have? what are the eigenvalues? What are the corresponding eigenvectors? What are the eigenvectors corresponding to the zero eigen values?
2. if w is an standard brownian motion, is w^3 a martingale?
3. prove that the price of a call option is a convex function of the strike price.
4. Suppose you are throwing a dart at a circular board. What is your expected distance from the center? Make any necessary assumptions. Suppose you win a dollar if you hit 10 times inside a radius of R/2, where R is the radius of the board. You have to pay 10c for every try. If you try 100 times, how much money would you have lost/made in expectation? Does your answer change if you are a pro and your probability of hitting inside R/2 is double of hitting outside R/2?
5. Suppose you have an old machine, which does not have a capability to multiply two numbers, but does have a capability to square a number. It also has addition and bit shift operators. Implement multiplication and division (integer division only)
6. Again the previous question, now you dont even have the squaring capability, but only bit shift, and addition. Implement multiplication
7. what do you know about const.
8. What is the problem with virtualization from the point of view of optimization. What can a compiler do when a function is not virtualized?
9. How is virtuality implemented in C++
10. integrate log^n x.
11. prove, from first principles, the differential of e^cos(x).
12. given the matrix A=(5 -3;-3 5), find a matrix M, such that A=M*M. Now find a matrix M such that A=M'*M
13. Suppose x_1, x_2...x_n are IID from [0,1] uniform interval. What is the expected value of the maximum. What is the expected value (max-min).
14. Suppose I have a routine that can sort n numbers in O(n) time. Prove me wrong.
15. Suppose you have the implied vol curve for call options. What is the arb free price of a digital struck at k given this implied vol curve.
16. Pricing a barrier option with a discrete barrier.
17. Distribution of the max of a brownian motion. Use it to price digital american and european call options.
18. Explain put call parity.
19. At one interview, I was asked to explain, in great detail, whatever I knew about the current credit problem (for about 25 mins). I did well only because I was reading the WSJ.
20. Given a fair coin, what is the expected number of trials you need to go to get 2 consecutive heads. 3 consecutive heads. generalize to N.
21. What is the variance on the number of trials in the question above?

 

[DominiConnor]

One well known firm went through a phase of asking candidates to prove Pythagoras theorem.
A surprising % floundered, in illuminating ways.

Some tried to remember the proof, and rather in the way of remembering the words of pop songs you liked when you were 15, there were gaps where candidates simply could not remember, as in "Baby we're on our way, we gonna mumble until the mumble gets high..."
Mumbling works better at retro pop concerts than mathematical proofs.

I would hope that people around here could work it out from first principles, and that is the way forward.

I'd also pick up on what Bob is saying. It is worth talking through your reasoning as you work these puzzles. It is very easy to hear a probability puzzle in a such a way that it is "A and B", rather than "A or B", which of course will lead you very astray.
Thus reflecting your interpretation, allows the interviewer to spot this and stop you drifting off track.

 

[msj]

These are questions asked at some banks for front office or research quant position.

1.If a is a column vector, then how many non-zero eigenvalues does the matrix aa' have? what are the eigenvalues? What are the corresponding eigenvectors? What are the eigenvectors corresponding to the zero eigen values?
2. if w is an standard brownian motion, is w^3 a martingale?
3. prove that the price of a call option is a convex function of the strike price.
4. Suppose you are throwing a dart at a circular board. What is your expected distance from the center? Make any necessary assumptions. Suppose you win a dollar if you hit 10 times inside a radius of R/2, where R is the radius of the board. You have to pay 10c for every try. If you try 100 times, how much money would you have lost/made in expectation? Does your answer change if you are a pro and your probability of hitting inside R/2 is double of hitting outside R/2?
...

hmm, i wonder where you got that list.

We are actually working on a book of questions and answers.

So i'd appreciate any contributions via Mark Joshi's Home Page or by e-mail.

 

[Andy Nguyen]

1) I have a well-shuffled deck of n red cards and n black cards, all facing down. I let you draw one card at a time. If you draw a black card, I pay you $1. If you draw a red card, you pay me $1. You can stop the game at any time. (As long as you want to play, I'll accommodate.)

1. What's the expected payoff of this game to you?

2. What's your optimal stopping rule?

[was asked at a Goldman Sachs on-site interview]

2) Three horses are in a race. Horse A is twice as likely to win as horse B, which in turn is twice as likely to win as horse C. What is the probability that horse A will not win the race?

3) Two princes are racing their horses. Each prince owns three horses, one in each "weight class." In every weight class, prince A's horse outruns prince B's, but a horse in a higher weight class always outruns a horse in a lower weight class. There will be three pairwise races, and each prince can enter any one of his horses into a race. The prince whose horses win 2 out of the 3 races gets the bragging rights.

How can prince B win?

[Adapted from a classic Chinese story]

4)Three horses are in a race. Horse A is twice as likely to win as horse B, which in turn is twice as likely to win as horse C. What is the probability that horse A will not win the race?

5) There are five bags containing the same number of coins. Four of the bags contain gold coins while the last bag contains silver coins coated with gold, and you are told that each gold coin weighs 10 oz. and each silver coin weighs 2 oz. less. You have a weighting scale (minimum=8 oz., maximum=large enough so you can weigh all five bags of coins) and you can take coins out of the bags. What's the minimum number of weighings you need to do in order to tell which bag has the silver coins?
[was asked this question at a State Street on-site a few years ago]

 

[dcifrths]

My feeling is 1/8 or 12.5% of it being a 6

thats gotta be right. conditional probability of it actually being a six and him reporting it to be a six.

Barron

 

[dcifrths]

1) I have a well-shuffled deck of n red cards and n black cards, all facing down. I let you draw one card at a time. If you draw a black card, I pay you $1. If you draw a red card, you pay me $1. You can stop the game at any time. (As long as you want to play, I'll accommodate.)

1. What's the expected payoff of this game to you?

E[game]= 0. trivial to prove.

2. What's your optimal stopping rule?

this is less clear to me. i'd think that it would be as soon as you are up. so if you win $1, you should stop and you should play until you are up $1.

that begs the question though, given the variance of the game, why not stop with more money? i don't know how to figure out the optimal stopping rule but would be curious to see it.

2) Three horses are in a race. Horse A is twice as likely to win as horse B, which in turn is twice as likely to win as horse C. What is the probability that horse A will not win the race?

P(C wins) = c.
P(B wins) = 2c.
P(A wins) = 4c.

c+2c+4c=1,
c=1/7.

P(A not wins) = 1-P(A wins) = 1 - 4*(1/7) = 3/7

3) Two princes are racing their horses. Each prince owns three horses, one in each "weight class." In every weight class, prince A's horse outruns prince B's, but a horse in a higher weight class always outruns a horse in a lower weight class. There will be three pairwise races, and each prince can enter any one of his horses into a race. The prince whose horses win 2 out of the 3 races gets the bragging rights.

How can prince B win?

A1 B1
A2 B2
A3 B3

3 = highest weight class

A(n) > B(n), but B(n+1) > A(n), so prince B can win if B(n+1) races A(n). that leaves A3 racing B1 while B2 and B3 race A1 and A2 respectively.

5) There are five bags containing the same number of coins. Four of the bags contain gold coins while the last bag contains silver coins coated with gold, and you are told that each gold coin weighs 10 oz. and each silver coin weighs 2 oz. less. You have a weighting scale (minimum=8 oz., maximum=large enough so you can weigh all five bags of coins) and you can take coins out of the bags. What's the minimum number of weighings you need to do in order to tell which bag has the silver coins?
[was asked this question at a State Street on-site a few years ago]

well the simple answer is at most it takes 5 weighings...but that is definitely wrong.

you can weigh sets of bags.

weighing 1: 3 bags.
weighing 2: 2 bags.

from there, you can tell which set of bags has the silver coins.

if it is set #2, it only takes 3 weighings,

if it is set #1, it takes 4 weighings...but both less than 5 weighings.

so minimum it takes via this methodology is 3 weighings.

Barron

 

[alain]

well the simple answer is at most it takes 5 weighings...but that is definitely wrong.

you can weigh sets of bags.

weighing 1: 3 bags.
weighing 2: 2 bags.

from there, you can tell which set of bags has the silver coins.

if it is set #2, it only takes 3 weighings,

if it is set #1, it takes 4 weighings...but both less than 5 weighings.

so minimum it takes via this methodology is 3 weighings.

Barron

here is my answer. let's take a single coin from every bag and market A, B, C, D and E so we know which coin belongs to which bag.

1) weigh 3 coins (ABC), if the weight is 30 oz, the silver coin is not here -> Go to step 2a. If the weight is less than 30oz, the silver coin is here, go to step 2b

2a) weigh one of the other coins D and leave E out. If D weighs 8 oz, D is the silver coin (and its bag is full of silver coins). If D weighs 10 oz, E is the silver coin. Total weighs 2.

2b) weigh 2 of the 3 coins (AB). If the weight is 20 oz, C is the silver coin. If not, do step 2a with A and B.

So, the minimum number of weighs to guarantee finding the false coin is still 3.

 

[nbzxroro]

To Andy`s original question:

1. Ans=sqrt(2).

let x^x.....=I=2. From the recursive feature we can see x^x^x.....=x^I. so x^I=x^2=2 (because I=2). then x=sqrt(2). The same technique is used to solve 6. let left hand side=I. Then sqrt(2+I)=I. so 2+I=I^2, two solutions, but you can only use the one bigger than 2 as the solution.

2. simple.

3. 1hr 5.4545 min.

At 1 O`clock, the angle between the two legs is pi/12. so the time it takes for the minute leg to catch the hour leg is: pi/6/(pi/30-pi/360)=5.4545 minute. Because the hour leg moves pi/6 in an hour(60 minute) and the minute leg moves 2pi in an hour (60 min).

4. 3/4.

The first and second points can be anywhere, only the third point matters. Let alpha be the angle determined by the two radius connecting the first and two points with the central point of the circle. The probability of the three points being different semicircle is that the third point lies in the area with angle alpha, so the probability is alpha/(2pi). alpha is uniformly distributed between 0 and pi, so the density is 1/pi. So the probability is the expectation of alpha/(2pi) with respect to the pdf 1/pi. By doing a simple integral the p is 1/4. So the probability of being in the same semicircle is 3/4.

5. 1/4.

Can be solved by figure. let x, y both uniformly distributed in [0,1], the sample space is a unit square. first assume x<y, so the probability is P(x<y, y>1-y, 1-x>x, 1-y+x>y-x) (the sum of any two is larger than the other), this corresponds to a triangular with an area of 1/8. For symmetry where x>y, you get another triangular with an area of 1/8. So the total probability is 1/4.

 

[nbzxroro]

To he yan's question:

Following the Bayesian Theorem: P=(1/6*3/4)/(1/6*3/4+5/6*1/4)=3/8

 

[juicyj]

1.If a is a column vector, then how many non-zero eigenvalues does the matrix aa' have? what are the eigenvalues? What are the corresponding eigenvectors? What are the eigenvectors corresponding to the zero eigen values?

Since aa' is a rank 1 matrix, there is only one nontrivial eigenvalue. If the eigenvalue is denoted c, then aa'v=cv. Also, taking the transpose of both sides, (aa'v)'=(cv)' meaning v'a'a=cv'. However, this time, a'a is a constant, so eigenvalue c=a'a. Now to find the associated eigenvector. Recall that a(a'v)=cv. Since a'v and c are both scalars, the equation may be rewritten (a'v)a=cv, and a is a multiple of v. Also, replacing v with a gives (a'a)a=(a'a)a, an equality. So a must be the eigenvector.

As for the eigenvectors, corresponding to 0, if a=[a_1 a_2 ... a_n], then the eigenvalues are of the form

[a_2+...+a_n ] [-a_1]
[-a_2 ] [a_1+a_3+...+a_n]
[-a_3] [-a_3]
. .
. and . and so forth.
. .
[-a_n ] [-a_n]

Keep in mind there are n of these.

12. given the matrix A=(5 -3;-3 5), find a matrix M, such that A=M*M. Now find a matrix M such that A=M'*M
M=[ a b ] where a=-3sqrt(2)/2,b=sqrt(1/2) (took long time, though)
[ b a ]

Represent M as [a b] multiply M^2=A out and do algebra. You'll find a=d and c=d. After
[c d]

plugging this back into M^2=A, multiply out again. a^2+b^2=5 and 2ab=-3. Substitute and solve.

For the second part, M is symmetric, so M=M'. Thus, the same M applies. (sad part is it took me almost as much time to figure out 2nd than first.)

13. Suppose x_1, x_2...x_n are IID from [0,1] uniform interval. What is the expected value of the maximum. What is the expected value (max-min).

\[E[max_i {X_i}]= int_0^1 int_0^1 ... \int_0^1 max_i {X_i} dx_1 dx_2 ... dx_n\]

We have to split up the n-dimensional space [0,1]x[0,1]x...x[0,1] into sections. One section will have x_1 be the maximum, another section with x_2 the maximum, and so forth. By symmetry, we can just consider the space where x_1 is the maximum Without loss of generality and multiply by n at the end. So assuming x_1 is the max, we can use the conditional probability

\[E[max_i {X_i}| X_1 is max]= int_0^1 int_0^x_1 ... \int_0^x_1 [x_1] dx_1 dx_2 ... dx_n\]
\(= [int_0^1 ... [x_1] [int_0^x_1 dx_2] ... [\int_0^x_1 dx_n] dx_1]
= [int_0^1 ... [x_1] [x_1] ... [x_1] dx_1]\)
\( = {[1]^(n+1)}/(n+1)\)
\( =1/(n+1)\)

There are n of these, so E[max_i {X_i}]=n/(n+1). Off the bat, you can see that at least for n=1, this formula is true.

As for the max-min, I'm gonna make the assumption that E[max-min]=E[max]-E[min] since the integral can be parsed. Through the same argument as above,

\[E[min_i X_i| X_1 is the min ]= \int_0^1 x_1(1-x_1)^(n-1)dx_1=1/[n(n+1)]. \]Multiplying by n yields

E[min]=1/n+1, which again makes sense at lease for n=1. Thus, E[max-min]=(n-1)/(n+1).


20. Given a fair coin, what is the expected number of trials you need to go to get 2 consecutive heads. 3 consecutive heads. generalize to N.

\[2(1/4)+3(1/8)+4(2/2^4)+5(3/2^5)+6(5/2^6)+7(8/2^7)+8(13/2^8)+9(21/2^8)+…\]

I don't have a closed form, but the formula is \(\sum_{i=1}^{infinity} (i+1)(F_{i-1}/2^{i+1})\), where F_i are the Fibonacci numbers.

Explanation: The first two are easy. There is a ¼ chance of getting two heads on the first two flips. There is a 1/8 chance you will get THH on three rolls. From henceforth, it's just a matter of finding the different ways you can end the sequence in THH, where the previous terms have no HH's. This is where the Fibonacci terms come in to play. I'm too tired to generalize to N (or even 3 for that matter). Variance, forget it.

 

[zonquan]

Interesting question , learn more.

 

[Andy Nguyen]

From GS interview
Suppose the stock S follows a geometric Brownian motion. Assume zero interest rate and dividend. Consider the two options:

Option A: Pays $1 at the end of 2nd year if stock > 100, nothing otherwise
Option B: Pays $1 at any time from now until the end of 2nd year when stock > 100. Once this is paid it terminates.

Assume that the initial stock price is strictly less than 100, what is the no-arbitrage price of option B relative to option A?

 

[Andy Nguyen]

I was asked this questions a while ago and I had no clue then.

Find the next 3 numbers in the sequence 183, 176, 170, 167,...

 

[Erica]

minus 2 sequentially? WRONG! ans pls.

 

[Muting]

From GS interview
Suppose the stock S follows a geometric Brownian motion. Assume zero interest rate and dividend. Consider the two options:

Option A: Pays $1 at the end of 2nd year if stock > 100, nothing otherwise
Option B: Pays $1 at any time from now until the end of 2nd year when stock > 100. Once this is paid it terminates.

Assume that the initial stock price is strictly less than 100, what is the no-arbitrage price of option B relative to option A?

I think the price of B under no-arbitrage argument is a little higher than A. First, B has higher probability finishing in the money(the price path can be above 100 during some period of 2 year and then go below 100 at 2 year end). And the payoff is just 1 dollar when it is in the money and there is no upside benefit. Finally, there is no cost of carry (interest rate and dividend rate are both zero). Hence early getting back the money makes no difference. So the difference is raised by the risk neutral probability of in the money. Andy, do we need to quantify for this problem?

 

[Muting]

To he yan's question:

Following the Bayesian Theorem: P=(1/6*3/4)/(1/6*3/4+5/6*1/4)=3/8

I would agree with nbz's answer.

 

[Muting]

1/2 is correct, and your reasoning sounds pretty good to me. What makes it work is that there are only two ways the outcome can be finally decided: by someone randomly choosing the jerk's seat, or else randomly choosing the last passenger's seat. The likelihood of these two outcomes is the same at every stage of the process; the first leads to the passenger definitely getting his/her own seat, the second leads to the passenger definitely not getting his/her own seat.

My reasoning is slightly different. Consider the last person (but not the 100th person) whose seat is taken by someone before him. Then this person has two choices: One is choose a seat which belongs to someone before him, the other is to choose the 100th person's seat. In this case, the probability is 1/2. The last person can be anyone from 2th to 99th. In all these cases, the probability is 1/2. If only the first person chose the wrong seat, he can only choose 100th person's seat. The probability is still 1/2.

 

[Andy Nguyen]

1. (BOfA, ML) There are a cup of milk and a cup of water. Take one teaspoon of milk,
put into the water cup; mix well. Take one teaspoon of the mixture in the water cup and put into the milk cup then mix well.
Which is higher: the percentage of water in the milk cup or the percentage of milk in the water cup ?

2. (Barclays, ML) \(W_t\) is brownian motion. N is cdf of normal \(N(0,1)\). Calculate \(E(N(W_t))\).

3. (GS) There are 5 thieves numbered 1,..,5 trying to divide 100 gold coins using this algorithm: the number 1 will come up with a way to divide money, if there is more than 50% agreement among them about his method (including the dividing thief) then it's done. If not, then they will kill the first thief and the second thief will divide money coming up with his own method. If you are the first one, what method you will use to divide money ?

4. (SG) There is a cubic cheese 3x3x3. There is a rat eating this cheese in the following manner: it east a corner (1x1x1) of the cubic the first day. The next day, it will eat another 1x1x1 cell which has the same outer face as the one it eats the day before. Find an algorithm so that the rate can eat the center cell the last day.

5. (ML, LB, SG, Bear, DB) The today price of a certain stock is 20$. Here is an option: if the stock reaches 40$ then the payoff is 1$. Price this option.

6. (SG) \(t < T\). W is brownian motion. Calculate \(E(W_T|W_t), E(W_t|W_T), E(W_t| |W_T| )\) (\(W_t\) conditioning to the absolute value of \(W_T\))

7. (JPM) There are parallel lines with distance d lying on the same 2-D plane. There is a line segment with length l>d. Find probability that this line segment not crossing any other lines.

8. (ML) \(T_1 < T_2\). Pricing forward-start option \(E(\frac{S_{T_2}}{S_{T_1}}-K)^{+}\)

 

[ramnik]

I was asked this questions a while ago and I had no clue then.
Find the next 3 numbers in the sequence 183, 176, 170, 167,...

Andy,
Do you know the answer to this? Its been quite a while and I do not think I have been able to make much progress... answer please