Google: Longest YouTube Autoplay Chain in Each Session

Hard
695.

Google: Longest YouTube Autoplay Chain in Each Session

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

ColumnType
event_idint
session_idint
video_idint
started_atdatetime
autoplay_fromint

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.

Example

The rows must come back in the order shown.

WatchEvent

event_idsession_idvideo_idstarted_atautoplay_from
1015012025-05-03 20:00:00NULL
1115022025-05-03 20:10:0010
1215032025-05-03 20:20:0011
1315042025-05-03 20:40:00NULL
1415052025-05-03 20:50:0013
2026012025-05-03 21:00:00NULL
2126022025-05-03 21:05:0020
2226032025-05-03 21:10:00NULL
2326042025-05-03 21:20:0022
3037012025-05-03 22:00:00NULL

Output

session_idroot_video_idchain_length
15013
26012
37011
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 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

ColumnType
event_idint
session_idint
video_idint
started_atdatetime
autoplay_fromint

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_idsession_idvideo_idstarted_atautoplay_from
1015012025-05-03 20:00:00NULL
1115022025-05-03 20:10:0010
1215032025-05-03 20:20:0011
1315042025-05-03 20:40:00NULL
1415052025-05-03 20:50:0013
2026012025-05-03 21:00:00NULL
2126022025-05-03 21:05:0020
2226032025-05-03 21:10:00NULL
2326042025-05-03 21:20:0022
3037012025-05-03 22:00:00NULL

Output

session_idroot_video_idchain_length
15013
26012
37011

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_id

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