Here is Google’s famous interview question:
Let’s say that you have 25 horses, and you want to pick the fastest 3 horses out of those 25. In each race, only 5 horses can run at the same time because there are only 5 tracks. What is the minimum number of races required to find the 3 fastest horses without using a stopwatch?
The official answer is seven. Unfortunately, the official answer is incorrect. The minimum number is actually six. The algorithm, which does not always work, works sometimes. This establishes the true minimum: the least number of guess that are possible (but not guaranteed) to get an answer. The link above shows a “proof of minimality” which is no proof at all.
Here is the algorithm:
Race #1 through #5. Horse #5 wins that race.
Race #5 through #9. Horse #9 wins and #5 gets 4th or 5th.
Race #9 through #13. Horse #13 wins and #9 gets 4th or 5th.
Race #13 through #17. Horse #17 wins and #13 gets 4th or 5th.
Race #17 through #21. Horse #21 wins and #17 gets 4th or 5th.
Race #21 through #25. Horse #21 gets no better than 3rd place.
Because horse #21 is faster than horses #1 through #20 AND horse #21 got no better than 3rd place, none of horses #1 through #20 could have placed in the top 3. That leaves the three fastest horses among #21 through #25. Since you know the result of the final race, congratulations you now know the three fastest horses in only six guesses.
Now, if this algorithm hits an exception (winner of previous race gets 1st, 2nd, or 3rd), then the number of required races to determine the 3 fastest horses goes up, but this does not change the minimum, only the average.
This is an important point in computer science. Some algorithms (like the purported correct answer) do really well on the average case. My algorithm has the best best-case time, but it has a worse average- and worst-case performance. As in sorting algorithms, which algorithm you choose depends on your requirements.
For example, my algorithm would be the best choice if you knew what the gambling odds were on the horses prior to racing them. You’d rank the horses by the worst-to-best odds and have a very good chance of getting the correct answer in only 6 guesses. If the horses were selected randomly, the standard algorithm would be superior: most of the time.
So, the next time you see this interview question, calmly explain why “6” is the correct answer. When you fail to get the job—which is highly likely because interviewers don’t like to be told they are wrong—you didn’t want to work there anyway.
Interesting observation. Your analysis represents a unique scenario in which the winning horse from a previous race places last or second last in a successive race, thereby eliminating all the horses from the previous race from placing second or third of all horses. And this unique scenario is repeated four times, which is very unique. What is the probability of this happening?
The probability is very small. I’m not sure how small, considering there are “25!” possible combinations of horses and most of them don’t yield a good result. I tried to do a quick probability calculation, but realized that it wasn’t trivial to calculate, so I didn’t bother.
Regardless, the solution is not even close to unique. There are a lot of don’t care conditions where the positions of the horses can be mixed without altering the outcome.
UPDATE: The chance of the two fastest horses being in the last group (slots 22 through 25) is 1%. The third fastest must be in slot 18 or greater, reducing the total probability to 0.25%. This is the upper bound (best case). Now, if the four fastest horses happen to be in the last group, then the order of the first five sets of horses doesn’t even matter: just race the winner of the previous race in the next group to get the 5th fastest horse after 5 rounds. The probability of this happening is 0.008%, which forms the lower bound (worst case). Thus, the true probability of solving the problem in six guesses is somewhere between 0.008% and 0.25%, or at least once in every 12,650 attempts.