Kalido Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
there IS a case that you can finish in 2 steps.
1. weigh 12 & 34
a) if even, faulty ball is in 5678
b) if not, faulty ball is in 1234
2. weigh 123 & 567 (suppose case "a")
if even, faulty ball is 8 ==> DONE in 2 steps.
if not, faulty ball is in 567, AND you will know if faulty is lighter or heavier
3. weigh 5 & 6
if even, faulty ball is 7
if not, faulty ball is the lighter one if you find out lighter being faulty or the other way
Assuming the weighing pan is a physical balance and the problem is to identify the fake ball (funnily enough the question doesn't say anything :(), it can be done in 3 measurements using the divide and conquer philosophy :P. Divide the balls into four groups of two balls each say A, B, C, D. Take group A and B and place them on the two sides of the scale. If they are equal in mass then the fake ball is in C or D else it is in A or B. Say they are equal. Now take group C on one side and A (or B) on the other side. If they are again equal then the fake ball is in D otherwise in C. Now take one of the ball from the fake ball group and have it measured with one of the balls from non fake groups. if they are again equal then the other ball is fake otherwise this one.
Whether you will consider the heavier pan or lighter pan in case both pans are unequal ??
doesn't matter as you know that the other parts are equal and you will be comparing one of the unequal group with them to just eliminate one more group in the second step
The interesting part is that knowing if the fake ball is heavier (or not) is helping a lot: you can do it using 2 measurements (3 vs 3 and then another one)
We can do it with 2 mesurment...
case 1: comapre 1,2,3 with 4,5,6
if both are identical then definaticaly fake ball is in 7,8 and you can easily identify the fake from 7 ,8 in next mesurment.
case 2: if 1,2,3 and 4,5,6 are not identical
then you can choose heavier from the and its confirm that the fake ball in that.Now in next mesurment choose two from three if they are identical the third one is the fake ball .
You can do it in 3 measurements (since we don't know if it is heavy or light, else it can be done in 2 measurements):
If we know that the fake ball is heavy or light:
first keep any 2 balls aside, and weigh the other 6 balls by placing 3 on each pan...
Case 1: if these balls weight equal (the scale is balanced), you know all 6 of these balls are identical and none is fake. If so, weigh the other 2 balls and find out whichever one is fake (using the knowledge of heavy/light).
Case 2: if the pans don't balance, you know one set of 3 balls being weighed currently contains the fake ball. Again, using the knowledge of heavy/light, weigh any 2 out of the 3 balls which are not weighing properly and you know your answer.
So that's 2 measurements.
If we DON'T know heavy or light, after weighing the 6 balls,
Case 1: if Case 1 above holds, use any one of those 6 balls (since they are all identical) and use it to weight against any one of the remaining 2 balls. If it weighs equal, the remaining ball (so this is still 2 weighings)
Case 2: NOW we need to know if it is heavier or lighter to proceed IMO... OR... again weigh like in Case 2 above... but just to make sure if the fake one is lighter or heavier, weigh of these balls with the remaining 3rd ball you will know...
let me know if this makes sense or I can give examples with numbered balls or so...
You can do it in 2 measurements. Put 3 balls each on either side of the weighing pan, if the weights are equal then the fake ball is between the 7th & 8th one, and in case the weighing pan tilts on any side then the fake ball is on the lighter side amongst the 3 balls. Use the weighing pan once again for the 2 balls out of the lighter 3, if the weights are equal the fake ball is the one which is not on the pan and if the weighing pan tilts the fake one is on the lighter side.
well 3 is correct:
1. chek 1,2,3,4 and 5,6,7,8, the group which is lighter, is the one with fake ball
2. suppose 1234 group is lighter, now chek 12 and 34, in this too, the ligher will contain fake
3. now we have pair, and it will take one operation
You don't know if the "fake" ball is heavier or lighter so using two groups won't get you anywhere. It would only tell you that yes indeed the balls are not all of uniform weight. But, you are right, weighing pan doesn't make much sense- it really should be a balance or a balance. Many scales have only one tray and measure weight based on gravity (like spring scales or electronic scales) a balance compares relative weight between two objects which you can use as a scale if you know the actual weight of one of the objects- if you don't you can only determine if the weights are equivalent or not.
The only concern is that we have a weighing pan. So we are not allowed to compare two different pair of balls at single time.
Divide and Conquer will be the approach but surely minimum try gonna be more as we don't know the fake ball is heavier or lighter.
Assuming the worst case scenario.
Step I: Weighing [1,2] and getting weight X
Step II: Weighing [3,4] and getting weight Y
as the scenario is assumed to be worst case, both are same. That means we have all good ball in [1,2,3,4] and fake ball is in [5,6,7,8]. Plus we know the weight of single good ball, let it is (Z) = X/2 or Y/2.
Step III: Weighing [5,6,7] if it is equal to (3Z) than ball number 8 is fake.
But in the worst case scenario fake ball is in [5,6,7]
Step IV: Weighing [5,6], if it is equal to (2Z) than ball 7 is fake. Otherwise one among 5 and 6.
Step V: Weighing [5] if equal to Z than ball 6 is fake otherwise 5.
We can do it with 3 measurements
- Selmeczy, Péter October 23, 2012Let the balls be numbered with 1, 2, ..., 8
Compare 1&2 with 3&4
If they are equal then the fake one is in [5..8] and all in [1..4] are good ones.
If they are not equal then all in [5..8] are good ones and the fake one is in [1..4]
So with one measurement we surely have 4 good balls and a set of 4 that contains 3 good and the fake.
Compare two of the "wrong" set with two good ones (from the other set)
If they are equal - you have a set of two that contains the wrong one.
If they are not - same thing.
So for the 3rd measurements you have a set of two that contains the wrong one and 6 that are surely good.
Compare one out of the wrong set with a good one.
If they are equal - the remaining from the wrong set is the fake.
If they are not - well, you know which one is the good one, the other is the fake.
It is left to the reader to prove that it cannot be done with 2 measurements.