Write SQL to compute max-overlap lists

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.

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).

Table lists

column	type	constraints
list_id	INT	PRIMARY KEY
owner_id	INT	NOT NULL
created_at	DATE	NOT NULL

Sample data:

created_at	list_id	owner_id
2025-05-30	1	10
2025-05-31	2	11
2025-06-01	3	12

Table list_items

column	type	constraints
list_id	INT	NOT NULL
item	VARCHAR(10)	NOT NULL

Sample data:

item	list_id
A	1
B	1
C	1
A	2
C	2
D	2
B	3
C	3
E	3

Expected output

One row with the unordered pair of lists (list_id_small < list_id_large) from 2025-05-26 to 2025-06-01 that has the maximum item overlap, along with the overlap count and Jaccard similarity. For the sample data, lists 1 and 2 have the maximum overlap (2 items, Jaccard 0.5) and win the tie-breakers.

jaccard	list_id_large	list_id_small	overlap_count
0.5	2	1	2

Hints

1. First restrict to recent lists, then deduplicate (list_id, item) pairs before counting.
2. Compute per-list distinct item counts and pairwise overlaps separately, then use |A ∪ B| = |A| + |B| − |A ∩ B| to get the Jaccard denominator.
3. Use ROW_NUMBER() ordered by overlap_count, then jaccard, then list_id_small/list_id_large to pick the single best pair.

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.

Table lists

column	type	constraints
list_id	INT	PRIMARY KEY
owner_id	INT	NOT NULL
created_at	DATE	NOT NULL

Sample data:

created_at	list_id	owner_id
2025-05-30	1	10
2025-05-31	2	11
2025-06-01	3	12

Table list_items

column	type	constraints
list_id	INT	NOT NULL
item	VARCHAR(10)	NOT NULL

Sample data:

item	list_id
A	1
B	1
C	1
A	2
C	2
D	2
B	3
C	3
E	3

Expected output

Up to 5 rows listing unordered list pairs (list_id_small < list_id_large) from 2025-05-26 to 2025-06-01, with their overlap_count and Jaccard similarity, ordered by overlap_count DESC, then jaccard DESC, then (list_id_small, list_id_large) ASC. With the sample data there are only three pairs, so all three are returned.

jaccard	list_id_large	list_id_small	overlap_count
0.5	2	1	2
0.5	3	1	2
0.2	3	2	1

Hints

1. Reuse the same CTE structure from the max-overlap query, but select multiple rows instead of ranking to a single row.
2. Order by overlap_count DESC, then jaccard DESC, then list_id_small and list_id_large to apply the tie-breaking rules.
3. Use LIMIT or FETCH FIRST N ROWS ONLY (depending on SQL dialect) to restrict the output to the top 5 pairs.