Algorithms For Interviews

[adnanaziz]

My co-author, Amit Prakash, and I have very recently completed our book Algorithms For Interviews. (By way of introduction, I'm a professor at UT Austin, and Amit works at Google.)

The book includes 174 solved problems. It targets people interviewing for software jobs, but there's quite a lot of material that may be of interest to quants, e.g., we have chapters on discrete mathematics and probability.

In addition to problems, there's material on problem solving skills and conducting yourself in an interview.

We've put a number of sample pages at the book website, and the Amazon page has a fairly in-depth preview too.

I hope that many of you will find it useful in a job search. Even if you aren't, the problems in the book should be a lot of fun.

Feel free to discuss the problems and their solutions on the board. Here's one to get you started:

"Bob repeatedly rolls an unbiased 6-sided dice. He stops when he has rolled all the six numbers on the dice. How many rolls will it take, on an average, for Bob to see all the six numbers?"
​

Cheers,
Adnan

 

[koupparis]

About 14.7, nice problem.

 

[adnanaziz]

The number of rolls to see all 6 numbers on a die

If you are wondering how koupparis came up with 14.7, here's one approach:

First we prove that if ($\langle X_1, X_2,\ldots \rangle$ ) is a sequence of Bernoulli IID random variables, with ($p(X_i = 1) = p$), then the expected time to see the first ($1$) is ($\frac{1}{p}$).

The reasoning is as follows: define ($F_i$) to be the event that the first ($1$) comes on the ($i$)-th trial. Then ($Pr(F_i) = (1-p)^{i-1} \cdot p$). Hence the expected time is ($S = \sum_{i=1} i \cdot (1-p)^{i-1} \cdot p$). This sum simplifies to ($\frac{1}{p}$) (multiply both sides by p, subtract, and sum the infinite geometric series on the right).

Now, we consider the problem of dice rolls. The key is to determine the expected time to see the k-th new value. Clearly, the expected time to see the first new value is just 1. The time to see the second new value from the first new value is ($\frac{1}{5/6}$) since the probability of seeing a new value, given that one value has already been seen, is ($5/6$). In this way, the time taken to see the third new value, given that two values have already been seen, is ($\frac{1}{4/6}$).

Generalizing this idea, the time taken to see the k-th new value, given that k-1values have already been seen, is ($\frac{1}{(6- (k-1)) /6}$).

Hence the expected time to see the sixth new value is ($\frac{6}{6} + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1} \approx 14.7$).

The approach above illustrate the principle of variation - this is a problem solving technique in which you solve a slightly different problem - how long does it take to see the i-th new element, given that i-1 elements have already been seen.

An alternative approach would be to perform Monte Carlo: simulate a "sufficiently large" number of experiments and compute the average of the number of rolls before all 6 numbers were seen.

If you liked this problem, try the following:

"You have an infinite supply of wooden rulers, each a yard long. Break a ruler at some point chosen uniformly at random, and keep the portion on the left. Repeat with fresh rulers until the sums of the lengths of the pieces you kept exceeds 1.

In expectation, how many rulers will you break in this process?"
​

Cheers,
Adnan
Algorithms for Interviews

 

[DominiConnor]

This might be a very useful book, certainly the more brainteasers you know, the better your job prospects.

If you'd like me to review your book, get in touch via Dominic of PaulDominic.com, and it is of course a brainteaser for you to work out why that might be a good idea

 

[marvinrobot]

number of sticks needed to reach 1

Took me a while to solve this, but I think the answer is e.

Probability that k sticks don't add up to one is 1/factorial(k). If X_k is the indicator variable that first k sticks don't add up to 1 then the total number of sticks needed to add up to 1 is essentially 1 + sum X_i where i goes from 0 to inf. Hence, the expected number is 1 + sum E(X_i) = e.

 

[adnanaziz]

number of sticks to add up to 1 & a problem from the birth of probability

marvinrobot's solution is quite right - the slightly tricky part is showing that the probability that the sum of N uniform [0,1] IID random variables is less than 1 is (1/N!).

This probability is a multiple integral of the form (\int_{X_1=0}^{1} \int_{X_2=0}^{1-X_1} \cdots \int_{X_N=0}^{1-(X_1+X_2+\cdots+X_{N-1})} 1 \, dX_N \cdots dX_2 dX_1) which can inductively be shown to be (1/N!).

Another interesting problem that came to me while flipping through Keith Devlin's excellent book "The Unfinished Game" is the following:

"Suppose Players P and Q are playing a game of table tennis. The first player to win 11 points is the victor. Because of bad weather, the match stops when P is leading, 7 to 5. The prize for winning the game is $1000. Assuming that P and Q are equally likely to win a point, and that the outcomes of separate points is independent, how should the prize be split between P and Q? Repeat the calculation assuming the probability of P winning a point is 7/12.

Now suppose the requirement is that a player must have won at least 11 points, and lead by two points. How would you split the prize?"
​

This problem was discussed by Pasal and Fermat, in a correspondence that has been credited with leading to modern probability theory; in particular the concept of expectation. Given the nature of the problem, I expect it should be interesting to financial engineers.

Have fun,
Adnan
algorithmsforinterviews.com

 

[marvinrobot]

prob of win for the other player =
1/64 + (6 choose 1)/128 + (7 choose 2) /256 + (8 choose 3)/512
1/64 + 6/128 + 21/256 + 56/512
= 130/512


Hence the prob of win for the leading player = 382/512
Hence the prize should be split 382:130

 

[adnanaziz]

The problem of points & one on option pricing

marvinrobot is right again, check out the Wikipedia article, Problem of points - Wikipedia, the free encyclopedia, or Devlin's book "The Problem of Points" for more history/details.

Here's a problem in our book that's right out of computational finance:

A call option gives the owner the right to buy something at a predetermined price at a predetermined time in the future.

If the option is not priced fairly, an arbitrageur can either buy or sell the option in conjunction with other transactions and come up with a scheme of making money in a guaranteed fashion. A fair price for an option would be a price such that no arbitrage scheme can be designed around it.

Consider an option to buy a stock S that currently trades at $100. The option is to buy the stock at $100 in 100 days.

Suppose we know there are only two possible outcomes - S will go to $120 or to $70.

An arbitrage is a situation where you can start with a portfolio (x_s shares and x_o options) which has negative value (since you are allowed to short shares and sell options, both x_s and x_o may be negative) and regardless of the movement in the share price, the portfolio has positive value.

For example, if the option is priced at $26, we can make money by buying one share for $100 and selling four options - the initial outlay on the portfolio is $100 - 4 X 26 = -$4. If the stock goes up, our portfolio is worth $120 + 20 X -4 = $80. If the stock goes down, the portfolio is worth $70. In either case, we make money with no initial investment, i.e., the option price allows for an arbitrage.

For what option price(s), are there no opportunities for arbitrage? (Assume that risk-free interest rates are 0.)
​

 

[Ilya W]

regarding first problem

I solved this problem using MC simulations. Probably a little more applied approach but works good For 10,000 times I generated the sample until all 6 numbers were hit. Then using
Sum of these sample's sizes devided by number of sims we come to average equal to 14.6914...

 

[pratikpoddar]

"Suppose Players P and Q are playing a game of table tennis. The first player to win 11 points is the victor. Because of bad weather, the match stops when P is leading, 7 to 5. The prize for winning the game is $1000. Assuming that P and Q are equally likely to win a point, and that the outcomes of separate points is independent, how should the prize be split between P and Q? Repeat the calculation assuming the probability of P winning a point is 7/12.

Now suppose the requirement is that a player must have won at least 11 points, and lead by two points. How would you split the prize?"
​

This problem was discussed by Pasal and Fermat, in a correspondence that has been credited with leading to modern probability theory; in particular the concept of expectation. Given the nature of the problem, I expect it should be interesting to financial engineers.

Equal Probability of P and Q

P(Q winning) = 1/64 + (6 choose 1)*1/128 + (7 choose 2)*1/256 + (8 choose 3)*1/512
= 1/64 + 6/128 + 21/256 + 56/512 = 130/512 = 0.253

Probability of P=7/12

P(Q winning) = (5/12)^6 + (6 choose 1)*(5/12)^6*(7/12)^1 + (7 choose 2)*(5/12)^6*(7/12)^2 + (8 choose 3)*(5/12)^6*(7/12)^3
= (5^6)*(1/12)^9 [(12*12*12 + 6*7*12*12 + 21*49*12 + 56*7*7*7)]
=614562500/5159780352 = 0.119

 

[quantyst]

Nice problem. I'd like to generalize it as follows:

Let X(1), X(2), ... be independent and identically distributed uniform random variables over [0,1]. Let y be any real number. Set N(y)=min{n: X(1)+X(2)+...+X(n)>y}. Find expected value E[N(y)]. As has been shown, E[N(1)]=e.

If we let f(y)= E[N(y)], then it can be shown that f(y)= 1 + INTEGRAL{f(u) [where u runs from max(0,y-1) to y]}.

The challenge now is to solve this integral equation. Any takers?

If you are wondering how koupparis came up with 14.7, here's one approach:

First we prove that if ($\langle X_1, X_2,\ldots \rangle$ ) is a sequence of Bernoulli IID random variables, with ($p(X_i = 1) = p$), then the expected time to see the first ($1$) is ($\frac{1}{p}$).

The reasoning is as follows: define ($F_i$) to be the event that the first ($1$) comes on the ($i$)-th trial. Then ($Pr(F_i) = (1-p)^{i-1} \cdot p$). Hence the expected time is ($S = \sum_{i=1} i \cdot (1-p)^{i-1} \cdot p$). This sum simplifies to ($\frac{1}{p}$) (multiply both sides by p, subtract, and sum the infinite geometric series on the right).

Now, we consider the problem of dice rolls. The key is to determine the expected time to see the k-th new value. Clearly, the expected time to see the first new value is just 1. The time to see the second new value from the first new value is ($\frac{1}{5/6}$) since the probability of seeing a new value, given that one value has already been seen, is ($5/6$). In this way, the time taken to see the third new value, given that two values have already been seen, is ($\frac{1}{4/6}$).

Generalizing this idea, the time taken to see the k-th new value, given that k-1values have already been seen, is ($\frac{1}{(6- (k-1)) /6}$).

Hence the expected time to see the sixth new value is ($\frac{6}{6} + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1} \approx 14.7$).

The approach above illustrate the principle of variation - this is a problem solving technique in which you solve a slightly different problem - how long does it take to see the i-th new element, given that i-1 elements have already been seen.

An alternative approach would be to perform Monte Carlo: simulate a "sufficiently large" number of experiments and compute the average of the number of rolls before all 6 numbers were seen.

If you liked this problem, try the following:

"You have an infinite supply of wooden rulers, each a yard long. Break a ruler at some point chosen uniformly at random, and keep the portion on the left. Repeat with fresh rulers until the sums of the lengths of the pieces you kept exceeds 1.

In expectation, how many rulers will you break in this process?"
​

Cheers,
Adnan
Algorithms for Interviews

 

[Daniel Duffy]

Here is another one:What is the probabillity that the quadratic equation

a.x^2 + b.x + c = 0

where a, b and c are N(0,1)

has 2 REAL roots?

 

[pruse]

Here is another one:What is the probabillity that the quadratic equation

a.x^2 + b.x + c = 0

where a, b and c are N(0,1)

has 2 REAL roots?

Are they i.i.d. (\mathcal{N}(0,1))?

 

[Daniel Duffy]

Are they i.i.d. (\mathcal{N}(0,1))?

Yes. The problem has deep roots.

I solved it as a test of some random number generators and using formulae for roots.

 

[quantyst]

Here's a solution:

Obviously for y<0: f(y)=0.

For 0<=y<=1: f(y)=exp(y)=e^y.

For 1<y: f(y)= 1 + INTEGRAL{f(u) [where u runs from (y-1) to y]}, which upon differentiation, gives f'(y)=f(y)-f(y-1). Now we can partition the interval [1,infinity) as [1,2)U[2,3)U[3,4)U...U[n,n+1)U.... so that for each n, if g(n,y) is a solution to the differential equation on the interval [n,n+1), then we can solve the differential equation f'(y)=f(y)-g(n,y-1) for the interval [n+1,n+2). The details are not difficult to produce.

Nice problem. I'd like to generalize it as follows:

Let X(1), X(2), ... be independent and identically distributed uniform random variables over [0,1]. Let y be any real number. Set N(y)=min{n: X(1)+X(2)+...+X(n)>y}. Find expected value E[N(y)]. As has been shown, E[N(1)]=e.

If we let f(y)= E[N(y)], then it can be shown that f(y)= 1 + INTEGRAL{f(u) [where u runs from max(0,y-1) to y]}.

The challenge now is to solve this integral equation. Any takers?