Amazon: Route Stops Delivered Out of the Planned Order
Route planners give each delivery route a stop sequence. The last-mile analytics team wants to know how often drivers deviate from it.
- Difficulty: Medium
- Topics: Window Functions, Aggregation
- Dialect: MySQL
- Problem: #587
Problem statement
Route planners give each delivery route a stop sequence. The last-mile analytics team wants to know how often drivers deviate from it.
Consider only the delivered stops of a route (delivered_at not NULL). A delivered stop is out of order when its position among the route's delivered stops by stop_seq differs from its position by delivered_at. Return route_id and out_of_order (the number of such stops) for every route with at least one; any order.
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: RouteStop
| Column | Type |
|---|---|
| route_id | varchar |
| stop_seq | int |
| delivered_at | datetime |
Primary key: route_id, stop_seq.
One row per planned stop; delivered_at is NULL when the stop was not delivered. No two stops of a route are delivered at the same moment.
Examples
Example 1
RouteStop
| route_id | stop_seq | delivered_at |
|---|---|---|
| DBL1-A | 1 | 2025-05-12 09:05:00 |
| DBL1-A | 2 | 2025-05-12 09:40:00 |
| DBL1-A | 3 | 2025-05-12 09:20:00 |
| DBL1-A | 4 | 2025-05-12 10:00:00 |
| DBL1-B | 1 | 2025-05-12 09:10:00 |
| DBL1-B | 2 | NULL |
| DBL1-B | 3 | 2025-05-12 09:50:00 |
| DHY2-C | 1 | 2025-05-12 11:00:00 |
| DHY2-C | 2 | NULL |
| DHY2-C | 3 | 2025-05-12 10:30:00 |
Output
| route_id | out_of_order |
|---|---|
| DBL1-A | 2 |
| DHY2-C | 2 |
How to solve Amazon: Route Stops Delivered Out of the Planned Order
A stop's planned position and actual position are two rankings of the same rows under different orders. ROW_NUMBER() OVER (PARTITION BY route_id ORDER BY stop_seq) numbers the delivered stops by plan, and the same function ordered by delivered_at numbers them by time; a stop is out of order exactly where the two numbers differ. Counting those per route and grouping gives the answer, and routes with no deviation form no group.
Undelivered stops are removed before numbering. If they stayed, a skipped stop would push every later stop's planned position up by one while not appearing in the delivery order at all, flagging stops the driver actually took in sequence. Because delivery times are distinct within a route, the time ordering is total and the numbering deterministic.
The alternative computes each position as a count — delivered stops with a sequence number at or below this one, and stops delivered at or before this one (a NULL time never satisfies <=). That is the definition of a row number spelled out with correlated subqueries; it is quadratic per route, whereas the window version sorts each route twice.
Reference solution (MySQL)
WITH d AS (
SELECT route_id,
ROW_NUMBER() OVER (PARTITION BY route_id ORDER BY stop_seq) AS planned_pos,
ROW_NUMBER() OVER (PARTITION BY route_id ORDER BY delivered_at) AS actual_pos
FROM RouteStop
WHERE delivered_at IS NOT NULL
)
SELECT route_id, COUNT(*) AS out_of_order
FROM d
WHERE planned_pos <> actual_pos
GROUP BY route_idAnother way
SELECT s.route_id, COUNT(*) AS out_of_order FROM RouteStop s
WHERE s.delivered_at IS NOT NULL
AND (SELECT COUNT(*) FROM RouteStop t WHERE t.route_id = s.route_id AND t.delivered_at IS NOT NULL AND t.stop_seq <= s.stop_seq)
<> (SELECT COUNT(*) FROM RouteStop t WHERE t.route_id = s.route_id AND t.delivered_at <= s.delivered_at)
GROUP BY s.route_id← Amazon: Savings Plan Coverage of Each AWS Account · Amazon: Prime Day Deals Not Below the 30-Day Low Price →