Customers Who Bought Every Product
Problem
A shop keeps its catalogue in product(key) and every sale in purchase(customer_id, product_key). Every product_key in purchase exists in product, and a customer can buy the same product many times. Write a query that returns the customers who have bought every product in the catalogue at least once, as a single column customer_id, sorted.
Examples
Input: product = [5, 6], purchase = [(1, 5), (2, 6), (3, 5), (3, 6), (1, 6)]
Output: [(1,), (3,)]
Why: customers 1 and 3 bought both 5 and 6; customer 2 never bought 5Input: product = [5, 6, 7], purchase = [(1, 5), (1, 5), (1, 6), (2, 5), (2, 6), (2, 7)]
Output: [(2,)]
Why: customer 1 has three rows but only two different productsInput: product = [8], purchase = []
Output: []
Why: edge case, nobody bought anythingHints
0 / 3
Turn the question around: a customer bought everything exactly when the number of different products they bought equals the number of products in the catalogue.
COUNT(product_key) per customer counts rows, so a repeat purchase would be counted twice. COUNT(DISTINCT product_key) counts products.
GROUP BY customer_id, then HAVING COUNT(DISTINCT product_key) = (SELECT COUNT(*) FROM product). HAVING filters groups after they are folded, which WHERE cannot do.
Solution
"Bought every product" is relational division, and the counting form is the one that fits in an interview: group the purchases by customer, count the distinct products in each group, and keep the groups whose count equals the size of the catalogue. DISTINCT inside the count is what stops a customer who bought the same item twice from passing with a product missing, and the comparison has to live in HAVING because the count only exists after GROUP BY has folded the rows. The count is safe because every purchased key exists in product; without that guarantee you would join to product first so stray keys cannot inflate it. The double NOT EXISTS form ("there is no product this customer has not bought") returns the same rows. Grouping costs O(n log n) with a sort or O(n) with hashing.
import sqlite3
QUERY = """
SELECT customer_id
FROM purchase
GROUP BY customer_id
HAVING COUNT(DISTINCT product_key) = (SELECT COUNT(*) FROM product)
ORDER BY customer_id
"""
def run(products, purchases):
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE product (key INTEGER PRIMARY KEY)")
db.execute("CREATE TABLE purchase (customer_id INTEGER, product_key INTEGER REFERENCES product(key))")
db.executemany("INSERT INTO product VALUES (?)", [(k,) for k in products])
db.executemany("INSERT INTO purchase VALUES (?, ?)", purchases)
return db.execute(QUERY).fetchall()
print(run([5, 6], [(1, 5), (2, 6), (3, 5), (3, 6), (1, 6)])) # -> [(1,), (3,)]
print(run([5, 6, 7], [(1, 5), (1, 5), (1, 6), (2, 5), (2, 6), (2, 7)])) # -> [(2,)]
print(run([8], [])) # -> []Stuck on the idea rather than the code? Aggregations & GROUP BY covers it.