Tech Interview

100 fogcreek programmers are lined up in a row by an assassin. the assassin puts red and blue hats on them. they can’t see their own hats, but they can see the hats of the people in front of them. the assassin starts in the back and says “what color is your hat?” the fogcreek programmer can only answer “red” or “blue.” the programmer is killed if he gives the wrong answer; then the assassin moves on to the next programmer. the programmers in front get to hear the answers of the programmers behind them, but not whether they live or die. they can consult and agree on a strategy before being lined up, but after being lined up and having the hats put on, they can’t communicate in any way other than those already specified. what strategy should they choose to maximize the number of programmers who are guaranteed to be saved?

Solution

this is a very difficult problem to solve during an interview (especially if you’ve already taxed the candidate’s brain). look for obvious solutions first, and the reasoning behind them and then try to lead them to the ultimate solution.

a logical answer could be all the programmers would just say “red” and that way about half of them would survive on average, assuming the hats were distributed randomly.

this is a good start and should naturally lead to having every other programmer say the color of the hat in front of them. the first programmer would say the color of the hat in front of him, then the next programmer would just say that color that was just said. so we can guarantee that half survive – the even numbered programmers (since the person behind them told them the answer). and potentially if the hats were distributed randomly some of the programmers would get lucky and the hat in front of them would be the same color as their own. so this strategy should save more than half, and on average 75% of them would live.

at this point, if the solution is not clear, the candidate may give answers like, “they could agree that if they said their hat color in a soft voice, it means the hat in front of them is the same color, and if they say it in a loud voice, it means the hat in front is a different color”. this is definitely good and on the correct track. another option is they could say “reeeeeeeeeeed” for x number of seconds, where x represented the distribution of hats where a hat was a bit in a binary number, (red = 1, blue = 0). another interesting answer. there are many others like these that “bend” the rules and come to a solution.

but the real solution acknowledges that the programmers can only say “red” or “blue” and cannot alter their voice in such a convincing way as to signal any information other than the word they said. a good way to get this point across, is simply to change the problem slightly by saying “the assassin gets to hear their plan before she puts the hats on, and so will try to thwart the plan however she can.”

so if they decide to all say “red”, she’ll put blue hats on all of them. if they decide to all say the color of the hat in front of them, she’ll alternate the hats on every head, guaranteeing half will die. even with the assassin hearing their plan, there is still a way to save almost everyone.

we know that the first person is never going to have any information about the color of their hat, so they cannot be guaranteed to survive. but, i’ll give you a hint to the solution: i can save every other person for sure.

solution: they agree that if the number of red hats that the back person can see is even, that programmer will say “red”. if they add up to an odd number, they will say “blue”. this way number 99 can look ahead and count the red hats. if they add up to an even number and number 100 said “red”, then 99 must be wearing a blue hat. if they add up to an even number and number 100 said “blue”, signalling an odd number of red hats, number 99 must also be wearing a red hat. number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in front to figure out what color hat is on 98’s head.

sample:

100  99  98  97  96  95  94 ... facing ->
 R    B   B   R   B   R   B ... -> 45 R and 48 B

this shows #100 wearing a red hat, 99 a blue, 98 a blue, 97 a red, 96 a blue, 95 a red, 94 a blue and 45 red hats – 48 blue hats on the people in front of them.

100 counts up the red hats: 47 total. so 100 says “blue”. the assassin kills 100. 99 counts up the red hats in front: 47. 100 said blue, so 100 saw an odd number. 99 sees an odd number, so 99 says “blue” and lives. 98 had counted 47 red hats, and 99 didn’t say “red” so thats still the total. 98 says “blue”. 97 counts up and finds 46 red hats. 99 and 98 didn’t say “red”, so his count is missing a red hat (its on his head, he realizes). he says “red”. 96 heard the “red” and now knows that there are an even number of “red” hats in front of 95. 96 sees 46, so he knows he has a “blue” hat. etc…

even if the assassin knows the plan, she can’t thwart it. she hears the plan, but she still has to put the hats on their heads. the plan doesn’t rely on any ordering of the hats, so the worst the assassin can do is to make sure #100 gets killed and thats the worst damage she can do.