Amazon Interview Question
Software Engineer / DevelopersI will number the balls form 1-10
2 balls - 1 : 2 = one try
3 balls - 1 : 2 = 1 try, since if 1 and 2 weighs the same, that leaves 3 as the one that weighs the most, if that isn't the case, then either 1 or 2 is the one that weighs the most.
4 balls - 1,2 : 3,4 to 1 : 2 = 2 tries
5 balls - 1,2 : 3,4 = 1 or 2 tries, same reason that i had for 3 balls
6 - 1,2,3 : 4,5,6, to 1 : 2 = 2 tries
7 - 1,2,3 : 4,5,6 to 1 : 2 = 1 or 2 tries
8 - 1,2,3,4 : 5,6,7,8 to 1,2 : 3,4 to 1 : 2 = 3 tries
9 - 1,2,3,4 : 5,6,7,8 to 1,2 : 3,4 to 1,2 = 1 or 3 tries
10 - 1,2,3,4,5 : 6,7,8,9,10 to 1,2 : 3,4 to 1 : 2 = 2 to 3 tries
The minimum test is 1 for odd number of balls and 2 for even number of balls, however, this is only the mininmum test when dealing with probability. If you are lucky enough to get both sides equal leaving one ball left over, then that would be a probability chance.
So i can't be sure on the precise answer for mininmum tests since the answer varies on probabil
8 Balls
Weigh(123 and 456) //Try-1
Case1
if(123 == 456)
weigh( 7 and 8) //Try-2
Case2
Weigh(123 and 456)
if( 123 > 456)
weigh( 1 and 2) //Try-2
If (1 == 2), 3 is heavy
Case3
if( 123 < 456)
weigh( 4 and 5) //Try-2
If (4 == 5), 6 is heavy
So, in TWO tries you can find out the heaviest ball.
Absolutely correct we don't need to weigh ball 7 n 8 in case 2 n 3 as they r off equal weight
How many trys if you do not know that different ball is heavy or light. Its just different then other 7 and you need to tell that which one, and which way.
Try this problem with 12 balls and one ball heavier or lighter(3 trys). ...Then try a non-adaptive solution also in 3 measurements ...this one is tough!
yaa , it is 3 step problem.
divide balls in group of 4-4-4, put 4-4 on weighin scale....if either side of weighing scale goes down, it means it contain heavy ball...... if it comes balanced that means the third group of 4 balls contain defected ball.
now try for 2-2 .....
then with 1-1....
Hi all,
Don't u think wen such a prob appears thr shud be a generic soln.
Here's my soln...
The total no. of tries will be the integer less than log (n) to the base 2(n representing the no. of balls) . So in this case it shud b 3. Try for 13 it s 3 again.
Don't know whether ths s correct or not but i think it has to hav a generalized soln.
but can't you do it if you have 3^n balls, like apurtha was talking about?
1.divide the balls into three groups [3, 3, and 2]
2. Weigh the 2 equal set, in this case the 3 and 3, if they are equal, you know the heavier ball is in the third set. if they aren't equal, you know which of the two sides is heavier, and you can divide into three groups again. you can do it using the scale twice, whereas dividing into two groups you need to weigh three times
This can be done 2 tries.
First , take 3, 3 balls for weighing. If any side is heavy , take the balls from the heavy side. Pick 2 balls from the heavier side of the balls , weigh them on the scale , if there any difference is shown, the ball on the heavier side is the culprit.
IF in the first weighing there is no difference , which indicates the heavier ball is present in the rest 2 balls. Weigh them in the second weighing to find out the heavier ball.
guys it s very simple
put one ball on each side. If they both have the same weigth, the balance will stabilise in the middle.
If one is heavier than we found our ball.
Now if the balance is stable, add again one ball on each side. If one side is heavier, then the last ball we put on this side is the heavy ball.
If it s stable again, do this one more time and you ll find the heavy ball
Guys,
Use Binary Search.
1 try: Place 4 balls on each side of the scale. Pick the heavier lot.
2nd try: Place 2 balls on each side of the scale. Again pick the heavier lot.
3rd try: Find the heavier of the selected two.
Divide them into 3 group 3,3,2 put 3,3 on scale if they are equal put 2 balls on the scale and find the one with heavy weight in 2 tries.
if one of the 3 group is heavy then divide it further in 2,1.
put 2 on scale if they are equal then the left out ball is heavy. otherwise also scale give us the heavy ball.
thus in all case we can find heavy ball in 2 tries
Ok, it took a good 20 minutes but I've got it. Label the balls a, b, c, d, e, f, g, h. Weight a, b, c against d, e, f. If they level out, then weight g against h and you're done. If they don't level out (for simplicity we'll say that a, b, c is heavier), then weight g, b, d against a, e, f. If they level out, then it is c. If g, b, d is heavier, it is b. If a, e, f is heavier, it is a.
8 balls, you don't know if the odd one is heavier/lighter.
- Neo July 19, 2007abc vs def
1) abc == def
Weigh a against g. If a == g, h is the odd one. If a < g or a > g, g is the odd one.
Total 2 tries.
2) abc < def
One of a, b, c could be a lighter ball; or one of d, e, f could be a heavier ball. g and h are normal balls.
Weigh abd against egh.
a) If abd == egh => c is lighter or f is heavier. Weigh one of them with g or h to know.
b) If abd < egh => a or b is lighter, or e is heavier. Weigh a against b. If they are equal, e is the heavier ball. Otherwise, the lighter among a and b is the lighter ball.
c) If abd > egh => d is a heavier ball.
So you can tell which ball is different and if it is heavier/lighter in 3 tries.