Amazon Interview Question
Software Engineer / Developersif 9 marbles, put them in 3 groups, so each group has 3 marbles so only one group would have different weight than the other two group since there's only 1 marble is different than the others. So take the two groups aside and you left with 3 marbles and weigh them again and you find the result!!
anonym's answer was correct. It doesn't matter if weighs more or less, no matter what it will make the group's weight different than the others.
I think 3 comparison is requires. Divide into 3 parts . Compare 1 & 2 part . If they are balanced defect is in 3rd part. If 1 & 2 imbalanced than take the lighter version from 1 & 2 comparison and compare it with 3rd part. If its equal than defect piece is another part from 1 & 2 comparison and its heavy else it will be lighter one. Now we know that ball is heavy or light . So now compare 2 balls in this part. if they are equal than 3rd one had defect and if not than heavy one has defect.
So in total 3 weighing would be required.
best case: two weighing, worst case: three weighing
divided into three triples. if equal, then look at the third triple, weigh two of the third triple, if equal, then the third one in the third triple is the one., else, then weigh the first triple and the second triple, then will know if the abnormal one is overweighted or not.
ok, if the two triples are not equal. then test the first triple and the third triple to know if overwieghted or light, also will know it is in side which triple, then test two of the abnormal triple, (cuz you know if the abnormal one is overweighted or light),then you know the answer
well tAlking about best cases and worst cases for this problem:-
we can have best case as 1 weighing
and worst case more than three weighing for sure
if we choose to make two sets of quadruplets and if they equal each other then the left over single marble is the defective one, hence best case of 1 weighing.
same for worst case..it can be gotten in other ways too I guess. I don't want to worry about the worst case anyway.
Thanks.
that's not the best case, since, you have 1/9 possibility to get the right ball, therefore, the expect number of operation is not the most optimal
what I argued about the worst case, and best case, which are both based on the same operations strategy. Otherwise, if you change the strategy, that's not the best or worst case, since every time, you have to do the same thing, whatever the result turns out
Yes, splitting into 3 vs 3 in first weighing will not give the answer in 2 weighings: If they turn out equal in first weighing, how will you determine in 1 weighing, of the last three, which is different?
In fact 2 weighings is not possible, it will take at least three if we don't know if the ball is heavy or light.
If I remember correctly, For k weighings, max you can do is (3^k - 3)/2. If you don't believe me, lookup the web!
here is the answer...in max 3 and min 2 weighs
divide the 9 coins into two parts say(l1,l2,l2,l4)and(h1,h2,h3,h4) and say the remaining coin is x.
step1.now weigh first part with the second one..
two possibilities are there.if both are equql,then go to step 3.otherwise go to step 2.
step2.divide the coins as(h1,h2,l1) and (h3,h4,x).weigh two parts.3 possibilities are there.
1.if both are equal,then 1 of l2,l3,l4 is lighter.so weigh l2 with l3.if both are equal,then l4 is odd and is lighter ow the lighter one is odd and is lighter.
2.if(h1,h2,l1) is heavier,then either of h1 or h2 is heavier.weigh h1 with h2.heavier one is odd and is heavier.if both are equal,then there is something wrong.
3.if(h3,h4,x) is heavier,then either h3 or h4 is heavier or l1 is lighter.so weigh h3 with h4.if both are equal,then l1 is odd and is lighter ow the coin on heavier side is odd and is heavy.
step3.weigh coin x with any of the remaining 8 coins.if x is on lighter side,then x is odd and is lighter ow x is odd and is heavier.
1234-5678
case 1234=5678
9 is the answer
Case 1234<5678
Learnt : 1234 is the lighter side
564-789
Case 564 = 789
Learnt : 123 contains ur answer
1-2
Case 1=2
3 is the answer
Case 1<2
1 is the answer
Case 1>2
2 is the answer
Case 789 < 564
5-6
Case 5=6
Not possible
Case 5<6
6 is the answer
Case 5>6
5 is the answer
Case 789 > 564
7-8
Case 7=8
4 is the answer
Case 7>8
7 is the answer
Case 7<8
8 is the answer
Case 1234>5678
W.L.O.G Answer can be determined in 2 more comparison.
1234-5678
case 1234=5678
9 is the answer
Case 1234<5678
Learnt : 1234 is the lighter side
564-789
Case 564 = 789
Learnt : 123 contains ur answer
1-2
Case 1=2
3 is the answer
Case 1<2
1 is the answer
Case 1>2
2 is the answer
Case 789 < 564
5-6
Case 5=6
Not possible
Case 5<6
6 is the answer
Case 5>6
5 is the answer
Case 789 > 564
7-8
Case 7=8
4 is the answer
Case 7>8
7 is the answer
Case 7<8
8 is the answer
Case 1234>5678
W.L.O.G Answer can be determined in 2 more comparison.
2attempts --best case.
first split into a,b,c(Each 3 balls)
then find out the group which has diff weight..(lets say a )
Second take 2 balls out of these 3 balls from group a.
if both the balls have same weight then the one u dint choose was faulty ball.
if balls have diff weight then exchange the ball and do another comparison..3 attempts.worst case
2 tries. first two groups of 3. if one is heavier you narrowed it down to that group of 3. if they are equal you narrowed it down to the remaining group of 3. then pick 2 and weigh those. if they are equal you know the 3rd is the one. if not you are down to 1 and are done.
2 weighings and some elimination.
2 passes .. weigh two triplets at a time, if they are balanced the overweight marble is in the third triplet and weigh two of the third triples..you will find one.. done!! Else if there is imbalance in the first two triplets then take the imbalanced triplet and weigh two of the marbles in it !! voila...
Nopes...the question does not say that a marble is 'overweight'..it just says it is not the same as others.
Let marbles be 123..9, L = light, H = heavy , G = good
- rottentomato November 23, 2008weigh 123-456
then if L-H
weigh 124-389, L-H again => weigh 1-3(G) => 1 or 2 for light, H-L => weigh 4-1(G) => 3 or 4 for heavy, equal => weigh 5-1(G) => 5 or 6
else
weigh 71-82, L-H => weigh 7-1(G) => 7 or 8, equal => 9
max 3 weighs