## Kalido Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
9
of 9 vote

We can do it with 3 measurements

Let 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.

Comment hidden because of low score. Click to expand.
0

Agreed with the explanation.

Comment hidden because of low score. Click to expand.
0

awesome

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Wrong. It's a weighing pan that has one pan and scale. It doesn't have two pans.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

Whether you will consider the heavier pan or lighter pan in case both pans are unequal ??

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

true...had there been 9 balls and we knew whether the balls where heavier or lighter then we could have done it in 2 steps.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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 .

Comment hidden because of low score. Click to expand.
0

The question says you don't know if the fake ball is heavy or light... so you will need at least one more weighing..

Comment hidden because of low score. Click to expand.
0
of 0 vote

3

Comment hidden because of low score. Click to expand.
0
of 2 vote

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...

Comment hidden because of low score. Click to expand.
0
of 0 vote

3 no more, no less

Comment hidden because of low score. Click to expand.
0
of 0 vote

Zero Measurements. If you have 8 identical balls and 1 is fake, then you do not have 8 identical balls now do you?

Comment hidden because of low score. Click to expand.
0
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

My post should have been a reply to Anonymous below.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

come on guys a weighing pan is NOT a scale. Stop using the scale and compare two bundles of balls

Comment hidden because of low score. Click to expand.
0
of 0 vote

In question,It says weighing pan.Assuming that the weighing machine is used to only weigh the balls and not to compare the weight, then we need to find weight of each ball before we do the above steps. and the fake ball might be lighter or heavier than other balls.

Comment hidden because of low score. Click to expand.
0
of 0 vote

In question,It says weighing pan.Assuming that the weighing machine is used to only weigh the balls and not to compare the weight, then we need to find weight of each ball before we do the above steps. and the fake ball might be lighter or heavier than other balls.

Comment hidden because of low score. Click to expand.
0
of 0 vote

In question,It says weighing pan.Assuming that the weighing machine is used to only weigh the balls and not to compare the weight, then we need to find weight of each ball before we do the above steps. and the fake ball might be lighter or heavier than other balls.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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  if equal to Z than ball 6 is fake otherwise 5.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Brilliant answer here with full detailed description of each possible scenario.. solvekarlo.com/index.php?subj=1&page=14

Comment hidden because of low score. Click to expand.
-1
of 1 vote

2

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Two measurements

Comment hidden because of low score. Click to expand.
0

In question,It says weighing pan.Assuming that the weighing machine is used to only weigh the balls and not to compare the weight, then we need to find weight of each ball before we do the above steps. and the fake ball might be lighter or heavier than other balls.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.