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.
Cool, I enjoy solving puzzles. I'll attempt it! So I tried not to look at the answer and began.
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):
The key differences are that in one problem (8 balls)
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.
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 lot easier.