It's not homework, I was just looking at a list of interview questions and nobody has answered it.
You have 10 balls. Out of 10 balls 9 of them weights the same, and 1 weighs just a little bit more. Find the heavier ball the in the least amount of steps - imagine you are using a balance to find this. (No. of steps == no. of times you balance.)
Hint: Should be able to find it in 2 steps. Naive way takes at most 3 steps.
Other urls found in this thread:
mytechinterviews.com
twitter.com
do your own homework
but its not homework.
Place four balls on each side of scale.
If balanced, discard all eight balls. Place remaining two on scale. Determine heaviest.
If unbalanced, remove the lighter four balls and place two of each from the heavy subset on either side of the scale. Compare the new heavy subset to determine heaviest.
Number of measures: 2 to 3.
just put each ball on the corner (don't think they are actually corners but you get the idea) of a decagon and you can find it in one step
Start placing them into the scale one by one. You will notice that one of the balls you picked up feels a bit heavy. It's that one.
O(0)
In English please
>Decagon balance.
Ok kid. If I asked you this question at an interview and you said 'decagon balance,' I would start ripping up your resume before you left the room.
mytechinterviews.com
thank you google.
You did not read what you linked.
On the flip side, if I was ever asked this meme question in a tech interview I'd walk out and inform other individuals that the company isn't to be taken seriously
why? it is perfectly valid
I was at an interview on friday and I was asked if I have a vinyl record collection (I do)
Invent a ten sided balance scale and put each ball on a side. Solved it in one step. Duh
(1/2)
This problem is impossible and here is how to prove it.
First, notice that it is impossible, in one step, to guarantee that you can determine which of four balls is heavier. To show this, consider the following possible balance measurements of four balls:
1. Measuring 1 on 1. This does not work because, if you are unlucky, the heavier ball will be one of the other two balls. Then you only have a 50/50 chance of guessing which ball is the heavier one.
2. Measuring 2 on 2. This does not work because if one side is heavier than the other, that only tells you that one of two balls is the heavier one.
3. Measuring 3 on 1 (plus two more balls that are guaranteed to not be the heavy one). This would only help if the side with the one test ball tilts heavier. If the side with the three test balls tilts heavier, then we do not know which of the three balls is the heavier.
4. Measuring 2 on 1 (plus one more ball that is guaranteed to not be the heavy one). This would only help if the balance either tilts to the side with the one test ball, or does not tilt at all. However, if it tilts to the side of the two test balls, we do not know which is the heavier one.
5. Measuring 4 on 0 (plus four more balls that are guaranteed to not be the heavy one). This obviously does not work as it will always tilt on the side with the four test balls, giving us no new information.
6. Measuring unequal numbers of balls. This is does not work because it is possible that the heavier ball is not twice as heavy as a normal ball.
Any other measurements are, in some way or another, identical to one of these five.
You drop them all on someone's back at the same time and the one that hurt the most is the heaviest.
(2/2)
So, now that we know that it is impossible to guarantee which of four balls is the heavier one in one balance, we know that, with ten balls, it is only possible to determine which is the heavier ball if we measure at least 7 balls against each other. This is true because if we measure 6 or less, and the scale does not tip, then we are left with at least 4 balls with one guaranteed to be heavier than the others. And as we have shown above, it is impossible to determine which is the heavier one in one balance.
Next, notice that measuring exactly 7 balls may not tell us any useful information, as I have explained above with point 6 (we cannot measure an odd number of balls equally on a scale). Therefore we must measure at least 8 balls against each other. This does not work however. To see this, suppose we number the balls 1-8 and place them on the scale, comparing 1-4 and 5-8. If it tilts such that 1-4 is the heavier side, then we are stuck with four balls, of which we know exactly one is heavier. As shown above, it is impossible to determine which of these four is the heavier one in one balance. Therefore, it is impossible to guarantee that, with ten balls with exactly one heavier than the others, that we can determine which is the heavier one in two balances.
>Measuring 2 on 2. This does not work because if one side is heavier than the other, that only tells you that one of two balls is the heavier one
Then you just do one more measurement, retard.
step one, get average weight of all balls.
step two. select ball with weight more than that.
The point is precisely that it is impossible to do in just one balance. It is easy to find out which of four balls is heavier in two balances, but you cannot do it in one. Learn some reading comprehension, faggot
1 put 5 balls on each side of the scale
2 discard the lighter side
3 place two balls on each side of scale and one in your hand
4 if they are equal the one in your hand is the heavy ball
Continue
>reading comprehension
No u.
The problem text is verbatim "Find the heavier ball the in the least amount of steps"
>Hint: Should be able to find it in 2 steps. Naive way takes at most 3 steps.
OP claims it's possible in 2, and that if you find a way to do it in 3 you are naive. Are you okay?
>rejects an interviewee for thinking outside the box
Shit company
Can anyone post more efficient method than one half of balls per side, pick heavier side, repeat? Is that log(n) algorithm?
take 4/4 if if they balance take the 1/1 left :2steps
take 4/4 if they dont balance mark all balls on the havier side with an x. remove lighter balls and put the same number of balls with x on each side. than determine heavier side and weight than again: 3steps
i dont think you can make it more efficient
A more efficient method guarantees 2 steps in 6/10 cases, and 3 in 4/10 cases. Number the balls 0-9, set 0 aside. Measure 1-3 vs 4-6. If it tilts (suppose 1-3 is heavier), measure 2 vs 3. If it tilts, the heavier one is the ball. If it does not tilt, you must measure 0 vs 1. Similarly, if 1-3 vs 4-6 does not tilt, you measure 7 vs 8, like with 2 vs 3.
I do not know if this is the most efficient method. But measuring half vs half guarantees 2 steps 2/10 times and 3 steps 8/10 times.
You could boil it down to information theory- you're only allowed 2 bits of information.
but you have a worst case where 7vs8 doesnt meassure either and u need 4 balances
woops, i am retarded forget please
hey same!