Amazon: Straight-Line Distance Driven on Each Delivery Route
Last-mile planners estimate a route's length from its stops' coordinates before real road data comes in.
- Difficulty: Medium
- Topics: Window Functions, Aggregation
- Dialect: MySQL
- Problem: #590
Problem statement
Last-mile planners estimate a route's length from its stops' coordinates before real road data comes in. Each route starts at the delivery station, at the origin (0, 0), and visits its stops in increasing stop_seq (sequence numbers may have gaps); the van does not return to the station.
For every route, return route_id and distance_km: the sum of the straight-line distances from the station to the first stop and between each pair of consecutive stops, rounded to 2 decimals. Return the rows in 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: DeliveryStop
| Column | Type |
|---|---|
| route_id | varchar |
| stop_seq | int |
| x_km | int |
| y_km | int |
Primary key: route_id, stop_seq.
One row per stop; x_km and y_km are the stop's position in kilometres east and north of the station.
Examples
Example 1
DeliveryStop
| route_id | stop_seq | x_km | y_km |
|---|---|---|---|
| DBL1-A | 1 | 3 | 4 |
| DBL1-A | 2 | 3 | 0 |
| DBL1-A | 5 | 0 | 0 |
| DBL1-B | 10 | -2 | 1 |
| DBL1-B | 20 | 1 | 5 |
| DHY2-C | 3 | 6 | 8 |
Output
| route_id | distance_km |
|---|---|
| DBL1-A | 12 |
| DBL1-B | 7.24 |
| DHY2-C | 10 |
How to solve Amazon: Straight-Line Distance Driven on Each Delivery Route
A route's length is the sum of its legs, and each leg runs from one stop to the stop before it. LAG(x_km, 1, 0) and LAG(y_km, 1, 0) over PARTITION BY route_id ORDER BY stop_seq put the previous stop's coordinates on each row; the third argument supplies 0 when there is no previous row, which is exactly the station at the origin, so the first leg needs no special case.
Each leg's length is the Euclidean distance SQRT(dx² + dy²), summed per route and rounded once at the end — rounding every leg first would make the total drift. Because the window orders by stop_seq rather than assuming consecutive numbers, gaps in the sequence are harmless; a join on stop_seq = prev + 1 would silently drop legs. A one-stop route is just the distance from the station.
The alternative finds the previous stop with correlated subqueries (ORDER BY stop_seq DESC LIMIT 1 among the lower sequence numbers) and defaults to the origin with COALESCE; it squares with POW. It reads the route once per stop, whereas LAG needs one sort per route.
Reference solution (MySQL)
WITH legs AS (
SELECT route_id, x_km, y_km,
LAG(x_km, 1, 0) OVER (PARTITION BY route_id ORDER BY stop_seq) AS px,
LAG(y_km, 1, 0) OVER (PARTITION BY route_id ORDER BY stop_seq) AS py
FROM DeliveryStop
)
SELECT route_id,
ROUND(SUM(SQRT((x_km - px) * (x_km - px) + (y_km - py) * (y_km - py))), 2) AS distance_km
FROM legs
GROUP BY route_idAnother way
SELECT route_id, ROUND(SUM(SQRT(POW(x_km - px, 2) + POW(y_km - py, 2))), 2) AS distance_km FROM (
SELECT s.route_id, s.x_km, s.y_km,
COALESCE((SELECT p.x_km FROM DeliveryStop p WHERE p.route_id = s.route_id AND p.stop_seq < s.stop_seq ORDER BY p.stop_seq DESC LIMIT 1), 0) AS px,
COALESCE((SELECT p.y_km FROM DeliveryStop p WHERE p.route_id = s.route_id AND p.stop_seq < s.stop_seq ORDER BY p.stop_seq DESC LIMIT 1), 0) AS py
FROM DeliveryStop s) t
GROUP BY route_id← Amazon: Referral and FBA Fees per Seller for October · Amazon: Clearing Price of Each Sponsored Products Auction →