Spotify: Playlist Pairs Sharing Half Their Available Tracks
To suggest "similar playlists", the discovery team looks for pairs of playlists with heavy overlap.
- Difficulty: Hard
- Topics: Joins, Aggregation, Subqueries
- Dialect: MySQL
- Problem: #947
Problem statement
To suggest "similar playlists", the discovery team looks for pairs of playlists with heavy overlap. Only tracks that are still available (is_available = 1) count — towards the overlap and towards a playlist's size. Two playlists overlap heavily when they share at least one available track and the shared tracks make up at least half of the smaller playlist's available tracks.
Return each such pair once, with the smaller id first, as playlist_a, playlist_b, shared_tracks and smaller_size (the smaller of the two playlists' available-track counts). Order by playlist_a, then playlist_b.
A practice scenario set at Spotify: the tables and data are invented, and this is not a question from, or endorsed by, Spotify.
Tables
Table: Track
| Column | Type |
|---|---|
| track_id | int |
| title | varchar |
| is_available | bool |
Primary key: track_id.
One row per track; is_available is 0 when the track was taken down in this market.
Table: PlaylistTrack
| Column | Type |
|---|---|
| playlist_id | int |
| track_id | int |
Primary key: playlist_id, track_id.
One row per track on a playlist; a track appears on a playlist at most once.
Examples
Example 1
Track
| track_id | title | is_available |
|---|---|---|
| 1 | Monsoon Letters | 1 |
| 2 | Chasing Neon | 1 |
| 3 | Paper Planes | 1 |
| 4 | Slow Rickshaw | 1 |
| 5 | Golden Hour | 0 |
| 6 | Static Hearts | 1 |
| 7 | Midnight Chai | 1 |
PlaylistTrack
| playlist_id | track_id |
|---|---|
| 10 | 1 |
| 10 | 2 |
| 10 | 3 |
| 10 | 4 |
| 20 | 1 |
| 20 | 2 |
| 20 | 6 |
| 20 | 7 |
| 30 | 3 |
| 30 | 5 |
| 30 | 6 |
| 40 | 5 |
| 40 | 7 |
Output
| playlist_a | playlist_b | shared_tracks | smaller_size |
|---|---|---|---|
| 10 | 20 | 2 | 4 |
| 10 | 30 | 1 | 2 |
| 20 | 30 | 1 | 2 |
| 20 | 40 | 1 | 1 |
How to solve Spotify: Playlist Pairs Sharing Half Their Available Tracks
The overlap of two playlists is found by a self join of the playlist–track pairs on the track: every row of the join is one track the two playlists share. The condition a.playlist_id < b.playlist_id keeps each unordered pair once (and never pairs a playlist with itself), and grouping by the pair counts the shared tracks. Pairs that share nothing never appear, as the statement requires.
Availability changes both sides of the comparison, so it is applied once up front in the avail CTE and reused for sizes and overlap. In the example Golden Hour is unavailable: playlist 30 counts as two tracks, not three, and playlist 40 as one. Playlists 30 and 40 then share nothing available, while 20 and 40 share Midnight Chai — one track, which is half of 40's single available track or more — so they qualify. Playlists 10 and 20 share 2 of 4; 10 and 30 share 1 of 2; 20 and 30 share 1 of 2.
The threshold is compared in integers, 2 * shared >= LEAST(size_a, size_b), so no rounding can sneak in. The alternative computes each playlist's size with correlated subqueries inside the grouped pair query and picks the smaller with CASE. The self join is quadratic in the number of playlists sharing a track — fine for curated catalogues, and the reason production systems use MinHash for this at scale.
Reference solution (MySQL)
WITH avail AS (
SELECT pt.playlist_id, pt.track_id
FROM PlaylistTrack pt
JOIN Track t ON t.track_id = pt.track_id
WHERE t.is_available = 1
), sizes AS (
SELECT playlist_id, COUNT(*) AS size FROM avail GROUP BY playlist_id
), shared AS (
SELECT a.playlist_id AS playlist_a, b.playlist_id AS playlist_b, COUNT(*) AS shared_tracks
FROM avail a
JOIN avail b ON b.track_id = a.track_id AND a.playlist_id < b.playlist_id
GROUP BY a.playlist_id, b.playlist_id
)
SELECT sh.playlist_a, sh.playlist_b, sh.shared_tracks, LEAST(sa.size, sb.size) AS smaller_size
FROM shared sh
JOIN sizes sa ON sa.playlist_id = sh.playlist_a
JOIN sizes sb ON sb.playlist_id = sh.playlist_b
WHERE 2 * sh.shared_tracks >= LEAST(sa.size, sb.size)
ORDER BY sh.playlist_a, sh.playlist_bAnother way
SELECT playlist_a, playlist_b, shared_tracks, smaller_size
FROM (SELECT x.playlist_a, x.playlist_b, x.shared_tracks,
CASE WHEN x.size_a < x.size_b THEN x.size_a ELSE x.size_b END AS smaller_size
FROM (SELECT a.playlist_id AS playlist_a, b.playlist_id AS playlist_b, COUNT(*) AS shared_tracks,
(SELECT COUNT(*) FROM PlaylistTrack p JOIN Track t ON t.track_id = p.track_id WHERE p.playlist_id = a.playlist_id AND t.is_available <> 0) AS size_a,
(SELECT COUNT(*) FROM PlaylistTrack p JOIN Track t ON t.track_id = p.track_id WHERE p.playlist_id = b.playlist_id AND t.is_available <> 0) AS size_b
FROM PlaylistTrack a
JOIN PlaylistTrack b ON b.track_id = a.track_id AND b.playlist_id > a.playlist_id
JOIN Track t ON t.track_id = a.track_id
WHERE t.is_available = 1
GROUP BY a.playlist_id, b.playlist_id) x) y
WHERE shared_tracks * 2 >= smaller_size
ORDER BY playlist_a, playlist_b← Spotify: Listeners Whose Top Genre Changed From Q1 to Q2 · Swiggy: Instamart Orders Delivered Within 10 Minutes →