Amazon: Route Stops Delivered Out of the Planned Order

Medium
587.

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.

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

ColumnType
route_idvarchar
stop_seqint
delivered_atdatetime

Primary key (together): 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.

Example

The rows may come back in any order; the columns must be the ones shown, in that order.

RouteStop

route_idstop_seqdelivered_at
DBL1-A12025-05-12 09:05:00
DBL1-A22025-05-12 09:40:00
DBL1-A32025-05-12 09:20:00
DBL1-A42025-05-12 10:00:00
DBL1-B12025-05-12 09:10:00
DBL1-B2NULL
DBL1-B32025-05-12 09:50:00
DHY2-C12025-05-12 11:00:00
DHY2-C2NULL
DHY2-C32025-05-12 10:30:00

Output

route_idout_of_order
DBL1-A2
DHY2-C2
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: 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

ColumnType
route_idvarchar
stop_seqint
delivered_atdatetime

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_idstop_seqdelivered_at
DBL1-A12025-05-12 09:05:00
DBL1-A22025-05-12 09:40:00
DBL1-A32025-05-12 09:20:00
DBL1-A42025-05-12 10:00:00
DBL1-B12025-05-12 09:10:00
DBL1-B2NULL
DBL1-B32025-05-12 09:50:00
DHY2-C12025-05-12 11:00:00
DHY2-C2NULL
DHY2-C32025-05-12 10:30:00

Output

route_idout_of_order
DBL1-A2
DHY2-C2

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_id

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