Uber: Trip Event Logs That Break the State Machine

Hard
996.

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

ColumnType
event_idint
trip_idint
event_typevarchar
event_atdatetime

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

ColumnType
from_statevarchar
to_statevarchar

Primary key (together): from_state, to_state.

Every allowed move; 'start' stands for "before the first event".

Example

The rows must come back in the order shown.

TripEvent

event_idtrip_idevent_typeevent_at
11requested2024-10-11 08:00:00
21accepted2024-10-11 08:00:30
31arrived2024-10-11 08:06:00
41started2024-10-11 08:07:00
51completed2024-10-11 08:30:00
62requested2024-10-11 09:00:00
72arrived2024-10-11 09:08:00
82started2024-10-11 09:09:00
93requested2024-10-11 09:30:00
103accepted2024-10-11 09:31:00
11 more rows

AllowedStep

from_stateto_state
startrequested
requestedaccepted
requestedcancelled
acceptedarrived
acceptedcancelled
arrivedstarted
arrivedcancelled
startedcompleted

Output

trip_idfrom_stateto_statebroken_at
2requestedarrived2024-10-11 09:08:00
3cancelledaccepted2024-10-11 09:35:00
4startaccepted2024-10-11 10:00:00
6acceptedstarted2024-10-11 11:06:00
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.

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

ColumnType
event_idint
trip_idint
event_typevarchar
event_atdatetime

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

ColumnType
from_statevarchar
to_statevarchar

Primary key: from_state, to_state.

Every allowed move; 'start' stands for "before the first event".

Examples

Example 1

TripEvent

event_idtrip_idevent_typeevent_at
11requested2024-10-11 08:00:00
21accepted2024-10-11 08:00:30
31arrived2024-10-11 08:06:00
41started2024-10-11 08:07:00
51completed2024-10-11 08:30:00
62requested2024-10-11 09:00:00
72arrived2024-10-11 09:08:00
82started2024-10-11 09:09:00
93requested2024-10-11 09:30:00
103accepted2024-10-11 09:31:00
113cancelled2024-10-11 09:33:00
123accepted2024-10-11 09:35:00
134accepted2024-10-11 10:00:00
144arrived2024-10-11 10:05:00
155requested2024-10-11 10:30:00
165cancelled2024-10-11 10:31:00
176requested2024-10-11 11:00:00
186accepted2024-10-11 11:01:00
196started2024-10-11 11:06:00
206arrived2024-10-11 11:07:00
216completed2024-10-11 11:25:00

AllowedStep

from_stateto_state
startrequested
requestedaccepted
requestedcancelled
acceptedarrived
acceptedcancelled
arrivedstarted
arrivedcancelled
startedcompleted

Output

trip_idfrom_stateto_statebroken_at
2requestedarrived2024-10-11 09:08:00
3cancelledaccepted2024-10-11 09:35:00
4startaccepted2024-10-11 10:00:00
6acceptedstarted2024-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_id

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