Uber: Longest Surge Episode in Each Zone

Hard
993.

Uber: Longest Surge Episode in Each Zone

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

ColumnType
zonevarchar
slot_startdatetime
multiplierdecimal

Primary key (together): 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.

Example

The rows must come back in the order shown.

SurgeReading

zoneslot_startmultiplier
Indiranagar2024-09-14 18:00:001.2
Indiranagar2024-09-14 18:05:001.5
Indiranagar2024-09-14 18:10:001.8
Indiranagar2024-09-14 18:15:002.1
Indiranagar2024-09-14 18:20:001.4
Indiranagar2024-09-14 18:25:001.6
Indiranagar2024-09-14 18:30:001.9
Indiranagar2024-09-14 18:40:001.7
Indiranagar2024-09-14 18:45:001.7
Indiranagar2024-09-14 18:50:001.5
3 more rows

Output

zoneepisode_startepisode_endslotspeak_multiplier
Indiranagar2024-09-14 18:05:002024-09-14 18:20:0032.1
Koramangala2024-09-14 19:00:002024-09-14 19:05:0011.5
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: 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

ColumnType
zonevarchar
slot_startdatetime
multiplierdecimal

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

zoneslot_startmultiplier
Indiranagar2024-09-14 18:00:001.2
Indiranagar2024-09-14 18:05:001.5
Indiranagar2024-09-14 18:10:001.8
Indiranagar2024-09-14 18:15:002.1
Indiranagar2024-09-14 18:20:001.4
Indiranagar2024-09-14 18:25:001.6
Indiranagar2024-09-14 18:30:001.9
Indiranagar2024-09-14 18:40:001.7
Indiranagar2024-09-14 18:45:001.7
Indiranagar2024-09-14 18:50:001.5
Whitefield2024-09-14 18:00:001
Whitefield2024-09-14 18:05:001.3
Koramangala2024-09-14 19:00:001.5

Output

zoneepisode_startepisode_endslotspeak_multiplier
Indiranagar2024-09-14 18:05:002024-09-14 18:20:0032.1
Koramangala2024-09-14 19:00:002024-09-14 19:05:0011.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 zone

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