Scott Logic Interview Question: If you had 8 balls and 7 ball... | Glassdoor.co.uk

Interview Question

Graduate Software Engineer Interview Edinburgh, Scotland

If you had 8 balls and 7 balls weighed the same but 1 was

heavier, what is the minimum amount of times you would need to place the balls on the scales to figure out which ball is heaviest.

0

Certainly it depends on the type of the scales.

A) If it is a balance scale, then 2 measurements are necessary and sufficient.

First measurement: Place 3-3 balls on both pans of the scales.

Case 1: If one pan is heavier, then the odd ball is the group of 3 balls in that pan.
In this case, second measurement: place 1-1 ball out of this group into each pan. If one is heavier, then that is the odd ball; if their weight is equal, then the 3rd is the odd ball.

Case 2: If these 3-3 balls have equal weights, then the odd ball is among the remaining 2 balls.
In this case, second measurement: place 1-1 ball of the remaining pair in each pan of the scales. The heavier is the odd ball.

Note that 2 measurements would be enough for 9 balls as well.

Caveat: It is necessary to decide whether the scales are in balance or not - with no information on the weight difference between the light and the heavy ball, and also no info on the sensitivity of the scales.
In other words: how can we decide if a slight imbalance is a consequence of a weight difference, or is it due to a measurement error that should be tolerated?

B) If it is a digital or spring scale (or something similar, where you measure a single load and it displays the weight), then 4 measurements are always sufficient, and fewer is not always enough.

There are many possible strategies, which fall basically into 2 different types:
1) Methods dependent on being able to compare the measured weight with a computed weight (a multiple or a fraction of a previous measurement result). In these cases it is enough to decide which weight is more, and there is no need to assess equality.
2) Methods where computation is not necessary (so the absolute weight is not needed, just to compare to other measured weights), but it is necessary to decide if two measured values are equal or not - and there is no information on the weight difference between the light and the heavy ball, and also no info on the error limits of the scales.

One example for type 1:
#1: Measure all 8 balls
#2: Measure a group of 4 balls. If their weight is more than the half of the weight taken in the previous step, then this group contains the heavier ball, otherwise the other group does. Select the heavier group.
#3: Repeat step #2 with 2 balls from the heavier group, and select the heavier pair in the same way.
#4: Repeat again with 1 ball from the heavier pair, and select the heavier ball.

An example for type 2 (similar to the method employed with the balance scale)
#1: Select 3 balls and weigh them.
#2: Select 3 different balls and weigh these as well.
Case 1: If one measured weight is heavier, then the odd ball is in that group. #3 and #4: weigh 1-1 ball out of this group. If one is heavier, then that one is the odd ball; if their weight is equal, then the 3rd is the odd ball.

Case 2: If these 3-3 balls have equal weights, then the odd ball is among the remaining 2 balls. #3 and #4: weigh each of these 2 balls. The heavier one is the odd ball.

Tamas Perger on 14 Jun 2017