Amazon: Packing Station Backlog Carried Hour to Hour

Hard
597.

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. 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

ColumnType
station_idvarchar
slotint
arrivalsint
capacityint

Primary key (together): station_id, slot.

One row per station per hour of a shift; slot 1 is the shift's first hour.

Example

The rows must come back in the order shown.

PackingHour

station_idslotarrivalscapacity
PK-011120100
PK-01290100
PK-01340100
PK-014150100
PK-015100100
PK-0216080
PK-02213080
PK-0238080

Output

station_idslotbacklog
PK-01120
PK-01210
PK-0130
PK-01450
PK-01550
PK-0210
PK-02250
PK-02350
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

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

ColumnType
station_idvarchar
slotint
arrivalsint
capacityint

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_idslotarrivalscapacity
PK-011120100
PK-01290100
PK-01340100
PK-014150100
PK-015100100
PK-0216080
PK-02213080
PK-0238080

Output

station_idslotbacklog
PK-01120
PK-01210
PK-0130
PK-01450
PK-01550
PK-0210
PK-02250
PK-02350

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, slot

Another 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 →