Walmart: Department Pairs Bought Together More Than by Chance
A Walmart store planner deciding which departments to place near each other wants the department pairs that shoppers buy together more often than chance…
- Difficulty: Hard
- Topics: Joins, Aggregation, Subqueries
- Dialect: MySQL
- Problem: #1019
Problem statement
A Walmart store planner deciding which departments to place near each other wants the department pairs that shoppers buy together more often than chance would predict — a lift above 1.
Let N be the number of baskets, n(A) the number of baskets containing department A, and n(A,B) the number containing both. A pair has lift above 1 when n(A,B) * N > n(A) * n(B). Considering pairs bought together in at least 2 baskets, return dept_a, dept_b (with dept_a alphabetically before dept_b) and together (n(A,B)) for every pair with lift above 1. A basket with several lines from one department counts once for it. Order by together descending, then dept_a, then dept_b.
A practice scenario set at Walmart: the tables and data are invented, and this is not a question from, or endorsed by, Walmart.
Tables
Table: BasketLine
| Column | Type |
|---|---|
| basket_id | int |
| line_no | int |
| department | varchar |
Primary key: basket_id, line_no.
One row per line on a register receipt; department is the line's department. Department names are single capitalised words.
Examples
Example 1
BasketLine
| basket_id | line_no | department |
|---|---|---|
| 1 | 1 | Grocery |
| 1 | 2 | Dairy |
| 1 | 3 | Produce |
| 2 | 1 | Grocery |
| 2 | 2 | Dairy |
| 3 | 1 | Grocery |
| 3 | 2 | Electronics |
| 4 | 1 | Dairy |
| 4 | 2 | Produce |
| 4 | 3 | Produce |
| 5 | 1 | Electronics |
| 5 | 2 | Toys |
| 6 | 1 | Grocery |
| 6 | 2 | Dairy |
| 6 | 3 | Bakery |
| 7 | 1 | Grocery |
| 7 | 2 | Produce |
Output
| dept_a | dept_b | together |
|---|---|---|
| Dairy | Grocery | 3 |
| Dairy | Produce | 2 |
How to solve Walmart: Department Pairs Bought Together More Than by Chance
Market-basket questions are all about counting at the right grain. A receipt with two Produce lines must count once for Produce, so the first step is SELECT DISTINCT basket_id, department — one row per basket and department. Every later count is a count of baskets, not of lines.
Pairs come from joining that set to itself on basket_id. The condition a.department < b.department keeps each unordered pair once (Dairy–Grocery, never also Grocery–Dairy) and drops a department paired with itself; grouping by the pair counts n(A,B). Separately, a grouped count gives n(A) per department, and one more count gives N. Joining the three puts all four numbers on one row.
Lift is n(A,B)·N / (n(A)·n(B)), and lift above 1 is the cross-multiplied test together * N > n(A) * n(B) — integers only, so there is no rounding to argue about. A pair that occurs in two baskets can still fail it when both departments are in most baskets anyway, which is exactly what lift is for.
The alternative pairs raw lines and uses COUNT(DISTINCT basket_id) to undo the duplicates, with the department and total counts as scalar subqueries. The self join is quadratic in the departments of a basket, which stays small for real receipts.
Reference solution (MySQL)
WITH bd AS (
SELECT DISTINCT basket_id, department FROM BasketLine
), total AS (
SELECT COUNT(DISTINCT basket_id) AS baskets FROM BasketLine
), dc AS (
SELECT department, COUNT(*) AS cnt FROM bd GROUP BY department
), pairs AS (
SELECT a.department AS dept_a, b.department AS dept_b, COUNT(*) AS together
FROM bd a
JOIN bd b ON b.basket_id = a.basket_id AND a.department < b.department
GROUP BY a.department, b.department
)
SELECT p.dept_a, p.dept_b, p.together
FROM pairs p
JOIN dc da ON da.department = p.dept_a
JOIN dc db ON db.department = p.dept_b
CROSS JOIN total t
WHERE p.together >= 2
AND p.together * t.baskets > da.cnt * db.cnt
ORDER BY p.together DESC, p.dept_a, p.dept_bAnother way
SELECT dept_a, dept_b, together FROM (
SELECT a.department AS dept_a, b.department AS dept_b, COUNT(DISTINCT a.basket_id) AS together
FROM BasketLine a
JOIN BasketLine b ON b.basket_id = a.basket_id AND a.department < b.department
GROUP BY a.department, b.department
) p
WHERE together >= 2
AND together * (SELECT COUNT(DISTINCT basket_id) FROM BasketLine)
> (SELECT COUNT(DISTINCT basket_id) FROM BasketLine x WHERE x.department = p.dept_a)
* (SELECT COUNT(DISTINCT basket_id) FROM BasketLine y WHERE y.department = p.dept_b)
ORDER BY together DESC, dept_a, dept_b← Walmart: Truck Routes Rebuilt From Store Geofence Pings · Walmart: Understaffed Stretches on the Sales Floor →