Uber: Evening Hours Where Requests Outran Online Drivers
The supply team plans driver incentives for the hours when demand overwhelms supply.
- Difficulty: Hard
- Topics: Subqueries, Dates, Aggregation
- Dialect: MySQL
- Problem: #992
Problem statement
The supply team plans driver incentives for the hours when demand overwhelms supply. It looks at the evening of 2024-08-09, the five hour slots starting at 17:00, 18:00, 19:00, 20:00 and 21:00.
For each city and slot, requests is the number of ride requests made in the slot (requested_at at or after the slot start and before the next slot), and drivers_online is the number of different drivers of that city whose shift overlapped the slot — online before the slot ended and offline after it began (a shift ending exactly at the slot start, or beginning exactly at its end, does not overlap). Return city, hour_start (as '2024-08-09 HH:00:00'), requests and drivers_online for every slot with requests greater than twice drivers_online, ordered by city, then hour_start.
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: RideRequest
| Column | Type |
|---|---|
| request_id | int |
| city | varchar |
| requested_at | datetime |
Primary key: request_id.
One row per ride request, whatever happened to it.
Table: DriverShift
| Column | Type |
|---|---|
| shift_id | int |
| driver_id | int |
| city | varchar |
| online_from | datetime |
| online_to | datetime |
Primary key: shift_id.
One row per stretch of time a driver was online; a driver may have several shifts in a day.
Examples
Example 1
RideRequest
| request_id | city | requested_at |
|---|---|---|
| 1 | Bengaluru | 2024-08-09 17:05:00 |
| 2 | Bengaluru | 2024-08-09 17:10:00 |
| 3 | Bengaluru | 2024-08-09 17:20:00 |
| 4 | Bengaluru | 2024-08-09 17:40:00 |
| 5 | Bengaluru | 2024-08-09 17:59:59 |
| 6 | Bengaluru | 2024-08-09 18:10:00 |
| 7 | Bengaluru | 2024-08-09 18:30:00 |
| 8 | Bengaluru | 2024-08-09 21:00:00 |
| 9 | Bengaluru | 2024-08-09 21:30:00 |
| 10 | Bengaluru | 2024-08-09 22:00:00 |
| 11 | Mumbai | 2024-08-09 19:15:00 |
| 12 | Mumbai | 2024-08-09 16:59:00 |
DriverShift
| shift_id | driver_id | city | online_from | online_to |
|---|---|---|---|---|
| 1 | 501 | Bengaluru | 2024-08-09 16:00:00 | 2024-08-09 17:30:00 |
| 2 | 502 | Bengaluru | 2024-08-09 17:00:00 | 2024-08-09 18:00:00 |
| 3 | 502 | Bengaluru | 2024-08-09 18:30:00 | 2024-08-09 19:00:00 |
| 4 | 503 | Bengaluru | 2024-08-09 20:00:00 | 2024-08-09 21:00:00 |
| 5 | 601 | Mumbai | 2024-08-09 16:00:00 | 2024-08-09 17:00:00 |
Output
| city | hour_start | requests | drivers_online |
|---|---|---|---|
| Bengaluru | 2024-08-09 17:00:00 | 5 | 2 |
| Bengaluru | 2024-08-09 21:00:00 | 2 | 0 |
| Mumbai | 2024-08-09 19:00:00 | 1 | 0 |
How to solve Uber: Evening Hours Where Requests Outran Online Drivers
The answer is per (city, slot), with two measures from two unrelated tables, so they are computed separately and then put side by side.
The solution builds the five slots with a recursive CTE (anchor 17:00, add an hour until 21:00) and joins requests into them with a half-open range, >= start AND < start + 1 hour, so a request at 17:59:59 belongs to 17:00 and one at exactly 22:00 to no slot. Only slots with requests can satisfy requests > 2 × drivers, so demand is the list of candidates.
For supply, a shift overlaps the slot when it began before the slot ended and ended after the slot began — the standard interval-overlap test, strict on both sides, so driver 502's shift ending at 18:00 does not count in the 18:00 slot and driver 503's ending at 21:00 not in the 21:00 slot. COUNT(DISTINCT driver_id) counts people, not shifts. The join is a LEFT JOIN grouped per demand row, so a slot with no overlapping shift still appears with 0 — Bengaluru at 21:00 and Mumbai at 19:00 are exactly the cases where supply was zero.
The alternative buckets requests with DATE_FORMAT(requested_at, '%Y-%m-%d %H:00:00') inside the window and counts drivers with a correlated subquery per bucket. Both are small joins over one evening's data; with indexes on (city, requested_at) and (city, online_from) they stay cheap at scale.
Reference solution (MySQL)
WITH RECURSIVE slots AS (
SELECT '2024-08-09 17:00:00' AS hour_start
UNION ALL
SELECT DATE_ADD(hour_start, INTERVAL 1 HOUR) FROM slots WHERE hour_start < '2024-08-09 21:00:00'
), demand AS (
SELECT r.city, s.hour_start, COUNT(*) AS requests
FROM slots s
JOIN RideRequest r ON r.requested_at >= s.hour_start AND r.requested_at < DATE_ADD(s.hour_start, INTERVAL 1 HOUR)
GROUP BY r.city, s.hour_start
), supply AS (
SELECT d.city, d.hour_start, COUNT(DISTINCT sh.driver_id) AS drivers_online
FROM demand d
LEFT JOIN DriverShift sh
ON sh.city = d.city AND sh.online_from < DATE_ADD(d.hour_start, INTERVAL 1 HOUR) AND sh.online_to > d.hour_start
GROUP BY d.city, d.hour_start
)
SELECT d.city, d.hour_start, d.requests, s.drivers_online
FROM demand d
JOIN supply s ON s.city = d.city AND s.hour_start = d.hour_start
WHERE d.requests > 2 * s.drivers_online
ORDER BY d.city, d.hour_startAnother way
SELECT city, hour_start, requests, drivers_online FROM (
SELECT b.city, b.hour_start, b.requests,
(SELECT COUNT(DISTINCT sh.driver_id) FROM DriverShift sh
WHERE sh.city = b.city AND sh.online_from < DATE_ADD(b.hour_start, INTERVAL 1 HOUR) AND sh.online_to > b.hour_start) AS drivers_online
FROM (SELECT city, DATE_FORMAT(requested_at, '%Y-%m-%d %H:00:00') AS hour_start, COUNT(*) AS requests
FROM RideRequest
WHERE requested_at >= '2024-08-09 17:00:00' AND requested_at < '2024-08-09 22:00:00'
GROUP BY city, DATE_FORMAT(requested_at, '%Y-%m-%d %H:00:00')) b
) x
WHERE requests > 2 * drivers_online
ORDER BY city, hour_start← Uber: Fleet Vehicles on Two Drivers' Shifts at Once · Uber: Longest Surge Episode in Each Zone →