There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Nilesh Raje wrote:Hi ,
My friend was asked this puzzle in a java interview. I need your help for the solution and solving technique of this.
1)You have 10 marbles and one is heavy. How many minimum iterations are needed to find the heavy marble.
2) There are two jars of capacity 5 and 3 liter. How to measure 7 liter of water using these two jars.
Ans) I guess this can be done this way.
Given : j1= 5 and j2=3
Step 1: Pour water in j1 till it fills that mean now j1 will hold 5 liters
Step 2: Now pour the remaning water in j2 so it now holds 2 liters.
Ummm is this right.?
Please help.
Thanks
Nilesh Raje wrote:
At step to i will have 5 lts already with me in j1 and j2 would be holding 2 lts so thats total of 7 lts measured. Why are you saying its incomplete?
1)You have 10 marbles and one is heavy. How many minimum iterations are needed to find the heavy marble.
2) There are two jars of capacity 5 and 3 liter. How to measure 7 liter of water using these two jars.
SCBCD, SCJP & MCP
HowToAskQuestions
Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Bert Bates wrote:I believe the more advanced version of the marble problem is this:
You have 12 marbles and one of them is either heavier or lighter than all the rest. Given a balance, and three weighings, determine which marble is different, and whether it's heavier or lighter.
This one took me a loooong time to solve
Make visible what, without you, might perhaps never have been seen.
- Robert Bresson
Venkat Divvela wrote:The solution to 12 marbles is. As Thillakan said marbles can be grouped by 3 1-3, 4-6,7-9,10-12.
suppose the 12th marble is heavier one.
It takes two weighings to find the group that has heavier marble. In the third weighing 10 and 11 can be compared and they are of same weight. So 12th marble is heavier than rest.
SCJP 5
Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Bert Bates wrote:I believe the more advanced version of the marble problem is this:
You have 12 marbles and one of them is either heavier or lighter than all the rest. Given a balance, and three weighings, determine which marble is different, and whether it's heavier or lighter.
This one took me a loooong time to solve
Make visible what, without you, might perhaps never have been seen.
- Robert Bresson
Michael Ernest wrote:I don't think this is completely correct.
In the first scenario, the first weighing yields a balance, so you know the odd marble is in group C. You divide C into two equal groups and weigh again. There must be an imbalance. If you switch a marble from each side and see no change in balance, however, you only know that you switched two uniform marbles. In this case, there are now two marbles that could be odd, but you don't know if the odd one is lighter or heavier.
Michael Ernest wrote:
If you start with four groups of 3, you can solve almost all cases in three weighings. I leave that as an exercise to other interested puzzlers. You eliminate six marbles by binary process. Then the fun begins.
If you start with three groups of 4, it comes to the same thing. You can eliminate one group in the first weighing, and four more marbles in the second weighing. What you can't do in all cases is isolate and characterize the odd marble in one more weighing.
Or maybe you can! I was so cross-eyed last night I couldn't see it. I would love some prime brain time to put this problem to bed, but it ain't happenin' for me today.
Make visible what, without you, might perhaps never have been seen.
- Robert Bresson
Make visible what, without you, might perhaps never have been seen.
- Robert Bresson
Michael Ernest wrote:Before your explanation, however, I inferred that 12 was the maximum one could handle with an odd marble in three weighings. Is that the case?
Consider Paul's rocket mass heater. |