On Tue, Sep 8, 2009 at 9:52 AM, Kiran K Karthikeyan <
[email protected]> wrote:
> I do a lot of interviews, both for Product Managers and for Tech profiles.
> I've had two questions which I've continuously asked, but need to change.
> I've enjoyed the responses of various candidates for these questions for
> almost 3 years now and it has been very interesting to see how different
> people think through them.
>
> Question 1:
>
> There are 12 steel (or any other material, the material is immaterial :) )
> balls (yes, I make it cubes when interviewing women) which were
> manufactured
> to be identical in every way and hence indistinguishable. However, one of
> them has a manufacturing defect and has either less or more weight that the
> other 11. Given a weighing scale (with no standard weights), you have to
> find out which of the balls is defective as well as whether it weighs
> lesser
> or more than the others.
>
> Obviously, there is no solution in 3 weighings
Hope you did not reject candidates for saying this is possible in 3
weighings. Haven't verified this completely -- it is possible I missed
something. The approach should be obvious, though. (As Thats mentioned,
this is something I first encountered and solved in school.)
(Sorry about the rich text mail. It is an attempt to keep the formatting
for the ASCII art below to keep from getting messed up.)
Divide the balls into 3 groups of 4 each -- a1-a4, b1-b4, c1-c4. Keep aX
balls on the left pan, bX balls on the right and cX ones outside.
a1 a2 a3 a4 b1 b2 b3 b4
____________ W1 ____________
------------------------
/\ c1 c2 c3 c4
Possibilities:
- Pans balance
Implies: One of the cX balls is defective
c1 c2 c3 X
___________ W2 ___________
------------------------
/\ c4
(X is one of the other balls we know is not defective.)
Possibilities:
- Pans balance
Implies: c4 is the defective ball
A weighing against any other will tell you
if it is lighter or heavier
- Left pan is heavier
Implies one of c1, c2 is heavier or c3 is lighter
c1 c2
___________ W3 ___________
------------------------
/\ c3
If the balance now shifts to the other pan, c2 is the
defective ball and it is heavier. If the left pan
continues to be heavier, c1 is the defective ball and
is heavier. If the pans balance, c3 is the lighter
ball.
Getting back to the other possibilities for the first
weighing:
Possibility:
- Left pan is heavier (Same analysis applies if the left
is lighter.)
Implies: Either one of the aX balls is
heavier or one of the bX balls is lighter.
a1 a2 b1 a3 b2 X
___________ W2 ___________
------------------------
/\ a4 b3 b4
Possibilities:
- Left pan stays heavier:
Implies: a1 or a2 is heavier or b2 is lighter.
(Those are the only balls that did not switch
sides.) Weigh a1 against a2. If they are equal, b2
is lighter. Or else, the heavier ball is defective.
- Right pan is now heavier
Implies: One of the balls that switched sides is
defective, i.e., b1 or a3. Put them on the same pan
and weigh them against two of the other
non-defective balls. If the pan with a3 and b1 is
heavier, a3 is the defective and heavier ball.
Otherwise, b1 is the defective and lighter ball.
- Pans balance:
Implies: a4 is heavier or one of b3 or b4 is
lighter. Weigh b3 against b4. If the pans balance,
a4 is defective. Otherwise, the lighter one of b3
and b4 is defective.
--
One hundred thousand lemmings can't be wrong.
