Uber: Trip Event Logs That Break the State Machine
Every trip moves through states — requested, accepted, arrived, started, completed, or cancelled along the way — and the app logs one event per state.
- Difficulty: Hard
- Topics: Window Functions, Joins, Subqueries
- Dialect: MySQL
- Problem: #996
Problem statement
Every trip moves through states — requested, accepted, arrived, started, completed, or cancelled along the way — and the app logs one event per state. A trip whose log skips or reverses a state points to a client bug or a lost event, so the data-quality team audits the logs against the allowed moves in AllowedStep.
Read each trip's events in order of event_at. Every consecutive pair of events is a step from the earlier event_type to the later one; the trip's first event is a step from 'start'. A step is invalid when (from_state, to_state) is not a row of AllowedStep. For every trip with at least one invalid step, return its first invalid step: trip_id, from_state, to_state and broken_at (the event_at of the step's later event). Order by trip_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: TripEvent
| Column | Type |
|---|---|
| event_id | int |
| trip_id | int |
| event_type | varchar |
| event_at | datetime |
Primary key: event_id.
One row per logged state change, event_type in lower case. No trip has two events at the same second.
Table: AllowedStep
| Column | Type |
|---|---|
| from_state | varchar |
| to_state | varchar |
Primary key: from_state, to_state.
Every allowed move; 'start' stands for "before the first event".
Examples
Example 1
TripEvent
| event_id | trip_id | event_type | event_at |
|---|---|---|---|
| 1 | 1 | requested | 2024-10-11 08:00:00 |
| 2 | 1 | accepted | 2024-10-11 08:00:30 |
| 3 | 1 | arrived | 2024-10-11 08:06:00 |
| 4 | 1 | started | 2024-10-11 08:07:00 |
| 5 | 1 | completed | 2024-10-11 08:30:00 |
| 6 | 2 | requested | 2024-10-11 09:00:00 |
| 7 | 2 | arrived | 2024-10-11 09:08:00 |
| 8 | 2 | started | 2024-10-11 09:09:00 |
| 9 | 3 | requested | 2024-10-11 09:30:00 |
| 10 | 3 | accepted | 2024-10-11 09:31:00 |
| 11 | 3 | cancelled | 2024-10-11 09:33:00 |
| 12 | 3 | accepted | 2024-10-11 09:35:00 |
| 13 | 4 | accepted | 2024-10-11 10:00:00 |
| 14 | 4 | arrived | 2024-10-11 10:05:00 |
| 15 | 5 | requested | 2024-10-11 10:30:00 |
| 16 | 5 | cancelled | 2024-10-11 10:31:00 |
| 17 | 6 | requested | 2024-10-11 11:00:00 |
| 18 | 6 | accepted | 2024-10-11 11:01:00 |
| 19 | 6 | started | 2024-10-11 11:06:00 |
| 20 | 6 | arrived | 2024-10-11 11:07:00 |
| 21 | 6 | completed | 2024-10-11 11:25:00 |
AllowedStep
| from_state | to_state |
|---|---|
| start | requested |
| requested | accepted |
| requested | cancelled |
| accepted | arrived |
| accepted | cancelled |
| arrived | started |
| arrived | cancelled |
| started | completed |
Output
| trip_id | from_state | to_state | broken_at |
|---|---|---|---|
| 2 | requested | arrived | 2024-10-11 09:08:00 |
| 3 | cancelled | accepted | 2024-10-11 09:35:00 |
| 4 | start | accepted | 2024-10-11 10:00:00 |
| 6 | accepted | started | 2024-10-11 11:06:00 |
How to solve Uber: Trip Event Logs That Break the State Machine
The audit compares the log with a state machine stored as data, so the work is to put the log in the same shape as AllowedStep — pairs of (from, to) — and look for pairs the table does not contain.
Steps. LAG(event_type, 1, 'start') OVER (PARTITION BY trip_id ORDER BY event_at) places each event next to the previous event of the same trip. Its third argument is the default for the first row, so the first event becomes a step from 'start'. That is how trip 4, whose log opens with accepted, is caught: ('start', 'accepted') is not an allowed move.
Invalid steps. A LEFT JOIN to AllowedStep on both columns, keeping rows where the join found nothing, is the anti join. Trip 2 skips accepted (requested → arrived); trip 3 comes back to life after a cancellation (cancelled → accepted); trip 6 starts before arriving and then arrives after starting — two invalid steps.
First one. ROW_NUMBER() per trip over the invalid steps, ordered by time, keeps only the earliest, so trip 6 reports accepted → started. Trips 1 and 5 have no invalid step and do not appear.
The alternative finds each previous event with a correlated ORDER BY … LIMIT 1 subquery, uses NOT EXISTS for the anti join, and keeps the invalid step whose time is the trip's minimum. Keeping the rules in a table rather than in a long CASE means a new state needs a new row, not a new query.
Reference solution (MySQL)
WITH steps AS (
SELECT trip_id, event_at,
LAG(event_type, 1, 'start') OVER (PARTITION BY trip_id ORDER BY event_at) AS from_state,
event_type AS to_state
FROM TripEvent
), bad AS (
SELECT s.trip_id, s.from_state, s.to_state, s.event_at,
ROW_NUMBER() OVER (PARTITION BY s.trip_id ORDER BY s.event_at) AS rn
FROM steps s
LEFT JOIN AllowedStep a ON a.from_state = s.from_state AND a.to_state = s.to_state
WHERE a.from_state IS NULL
)
SELECT trip_id, from_state, to_state, event_at AS broken_at
FROM bad
WHERE rn = 1
ORDER BY trip_idAnother way
WITH steps AS (
SELECT e.trip_id, e.event_at, e.event_type AS to_state,
COALESCE((SELECT p.event_type FROM TripEvent p
WHERE p.trip_id = e.trip_id AND p.event_at < e.event_at
ORDER BY p.event_at DESC LIMIT 1), 'start') AS from_state
FROM TripEvent e
), bad AS (
SELECT * FROM steps s
WHERE NOT EXISTS (SELECT 1 FROM AllowedStep a WHERE a.from_state = s.from_state AND a.to_state = s.to_state)
)
SELECT b.trip_id, b.from_state, b.to_state, b.event_at AS broken_at
FROM bad b
WHERE b.event_at = (SELECT MIN(x.event_at) FROM bad x WHERE x.trip_id = b.trip_id)
ORDER BY b.trip_id← Uber: Freight Lane Rates Spiking Over the 28-Day Average · Uber: Which Promo Gets Credit for a Rider's First Trip →