Write SQL to compute max-overlap lists
Company: Pinterest
Role: Data Scientist
Category: Data Manipulation (SQL/Python)
Difficulty: medium
Interview Round: Onsite
Invented schema and sample data below. Assume 'today' is 2025-09-01 and 'last 7 days' means 2025-08-26 through 2025-09-01 inclusive. Only consider lists whose created_at falls in that window.
Schema:
- lists(list_id INT PRIMARY KEY, owner_id INT, created_at DATE)
- list_items(list_id INT, item VARCHAR)
Sample tables:
lists
+---------+----------+------------+
| list_id | owner_id | created_at |
+---------+----------+------------+
| 1 | 10 | 2025-08-30 |
| 2 | 11 | 2025-08-31 |
| 3 | 12 | 2025-09-01 |
+---------+----------+------------+
list_items
+---------+------+
| list_id | item |
+---------+------+
| 1 | A |
| 1 | B |
| 1 | C |
| 2 | A |
| 2 | C |
| 2 | D |
| 3 | B |
| 3 | C |
| 3 | E |
+---------+------+
Task: Write a single SQL query that returns exactly one row: (list_id_small, list_id_large, overlap_count, jaccard) for the unordered pair of lists with the maximum item overlap among eligible lists. Define overlap_count = |items(Li) ∩ items(Lj)| and jaccard = overlap_count / |items(Li) ∪ items(Lj)|. Break ties by higher jaccard, then by (list_id_small, list_id_large) ascending. For the sample data above, the expected row is (1, 2, 2, 0.5). Requirements: 1) Do not count duplicate items within a list more than once. 2) Use standard SQL constructs (CTEs/window functions allowed). 3) Explain indexes you would add to make this fast at scale. 4) Provide a variant that returns the top-5 pairs.
Overview: This question evaluates proficiency in SQL data manipulation and set-based operations, focusing on deduplication, pairwise aggregation, and similarity metric computation (Jaccard) over relational tables.
Find the list pair with maximum item overlap in the last 7 days
You are given two tables:
- lists(list_id INT PRIMARY KEY, owner_id INT, created_at DATE)
- list_items(list_id INT, item VARCHAR)
Assume that "today" is 2025-06-01. For this problem, the phrase "last 7 days" is defined explicitly as the date range from 2025-05-26 through 2025-06-01 inclusive.
Only consider lists whose created_at falls in that window (created_at BETWEEN '2025-05-26' AND '2025-06-01').
Sample data:
lists
+---------+----------+------------+
| list_id | owner_id | created_at |
+---------+----------+------------+
| 1 | 10 | 2025-05-30 |
| 2 | 11 | 2025-05-31 |
| 3 | 12 | 2025-06-01 |
+---------+----------+------------+
list_items
+---------+------+
| list_id | item |
+---------+------+
| 1 | A |
| 1 | B |
| 1 | C |
| 2 | A |
| 2 | C |
| 2 | D |
| 3 | B |
| 3 | C |
| 3 | E |
+---------+------+
Task: Write a single SQL query that returns exactly one row: (list_id_small, list_id_large, overlap_count, jaccard) for the unordered pair of lists with the maximum item overlap among eligible lists.
Definitions:
- Let items(Li) be the set of distinct items in list i.
- overlap_count = |items(Li) ∩ items(Lj)|
- jaccard = overlap_count / |items(Li) ∪ items(Lj)|
Tie-breaking rules:
1) Prefer the pair with higher overlap_count.
2) If still tied, prefer the pair with higher jaccard.
3) If still tied, prefer the pair with (list_id_small, list_id_large) in ascending lexicographic order.
Conventions and requirements:
- Represent each unordered pair (Li, Lj) with list_id_small < list_id_large.
- Do not count duplicate items within a list more than once.
- Use only standard SQL constructs (CTEs and window functions are allowed).
- Also briefly explain which indexes you would add on these tables to make this query fast at scale (your explanation is not auto-graded, but is part of the interview discussion).
For the sample data above, the expected row is (1, 2, 2, 0.5).
Tables
lists(list_id INT, owner_id INT, created_at DATE)
list_items(list_id INT, item VARCHAR(10))
Hints
- First restrict to recent lists, then deduplicate (list_id, item) pairs before counting.
- Compute per-list distinct item counts and pairwise overlaps separately, then use |A ∪ B| = |A| + |B| − |A ∩ B| to get the Jaccard denominator.
Return the top-5 list pairs by maximum overlap
Using the same schema and date assumptions as in Question 1:
- lists(list_id INT PRIMARY KEY, owner_id INT, created_at DATE)
- list_items(list_id INT, item VARCHAR)
Only consider lists whose created_at is between '2025-05-26' and '2025-06-01' inclusive.
Sample data:
lists
+---------+----------+------------+
| list_id | owner_id | created_at |
+---------+----------+------------+
| 1 | 10 | 2025-05-30 |
| 2 | 11 | 2025-05-31 |
| 3 | 12 | 2025-06-01 |
+---------+----------+------------+
list_items
+---------+------+
| list_id | item |
+---------+------+
| 1 | A |
| 1 | B |
| 1 | C |
| 2 | A |
| 2 | C |
| 2 | D |
| 3 | B |
| 3 | C |
| 3 | E |
+---------+------+
Task: Write a SQL query that returns the **top 5** unordered list pairs (list_id_small, list_id_large) with the highest item overlap among eligible lists. For each pair, return (list_id_small, list_id_large, overlap_count, jaccard) with the same definitions as in Question 1:
- overlap_count = |items(Li) ∩ items(Lj)| using distinct items per list
- jaccard = overlap_count / |items(Li) ∪ items(Lj)|
Use the same tie-breaking rules as in Question 1 when ordering the results:
1) Higher overlap_count first.
2) If tied, higher jaccard first.
3) If still tied, smaller (list_id_small, list_id_large) first.
Return up to 5 rows ordered by these criteria.
Tables
lists(list_id INT, owner_id INT, created_at DATE)
list_items(list_id INT, item VARCHAR(10))
Hints
- Reuse the same CTE structure from the max-overlap query, but select multiple rows instead of ranking to a single row.
- Order by overlap_count DESC, then jaccard DESC, then list_id_small and list_id_large to apply the tie-breaking rules.