Fuel station queue with three dispensers: Frontier Interview's solution

Question: Fuel station queue with three dispensers

Companies: Tesla

Difficulty: Medium

Problem statement

A fuel station has three dispensers named X, Y and Z. Each starts with a known number of liters. A queue of cars waits at the station, and all of them are in line at time 0. Car i needs demands[i] liters.

Rules:

Only the car at the front of the queue chooses a dispenser. Cars never overtake one another.
The car may use a dispenser only if it is free (not serving a car) and holds at least the car's demand.
If several dispensers qualify, the car takes the first by name: X, then Y, then Z.
If none qualifies right now, the car waits at the front and blocks everyone behind it.
Fuel flows at 1 liter per second, so a car with demand d keeps its dispenser busy for d seconds. A dispenser that finishes at time t can serve the next car at time t.

A car's waiting time is the time it starts refuelling. Implement:

def max_wait(demands: list[int], x: int, y: int, z: int) -> int

Return the longest waiting time over all cars. Return -1 if some car can never refuel.

Constraints: 0 <= len(demands) <= 10^5; 0 <= demands[i], x, y, z <= 10^9.

Example 1: demands = [3, 5, 4, 2], x = 10, y = 5, z = 1 returns 7.

At 0, car 1 takes X (7 liters left, busy until 3). Car 2 takes Y (0 left, busy until 5).
Car 3 needs 4 liters. Only X has enough, so it waits and starts at 3 (3 left, busy until 7).
Car 4 needs 2 liters. Only X has enough, so it starts at 7.

Example 2: demands = [5, 1], x = 5, y = 0, z = 0 returns -1. Car 1 empties X, and no dispenser has fuel for car 2.

Approach

Clarify first. All cars are in the queue at time 0. Fuel flows at one liter per second, so a car with demand D occupies its dispenser for D seconds. Only the car at the front may choose. It takes the first free dispenser, in name order (X, then Y, then Z), that still holds at least D liters. If no free dispenser qualifies, it waits, and it blocks every car behind it. A car's waiting time is the moment it starts refuelling. Return the largest waiting time, or -1 if some car can never be served. Confirm these points out loud: ties by name, strict FIFO (no overtaking), and when a dispenser that frees at time t can be used (at t itself).

Brute force. Step a clock one second at a time. At each tick, release dispensers whose car finished, then let the front car pick if it can. This is correct but costs O(total time), and the total time can be the sum of all demands, which is huge.

Event-driven simulation. Nothing interesting happens between "a dispenser frees up" events, so jump straight to them. Keep, for each dispenser, the liters left and free_at, the time it finishes its current car. For the front car with demand d:

Collect the dispensers with fuel >= d. Fuel only goes down, and nobody else can take fuel while this car blocks the queue, so this set does not change while the car waits.
If the set is empty, the car never refuels. Return -1.
The car starts at start = max(now, min(free_at over the set)). It picks the first dispenser by name in the set with free_at <= start.
Record start as its wait, subtract d from that dispenser, set its free_at = start + d, and set now = start.

Invariants. now never decreases, because a car can't reach the front before the car ahead of it starts. At every step, fuel[i] is what dispenser i will have once its current car finishes. That is the right number to compare against, because the fuel is reserved the moment a car starts.

Why "wait for a busy one" is right. A free dispenser without enough fuel will never gain any. So if only busy dispensers qualify, the car must wait for the earliest of them. If none qualify at all, waiting is useless and the answer is -1.

Code

from __future__ import annotations


def max_wait(demands: list[int], x: int, y: int, z: int) -> int:
    """Longest time any car waits before it starts refuelling, or -1 if some car never can."""
    return simulate(demands, [x, y, z])


def simulate(demands: list[int], fuel: list[int]) -> int:
    fuel = list(fuel)             # remaining liters per dispenser, in name order
    free_at = [0] * len(fuel)     # time each dispenser finishes its current car
    now = 0                       # time the current car reaches the front of the queue
    worst = 0

    for d in demands:
        # Fuel only goes down, so this set is fixed while the car waits.
        able = [i for i, f in enumerate(fuel) if f >= d]
        if not able:
            return -1             # no dispenser will ever have enough
        # Earliest moment one of them is free; ties go to the first name.
        start = max(now, min(free_at[i] for i in able))
        pick = next(i for i in able if free_at[i] <= start)
        worst = max(worst, start)  # every car joins the queue at time 0
        fuel[pick] -= d
        free_at[pick] = start + d  # one liter per second
        now = start               # the next car reaches the front now
    return worst


if __name__ == "__main__":
    # A=X(10->7, busy to 3); B=Y(5->0, to 5); C waits for X at 3; D waits for X at 7.
    assert max_wait([3, 5, 4, 2], 10, 5, 1) == 7
    assert max_wait([], 1, 1, 1) == 0
    assert max_wait([4], 1, 2, 3) == -1
    assert max_wait([2, 2, 2], 6, 0, 0) == 4
    assert max_wait([1, 1, 1], 1, 1, 1) == 0
    assert max_wait([5, 1], 5, 0, 0) == -1
    assert max_wait([3, 3], 3, 3, 0) == 0
    assert max_wait([0, 0], 0, 0, 0) == 0
    # Car 2 skips busy X and takes free Z even though X is first by name.
    assert max_wait([4, 2], 9, 0, 2) == 0
    # Car 3 blocks: only Y can serve it, so car 4 waits too though Z is free.
    assert max_wait([1, 6, 6, 1], 1, 12, 5) == 6
    print("ok")

Complexity

Each car scans the k dispensers a constant number of times. With n cars that is O(n * k) time, which is O(n) for the fixed three dispensers.
Space is O(k) for the fuel and free_at arrays, beyond the input.
The per-second brute force is O(sum of demands * k). It is fine for tiny inputs but times out on demands near 10^9.

Test cases

demands=[3, 5, 4, 2], X=10, Y=5, Z=1 gives 7. Car 1 takes X at 0 (7 left, busy until 3). Car 2 takes Y at 0 (0 left, until 5). Car 3 needs 4, and only X qualifies, so it starts at 3 (3 left, until 7). Car 4 needs 2, and only X qualifies, so it starts at 7.
demands=[1, 6, 6, 1], X=1, Y=12, Z=5 gives 6. Car 3 must wait for Y until 6. Car 4 could use the free Z, but it is stuck behind car 3, so it also starts at 6.
demands=[4, 2], X=9, Y=0, Z=2 gives 0. X is busy, so car 2 takes the free Z even though X comes first by name.
demands=[2, 2, 2], X=6, Y=0, Z=0 gives 4. All three cars share X, one after another.
demands=[5, 1], X=5, Y=0, Z=0 gives -1. After car 1, no dispenser has any fuel for car 2.
demands=[4], X=1, Y=2, Z=3 gives -1. No dispenser ever holds 4 liters.
demands=[1, 1, 1], X=1, Y=1, Z=1 gives 0. Each car gets its own dispenser.
demands=[] gives 0. Also demands=[0, 0] with all dispensers empty gives 0, because a zero demand is always satisfiable.

Follow-ups

Report each car's dispenser or start time. Return the list of (name, start) pairs instead of the maximum. The loop already computes both.
k dispensers and many cars. Linear scans cost O(k) per car. Keep the free dispensers in a sorted structure keyed by fuel, and the busy ones in a min-heap keyed by free_at. Then a car finds the first qualifying free dispenser and the earliest qualifying busy one in O(log k) each. The "first by name" rule needs a segment tree over names that stores the max fuel among free dispensers, so you can descend to the leftmost free one with fuel >= d.
Cars arrive over time. Each car has an arrival time. The front car's start becomes max(arrival, now, earliest qualifying free_at), and its wait is start - arrival. The rest of the loop is the same.
No head-of-line blocking. If any waiting car may take any free dispenser, the simulation needs an event queue of "dispenser frees" events. At each event, scan the waiting cars in order for the first one that fits. Starvation of large-demand cars becomes a real question to discuss.
Different flow rates or refills. With rate r_i per dispenser, the busy time is ceil(d / r_i). With a tanker that refills dispensers at known times, the qualifying set is no longer fixed while a car waits, so you add refill events and recheck at each one.

Interviewer expectations

Mid-level (L4)

Asks how ties, blocking and the "free at time t" edge are handled before coding.
Writes a correct simulation, even a tick-by-tick one, and gets the -1 case right.
Traces one example by hand and checks it against the code.

Senior (L5)

Goes straight to the event-driven version and explains why time can jump to the next free time.
States that the qualifying set is fixed while the car waits, and uses that to detect -1 early.
Covers edge cases without prompting: empty queue, zero demand, a free dispenser that is too empty, a car stuck behind a blocked car.

Staff (L6+)

Generalizes to k dispensers with heaps or a segment tree, and to arrival times, without restructuring the code.
Discusses the policy trade-offs: FIFO fairness against throughput, and starvation if overtaking is allowed.
Separates the policy (which dispenser to pick) from the simulation engine so either can change, and says how they would test it, for example by comparing it with the per-second brute force on random inputs.