Google’s 25 Horses Problem

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.

Leave a Reply

Your email address will not be published. Required fields are marked *