Google: Longest Heartbeat Gap of Each Nest Device

Medium
688.

Google: Longest Heartbeat Gap of Each Nest Device

Nest devices send a heartbeat to the cloud while they are online. A reliability engineer wants, per device, its worst outage: the longest silence between two consecutive heartbeats.

For every device with at least 2 heartbeats, return device_id, room, longest_gap_minutes (the largest gap in whole minutes between consecutive heartbeats) and gap_started_at (the heartbeat that came right before that gap; if several gaps are equally longest, the earliest one). Order by longest_gap_minutes descending, then device_id ascending.

A practice scenario set at Google: the tables and data are invented, and this is not a question from, or endorsed by, Google.

Tables

Table: NestDevice

ColumnType
device_idint
roomvarchar
modelvarchar

Primary key: device_id.

One installed device.

Table: Heartbeat

ColumnType
device_idint
beat_atdatetime

Primary key (together): device_id, beat_at.

One heartbeat received; times are on whole minutes. device_id always names a device.

Example

The rows must come back in the order shown.

NestDevice

device_idroommodel
1Living roomNest Cam
2HallwayNest Thermostat
3GarageNest Doorbell

Heartbeat

device_idbeat_at
12025-06-01 08:00:00
12025-06-01 08:15:00
12025-06-01 09:45:00
12025-06-01 11:15:00
22025-06-01 08:00:00
22025-06-01 08:05:00
22025-06-01 12:05:00
32025-06-01 09:00:00

Output

device_idroomlongest_gap_minutesgap_started_at
2Hallway2402025-06-01 08:05:00
1Living room902025-06-01 08:15: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.

Google: Longest Heartbeat Gap of Each Nest Device

Nest devices send a heartbeat to the cloud while they are online.

  • Difficulty: Medium
  • Topics: Window Functions, Dates, Joins
  • Dialect: MySQL
  • Problem: #688

Problem statement

Nest devices send a heartbeat to the cloud while they are online. A reliability engineer wants, per device, its worst outage: the longest silence between two consecutive heartbeats.

For every device with at least 2 heartbeats, return device_id, room, longest_gap_minutes (the largest gap in whole minutes between consecutive heartbeats) and gap_started_at (the heartbeat that came right before that gap; if several gaps are equally longest, the earliest one). Order by longest_gap_minutes descending, then device_id ascending.

A practice scenario set at Google: the tables and data are invented, and this is not a question from, or endorsed by, Google.

Tables

Table: NestDevice

ColumnType
device_idint
roomvarchar
modelvarchar

Primary key: device_id.

One installed device.

Table: Heartbeat

ColumnType
device_idint
beat_atdatetime

Primary key: device_id, beat_at.

One heartbeat received; times are on whole minutes. device_id always names a device.

Examples

Example 1

NestDevice

device_idroommodel
1Living roomNest Cam
2HallwayNest Thermostat
3GarageNest Doorbell

Heartbeat

device_idbeat_at
12025-06-01 08:00:00
12025-06-01 08:15:00
12025-06-01 09:45:00
12025-06-01 11:15:00
22025-06-01 08:00:00
22025-06-01 08:05:00
22025-06-01 12:05:00
32025-06-01 09:00:00

Output

device_idroomlongest_gap_minutesgap_started_at
2Hallway2402025-06-01 08:05:00
1Living room902025-06-01 08:15:00

How to solve Google: Longest Heartbeat Gap of Each Nest Device

Each gap is defined by two consecutive heartbeats of one device, so LEAD(beat_at) OVER (PARTITION BY device_id ORDER BY beat_at) pairs every heartbeat with the next. The last heartbeat of a device has no successor and is dropped; a device with a single heartbeat therefore has no gaps at all and falls out, as the statement requires. TIMESTAMPDIFF(MINUTE, …) turns each pair into whole minutes (the computation is done in a separate step so the window and the date function are not nested).

Picking the largest gap and the row it belongs to is a top-1-per-group problem: ROW_NUMBER() ordered by gap DESC, beat_at makes the longest gap number 1 and, among equal longest gaps, the earliest. Joining the device gives the room.

The alternative finds each next heartbeat with a correlated MIN, keeps gaps equal to the device's maximum and takes the earliest start with MIN(beat_at). The window approach sorts each device's heartbeats once.

Reference solution (MySQL)

WITH nxt AS (
  SELECT device_id, beat_at,
         LEAD(beat_at) OVER (PARTITION BY device_id ORDER BY beat_at) AS next_at
  FROM Heartbeat
), gaps AS (
  SELECT device_id, beat_at, TIMESTAMPDIFF(MINUTE, beat_at, next_at) AS gap
  FROM nxt
  WHERE next_at IS NOT NULL
), ranked AS (
  SELECT device_id, beat_at, gap,
         ROW_NUMBER() OVER (PARTITION BY device_id ORDER BY gap DESC, beat_at) AS rn
  FROM gaps
)
SELECT r.device_id, d.room, r.gap AS longest_gap_minutes, r.beat_at AS gap_started_at
FROM ranked r
JOIN NestDevice d ON d.device_id = r.device_id
WHERE r.rn = 1
ORDER BY longest_gap_minutes DESC, r.device_id

Another way

WITH gaps AS (SELECT h.device_id, h.beat_at, TIMESTAMPDIFF(MINUTE, h.beat_at, (SELECT MIN(n.beat_at) FROM Heartbeat n WHERE n.device_id = h.device_id AND n.beat_at > h.beat_at)) AS gap FROM Heartbeat h) SELECT g.device_id, d.room, g.gap AS longest_gap_minutes, MIN(g.beat_at) AS gap_started_at FROM gaps g JOIN NestDevice d ON d.device_id = g.device_id WHERE g.gap = (SELECT MAX(g2.gap) FROM gaps g2 WHERE g2.device_id = g.device_id) GROUP BY g.device_id, d.room, g.gap ORDER BY longest_gap_minutes DESC, g.device_id

← Google: Searches Reformulated Within a Minute · Google: Cloud Cost Spikes Against the Trailing Week →