Amazon: Packing Station Backlog Carried Hour to Hour
Each hour, orders arrive at a fulfilment centre's packing station and the station can pack up to its capacity that hour.
- Difficulty: Hard
- Topics: Window Functions, Subqueries
- Dialect: MySQL
- Problem: #597
Problem statement
Each hour, orders arrive at a fulfilment centre's packing station and the station can pack up to its capacity that hour. Orders not packed wait in a backlog for the next hour. Spare capacity cannot be banked: when the station empties its backlog, the backlog is 0, never negative.
So the backlog at the end of an hour is previous backlog + arrivals − capacity, or 0 if that is negative; before the first slot the backlog is 0. Every station has a row for each slot from 1 up to its last, with no gaps. Return station_id, slot and backlog for every row, ordered by station_id, then slot.
A practice scenario set at Amazon: the tables and data are invented, and this is not a question from, or endorsed by, Amazon.
Tables
Table: PackingHour
| Column | Type |
|---|---|
| station_id | varchar |
| slot | int |
| arrivals | int |
| capacity | int |
Primary key: station_id, slot.
One row per station per hour of a shift; slot 1 is the shift's first hour.
Examples
Example 1
PackingHour
| station_id | slot | arrivals | capacity |
|---|---|---|---|
| PK-01 | 1 | 120 | 100 |
| PK-01 | 2 | 90 | 100 |
| PK-01 | 3 | 40 | 100 |
| PK-01 | 4 | 150 | 100 |
| PK-01 | 5 | 100 | 100 |
| PK-02 | 1 | 60 | 80 |
| PK-02 | 2 | 130 | 80 |
| PK-02 | 3 | 80 | 80 |
Output
| station_id | slot | backlog |
|---|---|---|
| PK-01 | 1 | 20 |
| PK-01 | 2 | 10 |
| PK-01 | 3 | 0 |
| PK-01 | 4 | 50 |
| PK-01 | 5 | 50 |
| PK-02 | 1 | 0 |
| PK-02 | 2 | 50 |
| PK-02 | 3 | 50 |
How to solve Amazon: Packing Station Backlog Carried Hour to Hour
If spare capacity could be banked, the backlog would be a running sum of arrivals − capacity. It cannot: an hour with idle capacity empties the queue to 0 and the rest of that capacity is lost, so the next hour starts from 0, not from a negative number. That clamp makes each hour depend on the previous hour's result, which a plain running sum cannot express.
A recursive CTE follows the definition literally. The anchor computes slot 1 from a backlog of 0; the recursive member joins each computed row to the same station's next slot (h.slot = q.slot + 1, which is safe because slots have no gaps) and applies GREATEST(previous + arrivals − capacity, 0). The recursion stops when no next slot exists, and all stations advance in parallel.
There is also a closed form, used by the alternative. Let net be the running sum of arrivals − capacity. Each time the clamp fires it discards exactly the amount by which net dips below its previous low, so the backlog is net − min(0, lowest net so far): a running SUM and a running MIN over window frames. This is the queueing recursion known as Lindley's equation. The window form sorts each station once; the recursive form does one join per slot.
Reference solution (MySQL)
WITH RECURSIVE q AS (
SELECT station_id, slot, GREATEST(arrivals - capacity, 0) AS backlog
FROM PackingHour
WHERE slot = 1
UNION ALL
SELECT h.station_id, h.slot, GREATEST(q.backlog + h.arrivals - h.capacity, 0)
FROM q
JOIN PackingHour h ON h.station_id = q.station_id AND h.slot = q.slot + 1
)
SELECT station_id, slot, backlog
FROM q
ORDER BY station_id, slotAnother way
WITH s AS (
SELECT station_id, slot,
SUM(arrivals - capacity) OVER (PARTITION BY station_id ORDER BY slot ROWS UNBOUNDED PRECEDING) AS net
FROM PackingHour
)
SELECT station_id, slot,
net - LEAST(0, MIN(net) OVER (PARTITION BY station_id ORDER BY slot ROWS UNBOUNDED PRECEDING)) AS backlog
FROM s
ORDER BY station_id, slot← Amazon: Suggested Subscribe & Save Cadence From Reorder Gaps · Apple: Genius Bar No-Shows at Every Store →