Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Stop posting questions from the web. Microsoft stopped asking these a long time ago. Get with the program.
Create three groups of 3 balls each.
Compare two of these groups (1st comparison)
If equal
Compare the two balls in second group (2nd comparison)
If equal
Return the uncompared ball
Else
Return the ball that is heavier
Else
Compare the balls in the group which came heavy in first comparison (2nd comparison)
If equal
Return the uncompared ball
Else
Return the ball that is heavier
In fact the above algorithm works in every case where the number of balls is 3^n for n>1 with one additional comparison.
e.g.
For 27 balls this can be done in 3 steps.
For 81 balls this can be done in 4 steps.
Just group the balls in 3 groups. i.e. 27/3 which reduced it to the original problem.
three and three first.Then if one side is heavier, take that side and put 1 ball on each. If one side is heavier, then that is the ball. If the two sides are equal, then the leftover ball is heavy.
If on the 3-3 balance, the two sides are equal, then take the leftover side and do the 1-1 shown
above.
1) take 4 balls on each side. Measure. If they are equal, the 9th ball you left out is the heavy one.
2) Otherwise split the heavy 4 group into two groups of two balls each and measure again.
3) Now drop the two balls from the heavy two group, the heavy one will land on the ground first.
LOL
take 4 balls on one side of measurement and another 4 balls on another side , then if equal means the 9 th one is heavy ...if the measurement is unequal.take the heaviest side and split into two and find which is heavy..
this is super easy. split the ball into three groups with 3 balls each. pick two groups out to measure if they are equal weight. this way, you could find out which group contains the heavy ball. Then from this particular group, you could pick two to do one more measurement, this way, you find out the heavy ball
- June October 27, 2013