The Water and Jug Problem is a classic logic puzzle that asks whether it's possible to measure exactly target liters of water using two jugs with capacities jug1 and jug2. You can perform three types of actions: fill a jug to the brim, empty a jug, or pour water from one jug into another until either the source is empty or the destination is full.
Uber and Google use this Water and Jug Problem interview question to see if a candidate can model a physical process as a mathematical or graph problem. It can be solved using either Graph Traversal (BFS/DFS) or Number Theory (GCD). It tests your ability to recognize the "State Space Search" pattern, where each state is the current amount of water in the two jugs.
There are two main ways to solve this:
target is a multiple of the Greatest Common Divisor (GCD) of jug1 and jug2, and target <= jug1 + jug2.(x, y) as a node in a graph. Starting from (0, 0), you explore all possible next states. This is the BFS interview pattern for state discovery.Suppose jug1 = 3, jug2 = 5, and target = 4.
Candidates often miss the total capacity constraint—you can't measure more water than the sum of both jugs. In the BFS approach, forgetting to use a "visited" set to track seen states is a major mistake that leads to infinite loops. If using the math approach, many forget to handle the target = 0 case or the case where one jug has zero capacity.
Learn the GCD (Greatest Common Divisor) algorithm (Euclidean algorithm). It’s a powerful tool that appears in many math-heavy coding problems. Also, practice converting "simulation" problems into "graph search" problems by defining what a "state" looks like.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Bulb Switcher II | Medium | Solve | |
| Nested List Weight Sum | Medium | Solve | |
| Detonate the Maximum Bombs | Medium | Solve | |
| Time Needed to Inform All Employees | Medium | Solve | |
| Reorder Routes to Make All Paths Lead to the City Zero | Medium | Solve |