Blue Jeans Interview Question
Software Engineer in TestsTeam: NA
Country: India
Interview Type: In-Person
This can be done in maximum 3 iterations:
Divide balls in groups of 3 (say A,B,C)and a extra ball x.
Iteration 1: Measure group A against B.
Iteration 2. Measure group B against C.
Now with above two Iterations you could get:
if A=B=C,implies X is faulty
If A!=B && B!=C,implies faulty ball belongs to group B
Therefore,with two iterations,we can get the group with faulty ball.Further we can deduce the faulty ball is heavier or lighter based upon if the faulty group is heavier/lighter compared to other groups.
Lets say group with faulty ball is A.
Now Iteration 3: measure two balls from A against each other
If two balls weigh same,the third ball in the group is faulty
If the ball do not weigh same,the one which is heavier(if A was heavier than other groups) is faulty and vise versa.
Weigh 5 balls at a time. Select the faulty batch. Divide the 5 balls from the faulty batch into 2 group of two balls each. If none of them is faulty, the left out ball is faulty else, if one of the batches of 2 is faulty, compare the two balls again to find the faulty one!
So, its 3 comparisons at the most.
Usually The Ball with our air, weighs more
Divide the Ball into 3 groups: 4(A) 4(B) 2(C)
->First weigh A and B.
-> If both equal, then c is faulty.
-> divide C(2) balls and igh them separately, which gives faulty ball.
-> So totally 2 steps.
----------------------------------------------------------------------------
-> First weigh A and B.
-> If A > B, then C is fine.
-> Divide A into 2 batches and weigh them separately.
-> Take the faulty batch, and try weighing again.
-> Totally 3 steps
Weigh the ten balls in batches of 5. Select the 5 that are the wrong weight. Then weigh four of the remaining 5 in batches of two. If both batches have the correct weight, then the fifth ball is the bad ball. Else, select the two balls which have the wrong weight and weigh one, if it's got the right weight then the other ball is bad, else it's the bad one.
A total of 3 weightings maximum.
A B C D
3 3 3 1
weigh A and B: same ->1 weigh over
weigh B and C: same ->1 weigh over
D is probelmatic
maximum weighing 2.
Worst case:
weigh A and B: same ->1 weigh over
weigh B and C: not same ->1 weigh over
C is problematic so divide C as 1, 1 and 1.
Weigh 1 and 1 : same so third 1 is probelmatic : 3 weigh over
maximum weighing 3.
@aka Can you plz explain in detail that how can u make this approach work with 10 balls in maximum weighing 3??
Suppose you don't know if the faulty ball is lighter or heavier.
First measure A=3 and B=3
CASE 1:
If equal you get the weight of unfaulty ball.
Measure C=2 D=2 It must be unbalanced, take any of the them (say C=2) and weigh with 2 of previous 6 balls.
If they weigh same, you have faulty in other 2 (D=2 here).
If they weigh different, you have faulty in that 2 balls (C=2).
If weigh lighter, faulty is lighter, if weigh heavier faulty is heavier.
CASE 1A: (C=2 weigh different than previous unfaulty balls)
Weigh these balls against eachother and you'll get the faulty ball.
CASE 1B: (C=2 weigh same as previous unfaulty balls)
Weigh D=2 against eachother and you'll get the faulty ball.
CASE 2:
If not equal, faulty ball is in either A=3 or B=3. (Note which one is heavier/lighter)
Weigh A=3 against C=3 (Remaining 4 balls must be unfaulty)
CASE 2A:
If they weigh same Faulty ball is in B=3.
We already know that the faulty ball is heavier/lighter. Compare any 2 balls, if they weigh same, 3rd ball is faulty. If they don't heavier/lighter ball is faulty depending on the previous condition.
CASE 2B:
If they don't weigh same faulty ball is in A=3. (Note which one is heavier/lighter)
Follow the same steps as in 2A.
Let say there are 8 balls below, all are of same weight except one ( let say number 1 is heavier )
1 2 3 4 5 6 7 8
Now we need to figure out "1" is heavier.
Step1 : --> Let say remove two balls from the list ( 7 and 8)
---> Weigh 6 balls
----> If Weight of (1+ 2+3) = (5+6+7) then either 7 or 8 is heavier else
---->If Weight of (1+ 2+3) > (5+6+7) then ignore (5+6+7)
-----> Now focus on (1,2,3) and weigh again
-----> If weight of (2) > (3) then ignore (1) and "3" is the answer else
------> If weight of (2) = (3) then "1" is the heaviest ball
Suppose the tem balls are ABCDEFGHIJ.
Weigh ABC vs. DEF.
Case 1: Equal weight, meaning one of GHIJ is defective.
Weigh G vs. H.
Case 1a: Equal weight, meaning one of I or J is defective. Weigh I vs. one healthy ball (say A). If weigh equals, J is defective. If weigh differs, I is defective.
Case 1b: Weigh G and H are different, meaning one is defective. Weigh G vs. one healthy ball (say A). If weigh equals, H is defective. If weigh differs, G is defective.
Therefore, for Case 1, 3 weighing would guarantee identification.
Case 2: Weigh differs, say ABC is heavier than DEF. Then either one of ABC is too light, or one of DEF is too heavy.
Weigh AD vs. BE.
Case 2a: If AD and BE weigh equal, then either C is too light or F is too heavy. Weigh C vs. one healthy ball (say A). If weigh equals, F is defective. If weigh differs, C is defective.
Case 2b: AD and BE weigh different, say AD is lighter than BE. Then it means either B is too heavy or D is too light (A and E are safe in such case). Weigh B vs. one healthy ball (say A). If weigh equals, D is defective. If weigh differs, B is defective.
Therefore, for Case 2, 3 weighing would also guarantee identification.
In fact, 3 weighings would be adequate to identify the defective from 11 balls.
Suppose the tem balls are ABCDEFGHIJK.
Weigh ABC vs. DEF.
For Case 2 (ABC heavier than DEF), same as previous answer.
For Case 1, which implies one of GHIJK is defective -- weigh GH vs. IA (A being a healthy ball).
Case 1a: they weigh equal, meaning either J or K is defective. Simple.
Case 2a: they weigh different, say, GH is heavier than IA. That means either G is heavy, H is heavy or I is light. Weigh G vs. H. If one is heavier, that is the defective one. If they weigh the same, then I is the defective one.
It is just like the eight balls problem.
Take eight balls and keep 2 aside.
Take six balls and keep 2 aside.
Now we have combination of 6, 2, 2.
Case 1 : now weigh six balls into group of 3. if they are equal copare other two pairs of two balls each. Max. times ; 3
Case 2: If in the case of six balls, a group of three balls is heavier.
Take that group and keep 1 ball aside.
sub case a) the two balls are equal, the remaining is faulty.
sub case b) the two balls are unequal the one which is heavier is faulty.
Max. times : 3
Divide balls into 3 groups (A, B, C) of 3 balls each, and an extra ball (X).
- gen-y-s April 09, 2013Compare groups A and B, and then compare B and C.
If A=B=C then X is the faulty ball.
If A!=B and B!=C then the faulty ball is in B, other wise it's in A if A!=B, or in C if B!=C.
After determining the group that the faulty ball belongs to, compare two of the balls (b0, b1) in this group (the last ball left is b2).
If b0=b1 then the faulty ball is b2.
if b0!=b1 compare b0 and b2. If b0=b2 then b1 is fauly, otherwise b0 is faulty.
Max comparisons are 4.