“There is no real difference between work and play – it's all living.”

-Richard Branson

25 Horses Problem

This post was migrated from my old blog and has been slightly modified for improved readability.


Update (March 2012): Terry Ng found an error in my original solution. In the step before the final race, I eliminated all horses with a 3rd place finish from the first 5 races, this included horse W. Instead we should eliminate horse G, as explained in this updated version of the solution.

Earlier this week, a technical sourcer from Palantir contacted me after she noticed my LinkedIn profile. She said it was impressive for someone who’s still in school and she would like to have a brief chat with me regarding career opportunities.

So I started reading about Palantir, including this article which appeared in my Twitter feed. On the 5th page, there’s an example of an interview question that Palantir may ask.

You have 25 horses and can race them in heats of 5.
You know the order the horses finished in, but not their times.
How many heats are necessary to find the fastest?
First and second? First, second, and third?

Cool, I enjoy solving puzzles. I’ll attempt it! And so began this journey…

8 Balls Problem

This question reminded of the 8 balls problem. For those not familiar with it, I made this drawing.[1]

Investigating The 25 Horses Problem

The 25 horses problem is kind of similar:

  • There’s a given amount of items
  • One item stands out from the rest and you have to find out which
  • You can group the items and gain limited information at each step
  • How many steps are necessary to find the correct item?

The key differences are that in one problem (8 balls)

  1. you count the number of steps (weighings - 2 groups at a time)
  2. you choose your group size (both groups must have the same size)

whereas in the other problem (25 horses)

  1. you count the number of groups (races)
  2. your group size is fixed and given

So they’re different optimization problems. The 25 horses problem also goes a few steps further, because not only does it ask for the first item, it also asks for the second and third item.

The posed question is a bit confusing, and having no interviewer to clarify doesn’t help. A horse is not consistently the fastest. A horse that wins one race, may not win its next. In other words, the fastest horse changes every race if measured by order they finish in. If measured by time, the fastest horse does not change (until the fastest record is broken). But since time is out of the question, let’s just ignore time completely.

Attempt

Conclusion

With the (supposedly correct) answer in front of you, the problem seems simple. But admittedly I had a tougher time with this problem than I anticipated. That probably came from initially thinking that it was very similar to the 8 Balls Problem.

If I were asked this during an interview, I’m not sure if I would get it right on the spot. It’s a tricky problem and I’d of course be nervous because of the time constraints and the risk of missing a career opportunity if I screw up. I would definitely be using a whiteboard or a piece of paper as a visual aid, makes tackling such problems a lot easier.

[1] In the actual task, the balls look identical.