Uber: Longest Surge Episode in Each Zone — SQL Problem
Surge pricing is recalculated every 5 minutes per zone. A pricing analyst wants each zone's longest uninterrupted spell of high surge on the evening of…
- Difficulty: Hard
- Topics: Window Functions, Dates
- Dialect: MySQL
- Problem: #993
Problem statement
Surge pricing is recalculated every 5 minutes per zone. A pricing analyst wants each zone's longest uninterrupted spell of high surge on the evening of 2024-09-14.
A slot is hot when its multiplier is at least 1.5. An episode is a maximal run of hot slots of one zone in which each slot starts exactly 5 minutes after the previous one (a missing reading breaks the run). For each zone with at least one hot slot, return its longest episode: zone, episode_start (the first slot's start), episode_end (the last slot's start plus 5 minutes), slots and peak_multiplier. If two episodes tie on length, return the earlier one. Order by zone.
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: SurgeReading
| Column | Type |
|---|---|
| zone | varchar |
| slot_start | datetime |
| multiplier | decimal |
Primary key: zone, slot_start.
One row per zone per 5-minute slot that had a reading; slot_start is always on a 5-minute mark of 2024-09-14.
Examples
Example 1
SurgeReading
| zone | slot_start | multiplier |
|---|---|---|
| Indiranagar | 2024-09-14 18:00:00 | 1.2 |
| Indiranagar | 2024-09-14 18:05:00 | 1.5 |
| Indiranagar | 2024-09-14 18:10:00 | 1.8 |
| Indiranagar | 2024-09-14 18:15:00 | 2.1 |
| Indiranagar | 2024-09-14 18:20:00 | 1.4 |
| Indiranagar | 2024-09-14 18:25:00 | 1.6 |
| Indiranagar | 2024-09-14 18:30:00 | 1.9 |
| Indiranagar | 2024-09-14 18:40:00 | 1.7 |
| Indiranagar | 2024-09-14 18:45:00 | 1.7 |
| Indiranagar | 2024-09-14 18:50:00 | 1.5 |
| Whitefield | 2024-09-14 18:00:00 | 1 |
| Whitefield | 2024-09-14 18:05:00 | 1.3 |
| Koramangala | 2024-09-14 19:00:00 | 1.5 |
Output
| zone | episode_start | episode_end | slots | peak_multiplier |
|---|---|---|---|---|
| Indiranagar | 2024-09-14 18:05:00 | 2024-09-14 18:20:00 | 3 | 2.1 |
| Koramangala | 2024-09-14 19:00:00 | 2024-09-14 19:05:00 | 1 | 1.5 |
How to solve Uber: Longest Surge Episode in Each Zone
This is gaps and islands: the islands are runs of consecutive hot slots, and the gaps are cool slots or missing readings. Filtering to multiplier >= 1.5 first leaves only hot slots, and a gap in time now marks the end of an island.
The classic trick numbers the slots twice. TIMESTAMPDIFF(MINUTE, midnight, slot_start) DIV 5 is the slot's position in the day; ROW_NUMBER() per zone is its position among the hot slots. Inside one island both advance by one per row, so their difference is constant; a gap makes the slot number jump while the row number does not, so the difference changes. Grouping by (zone, difference) gives one row per episode with its first slot, last slot plus 5 minutes, length and peak. (The slot number is always far larger than the row number, so the subtraction never goes negative — MySQL's unsigned ROW_NUMBER would otherwise complain.)
Finally ROW_NUMBER() OVER (PARTITION BY zone ORDER BY slots DESC, episode_start) ranks the episodes and the first is kept: in Indiranagar the 18:05 and 18:40 episodes both have three slots, and the earlier wins. The missing 18:35 reading ends the 18:25 episode at two slots. The alternative marks island starts with LAG and a running SUM, and picks the winner with NOT EXISTS — no longer episode, and no equally long earlier one.
Reference solution (MySQL)
WITH hot AS (
SELECT zone, slot_start, multiplier,
TIMESTAMPDIFF(MINUTE, '2024-09-14 00:00:00', slot_start) DIV 5
- ROW_NUMBER() OVER (PARTITION BY zone ORDER BY slot_start) AS grp
FROM SurgeReading
WHERE multiplier >= 1.5
), episodes AS (
SELECT zone, MIN(slot_start) AS episode_start,
DATE_ADD(MAX(slot_start), INTERVAL 5 MINUTE) AS episode_end,
COUNT(*) AS slots, MAX(multiplier) AS peak_multiplier
FROM hot
GROUP BY zone, grp
), ranked AS (
SELECT e.*, ROW_NUMBER() OVER (PARTITION BY zone ORDER BY slots DESC, episode_start) AS pos
FROM episodes e
)
SELECT zone, episode_start, episode_end, slots, peak_multiplier
FROM ranked
WHERE pos = 1
ORDER BY zoneAnother way
WITH marked AS (
SELECT zone, slot_start, multiplier,
CASE WHEN LAG(slot_start) OVER (PARTITION BY zone ORDER BY slot_start) = DATE_SUB(slot_start, INTERVAL 5 MINUTE)
THEN 0 ELSE 1 END AS is_start
FROM SurgeReading
WHERE multiplier >= 1.5
), numbered AS (
SELECT zone, slot_start, multiplier,
SUM(is_start) OVER (PARTITION BY zone ORDER BY slot_start ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS ep
FROM marked
), episodes AS (
SELECT zone, MIN(slot_start) AS episode_start, DATE_ADD(MAX(slot_start), INTERVAL 5 MINUTE) AS episode_end,
COUNT(*) AS slots, MAX(multiplier) AS peak_multiplier
FROM numbered GROUP BY zone, ep
)
SELECT e.zone, e.episode_start, e.episode_end, e.slots, e.peak_multiplier
FROM episodes e
WHERE NOT EXISTS (
SELECT 1 FROM episodes o
WHERE o.zone = e.zone
AND (o.slots > e.slots OR (o.slots = e.slots AND o.episode_start < e.episode_start))
)
ORDER BY e.zone← Uber: Evening Hours Where Requests Outran Online Drivers · Uber: Split Fare Shares to the Paisa →