A tough interview question
Yesterday I stumbled across an interesting post on Reddit about a really tough interview question. It’s not that uncommon to be asked to solve a puzzle during software interviews, but it’s also not exactly clear what information can be deduced from the candidate’s ability to answer them.
The puzzle is as follows:
You have 12 identical balls. One of them is slightly different in weight than the rest. You have three weighs of a balance scale to determine which ball is different and whether it is heavier or lighter.
An easier version
I have heard of a similar (yet much easier) puzzle before, which goes as follows:
You are given 8 identical looking balls. One of them is heavier than the rest of the 7 (all the others weigh exactly the same). You are provided with a simple mechanical balance and you are restricted to only 2 uses. Find the heavier ball.
Let’s try and solve the easier version first and then switch our attention to the more difficult one.
So we have 8 identical balls, let’s name them: 1,2,3,4,5,6,7 and 8.
We start off by weighing {1,2,3} against {4,5,6}. There are 3 scenarios which can arise from this.
If {1,2,3} against {4,5,6} are equal, then we know either 7 or 8 is the heavy ball. We simply weigh {7} against {8} to get the result.
If {1,2,3} is heavier, we weigh {1} against {2} – either we will find the heavier ball or they will be equal in which case we know 3 is the heavier ball.
If {4,5,6} is heavier we follow the same pattern (as with {1,2,3}) to find the heavier ball.
The difficult version
Ok, let’s try and solve the original problem with 12 balls. Once again, let’s name them: 1,2,3,4,5,6,7,8,9,10,11 and 12.
I first tried a similar approach as with the easy version and started off by weighing {1,2,3,4,5,6} against {7,8,9,10,11,12}. I quickly abandoned that route since it’s easy to tell that you can’t find the odd ball within the next 2 weighings. Remember that we need to find the odd ball and say whether it is heavier or lighter.
We start off by weighing {1,2,3,4} against {5,6,7,8}. As before, we have 3 scenarios which can arise from this, the last 2 having an identical solution.
If {1,2,3,4} against {5,6,7,8} are equal, then we know one of {9,10,11,12} is the odd ball. The key here is to realize that 1 through 8 are now normal balls and use that information. So let’s weigh {9,10,11} against 3 of the normal balls – {1,2,3}. Now we have 3 scenarios to deal with – either {9,10,11} are heavier or lighter than the 3 normals, or they are equal which makes them normal themselves. This last case is the easiest to solve – if {9,10,11} are normal we know 12 is the odd ball and we use our last weighing to find out whether it’s heavier or lighter. (We simply put {12} against a normal ball.) Now let’s look at the other 2 scenarios (which are very similar). If {9,10,11} are lighter than the 3 normal balls we weigh 9 against 10. Either we will find the lighter one through the weighing or they will be equal in which case 11 is the lighter one. That takes care of the scenario where {9,10,11} are lighter than 3 normal balls and we use the same logic when {9,10,11} are heavier than 3 normal balls.
Great, that takes care of the scenario where {1,2,3,4} against {5,6,7,8} are equal. But what if they are not? Either {1,2,3,4} will be lighter than {5,6,7,8} or it will be heavier. Again, these 2 scenarios are actually the same (only our abitrary numbering is different) so if we solve one of these scenarios we have solved the puzzle. Nearly there!
For simplicity sake, let’s say {1,2,3,4} is lighter than {5,6,7,8}. We now have 2 weighings to find the odd ball and we also know we have 4 normal balls – {9,10,11,12}. We also know that we have 4 possibly lighter balls – {1,2,3,4} and 4 possibly heavier balls – {5,6,7,8}. (This is the trickiest part of the puzzle) We now weigh {1,2,5} and {3,6,normal} where normal can be any of the balls already identified as normal – {9,10,11,12}. We now have 3 different scenarios.
If {1,2,5} is heavier than {3,6,normal} we know that either 5 is heavier than normal or 3 is lighter than normal. (We knew that 1 and 2 were either normal or lighter, they can’t be heavier.) We now weigh {5} against a normal ball. The weighing will either tell us that 5 is heavier or it will tell us that 5 is normal in which case 3 is lighter.
If {1,2,5} is lighter than {3,6,normal} we know that either 1 or 2 is lighter than normal or 6 is heavier than normal. We now weight {1} and {2}. Either the scale will be equal which means 6 is heavier than normal or the weighing will tell us which of 1 or 2 is the lighter ball.
If {1,2,5} is equal to {3,6,normal} we know that either 4 is lighter than normal or either 7 or 8 is heavier than normal. We now weigh {7} and {8}. Either the scale will be equal which means 4 is lighter than normal or the weighing will tell us which of 7 or 8 is heavier.
That covers all the scenarios!
Puzzles as interview questions
I could probably write a whole article about the value of using puzzles as software interview questions. There might be some value added in certain scenarios, but in this case I would think that the question is exceptionally difficult and would probably just confuse a potential candidate.
Instead of asking a developer to solve brain teasers, rather get them to write code. Pairing and coding questions are much better indicators of someone’s ability to write code.
You wouldn’t employ a potential chef without asking him to cook something, would you? Happy coding.