Amazon Interview Question Software Engineer / Developers




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

8 balls, you don't know if the odd one is heavier/lighter.

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

- Neo on July 19, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I 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

- me on June 16, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

seriously!! what are you even trying to do??

- JH on December 31, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

dis man has gone madddddddddd :P

- stiffler on September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

question says 8 balls.. then y r u adding those 2 balls of urs and making it 10??? :P

- lolster on October 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Apurva Mehta on August 20, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Absolutely correct we don't need to weigh ball 7 n 8 in case 2 n 3 as they r off equal weight

- sweet on June 13, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct !! Nice and easy :)

- Addy on June 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

why would we want to measure 7 & 8. I am hoping there is ONLY one heavy ball. So if 123 comes out to be heavy, the heavy ball is either 1 ,2 or 3. And if 123 < 456, then the heavy ball is either 4, 5 or 6.

- Apurva on August 22, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- SS on October 10, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

3 measurments

- Petru on January 17, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Apurva is correct.

Also, measuring 9 balls to find the heaviest only takes 2 tries in much the same logic as 8.

- Charles on December 05, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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!

- Petru on January 15, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- samar on June 04, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not that simple ...Your first step is correct 4 vs 4 , but the ball could be either heavy or light ...so you don't know on which side it is.

- Petru on January 16, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

does anybody know the solution for SS` question?

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.

one of my friends told me you can do 13 balls with above condition in 3 turns..

- Tushar on February 13, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- ASHISH NIJHARA on March 18, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if you have 2^n number of balls, its really easy:
1. divide the balls into 2 groups [here, 4 balls each]
2. since one ball is heavier, one side will be heavier, divide that side into two and follow till you have two balls left

- adharma on April 04, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- whitaker on May 18, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous on July 30, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- brapapapa on January 16, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You solution takes more than 2 measurements wheras this can be easily done in just 2 measurements.

- gauravk.18 on March 31, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- k on May 29, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no you can do it in two moves

- Anonymous on February 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Amazon has 8 balls, it is a freak of nature. i have only 2

- amsota on March 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Arpit on March 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

umm i need help with this um okay their are 8 balls and one is lighter than the others you can use a scale but you can only use it twice how would you know which one is lighter?

- me on August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you have 8 balls one of them is lighter you have a scale but you can only use it twice how would you know which one is lighter can anyone help

- isaac on August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Mad question Mad answers

- Maxwell john joseph peters domanic develemenatl mentooonsaaaaa on November 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Divya on November 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

weigh 3 balls each side
IF even then weight the remaining two
IF one side is heavier weigh two of the Balls from the heavy side ( one on each side )
IF even the ball not weighed is the heavy or IF not even the Heavy ball will be obvious as the heaver one on the scale.

- Phil Pinkerton on February 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Generalized solution something like takes MAXIMUM x moves for N balls where
3^(x-1) < N <= 3^x
(for some non worst cases it can be less, as low as 1 move)

9 balls can be done in 2 moves
10-27 in 3 moves (or sometimes as low as 1)

- Anonymous on February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I Apurva, your solution ignores the possibility of weighing 7 & 8 in cases 2 and 3. So two tries cannot be the minimum.

- Manish on August 20, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

dont need 7 and 8. if we moved to cases 2 and 3, that implies that 123<>456 hence the heavier ball has to be 1,2,3,4,5 or 6.

- c on April 23, 2008 | Flag


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More