Walmart: Department Pairs Bought Together More Than by Chance

Hard
1019.

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

ColumnType
basket_idint
line_noint
departmentvarchar

Primary key (together): basket_id, line_no.

One row per line on a register receipt; department is the line's department. Department names are single capitalised words.

Example

The rows must come back in the order shown.

BasketLine

basket_idline_nodepartment
11Grocery
12Dairy
13Produce
21Grocery
22Dairy
31Grocery
32Electronics
41Dairy
42Produce
43Produce
7 more rows

Output

dept_adept_btogether
DairyGrocery3
DairyProduce2
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.

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

ColumnType
basket_idint
line_noint
departmentvarchar

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_idline_nodepartment
11Grocery
12Dairy
13Produce
21Grocery
22Dairy
31Grocery
32Electronics
41Dairy
42Produce
43Produce
51Electronics
52Toys
61Grocery
62Dairy
63Bakery
71Grocery
72Produce

Output

dept_adept_btogether
DairyGrocery3
DairyProduce2

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_b

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