Question: If you had an infinite supply of water and a 5 quart and 3 quart pails, how would you measure exactly 4 quarts? and What is the least number of steps you need?
Update: There is a better solution in the comments section which requires only 6 steps.
Answer: This question is very simple actually. Since we can’t hold 4 quarts in the 3 quart pail, we have to look to filling up the 5 quart pail with exactly 4 quarts. Lets count the steps as we move along
1. Fill 3 quart pail ( 5p – 0, 3p – 3)
2. Transfer to 5 quart pail (5p – 3, 3p – 0)
3. Fill 3 quart pail ( 5p – 3, 3p – 3)
4. Transfer to 5 quart pail (5p – 5, 3p – 1)
5. Empty 5 quart pail (5p – 0, 3p – 1)
6. Transfer to 5 quart pail (5p – 1, 3p – 0)
7. Fill 3 quart pail ( 5p – 1, 3p – 3)
8. Transfer to 5 quart pail (5p – 4, 3p – 0) We are done!!!
That was easy right. Now for those who are mathematical and need everything solved in terms of a formula, here comes a little more mathematical solution.
Now the general steps are to fill up the 3 quart pail and keep transferring to the 5 quart pail (empty if full) until we hit 4 quarts. Therefore, the total amount of water we filled in the 3 quart pail must be equal to 4 more than a multiple of 5 (since we discard 5 quarts of water at a time). From this, we can derive this formula.
5n + 4 = 3m, where n and m are arbitrary positive integers
n represents the number of times we had to empty the 5 quart pail and m represents the number of times we had to fill up the 3 quart pail.
Now all we have to do is solve for the lowest set of positive integer solutions for {n,m}. {1, 3} is the lowest set. Some of the other solutions are {4, 8}, {7, 13}, {10, 18} and so on.
Hope you enjoyed the nerdy mathematical solution.
If you have any questions, please feel free to send me an email at [email protected]. If you have any interview questions which you feel would benefit others, I would love to hear about it.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
6 steps
1. Fill 5p
2. Transfer 3quart of 5 to 3p
3. Make empty 3p
4. Transfer remaining 2quart of 5p to 3p
5. Fill 5p
6. Transfer 1quart of 5p to 3p =>>Ans remaining 4quart in 5p
1. Fill 5 and 3 quart pail simultaneously
2. Empty 3 quart pail once its filled, and now let it fill for remaining 2 quart (i.e. when 3 quart pail if full, we have 2 quartz in 5 quart pail)
3. Now, by the time we fill 3 quart pail with 2 quartz of water, we have 5 quartz pail full. So now empty the 5 quarts pail.
4. Now, 3 quart pail is getting filled with 1 more quartz of water and simultaneously 5 quart pail is also getting filled. When 3 quart pail is full, shift the entire water in 5 quart pail (Since, right now 5 quart pail has 1 quart of water and 3 quartz pail has 3 quartz of water)
***** Best Solution ***** 🙂
1. Fill 5 quart pail & Transfer to 3 quart pail (5p = 2, 3p = 3)
2. Throw water of 3 quart pail & Transfer 5 quart pail water to 3 quart pail (5p = 0, 3p = 2)
3. Fill 5 quart pail & Transfer to 3 quart pail (5p = 4, 3p = 3)
You will be left with 4 quarts in 5 quart pail 🙂
Shrenik’s answer assumes that the pail is a perfect cylinder or prism, whose sides make a 90 degree angle with the base. If that is the case, then that answer could possibly work (if you are completely accurate when you’re tilting). But most pails are tapered, having a wider top and a narrower bottom. And in those cases, that method would not work.
Containers need not to be symmetrical. So minimum #steps will be 6 by the solution provided by Michael.
I am impressed with Shrenik’s solution…but I have my own alternative:
1. Fill 3 quart pail and transfer to 5 quart pail
2. Fill 3 quart pail again and while transferring, now, when 5 quart pail is full, retain the water in 3 quart pail (1 quart), whilst emptying the 5 quart pail.
3. Now transfer 1 quart from 3 quart pail to 5 quart pail.
4. Fill 3 quart pail and transfer to 5 quart pail.
Maybe transferring the contents is also considered one step!
I’m with Shrenik. I was going to leave that answer but he/she already did. Its the fastest and its the simplest. Such logic hasn’t landed me a job anywhere near google or microsoft though…
Michael Brunton …Your answer s best among other answers so far.,cheers!!:)
Thinking a little outside the box, or pail as it were…
1. Place the 3 quart pail in 5 quart pail.
2. Fill the 5 quart pail, whilst holding the 3 quart pail such that both rims are coplanar.
3. Remove the 3 quart pail and transfer the contents (2 quarts) to it.
4. Fill the 5 quart pail.
5. Transfer the contents to the 3 quart pail until full (1 quart).
You are now left with 4 quarts in the 5 quart pail.
I guess that could be a solution provided you talk in through with the interviewers and they don’t mind that answer. My guess is that they will likely make an excuse at that point to make sure you can’t use that logic. 🙂
How about using the diagonal-divides-in-half property of a symmetrical container? For example if you fill a pail to the brim and then tilt it to the point where the surface of the water overlaps the diagonal plane of the pail from the bottom to the top, the pail will be exactly 1/2 full.
1. Fill 5 quart pail, tilt
2. Fill 3 quart pail, tilt
3. Transfer contents of 3 quart to 5 quart pail
I’m pretty certain there is a faster solution to this, but I’m not sure that I can mathematically prove that it always works.
1. Fill the 5 quart jug (5p = 5, 3p = 0)
2. Transfer to 3 quart jug (5p = 2, 3p = 3)
3. Throw away 3 quart jug (5p = 2, 3p = 0)
4. Transfer to 3 quart jug (5p = 0, 3p = 2)
5. Fill 5 quart jug (5p = 5, 3p = 2)
6. Transfer to 3 quart jug (5p = 4, 3p = 3)
Hope that proves interesting.