Cracking The Coding Interview Together – Problem 6.5: Jugs of Water

We have all been there: sitting in an interview room, or perhaps watching a classic action movie like Die Hard with a Vengeance, when the antagonist presents a seemingly simple puzzle. You have a five-quart jug, a three-quart jug, and an unlimited supply of water. Your mission, should you choose to accept it, is to measure out exactly four quarts of water. There are no markings on the jugs, and guessing by eye is a recipe for disaster.

At first glance, this feels like a riddle designed to test your lateral thinking. But as senior engineers, we must look past the physical props and see the underlying system. This is not just a brain teaser; it is a classic state-transition and graph-traversal problem. Our shared goal today is to demystify this puzzle, model it as a formal state-space search, and write a production-ready, generic solver in Java that can handle any arbitrary jug capacities and target volumes.

Problem Statement

Let us formally define the operational parameters of our challenge:

• Inputs:
  • A jug with a maximum capacity of 5 quarts (let's call it Jug A).
  • A jug with a maximum capacity of 3 quarts (let's call it Jug B).
  • An unlimited source of water (e.g., a running tap) and a drain to discard water.
• Allowed Operations:
  • Fill any jug completely to its brim.
  • Empty any jug completely into the drain.
  • Pour water from one jug into another until either the receiving jug is full or the pouring jug is empty.
• Goal: Measure out exactly 4 quarts of water in one of the jugs using the minimum number of operations.

Analyze the Problem Together

Let's break down the constraints and find the "Aha!" moment. Why is this problem interesting? It is because we cannot measure arbitrary amounts of water directly. We can only transition between discrete states determined by the capacities of our containers.

Mathematically, this problem is governed by Bézout's Identity. The identity states that for any integers $a$ and $b$, the equation $ax + by = d$ has a solution in integers if and only if $d$ is a multiple of the greatest common divisor (GCD) of $a$ and $b$. Here, our capacities are 5 and 3. Since $\gcd(5, 3) = 1$, we can measure any integer volume up to the maximum capacity of 5 quarts, including our target of 4 quarts.

If we try to solve this naively by guessing steps, we might get lucky, but we risk falling into infinite loops or missing the most efficient path. Instead, we should view this as a State Transition Graph:

• Nodes (States): Represented as an ordered pair (x, y), where x is the current volume in the 5-quart jug, and y is the current volume in the 3-quart jug.
• Edges (Transitions): The valid operations (Fill, Empty, Pour) that take us from one state to another.

Because we want to find the shortest sequence of steps to reach our target state, a Breadth-First Search (BFS) is the perfect architectural choice. BFS guarantees that the first time we encounter our target volume, we have found the path with the fewest transitions.

Questions for the Interviewer

Before jumping into the code, a senior engineer always clarifies the boundaries of the problem. Here are the questions we should ask:

1. "Can the target volume be distributed across both jugs, or must it reside entirely in a single jug?" (For our implementation, we will assume the target can be in either jug, though with 5 and 3, a target of 4 must reside in the 5-quart jug since the 3-quart jug cannot hold it).
2. "How should we handle impossible targets?" (e.g., trying to measure 4 quarts with a 6-quart and a 2-quart jug, where $\gcd(6,2)=2$, making 4 possible but 3 impossible. We should return an empty path or throw an exception).
3. "Are we optimizing for execution speed, memory footprint, or code readability?" (We will aim for a clean, object-oriented design that balances all three, using a generic state representation).

Think About the Solution

Let's design our high-level architecture. We need:

1. A State class to represent the current water levels in both jugs. To reconstruct our path once we find the solution, each state should keep a reference to its parent state and the action that led to it.
2. A mechanism to generate all valid next states from a given state. From any state (x, y), we have up to 6 possible transitions:
   • Fill Jug A: (A_max, y)
   • Fill Jug B: (x, B_max)
   • Empty Jug A: (0, y)
   • Empty Jug B: (x, 0)
   • Pour A into B: Pour until B is full or A is empty.
   • Pour B into A: Pour until A is full or B is empty.
3. A visited set to keep track of states we have already evaluated. This prevents infinite cycles (e.g., filling and emptying the same jug repeatedly).
4. A queue to manage our BFS traversal.

Write Code and Explain

Let's implement this elegant, production-ready solution in Java.

import java.util.*;

public class WaterJugSolver {

    // Represents the state of the two jugs at any point in time
    public static class State {
        final int jug1;
        final int jug2;
        final State parent;
        final String action;

        public State(int jug1, int jug2, State parent, String action) {
            this.jug1 = jug1;
            this.jug2 = jug2;
            this.parent = parent;
            this.action = action;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            State state = (State) o;
            return jug1 == state.jug1 && jug2 == state.jug2;
        }

        @Override
        public int hashCode() {
            return Objects.hash(jug1, jug2);
        }

        @Override
        public String toString() {
            return String.format("[%d, %d] (%s)", jug1, jug2, action);
        }
    }

    public static List<State> solve(int cap1, int cap2, int target) {
        // If target is larger than both jugs, it's impossible
        if (target > Math.max(cap1, cap2)) {
            return Collections.emptyList();
        }
        // If target is not divisible by the GCD of both capacities, it's impossible
        if (target % gcd(cap1, cap2) != 0) {
            return Collections.emptyList();
        }

        Queue<State> queue = new LinkedList<>();
        Set<State> visited = new HashSet<>();

        State initialState = new State(0, 0, null, "Initial State");
        queue.offer(initialState);
        visited.add(initialState);

        while (!queue.isEmpty()) {
            State current = queue.poll();

            // Check if we reached our target in either jug
            if (current.jug1 == target || current.jug2 == target) {
                return buildPath(current);
            }

            for (State nextState : getNextStates(current, cap1, cap2)) {
                if (!visited.contains(nextState)) {
                    visited.add(nextState);
                    queue.offer(nextState);
                }
            }
        }

        return Collections.emptyList();
    }

    private static List<State> getNextStates(State curr, int cap1, int cap2) {
        List<State> nextStates = new ArrayList<>();

        // 1. Fill Jug 1
        nextStates.add(new State(cap1, curr.jug2, curr, "Fill Jug 1"));
        // 2. Fill Jug 2
        nextStates.add(new State(curr.jug1, cap2, curr, "Fill Jug 2"));
        // 3. Empty Jug 1
        nextStates.add(new State(0, curr.jug2, curr, "Empty Jug 1"));
        // 4. Empty Jug 2
        nextStates.add(new State(curr.jug1, 0, curr, "Empty Jug 2"));

        // 5. Pour Jug 1 -> Jug 2
        int pour1To2 = Math.min(curr.jug1, cap2 - curr.jug2);
        nextStates.add(new State(curr.jug1 - pour1To2, curr.jug2 + pour1To2, curr, "Pour Jug 1 -> Jug 2"));

        // 6. Pour Jug 2 -> Jug 1
        int pour2To1 = Math.min(curr.jug2, cap1 - curr.jug1);
        nextStates.add(new State(curr.jug1 + pour2To1, curr.jug2 - pour2To1, curr, "Pour Jug 2 -> Jug 1"));

        return nextStates;
    }

    private static List<State> buildPath(State state) {
        List<State> path = new ArrayList<>();
        State curr = state;
        while (curr != null) {
            path.add(curr);
            curr = curr.parent;
        }
        Collections.reverse(path);
        return path;
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        int jug1Cap = 5;
        int jug2Cap = 3;
        int target = 4;

        System.out.println("Solving for Jug1=" + jug1Cap + ", Jug2=" + jug2Cap + ", Target=" + target);
        List<State> solution = solve(jug1Cap, jug2Cap, target);

        if (solution.isEmpty()) {
            System.out.println("No solution possible.");
        } else {
            for (int i = 0; i < solution.size(); i++) {
                System.out.println("Step " + i + ": " + solution.get(i));
            }
        }
    }
}

Code Walkthrough

Let's trace how our code solves the 5-quart and 3-quart problem to reach exactly 4 quarts:

1. We start at [0, 0].
2. We fill the 5-quart jug: [5, 0].
3. We pour the 5-quart jug into the 3-quart jug: [2, 3] (since the 3-quart jug can only hold 3 quarts, 2 quarts remain in the 5-quart jug).
4. We empty the 3-quart jug: [2, 0].
5. We pour the remaining 2 quarts from the 5-quart jug into the 3-quart jug: [0, 2].
6. We fill the 5-quart jug again: [5, 2].
7. We pour from the 5-quart jug into the 3-quart jug until the 3-quart jug is full. Since it already has 2 quarts, it only takes 1 quart: [4, 3].
8. Success! The 5-quart jug now contains exactly 4 quarts of water.

Time & Space Complexity

Analyzing complexity for state-space searches requires looking at the size of the state space.

• Time Complexity: $\mathcal{O}(C_1 \times C_2)$, where $C_1$ and $C_2$ are the capacities of the two jugs. In the worst case, we might have to visit every possible combination of water levels. Since the levels are integers bounded by the capacities, the total number of unique states is at most $(C_1 + 1) \times (C_2 + 1)$. For each state, we perform $\mathcal{O}(1)$ work to generate transitions.
• Space Complexity: $\mathcal{O}(C_1 \times C_2)$. We store visited states in a hash set and active states in our BFS queue. The maximum size of these structures is proportional to the total number of unique states.

Why This Problem Matters (The Senior Perspective)

As senior engineers, we must look beyond the immediate puzzle. Why does this matter in real-world software design?

This problem is a textbook example of a Finite State Machine (FSM) and State-Space Search. In production, you will encounter this pattern in several domains:

• Workflow Engines: Systems like Temporal or AWS Step Functions transition through discrete states based on external events. Ensuring that a workflow cannot enter an invalid state or an infinite loop uses the exact same cycle-detection and validation logic we implemented here.
• Transaction Rollbacks and Sagas: When executing distributed transactions, if a step fails, you must transition backward or execute compensating actions. Modeling these transitions as a directed graph allows you to find the safest recovery path.
• Network Routing and Game AI: Finding the shortest path of actions to achieve a goal state is the foundation of routing protocols and decision-making agents.

Final Thoughts

We took a classic brain teaser, stripped away its physical disguise, and modeled it as a clean, mathematical graph search. By applying BFS, we guaranteed finding the most efficient sequence of steps while avoiding infinite loops through state tracking.

Can you think of how you would modify this algorithm to support three or more jugs? How would the state representation change? Let us know your thoughts in the comments below!

Until next time, keep coding, keep learning, and let's keep cracking these challenges together.