Google Interview Question
Software Engineer / DevelopersFirst of all, it says random direction and not necessarily along the edges only. Now we have two cases at hand:
Case-1: We don't know the speed of the ants.
Answer: We can not determine the probability in any way.
Case-2: Assuming constant and equal speeds.
Answer: The ants will meet only when they travel "equal" distance. This essentially means - they will meet only at the centroid of this equilateral triangle! This is the basic logic behind it. I don't know how to show this in terms of probability. But I will try to present a solution - Assuming that each ant can move in 360 directions (based on 360 degrees of a circle), only ONE direction leads to the centroid of the equilateral triangle. This is true for all the three ants. So, it might be said that the probability of their meeting (assuming 360 directions for each ant), is 1/360 * 1/360 * 1/360.
And, it nowhere says that meeting of only 2 ants is sufficient. We just want to know when ALL THREE will meet. I strongly feel that Case-2 is the solution they were looking for.
they have to walk around the triangle in the same direction, so as to not collide
so 1/8 , 1/2 * 1/2 * 1/2
There are 8 possibilities:
L L L
L L R
L R L
L R R
R L L
R L R
R R L
R R R
Because at least 2 ants have the same direction, all 3 will never meet.
1. Any random direction means they don't have to stay on the edges.
2. Even if 1 is not true, it would depend on their speed.
3. If an interviewer cannot frame a question right, they should go fuck themselves.
Ignore ants behavior, we are not concerned about area of triangle nor how ants will travel nor where or how fast they will travel. All we want to know is the probability of (consider all) ants meeting.
Assuming ant1 meeting ant2 is same as ant2 meeting ant1.
P(All ants will meet) = (number of ways all ants can meet) / (total number of possible events)
Given three ants a1,a2,a3;
The following events are possible
a. None will meet is = organizing each separately = {a1},{a2},{a3} = 1
b. Two will meet = organizing two elements together = {a1,a2},{a2,a3},{a3,a1} = 3
c. Three will meet = organizing all together = {a1,a2,a3] = 1
Probability = 1/5 = .2
Maybe I can convince the interviewer with this solution. The interviewer looks at how you are approaching rather than if you got the solution or not, thats what I believe.
- What is the probability of meeting the dinosaur at the center of the city?
- 1/2!
- WHY??
- Either I meet it or not.
I think meeting a dinosaur is more like a zero because we can use Bayesian theorem and given that dinosaurs are extinct. The probability is zero. Thanks
it is 3/4.
Proba that they meet is 1-porbability that they don't meet.
lets calculate the proba that they don't meet :
each can move in 2 directions, which are totally independent so you can multiply...
they are 3, they can move each in two direction :
1/2*1/2*1/2 but this can be in either form left to right or right to Left, so multiply this proba by 2 wich is 1/2*1/2*1/2 *2 = 1/4
remember it is the probability that they don't meet so :
1-1/4 = 3/4
Why assume that the triangle has only sides and not a planar area, where ants can move ? Why not consider that the triangle's complement is also a planar area where ants can move, the question never said ants move along the sides of the triangle ?
Why assume ants have equal speed, and not consider variable speeds ?
The question is bogus... and I do not want to spend time on all assumed versions of it...
Total no. of ways they can move = 2*2*2 = 8
- Hari Prasad Perabattula September 26, 2010Only 2 ways (clockwise n anticlockwise) not to collide.
Probability for not to collide = 2/8 = 1/4.
To collide = 1-(1/4) = 3/4 = 0.75
:-)