IBM Interview Question
Developer Program EngineersTeam: FRESHER
Country: India
Interview Type: Written Test
5 balls and 1 weight, so the max ways is log6. so 3 steps would get the result.
balls:1,2,3,4,5
1) put 1, 2 in scale, if 1 == 2, put 3, 4 in scale, if 3 ==4, then 5 is the ball. put 5 and 1 in scale, then now 5 is lighter or heavier.
2) put 1, 2 in scale, if 1 == 2, put 3, 4 in scale, if 3 != 4, then 3 or 4 is the ball, take 3 away, put 1, 4 in scale, if 1 == 4, then 3 is the ball, by last step, we know 3 is lighter or heavier. if 1 ! = 4, then 4 is the ball, by last step, we know 4 is lighter or heavier.
3)put 1, 2 in scale, if 1 !=2, 1 or 2 is the ball, take 1 away, and put 2, 3 in scale, if 2 == 3, then 1 is the ball, by last step, we know 1 is lighter or heavier. if 2 !=3, then 2 is the ball, by last step, we know 2 is lighter or heavier.
Assume that 4 balls are of 1 kg and 5th ball is of 2 kg.
1. Place 3 balls on left side and 2 balls on the right side.
2. If both the sides are equal, then compare these 2 balls on the right side, you will get a heavier ball.
3. If left side is heavier, then compare these 3 balls by putting 2 balls on left side and 1 ball on right side.
If both the sides are equal, then ball on right side is heavier,
Otherwise again compare the 2 balls on the left side, you will get a heavier ball.
take any 2 balls at first and weigh them if they are equal take the next 2 balls. if they are also equal then the 5th ball is the heavier. By doing this we can do it in 2 attempts
We can find the average weights of all the balls and select the balls whose weights are more than the average and find the heaviest say for example (1+2+3+4+5)/5=3 now compare only 4 and 5 to find the heaviest.
take any four ball and compare the weight having in pair of two.
if bith set of ball is equal then the fifth one which is not measured is heavier.
if one of the set if heavier then compare between that two ball.
I thnk its Right ..
But u give Reply in logical way so it is benefical for me................
to be more clear..
let say u have a,b,c,d,e.. 5 ball.
take a and b, c and d together and compare the weight between these two sets.
if both are equal so, e is heavier.
if set a and b is heavier then compare the weight between then and find the heavier one, otherwise compare the set of c and d.
@sjain: I am not satisfied with your ans.
Suppose we have all 5 balls in Kg. 3,4,5,6,7 And we picked 3,7 and 5,6 as two lot.
So we got 5,6 as the heavier combination and then according to you it will be 6 as our ans.
but correct ans is 7.
Let me know if I am missing any point.
I guess you are right, but if that is actually the case then we need to prove that it is impossible, it can be proved some concept called information theory.
5 balls
2 weighs gives us two outcomes , two bits of information
can represent 00, 01, 11, 10 (4 states)
but there are 5 balls hence, it is impossible.
you are right, but you forgot about information of heavier or lesser. If it is given that one is lesser than the solution exist. And outcome of any comparison has 3 options (>,<,=), therefore, as a result of 2 comparisons we have 9 states but the result has 10 states (5 (balls) x 2 (heavier or lesser) ) . So there is always 1 state which is anrechable
Leave them from same height......which reaches the ground first is the heaviest ball :-) LOL
1st thing in question weight was not specified,
second if you consider weight then also the height of balls in the water from ground will vary according to there weight...
Or 3rd you can take a large tub with more water....
or 4th solution-
full a bucket of water,
for each ball,drop the ball in the bucket,measure the water coming out from bucket,
the heavier ball the more water ( Buoyancy Rule, Archimedes' principle)
@Ashwini
good thinking outside the box, I guess the problem description here is not complete, if it was then it would have included a simple balance and the interviewer is test the knowledge on the information theory, see below Tigran's comment.
The maximum ways to find the solution is 3 and minumum ways is 1.
- sheshu March 06, 2013lets say, we have 12345 balls.
Now weigh 12 and 34.
If both are equal then 5 is the heavier/lighter ball.
If 12 and 34 weight are different then we conclude that 5 is correct ball.
step1: compare 1 and 3
if equal then answer is either 2 or 4.
now compare 2 and 5
if equal 4 is answer.
if not equal 5 is the answer.
if 1 and 3 not eqal
compare 1and 5
if equal 3 is answer.
if not equal 1 is answer.
So in worst case we have 3 weights. in best case we it is only 1 weight.