Water-Jug Pouring Problems

The canonical version: given a 3-liter jug and a 5-liter jug, with no markings on either, measure out exactly 4 liters. The only allowed moves are filling a jug to the top, emptying a jug completely, or pouring from one jug into the other until either the source empties or the destination fills. There's no direct way to "measure 4," so the trick is realizing every reachable amount is just a sequence of these moves away from empty.

The clean way to solve it — and the way to explain your reasoning out loud in an interview — is to treat each pair of fill levels, like (jug A, jug B), as a state, and each fill/empty/pour move as an edge to a new state. Starting from (0,0), you're really doing a search over reachable states until one of them shows 4 liters in either jug: fill the 5, pour into the 3 (leaves 2 in the 5, 3 in the 3), empty the 3, pour the 2 from the 5 into the 3, fill the 5 again, pour from the 5 into the 3 until the 3 is full — that only takes 1 more liter, leaving exactly 4 in the 5-liter jug.

The underlying fact that makes some targets reachable and others not is number-theoretic: with jugs of size $a$ and $b$, every reachable amount is a combination $ma + nb$ for integers $m, n$, so the target must be a multiple of $\gcd(a,b)$ — 4 is reachable with a 3 and a 5 because $\gcd(3,5)=1$ divides everything.