Uber: Back-to-Back Trips Starting in the Last Drop Zone
Dispatch tries to give a driver their next trip close to where the last one ended, cutting the empty kilometres.
- Difficulty: Medium
- Topics: Window Functions, Dates, Conditional Logic
- Dialect: MySQL
- Problem: #990
Problem statement
Dispatch tries to give a driver their next trip close to where the last one ended, cutting the empty kilometres. The marketplace team measures how often that works.
Take each driver's trips in order of pickup_at. A trip is chained when the driver's previous trip dropped off in the zone where this trip picks up, and this pickup came at most 15 minutes (900 seconds) after that drop-off. A driver's first trip is never chained. For every driver return driver_id, trips and chained_trips, ordered by chained_trips descending, then driver_id.
A practice scenario set at Uber: the tables and data are invented, and this is not a question from, or endorsed by, Uber.
Tables
Table: DriverTrip
| Column | Type |
|---|---|
| trip_id | int |
| driver_id | int |
| pickup_zone | varchar |
| drop_zone | varchar |
| pickup_at | datetime |
| dropoff_at | datetime |
Primary key: trip_id.
One row per completed trip. A driver's trips never overlap, so no two of them share a pickup_at.
Examples
Example 1
DriverTrip
| trip_id | driver_id | pickup_zone | drop_zone | pickup_at | dropoff_at |
|---|---|---|---|---|---|
| 1 | 1 | Koramangala | Indiranagar | 2024-09-05 08:00:00 | 2024-09-05 08:25:00 |
| 2 | 1 | Indiranagar | MG Road | 2024-09-05 08:35:00 | 2024-09-05 08:55:00 |
| 3 | 1 | MG Road | Whitefield | 2024-09-05 09:10:00 | 2024-09-05 09:50:00 |
| 4 | 1 | HSR Layout | Koramangala | 2024-09-05 10:00:00 | 2024-09-05 10:20:00 |
| 5 | 2 | Airport | Whitefield | 2024-09-05 06:00:00 | 2024-09-05 06:50:00 |
| 6 | 2 | Whitefield | Airport | 2024-09-05 07:06:00 | 2024-09-05 07:50:00 |
| 7 | 3 | MG Road | HSR Layout | 2024-09-05 11:00:00 | 2024-09-05 11:30:00 |
Output
| driver_id | trips | chained_trips |
|---|---|---|
| 1 | 4 | 2 |
| 2 | 2 | 0 |
| 3 | 1 | 0 |
How to solve Uber: Back-to-Back Trips Starting in the Last Drop Zone
The rule compares each trip with the previous trip of the same driver, which is what LAG is for. Partitioned by driver and ordered by pickup_at, LAG(drop_zone) and LAG(dropoff_at) put the last trip's end zone and end time on the current row.
A trip is chained when both conditions hold: its pickup zone equals the previous drop zone, and TIMESTAMPDIFF(SECOND, prev_dropoff_at, pickup_at) is at most 900. The bound is inclusive, so trip 3 — picked up exactly 15 minutes after trip 2 dropped off at MG Road — is chained, while driver 2's second trip, 16 minutes later, is not. Trip 4 is quick but starts in another zone. On a first trip both LAG values are NULL, the comparisons are unknown, and the CASE falls to 0; the trip still counts in COUNT(*).
The alternative finds the previous trip without window functions: a self join on earlier trips of the same driver, with NOT EXISTS ruling out any trip in between, plus the zone and time conditions in the ON clause; COUNT(p.trip_id) then counts the trips that found a chaining predecessor. The window version is one sort per driver; the join version is quadratic, which is why LAG is the tool of choice here.
Reference solution (MySQL)
WITH seq AS (
SELECT driver_id, pickup_zone, pickup_at,
LAG(drop_zone) OVER (PARTITION BY driver_id ORDER BY pickup_at) AS prev_drop_zone,
LAG(dropoff_at) OVER (PARTITION BY driver_id ORDER BY pickup_at) AS prev_dropoff_at
FROM DriverTrip
)
SELECT driver_id, COUNT(*) AS trips,
SUM(CASE WHEN pickup_zone = prev_drop_zone
AND TIMESTAMPDIFF(SECOND, prev_dropoff_at, pickup_at) <= 900 THEN 1 ELSE 0 END) AS chained_trips
FROM seq
GROUP BY driver_id
ORDER BY chained_trips DESC, driver_idAnother way
SELECT t.driver_id, COUNT(*) AS trips, COUNT(p.trip_id) AS chained_trips
FROM DriverTrip t
LEFT JOIN DriverTrip p
ON p.driver_id = t.driver_id
AND p.pickup_at < t.pickup_at
AND NOT EXISTS (SELECT 1 FROM DriverTrip m WHERE m.driver_id = t.driver_id AND m.pickup_at > p.pickup_at AND m.pickup_at < t.pickup_at)
AND p.drop_zone = t.pickup_zone
AND t.pickup_at <= DATE_ADD(p.dropoff_at, INTERVAL 15 MINUTE)
GROUP BY t.driver_id
ORDER BY chained_trips DESC, t.driver_id← Uber: UberX Share Requests Matched With a Co-Rider · Uber: Fleet Vehicles on Two Drivers' Shifts at Once →