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
| Column | Type |
|---|---|
| device_id | int |
| room | varchar |
| model | varchar |
Primary key: device_id.
One installed device.
Table: Heartbeat
| Column | Type |
|---|---|
| device_id | int |
| beat_at | datetime |
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_id | room | model |
|---|---|---|
| 1 | Living room | Nest Cam |
| 2 | Hallway | Nest Thermostat |
| 3 | Garage | Nest Doorbell |
Heartbeat
| device_id | beat_at |
|---|---|
| 1 | 2025-06-01 08:00:00 |
| 1 | 2025-06-01 08:15:00 |
| 1 | 2025-06-01 09:45:00 |
| 1 | 2025-06-01 11:15:00 |
| 2 | 2025-06-01 08:00:00 |
| 2 | 2025-06-01 08:05:00 |
| 2 | 2025-06-01 12:05:00 |
| 3 | 2025-06-01 09:00:00 |
Output
| device_id | room | longest_gap_minutes | gap_started_at |
|---|---|---|---|
| 2 | Hallway | 240 | 2025-06-01 08:05:00 |
| 1 | Living room | 90 | 2025-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_idAnother 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 →