Amazon: Straight-Line Distance Driven on Each Delivery Route

Medium
590.

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

ColumnType
route_idvarchar
stop_seqint
x_kmint
y_kmint

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

Example

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

DeliveryStop

route_idstop_seqx_kmy_km
DBL1-A134
DBL1-A230
DBL1-A500
DBL1-B10-21
DBL1-B2015
DHY2-C368

Output

route_iddistance_km
DBL1-A12
DBL1-B7.24
DHY2-C10
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: 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

ColumnType
route_idvarchar
stop_seqint
x_kmint
y_kmint

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_idstop_seqx_kmy_km
DBL1-A134
DBL1-A230
DBL1-A500
DBL1-B10-21
DBL1-B2015
DHY2-C368

Output

route_iddistance_km
DBL1-A12
DBL1-B7.24
DHY2-C10

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_id

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