## Goldman Sachs Interview Question for Software Engineers

Team: Strats
Country: India

Comment hidden because of low score. Click to expand.
2
of 2 vote

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:

``````public int flipCoins(int k, int n) {
int final Ntrials = 100000;
int cnt;
for (int j=0; j<Ntrials; j++)
if (isSuccess(k, n)) 		cnt++;

return (int) Math.round(cnt*100.0/Ntrials);
}

private boolean isSuccess(int k, int n) {
int cnt = 0;
for (int j=0; j<n; j++)
if (Math.random()>0.5) 		cnt++;
return cnt == k;
}``````

This code gives the probability p_220/400 ~= 0.53%

Comment hidden because of low score. Click to expand.
4

at least 220 heads, not exactly 220 heads

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 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);
}``````

Comment hidden because of low score. Click to expand.
0

mistake:

``````else if (n == 1)
{
return BigDecimal.ONE;
}``````

should be:

``````else if (n == k)
{
return BigDecimal.ONE;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

400c220*[(1/2)^220]

Comment hidden because of low score. Click to expand.
0
of 0 vote

sw

Comment hidden because of low score. Click to expand.
0

correction in above explaination:

Total combination for getting head 220 times in 400 times coin toss --> 400C220
Total combination for getting head 221 times in 400 times coin toss --> 400C221
...
Total combination for getting head all 400 times in 400 times coin toss --> 400C400

Comment hidden because of low score. Click to expand.
0
of 0 vote

<=> 11 out of 20 , 50% - (1 out of 20)

Comment hidden because of low score. Click to expand.
0
of 0 vote

<=> 11 out of 20 = 50% - (1 out of 20)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

(1/2)^20

Comment hidden because of low score. Click to expand.
0

not correct

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.