808. Soup Servings

This problem is a favorite at companies like Google and Amazon for testing probabilistic thinking combined with dynamic programming optimization. At first glance, it looks like a complex probability tree problem, but the key to solving this problem is to recognize that soup A depletes faster than soup B, leading to a convergence pattern that allows us to avoid computing exact probabilities for large inputs.

This problem evaluates your ability to handle probabilities in recursive states and your observation skills for edge cases.

Problem statement

We have two soups, soup A and soup B, each starting with n mL. We need to serve these soups following a specific process.

The serving process:

At each turn, we randomly choose one of four serving operations. Each operation has an equal probability of 0.25 (25%) of being selected:

1. Serve 100 mL from soup A and 0 mL from soup B
2. Serve 75 mL from soup A and 25 mL from soup B
3. Serve 50 mL from soup A and 50 mL from soup B
4. Serve 25 mL from soup A and 75 mL from soup B

Notice that soup A is always served in larger or equal amounts compared to soup B in each operation. This means soup A tends to empty faster than soup B.

Important rules:

• If an operation requires more soup than what remains, we serve all the remaining soup of that type. For example, if we have 30 mL of soup A left and operation 1 is selected (which asks for 100 mL), we serve all 30 mL.
• The serving process stops immediately after any turn in which soup A becomes empty, soup B becomes empty, or both soups become empty simultaneously.
• We continue this process turn by turn, randomly selecting an operation each time, until at least one soup is completely empty.

What you need to calculate:

Your task is to return the probability that soup A will be empty first, plus half the probability that soup A and soup B become empty at the same time.

In other words, calculate:

• P(A empties first) + 0.5 × P(A and B empty simultaneously)

Answers within 10⁻⁵ of the actual answer are considered correct.

Constraints:

• 0 <= n <= 10⁹

Examples

Intuition

The key mental model is that every move reduces A by at least as much as B, on average. That means as n grows, it becomes increasingly likely that A empties first. The problem is asking for a weighted probability:

• If A empties first, contribute 1
• If B empties first, contribute 0
• If both empty together, contribute 0.5

So each state (a, b) has a single value: the expected score starting from those remaining amounts.

Naive approach using recursion

The logic: From a given state (a, b) (the remaining soup in A and B), we try all four serving operations. Each operation moves us to a smaller subproblem, and we keep branching until we hit a stopping condition:

• a <= 0 and b > 0 → A emptied first, return 1.
• b <= 0 and a > 0 → B emptied first, return 0.
• a <= 0 and b <= 0 → both emptied together, return 0.5.

As each operation is chosen with probability 0.25, the recursive function would return the average of the four recursive results.
The drawback: The recursion tree explodes because the same (a, b) pairs occur through many paths. This creates heavily overlapping subproblems, making the brute-force approach infeasible even for moderate n.

This creates a 4-way branching tree. After t turns, there can be up to 4^t paths. Many of those paths reach the same remaining amounts (a, b) in different ways, so the recursion keeps recomputing the same states repeatedly. That overlap is exactly what makes this approach slow.

This approach also results in the two following practical issues:

• Time blow-up: Exponential branching makes the runtime explode even when n is not that large.
• State granularity: If you track soup in milliliters, the number of possible (a, b) states is massive, so even caching becomes unrealistic unless you scale down to 25 mL units.

This is why we need memoization plus scaling; otherwise, the recursion is doing the same work over and over.

Optimized approach using Dynamic Programming

This is the interview “gold standard” because we turn a probabilistic process into a small memoized DP by scaling amounts into 25 mL units.

Scale the problem

All pours are multiples of 25 mL, which means we never need to track every single milliliter. We can compress the state space by converting the problem into 25 mL units.

First, define:

• N = ceil(n / 25)
• Treat 1 unit = 25 mL

So if n = 50, then N = 2. If n = 51, then N = 3 (because we round up). Now rewrite each serving operation (soup A, soup B) in units:

• Pour (100, 0) mL becomes (4, 0) units
• Pour (75, 25) mL becomes (3, 1) units
• Pour (50, 50) mL becomes (2, 2) units
• Pour (25, 75) mL becomes (1, 3) units

At this point, each DP state is just: dp(a, b) = the expected final score starting from a units of A and b units of B. Where the score is:

• 1.0 if A empties first
• 0.0 if B empties first
• 0.5 if both empty on the same turn

Base cases

These encode exactly how the process ends:

• If a <= 0 and b <= 0, return 0.5. Both soups are empty after the same turn, so we take half credit.
• If a <= 0 and b > 0 return 1.0. Soup A is empty first, so this path contributes fully.
• If b <= 0 and a > 0 return 0. Soup B is empty first, so this path contributes nothing.

These base cases also correctly handle over-pouring. If a move would reduce a soup below zero, we treat that as empty, which is why we check <= 0.

Transition (Recurrence)

From a state (a, b), we take one random operation, each with probability 0.25, and move to a smaller state:

dp(a, b) = 0.25 x (dp(a-4, b) + dp(a-3, b-1) + dp(a-2, b-2) + dp(a-1, b-3))

Interpretation:

• Each term corresponds to one serving option.
• We average them because all options are equally likely.
• Every recursive call reduces at least one of a or b, so we are guaranteed to eventually hit a base case.

This scaling step is what turns a problem that looks unbounded in raw milliliters into a DP with a limited number of states.

Large-n shortcut

For large n, the answer becomes extremely close to 1.0. For this problem, once n >= 4800, returning 1.0 is already accurate within 10-5, so we can skip the DP and avoid extra work.

Step-by-step algorithm

This algorithm is implemented as follows:

Recursive helper function dp(a, b) with memoization( @lru_cache(maxsize=None)): This function computes the probability from state (a, b) where a and b represent remaining units of soup A and B respectively:

1. If a is less than or equal to 0 and b is less than or equal to 0,
   1. Return 0.5
2. If a is less than or equal to 0,
   1. Return 1.0
3. if b is less than or equal to 0,
   1. Return 0.0
4. If neither soup is empty yet, one random operation happens next. Calculate the probability by averaging the results of all four equally likely serving operations and multiply the sum of all four results by 0.25 (since each operation has probability 0.25).:
   1. Operation 1: Pour (4, 0) units, call dp(a - 4, b) to get the probability from the new state.
   2. Operation 2: Pour (3, 1) units, call dp(a - 3, b - 1) to get the probability from the new state.
   3. Operation 3: Pour (2, 2) units, call dp(a - 2, b - 2) to get the probability from the new state.
   4. Operation 4: Pour (1, 3) units, call dp(a - 1, b - 3) to get the probability from the new state.
5. Return the computed probability, which is automatically cached by lru_cache for this state (a, b).

Mian method soup_servings(n): This function calculates the probability that soup A empties first plus half the probability that both soups empty simultaneously by performing the following operations:

1. If n == 0, both soups are already empty, so return 0.5.
2. If n is greater than or equal to 4800, return 1.0.
3. Convert the soup quantity into 25 mL units using: N = ceil(n / 25).
4. Call dp(N, N) with the initial state where both soups have N units and return the result.

Let’s look at the following illustration to better understand the solution.

1 / 7

Code implementation

Let’s look at the following code to understand its implementation.

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(a, b):
    # Base cases
    if a <= 0 and b <= 0:
        return 0.5
    if a <= 0:
        return 1.0
    if b <= 0:
        return 0.0
    # Four equally likely operations in unit space:
    # (4,0), (3,1), (2,2), (1,3)
    
    return 0.25 * (
        dp(a - 4, b) +
        dp(a - 3, b - 1) +
        dp(a - 2, b - 2) +
        dp(a - 1, b - 3)
    )
        
def soupServings(n):
    # Both are empty immediately
    if n == 0:
        return 0.5
    # For very large n, the probability approaches 1 quickly.
    # 4800 is a commonly used cutoff that stays within 1e-5 tolerance.
    if n >= 4800:
        return 1.0

    # Convert to 25 mL units (ceiling division)
    N = (n + 24) // 25

    return dp(N, N)

def main():
    tests = [
        0,      # both empty
        50,     # example 1
        100,    # example 2
        660,    # mid-range
        10000,  # triggers large-n shortcut
    ]
    for i, n in enumerate(tests, 1):
        result = f"{soupServings(n):.5f}"
        print(f"{i}. \t Input: {n}")
        print(f" \t Output: {result}")
        print("-"*75)

if __name__ == "__main__":
    main()

Time complexity

The algorithm’s time complexity is O(N²), because after converting to 25 mL units (N = ceil(n / 25)), the DP can visit up to N × N distinct states, and each state does constant work to average four transitions.

Space complexity

The algorithm’s space complexity is O(N²), because memoization cache stores one value per (a, b) state., which in the worst case stores up to N × N values.

Common pitfalls and interview tips

1. Forgetting the 0.5 case when both empty together: If you return 1 or 0 there, the result is consistently off.
2. Not scaling by 25 mL units: Working in raw milliliters makes the state space too large and the DP too slow.
3. Missing the large-n cutoff: With n up to 109, you need the convergence shortcut, otherwise you waste time and memory.