Suppose you had 8 billiard balls, and one of them was slightly heavier, but the only way to tell was by putting it on a scale against another. What's the fewest number of times you'd have to use the scale to find the heavier ball?
Lets have some fun.... (and prepare for that MS interview :P)
- Thread starter gopunk
- Start date
RedRooster
Diamond Member
- Sep 14, 2000
- 6,596
- 0
- 76
Ok, I can already see the first joke coming, but anyone willing to bet on when the words "cancerous" and "testical" are going to be used? I'd say by the 37th post, no later.
Maetryx
Diamond Member
- Jan 18, 2001
- 4,849
- 1
- 81
If you put 3 on each side, and they all balance out, then the heavier is one of the 2 remaing. So one more time and then you've got it.
If you put 3 on each side, and one side is heavier, then concentrate only on the 3 on the heavy side. Weigh two of those. If they balance, then the third is it. If they don't, well then you have the heavier one on the heavy side of the scales.
Either way, 2 wieghings will *necessarily* get you to the heaviest ball. For the record, I think my solution is the best one, and I am not familiar with this puzzle.
If you put 3 on each side, and one side is heavier, then concentrate only on the 3 on the heavy side. Weigh two of those. If they balance, then the third is it. If they don't, well then you have the heavier one on the heavy side of the scales.
Either way, 2 wieghings will *necessarily* get you to the heaviest ball. For the record, I think my solution is the best one, and I am not familiar with this puzzle.
uh.............twice.
you said to find the heavier ball, but not the heaviest ball. So you put the first one in. Then you put the second one in. there.
you said to find the heavier ball, but not the heaviest ball. So you put the first one in. Then you put the second one in. there.
alright i'll post the answer since i'm tired of waiting 
i didn't get it right either.
2.
you take 3 balls on each side, leaving 2 out. if they are equal, you then weigh the 2 remaining and find it that way.
if they are not equal, discard the lighter set, and weigh 2 of the balls from the heavier one. if they are equal, then the one left out is the heaviest, and if they are not, then you know which one of them is heavier since they are on the scale.
i didn't get it right either.
2.
you take 3 balls on each side, leaving 2 out. if they are equal, you then weigh the 2 remaining and find it that way.
if they are not equal, discard the lighter set, and weigh 2 of the balls from the heavier one. if they are equal, then the one left out is the heaviest, and if they are not, then you know which one of them is heavier since they are on the scale.
I see... a wording issue... good call, but wouldn't it only be once since heavier is between two objects?
Pretty clever, I said 3.
4 on each side
take the heavier side from the above and you now have 2 on each side
take the heavier side from the above and you now have 1 on each side
Oh well...
4 on each side
take the heavier side from the above and you now have 2 on each side
take the heavier side from the above and you now have 1 on each side
Oh well...
I don't agree with the answer, at least to the question that you proposed. You never stated that you could use multiples and the phrase "only way to tell was by putting it on a scale against another" implies that you must do it one at a time.
That's what I thought too. I figured that if that were the case, you'd have a "depth" of 8 (8 balls permuted for each side max) and 2 sides, so you have 8 ^ 2 total permutations to find the heavier ball, at a maximum. Since using this method, determining the ball in less than 8^2 permutations is non-deterministic, I figured there was probably a semantic anamoly in the question allowing one to put multiple balls on each side.
I've heard MS asks more direct questions, like..
"Why are manholes round?"
No ambiguities with that one
It's a search problem, so "binary search" should be popping into your mind. As Descartes says, follow the usual divide-and-conquer (4,4) (2,2) (1,1) = 3 tries = log2(8)
I got the correct answer fairly easily, but I've worked with a lot of algorithms so I knew where to start.
In case some of you are interested, the way I figured it out is to first acknowledge the simple facts (the ones you probably realize but don't think about).
The most important fact here is that in order to gain any useful information, the number of balls on each end of the scale must be equal.
The straight-forward algorithm (which Descartes mentioned) is to start with 4v4, and simply divide until you get 1v1. I also tried this first, but was unimpressed with 3 iterations, and I sensed that there was some redundancy (if for no other reason, I realized questions asked like this aren't usually answered with the straight-forward approach, and the correct one would have to be more clever).
Since the number of balls on each end must be equal in order to get any useful information, the next algorithm I would try would simply be 3v3 instead of 4v4. The only way to get this is to "hold" two.. which I did, and once you get on this track it's pretty easy to figure out.
In case some of you are interested, the way I figured it out is to first acknowledge the simple facts (the ones you probably realize but don't think about).
The most important fact here is that in order to gain any useful information, the number of balls on each end of the scale must be equal.
The straight-forward algorithm (which Descartes mentioned) is to start with 4v4, and simply divide until you get 1v1. I also tried this first, but was unimpressed with 3 iterations, and I sensed that there was some redundancy (if for no other reason, I realized questions asked like this aren't usually answered with the straight-forward approach, and the correct one would have to be more clever).
Since the number of balls on each end must be equal in order to get any useful information, the next algorithm I would try would simply be 3v3 instead of 4v4. The only way to get this is to "hold" two.. which I did, and once you get on this track it's pretty easy to figure out.
Originally posted by: Maetryx
I think the most important thing to notice, indeed to remember, is that Maetryx solved it first.
STFU :|
I've heard MS asks more direct questions, like..
"Why are manholes round?"
No ambiguities with that one
meh... i got this from a website that has a big 'ol list of ms interview questions
"Why are manholes round?"
No ambiguities with that one
meh... i got this from a website that has a big 'ol list of ms interview questions
Originally posted by: gopunk
I've heard MS asks more direct questions, like..
"Why are manholes round?"
No ambiguities with that one
meh... i got this from a website that has a big 'ol list of ms interview questions
ive gotten both those questions in interviews.
TRENDING THREADS
-
Discussion Zen 5 Speculation (EPYC Turin and Strix Point/Granite Ridge - Ryzen 9000)- Started by DisEnchantment
- Replies: 25K
-
Discussion Intel Meteor, Arrow, Lunar & Panther Lakes + WCL Discussion Threads
- Started by Tigerick
- Replies: 23K
-
Discussion Intel current and future Lakes & Rapids thread- Started by TheF34RChannel
- Replies: 23K
-
-
Facebook
Twitter