Interview practice: Racing horses

This one is a puzzle question. I’m personally not the biggest fan of these types of problems and would never ask something like this in an interview. That being said, they are kind of fun, and the following problem is no exception. Its an entertaining logic question that can give insight into a candidate’s thought process and how they approach an optimization problem.

There are 25 race horses and you want to find the fastest one. You can only race 5 horses at a time, and you can’t write down their times. How many races does it take to find the fastest three horses?

Here’s how I approached it. The first thing to do is figure out all the assumptions inherent in any puzzle question. The first and most crucial assumption is that the finish times for each horse remains the same across races. Without this assumption, the task is impossible, as the fastest horse could change between races: horse #1 could beat horse #2 in the first race, but lose to it in the second race. The second assumption is that there are no ties. There is a clear ranking in finish times for the horses.

Now with those out of the way, we can approach the problem. The most obvious thing to do first is to divide the 25 horses into five groups, and then race each group. This will identify the fastest horse in each heat. Now we just race the five fastest horses from each group. The winner will be the fastest out of all 25 horses, and we will have identified the fastest horse in just six races. Let’s call this winner horse #1, and assume he came from group #1. That’s the easy part. Now the question remains, how many races do we now need to find the second fastest horse? Should we just pick the second fastest horse from race #6? Should we race all the second place finishers from the five groups as well?

At this point it would be helpful to do some whiteboarding. Let’s write down some concrete race times.

Race #1:
Horse #1 1 minute
Horse #2 2 minute
Horse #3 3 minute
Horse #4 4 minute
Horse #5 5 minute

Race #2:
Horse #6 1.6 minutes
Horse #7 1.7 minutes
Horse #8 1.8 minutes
Horse #9 1.9 minutes
Horse #10 1.95 minutes

By writing out the first two races and assigning some times we can see that it is entirely possible that all the horses in the second heat are actually faster than all of the other horses in the first heat save for horse #1. Let’s write down some more race times for the other heats.

Race #3:
Horse #11 1.1 minutes
Horse #12 1.2 minutes
Horse #13 1.3 minutes
Horse #14 1.4 minutes
Horse #15 1.5 minutes

Again, we see that for the third heat, it is entirely possible that all the horses are faster than all of the other horses in the first heat save for horse #2. At this point it may seem that it is necessary to race all the second place finishers in each heat, before racing the winner of the seventh race against the second place finisher of the sixth race. But that’s not quite true.

Race #4:
Horse #16 1.01 minutes
Horse #17 1.02 minutes
Horse #18 1.03 minutes
Horse #19 1.04 minutes
Horse #20 1.05 minutes

Race #5:
Horse #21 1.001 minutes
Horse #22 1.002 minutes
Horse #23 1.003 minutes
Horse #24 1.004 minutes
Horse #25 1.005 minutes

Race #6:
Horse #1 comes in first place at 1 minute
Horse #21 comes in second at 1.001 minutes
Horse #16 comes in third at 1.01 minutes
Horse #11 comes in fourth at 1.1 minutes
Horse #6 comes in fifth at 1.6 minutes

From this we can quickly see that the second place finisher of race #6 (horse #21 from heat 5 from our whiteboard example) is faster than the first place finishers of heats 2,3, and 4. This means that he is also going to be faster than all the horses in heats 2,3, and 4. We can quickly eliminate all those horses as being the second fastest. Thus the only horses to consider for being second fastest are either the second place finisher in heat 6, or the second fastest horse from the winning heat the fastest horse was from (horse #2 from heat 1 in this case). So we race them. So far, we’ve had to do seven races.

So what about identifying the third fastest horse? Based on the same logic as above, we know that the third place finisher of race #6 (horse #16 from heat 4 from our whiteboard example) is faster than all the horses in heats 2 and 3. We do not know if this third place finisher is faster than the second or third place finisher from the winning heat (Horse #2 and #3 from heat 1), or the second place finisher from the heat that the second fastest horse came from (horse #22 from heat 5 in this case). Note for the latter case, we don’t need to consider the third place finisher from this heat, because at best it could only be the fourth fastest horse overall (we know by its placement that it must be slower than the first and second place finishers in its heat and slower than the fastest horse overall). Since we don’t care about the fourth fastest horse, we can eliminate it from consideration. So, there are only four horses to consider for third fastest, and we will need to have them compete in an eighth race to find the third fastest horse overall.

Or do we? In race #7, we raced horse #2 from heat 1 against horse #21 from heat 5. In race #8, we raced horse #2 from heat 1 again. There are only five horses we need to consider for second and third fastest, so we can combine races #7 and #8 into one. The second and third place finishers of the seventh race are the second and third fastest horses, respectively. In total, we just need seven races.

The general algorithm is:
Divide the 25 horses into groups of five.
Race each group.
Select the winner from each group and race them.
The winner from this race is the fastest horse. Let heat A denote the winning heat this horse is from, heat B denote the heat that the second place winner is from, and heat C denote the heat that the third place winner is from.
Now race horse #2 and #3 from heat A, horse #1 and #2 from heat B, and horse #1 from heat C (where #1, #2, and #3 denotes what place the horse finished for that given heat) in a final seventh race.
The first and second place winners of this race are the second and third fastest horses.

Dwarves, demons and puzzle questions

Here’s an interesting puzzle question that I was asked once at an interview:

Ten dwarves are being held captive by a powerful demon. One day, the demon offers all ten dwarves freedom on the condition that they play a game of his (Rumor has it the demon is a big fan of the Saw movies). The diabolical setup is as follows. The dwarves will all line up in a single file. The demon will then magically implant a gem into the back of each dwarf’s head. The gem is either red or green; the color is chosen at random. Starting from the back of the line, the demon will then ask each dwarf what color gem they have. Each dwarf may only respond with “red” or “green”. Any other response will result in insta-death for all ten dwarves. The important thing to keep in mind here is that each dwarf can only see the color of the gems in front of him. He must remain physically still during the duration of this game. This means he may not turn around, move out of line, hold up any mirrors, use sign language, or employ any other such physical methods of determining or communicating gem colors. Doing so will also result in insta-death for everybody. The game is tomorrow night. What strategy can the dwarves employ to save the maximum number of dwarves?

If the dwarves just guess, then each has a 50% chance of survival. This is the bare minimum baseline that we want to beat. But how? Each dwarf can see all the colors of the gems in front of him, so any solution will require at least one dwarf to convey that information to others. Obviously this means there will have to be at least one “sacrificial” dwarf. The demon starts with the dwarf at the back of the line, so let’s start there. I’ll refer to this guy as Dwarf #10. He can see all the gems in front of him. How can he pass on this information? The situation seems grim. There are nine dwarves in front, so this means there are 2^9 possible permutations of gem lineups. How can he possibly represent 512 total possible permutations when he is only limited to two responses?

One possible strategy would be to increase the total number of possible responses through subtle variations in each answer. For example, dwarf #10 could vary the pitch of his response. Each pitch would correspond to a different gem permutation. Essentially, this would be a lookup table with 512 entries containing key value pairs of frequency and gem permutation. The word “red” sung at a frequency of 440 Hz might mean that he sees five red gems in front of him, followed by a green gem, followed by three more red gems. A response of “green” sung at a frequency of 196 Hz would mean four red, two green, followed by three reds. We can quickly see that this is not a very practical solution. Assuming they have a trained singer who has perfect pitch, and assuming the dwarves can distinguish between them, they’d still need to commit this table to memory in a day. Answers to puzzle questions aren’t typically complicated, so a different approach is needed.

Perhaps we can simplify things. We don’t actually need to represent all 512 permutations. The key thing to remember here is that each dwarf can see all the gems in front of him. Let’s say Dwarf #9 in the line sees five green gems and three red gems in front of him. Let’s also say that Dwarf #10 somehow managed to tell him that he sees four red gems total. Well in that case, Dwarf #9 can correctly determine that his own gem is red. We are close to arriving at a working solution here. Dwarf #10 just needs to let everyone else know the total number of red gems. However, we are again faced with the problem of having just two possible responses available to us, while nine possible values exist for the number of red gems. Well, it turns out we can simplify things even further. The dwarves don’t need to know the exact number of red gems, they just need to know if the total number of red gems is odd or even.

To see why this works, consider the following example. The dwarves meet up and decide that a response of “red” will mean that there are an even number of red gems and that a response of “green” means there is an odd number of red gems. Dwarf #10 sees five red gems and four green gems in front of him, and responds with “green”. Dwarf #9 now counts four reds and four greens in front of him. Because he sees an even number of red gems, and because he knows that the total number of red gems is odd, he can quickly arrive at the conclusion that his own gem must be red. He answers correctly and goes free. Dwarf #8 now knows that there is only an even number of red gems left. He counts four red gems and three green gems in front of him. Seeing that there is already an even number of red gems in front of him, he correctly ascertains that his own color is green. Each dwarf down the line will be able to figure out their own color in a similar fashion. Dwarves #9 through #1 are guaranteed freedom, while dwarf #10 will still have a 50% chance of making it out alive.

These types of questions can definitely be tricky and nerve wracking. The trick to approaching them in an interview is to think out loud and ask questions that clarify the problem and the underlying assumptions. Even if you don’t get the answer correct, you can still demonstrate to the interviewer your problem solving thought process, and more importantly, your ability to articulate that thought process.

I like this particular question because it is a good example of being able to solve a seemingly complex problem with a limited of resources (in this case, one boolean variable) through a process of simplification. This is invaluable in the field of software engineering. Puzzle questions like this test your ability of abstraction. Can you break a problem down into its bare essentials and arrive at a logical solution? I’m still quite ambivalent toward the use of such questions in interviews though. Sure, a well designed brain teaser does test a candidate’s problem solving ability. But it does not test their programming ability at all. Why not simply ask a programming question instead, which lets you assess both at the same time?

Microsoft pioneered the use of these types of questions back in the day. Their history and usage in the tech world is described further in the delightful book, How would you move Mt Fuji, which also contains a challenging collection of these brain teasers. Microsoft’s reasoning behind the use of such questions was that it was more important to hire people who were smart, and not necessarily people who could write code. If candidates were intelligent enough to solve these riddles, they’d be smart enough to become programmers too. This reminds me of a funny joke I once heard from a guy I knew at Amazon:

Yeah sure, Microsoft used to hire people based on their ability to solve puzzle questions. These were the same people that ended up writing Internet Explorer 6*. Their usage has fallen out of favor ever since.

So, while I do think that these puzzles are a great way to pass time, sharpen your brain, and have fun, I do not believe that they’re the best use of time at an interview. You can only ask so many questions in your allotted time slot, so simply asking a tough programming question instead makes far more sense to me.

FOOTNOTES
*IE6, the browser that’s so bad that even Microsoft is begging their users to abandon it: http://www.ie6countdown.com/