|
You are given 80 balls and out of which only 1 has more weight than other 79
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
You are given 80 balls and out of which only 1 has more weight than other 79
Question:
you are given 80 balls and out of which only 1 has more weight than other 79. also, you are given weighing machine which can weigh any number of balls of 2 sets( 40 40 or 25 25 etc) at one time.
find the minimum number of steps required to find the ball of more weight than others. (i tried it came out to be 5 steps atleast, but he wanted more efficient solution )
maybe an answer:
Assume the ball we need to find is X. Divide into 3 groups, A (27 balls), B (27 balls), C (26 balls)
Step 1: Weight A vs B, whichever is heavier has X. If equal, then C has X. If C has X, choose a random ball in A and put into C so that C has 27 balls.
Step 2: After step 1, we determine which group has X, and the group size is 27. Divide into 3 smaller groups, each of size 9, and repeat the same procedure.
In short, we have, 80 -> 27 -> 9 -> 3 -> 1, 4 steps in total to find X.
(Continued on next question...)
Other Interview Questions
| 