Goldman Sachs Interview Question for Analysts






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

Found solution on some website

Let x represent the expected number of moves it takes to reach the ant when the spider is one move away (i.e., at any one of the three vertices of the cube adjacent to the ant). Let y represent the expected number of moves it takes to reach the ant when the spider is two moves away, and let z represent the expected number of moves it takes to reach the ant when the spider is three moves away (at the opposite vertex on the cube).

Then z = 1 + y, since after the first move, the spider will be one move away. From this point, there is a (2/3) chance that the spider will move to a vertex adjacent to the ant and there is a (1/3) chance he will move back to his starting position, 3 moves from the ant. Thus,
y = 1 + (2/3)x + (1/3)z.

Similarly, x = (1/3)(1) + (2/3)(y + 1). This system of 3 equations with 3 unknowns has solution z=10, y=9, and x=7. So, it will take 10 steps to reach the ant, on average, from the spider's initial position.

- A February 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

very nice, thanks!

- ttgg February 26, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is smart solution instead of using random walk to solve the problem.

- Anonymous February 26, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution is not right, first we need to know what 1/3 means and what x means , and if you use 1/3 to multiply x , what does the result mean, according to this , other conclusion are wrong.

- cubeguy March 08, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

cubeguy you are stupid

- Anonymous March 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution makes sense. I also did a little monte-carlo simulation to double check, and it comes up with 10 as well.

- Isaac May 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

perfect

- Anonymous August 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

kdelmfl

- Anonymous August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

awesome!

- Anonymous October 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Let x=number of turns to reach ant from starting point.
Let y=number of turns to reach ant from diagonal corner on same face as ant.
Let z=number of turns to reach ant from an adjacent corner to ant.

After one turn the spider will be on a diagonal corner of a common face as the ant. So the mean number of turns from the x position is one more than the mean number from the y position:

E(x)=1+E(y).

Once at a y position there is a 2/3 chance it will then move to a z position, and a 1/3 chance back to an x position:

E(y)=(2/3)*(1+E(z))+(1/3)*(1+E(x)).

If the spider arrives at a z position there is a 1/3 chance it will move to the ant, and a 2/3 chance it will move back to a y position:

E(z)=(1/3)*1+(2/3)*(1+E(y)).

With these three equations and three unknowns it is not difficult to solve for E(x), E(y), and E(z).

- sakshi August 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can the spider move back along an edge?
If yes, there are potentially infinite number of ways to reach the ant.
If no, the number of ways = 3! = 6 xyz,xzy,yxz,yzx,zxy,zyx

- sdm February 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, the spider can move any direction (even back and forth). we want to find the expected average number of steps to reach to the ant. It is like a random walk problem, but I do not know how to do it...

- tsg2002cn February 25, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes it can take infinite steps, but the probability of that would be infinitly small, hence the expected number would be some reasonable number...

- Anonymous July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

does it say that average number of steps obtained after probability analysis should be a correct answer?Coz a closer look at the problem shows that spider can reach ant in only odd number of steps

- Anonymous April 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

u r an idiot

- Anonymous July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@A

it should be x=1*(1/3) + 2/3*(y)

not x=1*(1/3) + 2/3*(y+1)

- spandan July 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain why..?

- san July 24, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@A great :)

- S&S July 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

shouldn't y be;

y= 1/3(z) + 2/3(x);
rather than
y= 1+ 1/3(z) + 2/3(x);

- Anonymous August 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the solution should be:
x=1*(1/3)+y*(2/3)
y=x*(2/3)+z*(1/3)
z=y+1
so
x=2, y=2.5 and z=3.5

- waterfall August 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Formulated problem as a 4-state Markov Chain and used expected time to absorption properties. The solution is indeed 10.

- truth September 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there is a problem in the phrasing. It should have asked for the average number of steps instead of the expected number of steps. The _average_ number of steps might be 10, but the _expected_ number of steps cannot be 10, since the solution cannot occur in 10 steps.

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

whats the expected value of a throw of a dice?

- tom August 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution absolutely is correct! It's logic and I found the same result via monte-carlo!

- Anonymous August 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for the last equation I would write x = 1 + (1/3)*0 + (2/3)*y, seems clearer to me.
In words: If the spyder (which is one step away from the ant) does ONE step, than with a probability of 1/3 it will need to do 0 further steps and with a probability of 2/3 it will have to do (in average) y further steps.

- Anonymous August 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem has a much simpler solution.
Let the spider do 1 move. It will be in any of the 3 vertices adjacent to its initial position.
From there on, consider pairs of moves. After 2 moves, spider can either end up at the ant, or stay within those 3 vertices.
The chance of getting to the ant is 2/3 * 1/3 = 2/9 (2/3 because spider needs to move to any 2 vertices next to the ant on the first move, and 1/3 because from there it needs to move to the ant on the second move).
So the expected number of move pairs to reach the and is Epairs = 1/p = 1 / (2/9) = 9/2, and the expected number of moves is Emoves = Epairs * 2 = 9/2 * 2 = 9.
Add to this the initial move, and you have E = 1 + Emoves = 1 + 9 = 10.

- AG October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

x*2.23607

guys use PGT

- Govind March 10, 2016 | Flag Reply


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