Google: Longest YouTube Autoplay Chain in Each Session
The YouTube recommendations team measures how far autoplay carries a viewer.
- Difficulty: Hard
- Topics: Subqueries, Window Functions
- Dialect: MySQL
- Problem: #695
Problem statement
The YouTube recommendations team measures how far autoplay carries a viewer. Each watch event either was chosen by the viewer (autoplay_from is NULL) or was autoplayed from the event recorded in autoplay_from. A chain is a chosen event followed by every event autoplayed from it, then from that one, and so on.
For every session, return session_id, root_video_id (the video_id of the chosen event that starts its longest chain) and chain_length (the number of events in that chain, 1 for a chosen event nothing autoplayed from). If chains tie for longest, the one whose chosen event started earlier wins. Order by session_id.
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: WatchEvent
| Column | Type |
|---|---|
| event_id | int |
| session_id | int |
| video_id | int |
| started_at | datetime |
| autoplay_from | int |
Primary key: event_id.
One video play. autoplay_from is the event_id of the play that autoplayed this one — always the play directly before it in the same session — or NULL when the viewer picked it. Start times within a session are distinct; every session's first event is chosen.
Examples
Example 1
WatchEvent
| event_id | session_id | video_id | started_at | autoplay_from |
|---|---|---|---|---|
| 10 | 1 | 501 | 2025-05-03 20:00:00 | NULL |
| 11 | 1 | 502 | 2025-05-03 20:10:00 | 10 |
| 12 | 1 | 503 | 2025-05-03 20:20:00 | 11 |
| 13 | 1 | 504 | 2025-05-03 20:40:00 | NULL |
| 14 | 1 | 505 | 2025-05-03 20:50:00 | 13 |
| 20 | 2 | 601 | 2025-05-03 21:00:00 | NULL |
| 21 | 2 | 602 | 2025-05-03 21:05:00 | 20 |
| 22 | 2 | 603 | 2025-05-03 21:10:00 | NULL |
| 23 | 2 | 604 | 2025-05-03 21:20:00 | 22 |
| 30 | 3 | 701 | 2025-05-03 22:00:00 | NULL |
Output
| session_id | root_video_id | chain_length |
|---|---|---|
| 1 | 501 | 3 |
| 2 | 601 | 2 |
| 3 | 701 | 1 |
How to solve Google: Longest YouTube Autoplay Chain in Each Session
The data is a set of linked lists: each autoplayed event points back to its source. A recursive CTE walks them forward. The anchor takes every chosen event as a chain of length 1 whose root is itself; the recursive step joins events whose autoplay_from is the current tail and adds one to the length, keeping the root. The recursion stops by itself when no event points at the tail. The longest length reached from each root, MAX(len), is that chain's size.
Each root is a chosen event, so joining it back to WatchEvent gives its session, video and start time. Ranking the chains of a session by chain_length DESC, started_at and keeping number 1 picks the longest chain, the earlier-started one on a tie (start times in a session are distinct, so the order is total). A session with a single chosen play has one chain of length 1.
The alternative uses the guarantee that an autoplayed play directly follows its source: then chains are islands of consecutive plays, each starting at a chosen event, and a running SUM of chosen-event flags numbers them. The recursive version follows the links themselves and would still work if that ordering guarantee were dropped; it costs one join per chain step.
Reference solution (MySQL)
WITH RECURSIVE chain (root_id, cur_id, len) AS (
SELECT event_id, event_id, 1
FROM WatchEvent
WHERE autoplay_from IS NULL
UNION ALL
SELECT c.root_id, w.event_id, c.len + 1
FROM chain c
JOIN WatchEvent w ON w.autoplay_from = c.cur_id
), lengths AS (
SELECT root_id, MAX(len) AS chain_length
FROM chain
GROUP BY root_id
), ranked AS (
SELECT r.session_id, r.video_id, l.chain_length,
ROW_NUMBER() OVER (PARTITION BY r.session_id
ORDER BY l.chain_length DESC, r.started_at) AS rn
FROM lengths l
JOIN WatchEvent r ON r.event_id = l.root_id
)
SELECT session_id, video_id AS root_video_id, chain_length
FROM ranked
WHERE rn = 1
ORDER BY session_idAnother way
WITH tagged AS (SELECT event_id, session_id, video_id, started_at, autoplay_from, SUM(CASE WHEN autoplay_from IS NULL THEN 1 ELSE 0 END) OVER (PARTITION BY session_id ORDER BY started_at ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS chain_no FROM WatchEvent), chains AS (SELECT session_id, chain_no, COUNT(*) AS chain_length, MIN(started_at) AS root_at FROM tagged GROUP BY session_id, chain_no), best AS (SELECT session_id, chain_length, root_at, ROW_NUMBER() OVER (PARTITION BY session_id ORDER BY chain_length DESC, root_at) AS rn FROM chains) SELECT b.session_id, t.video_id AS root_video_id, b.chain_length FROM best b JOIN tagged t ON t.session_id = b.session_id AND t.started_at = b.root_at WHERE b.rn = 1 ORDER BY b.session_id← Google: Prorated Workspace Seat-Days for June 2025 · Google: Median First-Reply Time in Gmail Support Threads →