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/