:: Context (Would I move Mt. Fuji?) ::
I couldn’t help wondering if I ever was in Gene McKenna’s shoes for this interview with Microsoft…
The Interview Scene (excerpt from the book):
Suppose you had eight billiard balls, the recruiter began. One of them is slightly heavier, but the only way to tell is by putting it on a scale against the others. What’s the fewest number of times you’d have to use the scale to find the heavier ball?
I shouldn’t deny the fact here that I am not facing this kind of question for the first time . I first heard a similar kind from one of my close friend who was proudly eliciting his success on an interview with Infosys. Well! now you see the line of corporations who has joined this “recruitment-methodology” band-wagon. So, I was kind of ready for this one. I have this habit (good as well as bad) of manipulating similar problems, imparting to it the “larger than life” image that I like to confront, just for the sake of personal joy and satisfaction. And I ended up wondering thus:
Suppose if it wasn’t known if the odd ball in the set was either heavier or lighter, what’s the fewest number of times one would have to use the scale to find the odd one?
Please give it a try if you haven’t, before you read my take on both. To start with, i have highlighted (bold and italicised) the key words that matter.
:: My Take On It ::
:: Take 1::
There are different solutions to this problem. “Divide and Conquer” is the key solution to this problem. But, how would you divide to make the conquest complete in the shortest possible moves?
Sets of 3 or its multiples are ideal in terms of elimination, in this case, as the last set would be reduced to just 3 and with just one weighing we can isolate the heavier/lighter ball. Let me explain it further. If the heavier/lighter ball is one among the 2 that is weighed, the heavier/lighter
scale indicates the heavier/lighter ball whereas if they weigh the same, then the third ball that is not weighed is the heavier/lighter one. On this account, let us try to divide these 8 balls into sets of 3 which leaves us with three sets namely A, B & C with 3, 3 & 2 balls respectively. The heavier ball in our case should lie in any of these 3 (A, B & C) sets.
Step 1 would be to determine this set. The easiest way is to weigh sets A & B of three balls each.
- If A weighs more, the heavier ball is in set A
- If B weighs more, the heavier ball is in set B
- And if A & B weighs equal, the heavier ball is in set C
Step 2 would be to determine the heavier ball as we have reached the final set by now. And as explained earlier, we know how to determine the heavier ball from a set of 3 (A or B) with just one weighing. And of course, to the get the heavier ball from set C is just direct weighing.
:: So in just 2 weighing (cumulative weighing from step 1 through 2), we can determine the heavier/lighter ball ::
:: Take 2 ::
Now consider the case when we don’t know if the odd ball is heavier or lighter than the rest. Divide and Conquer principle applies here as well.
Figure 1 below shows the division of balls into various sets (A through H) for determining the odd ball in the most optimal number of weighings. The dotted lines indicate how sets G & H are derived (the details are available in Figure2):
Figure 2 below depicts the complete flow chart for determining the odd ball in the most optimal number of weighings:
:: So in just 3 weighing, we can determine the heavier/lighter ball ::