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%

- autoboli February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 4 votes

at least 220 heads, not exactly 220 heads

- Anonymous June 14, 2015 | Flag
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.

- owen February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- xlzhang.iop March 27, 2015 | Flag
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)

- raja roy June 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- raja roy June 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Raja Roy June 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Raja Roy June 28, 2015 | Flag
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 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);
	}

- dexhop February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

mistake:

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

should be:

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

- dexhop February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous June 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sw

- Anonymous June 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- raja roy June 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous January 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- contributor January 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

(1/2)^20

- BinaryGeek February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not correct

- Anonymous June 22, 2015 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More