Blog‎ > ‎

### 25 Horses Problem

posted 27 Nov 2011, 13:00 by Dennis Ideler   [ updated 10 Mar 2012, 05:43 ]
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. Coincidentally, a person I follow on twitter tweeted this article regarding Palantir. To my surprise, he now works for Palantir - he didn't when I started following him.

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! So I tried not to look at the answer and began.

#### 8 Balls Problem

This question reminded of the 8 balls problem. For those not familiar with it, I made this drawing (in the actual task the ball colours and their dimensions look identical):

#### Investigating The 25 Horses Problem

The 25 horses problem is similar in the sense that

• There's a given amount of items.
• One item stands out from the rest (though not visually) and you have to find out which.
• Each step you can group the items and gain limited information.
• How many steps are necessary to gain enough information to guarantee you found 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.

I admit that the question is 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 his 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.

#### 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.