Goldman Sachs Interview Question
Software EngineersTeam: Strats
Country: India
The binomial distribution gets close to the normal distribution as n gets larger. N(np, np(1-p)) is the approximation, and here we have n=400 and p=0.5, thus have N(200,100).
220 is 2 standard deviation away from 200, the mean, in this case. Thus, the answer would be about (1-P(N(0,1)<=2)) = 0.05
Of course, I'm not sure if this is what interview wanted.
This is a nice solution if you are required to give a quick answer to the question. The binomial distribution may be well approximated by Normal is n is fairly large (~100), which would be N(np, sqrt(npq)) = N(200, 10) here. The Z score of 220 is (220 - 200) / 10 = 2. According to Normal distribution, P(|X| < 2) = 0.95, thus the probability of X > 200 would be P(X > 200) = (1 - 95%) / 2 = 2.5%, which is indeed a good approximation.
I believe total probability should be
[400C220 + 400C221 + 400C222 + ..... + 400C400] / (2 ^ 400)
400C220 --> Getting exactly one heading 220 times
400C221 --> Getting exactly one heading 221 times
...
400C400 --> Getting exactly one heading 400 times
2 ^ 400 --> Total possibility
Approximate percentage value= [180* (400C220) * 100]/ (2^400)
correction in above explanation
Total combination possible in getting exactly 220 head out of 400 coin toss --> 400C220
Total combination possible in getting exactly 221 head out of 400 coin toss --> 400C221
Total combination possible in getting exactly 222 head out of 400 coin toss --> 400C222
...
...
..
Total combination possible in getting all 400 head out of 400 coin toss --> 400C400
correction in above explanation
Total combination possible in getting exactly 220 head out of 400 coin toss --> 400C220
Total combination possible in getting exactly 221 head out of 400 coin toss --> 400C221
Total combination possible in getting exactly 222 head out of 400 coin toss --> 400C222
...
...
..
Total combination possible in getting all 400 head out of 400 coin toss --> 400C400
correction in above explanation
Total combination possible in getting exactly 220 head out of 400 coin toss --> 400C220
Total combination possible in getting exactly 221 head out of 400 coin toss --> 400C221
Total combination possible in getting exactly 222 head out of 400 coin toss --> 400C222
...
...
..
Total combination possible in getting all 400 head out of 400 coin toss --> 400C400
correction in above explanation
Total combination possible in getting exactly 220 head out of 400 coin toss --> 400C220
Total combination possible in getting exactly 221 head out of 400 coin toss --> 400C221
Total combination possible in getting exactly 222 head out of 400 coin toss --> 400C222
...
...
..
Total combination possible in getting all 400 head out of 400 coin toss --> 400C400
correction in above explanation
Total combination possible in getting exactly 220 head out of 400 coin toss --> 400C220
Total combination possible in getting exactly 221 head out of 400 coin toss --> 400C221
Total combination possible in getting exactly 222 head out of 400 coin toss --> 400C222
...
...
..
Total combination possible in getting all 400 head out of 400 coin toss --> 400C400
n choose k for 220 (k) heads out of 400 (n) coin tosses gives the number of possible outcomes where you get exactly 220 heads. This would be:
outcomes = factorial(400) / (factorial(220) * factorial(400 - 220))
The probability of this happening would be outcomes divided by the total number of possible states flipping a coin 400 times could result in:
outcomes / 2 ^ 400
Since the questions says "at least 220 heads," you need to add the probabilities of getting 220, 221, 222, ..., 400 heads together.
The nHeadsOrMore function below does this by using Java's arbitrary precision class, BigDecimal.
I get ~2.55%
BigDecimal factorial(int n)
{
if (n == 0 || n == 1)
{
return BigDecimal.ONE;
}
BigDecimal rv = BigDecimal.ONE;
for (int i = 2; i <= n; ++i)
{
rv = rv.multiply(new BigDecimal(i));
}
return rv;
}
BigDecimal nChooseK(int n, int k)
{
if (n < k)
{
return BigDecimal.ZERO;
}
else if (n == 1)
{
return BigDecimal.ONE;
}
return factorial(n).divide(factorial(k).multiply(factorial(n - k)));
}
BigDecimal nHeadsOrMore(int numHeads, int numTosses)
{
BigDecimal result = BigDecimal.ZERO;
BigDecimal numPossibleOutcomes = (new BigDecimal(2)).pow(numTosses);
for (int i = numHeads; i <= numTosses; ++i)
{
result = result.add(nChooseK(numTosses, i));
}
return result.divide(numPossibleOutcomes);
}
Probability of getting 'k' successes of probability 'p' within 'n' events is given by binomial distribution:
(n choose k) p^k(1-p)^(n-k)
In other words, I want to observe 'k' successes and '(n-k)' not successes and I do not care about permutation in which the events come (n choose k). Now lets substitute real numbers into the formula and we get:
p_220 = 400!/(220!*180!) 0.5^220*0.5^180
Notice that there is one significant problem which is factorial. Typically everything that is bigger than 69! is overflow even for long, here we have 400!, hence unfeasible to compute unless we implement the method that does string multiplication.
What the interviewer wanted us to do? I guess the goal was to identify this problem and propose empirical approach, hence, repeat experiment many times and estimate the probability.
A sample code is shown below:
This code gives the probability p_220/400 ~= 0.53%
- autoboli February 01, 2015