Spotify: Playlist Pairs Sharing Half Their Available Tracks

Hard
947.

Spotify: Playlist Pairs Sharing Half Their Available Tracks

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

ColumnType
track_idint
titlevarchar
is_availablebool

Primary key: track_id.

One row per track; is_available is 0 when the track was taken down in this market.

Table: PlaylistTrack

ColumnType
playlist_idint
track_idint

Primary key (together): playlist_id, track_id.

One row per track on a playlist; a track appears on a playlist at most once.

Example

The rows must come back in the order shown.

Track

track_idtitleis_available
1Monsoon Letters1
2Chasing Neon1
3Paper Planes1
4Slow Rickshaw1
5Golden Hour0
6Static Hearts1
7Midnight Chai1

PlaylistTrack

playlist_idtrack_id
101
102
103
104
201
202
206
207
303
305
3 more rows

Output

playlist_aplaylist_bshared_trackssmaller_size
102024
103012
203012
204011
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.

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

ColumnType
track_idint
titlevarchar
is_availablebool

Primary key: track_id.

One row per track; is_available is 0 when the track was taken down in this market.

Table: PlaylistTrack

ColumnType
playlist_idint
track_idint

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_idtitleis_available
1Monsoon Letters1
2Chasing Neon1
3Paper Planes1
4Slow Rickshaw1
5Golden Hour0
6Static Hearts1
7Midnight Chai1

PlaylistTrack

playlist_idtrack_id
101
102
103
104
201
202
206
207
303
305
306
405
407

Output

playlist_aplaylist_bshared_trackssmaller_size
102024
103012
203012
204011

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_b

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