Uber: Airport Queue Position When Each Driver Arrived
The airport app tells a driver their place in the queue the moment they enter the holding lot.
- Difficulty: Medium
- Topics: Subqueries, Joins, Dates
- Dialect: MySQL
- Problem: #986
Problem statement
The airport app tells a driver their place in the queue the moment they enter the holding lot. The operations team wants to rebuild that number from the queue log to audit it.
A driver's queue_position on arrival is 1 plus the number of drivers at the same airport who joined earlier and were still waiting at that moment — that is, whose left_at is after this driver's joined_at (a driver leaving at the very same second is already gone). Return entry_id, driver_id and queue_position for every entry, ordered by entry_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: QueueEntry
| Column | Type |
|---|---|
| entry_id | int |
| driver_id | int |
| airport | varchar |
| joined_at | datetime |
| left_at | datetime |
Primary key: entry_id.
One row per time a driver entered an airport queue; left_at is when they were dispatched or gave up, always after joined_at. No two entries at the same airport share a joined_at.
Examples
Example 1
QueueEntry
| entry_id | driver_id | airport | joined_at | left_at |
|---|---|---|---|---|
| 1 | 21 | BLR | 2024-08-01 05:00:00 | 2024-08-01 05:40:00 |
| 2 | 22 | BLR | 2024-08-01 05:10:00 | 2024-08-01 05:30:00 |
| 3 | 23 | BLR | 2024-08-01 05:20:00 | 2024-08-01 06:10:00 |
| 4 | 24 | BLR | 2024-08-01 05:30:00 | 2024-08-01 05:50:00 |
| 5 | 25 | BLR | 2024-08-01 06:00:00 | 2024-08-01 06:20:00 |
| 6 | 31 | DEL | 2024-08-01 05:15:00 | 2024-08-01 05:45:00 |
Output
| entry_id | driver_id | queue_position |
|---|---|---|
| 1 | 21 | 1 |
| 2 | 22 | 2 |
| 3 | 23 | 3 |
| 4 | 24 | 3 |
| 5 | 25 | 2 |
| 6 | 31 | 1 |
How to solve Uber: Airport Queue Position When Each Driver Arrived
The position depends on the state of the queue at one instant, the moment this driver joined. A driver o is ahead in the queue at that instant if they joined earlier (o.joined_at < q.joined_at) and had not yet left (o.left_at > q.joined_at), at the same airport. Counting those drivers and adding one gives the position.
The solution does the count in a correlated scalar subquery, evaluated once per entry. COUNT(*) over no rows is 0, so a driver who arrives to an empty lot is position 1. The strict > on left_at implements the rule that a driver dispatched at the very second another arrives is already gone — in the example, driver 22 left at 05:30, exactly when driver 24 joined, so driver 24 is third, behind 21 and 23, not fourth.
The alternative is a LEFT JOIN of the table to itself on the same condition, grouped per entry: COUNT(o.entry_id) counts only real matches, never the NULL row an unmatched entry keeps. Both are quadratic in the entries of one airport, which is fine for a day's log; an index on (airport, joined_at) narrows each lookup.
Reference solution (MySQL)
SELECT q.entry_id, q.driver_id,
1 + (SELECT COUNT(*) FROM QueueEntry o
WHERE o.airport = q.airport
AND o.joined_at < q.joined_at
AND o.left_at > q.joined_at) AS queue_position
FROM QueueEntry q
ORDER BY q.entry_idAnother way
SELECT q.entry_id, q.driver_id, 1 + COUNT(o.entry_id) AS queue_position
FROM QueueEntry q
LEFT JOIN QueueEntry o
ON o.airport = q.airport AND o.joined_at < q.joined_at AND o.left_at > q.joined_at
GROUP BY q.entry_id, q.driver_id
ORDER BY q.entry_id← Uber: Promo Abuse — One Device, Many Accounts, Same Campaign · Uber: Rider Referrals That Qualified for the Bonus →