Find Product Recommendation Pairs - Practice Coding Problems

Find Product Recommendation Pairs - Problem

Database Medium

Amazon wants to implement the "Customers who bought this also bought..." feature based on co-purchase patterns.

Given two tables:

ProductPurchases: Records of user purchases with quantities
ProductInfo: Product details including category and price

Write a solution to:

Identify distinct product pairs frequently purchased together by the same customers (where product1_id < product2_id)
For each product pair, determine how many customers purchased both products

A product pair is considered for recommendation if at least 3 different customers have purchased both products.

Return results ordered by customer_count in descending order, then by product1_id ascending, then by product2_id ascending.

Table Schema

ProductPurchases

Column Name	Type	Description
`user_id` PK	int	Unique identifier for each user
`product_id` PK	int	Unique identifier for each product
`quantity`	int	Quantity of product purchased by user

Primary Key: (user_id, product_id)

ProductInfo

Column Name	Type	Description
`product_id` PK	int	Unique identifier for each product
`category`	varchar	Product category
`price`	decimal	Product price

Primary Key: product_id

Input & Output

Example 1 — Basic Product Pairs

Input Tables:

ProductPurchases

user_id	product_id	quantity
1	101	2
1	102	1
1	103	3
2	101	1
2	102	3
3	101	2
3	102	1
3	104	2
4	101	1
4	103	2

ProductInfo

product_id	category	price
101	Electronics	299.99
102	Electronics	199.99
103	Books	29.99
104	Home	89.99

Output:

product1_id	product2_id	customer_count
101	102	3

💡 Note:

Products 101 and 102 are purchased together by users 1, 2, and 3 (3 customers total), meeting the minimum threshold of 3. Other pairs like (101,103) and (101,104) only have 2 customers each, so they don't qualify.

Example 2 — Multiple Qualifying Pairs

Input Tables:

ProductPurchases

user_id	product_id	quantity
1	201	1
1	202	2
2	201	1
2	202	1
3	201	3
3	202	1
4	201	2
4	202	1
1	203	1
2	203	2
3	203	1

ProductInfo

product_id	category	price
201	Fashion	79.99
202	Fashion	49.99
203	Beauty	24.99

Output:

product1_id	product2_id	customer_count
201	202	4
201	203	3

💡 Note:

Two product pairs qualify: (201,202) with 4 customers and (201,203) with 3 customers. Results are ordered by customer_count descending, so (201,202) appears first.

Example 3 — No Qualifying Pairs

Input Tables:

ProductPurchases

user_id	product_id	quantity
1	301	1
1	302	2
2	301	1
3	302	1
4	303	2

ProductInfo

product_id	category	price
301	Sports	159.99
302	Sports	89.99
303	Toys	39.99

Output:

product1_id	product2_id	customer_count

💡 Note:

Only user 1 bought both products 301 and 302 together. Since this is less than the required 3 customers, no product pairs qualify for recommendation.

Constraints

1 ≤ user_id ≤ 1000
1 ≤ product_id ≤ 10000
1 ≤ quantity ≤ 100
At least 3 different customers must purchase both products for recommendation
Product pairs must satisfy product1_id < product2_id

Visualization

Tap to expand

Understanding the Visualization

Input Tables

ProductPurchases and ProductInfo

Self-Join

Join purchases on user_id

Filter & Count

Product pairs with 3+ customers

Key Takeaway

🎯 Key Insight: Self-join reveals hidden purchase patterns for personalized product recommendations

Asked in

a Amazon 28 G Google 15 f Meta 12

Use self-join on ProductPurchases table to find product pairs bought by same users. Apply WHERE product1_id < product2_id to avoid duplicates, then GROUP BY and count distinct customers with HAVING COUNT(*) >= 3.

Table Schema

ProductPurchases

Column Name	Type	Description
`user_id` PK	int	Unique identifier for each user
`product_id` PK	int	Unique identifier for each product
`quantity`	int	Quantity of product purchased by user

Primary Key: (user_id, product_id)

ProductInfo

Column Name	Type	Description
`product_id` PK	int	Unique identifier for each product
`category`	varchar	Product category
`price`	decimal	Product price

Primary Key: product_id

Common Approaches

Approach	Time	Space	Notes
✓ Self-Join with Aggregation	O(n²)	O(p²)	Join ProductPurchases with itself to find product pairs bought by same users

Self-Join with Aggregation — Algorithm Steps

Step 1: Self-join ProductPurchases on user_id to create product pairs
Step 2: Filter where product1_id < product2_id to avoid duplicate pairs
Step 3: Group by product pair and count distinct customers
Step 4: Filter pairs with at least 3 customers and order results

Visualization

Tap to expand

Step-by-Step Walkthrough

Self-Join

Join on user_id

Filter

product1_id < product2_id

Count

Count distinct customers

Code -

solution.c — C

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Self-join creates combinations of purchases per user

⚠ Quadratic Growth

Space Complexity

O(p²)

Storage for all valid product pairs

✓ Linear Space

23.5K Views

Medium-High Frequency

~18 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Table Schema

Input & Output

Constraints

Visualization

Related Problems

Table Schema

Common Approaches

Self-Join with Aggregation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler