Algorithms | Brain Teaser

Earlier this year I decided to get a mentor. Someone who works in a robust codebase on a daily basis but is new enough to the industry to understand those challenges that come along with ramping up on data structure and algorithms. We meet weekly and he walks me through white-boarding algorithms. This is one that I learned last week. This is my second time running through the exercise. 

You have a five-quart jug, a three quart jug and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water? Note that the jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would be impossible.
— Cracking the Coding Interview, Gayle Laakmann McDowell

Let's walk through this problem. You start by filling the five-quart jug with water and pour off three into the other jug. This leaves you with two quarts of water in the five-quart jug. Then, pour out the water in the three-quart jug and fill it with the remaining two quarts from the five-quart jug. Now, the five-quart jug is empty and the three-quart jug has only two quarts. Fill up the five-quart jug with water and top up the three-quart jug with one more quart of water to fill it to the brim. The five-quart jug is left with four quarts of water. The end.

 Whiteboarding on a post it

Whiteboarding on a post it