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 5 You have 25 horses and can race them in heats of 5. Cool, I enjoy solving puzzles. I'll attempt it! So I tried not to look at the answer and began. ## 8 Balls ProblemThis question reminded of the8 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 - 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) - you count the number of steps (weighings - 2 groups at a time)
- you choose your group size (both groups must have the same size)
- you count the number of groups (races)
- your group size is fixed and given
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. ## 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
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 |

Blog >