Microsoft Interview Question
Country: United States
seperate 9 balls to 3 groupe, each groupe contains 3 balls -> compare two groupe-> the heavier groupe contains the heaviest ball; if same weigh, third groupe contains this ball -> take two balls from the heaviest group found above, compare weigh-> same weigh than third one is the heaviest one, if not, the heavier one is the heaviest ball. VoilĂ xD
It is clear that we can find the heavier ball amongst 3 balls with only one operation(comparison).
Here is my solution:
START:Divide 9 balls to three groups of 3 randomly.
weigh two randomly selected groups against each other:
IF they are equal, THEN weigh two members of third group against each other to find the heavier one.
ELSE IF they are not equal, THEN select the heavier group and run the comparison test on it.
So the total comparison of TWO is enough.
That can't be a MS interview Question!
1. Weight 3 balls against 3 balls: either one of these groups weight more or the heavy ball is in the 3rd group.
2. Out of the heavier ball group, Weight 1 ball against another: other one of them is heavier or the heavy ball is the one you didn't touch
with 3 operations it is simple
compare first 4 balls, next 4 balls, if weight is equal, then 9th ball is having more weight.
else , take the set of 4 balls with max weight and divide into set of 2 and compare again, take set with maximum weight, compare those 2 balls in that set, take the ball with the highest weight and return.
It is clear that we can find the heavier ball amongst 3 balls with only one operation(comparison).
Here is my solution:
START:Divide 9 balls to three groups of 3 randomly.
weigh two randomly selected groups against each other:
IF they are equal, THEN weigh two members of third group against each other to find the heavier one.
ELSE IF they are not equal, THEN select the heavier group and run the comparison test on it.
So the total comparison of TWO is enough.
I will weigh 3 balls with other 3 balls & keep the rest 3 aside. If those 3 balls are equal to the other 3 balls then the heavier ball is among the rest of 3. Then I will take 2 balls from the rest of 3 and weigh them. If these 2 are equal then the remaining one is heavier or any one of them are heavier found in balancing.
It is right just like 3 bolls for first consideration.
Suppose we have 3 bolls in bag and we pick 2 boll from bag and compare their weight scale.
If weight scale is same means boll inside the bag is more weighted than other two.
3--->1--->operation
9--->3----->3---->3
3 will take rest into bag and pair 3 bolls will be outside for compare.
Therefore 2--->max operation.
Suppose we have only 3 balls, 1 of them is heavier. This is 3-ball problem.
- ninhnnsoc February 26, 2015Then, we take 2 balls, leave 1 ball alone. Weight 2 chosen balls by a balance scale. We can easily identify which ball is heavier: one of the two chosen balls (if the scale is not balanced) or the one that left alone (if the scale is balanced).
So for 3 balls we can solve using 1 operation.
Now instead one ball, we put 3 balls into a bag. Thus, we have 3 bags, one of them is heavier. It becomes 3-bag problem. Using 1 operation we can identify which bag is heavier.
Then it reduces problem to the 3-ball problem above.
Totally, 2 operations are enough to find the heavier ball.