Goldman Sachs Interview Question
AnalystsThe 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.
This solution makes sense. I also did a little monte-carlo simulation to double check, and it comes up with 10 as well.
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).
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
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...
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
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.
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.
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.
Found solution on some website
- A February 25, 2010Let 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.