Friend Suggestions From Two or More Mutual Friends
"People you may know" suggests two users to each other when they are not friends yet, have at least two mutual friends, and neither has blocked the other.
- Difficulty: Hard
- Topics: Joins, Aggregation, Subqueries
- Dialect: MySQL
- Problem: #442
Problem statement
"People you may know" suggests two users to each other when they are not friends yet, have at least two mutual friends, and neither has blocked the other. Friendship is mutual and each friendship is stored once, with user_a < user_b.
Return each suggested pair once with the columns user_id (the smaller id), suggested_id (the larger id) and mutual_friends, ordered by mutual_friends descending, then user_id, then suggested_id.
Tables
Table: users
| Column | Type |
|---|---|
| user_id | int |
| handle | varchar |
Primary key: user_id.
One row per account.
Table: friendships
| Column | Type |
|---|---|
| user_a | int |
| user_b | int |
| since | date |
Primary key: user_a, user_b.
One row per friendship, always with user_a < user_b; both are rows of users.
Table: blocks
| Column | Type |
|---|---|
| blocker_id | int |
| blocked_id | int |
Primary key: blocker_id, blocked_id.
blocker_id has blocked blocked_id. A block in either direction rules a suggestion out.
Examples
Example 1
users
| user_id | handle |
|---|---|
| 1 | aarav.eats |
| 2 | diya_travels |
| 3 | kabir.codes |
| 4 | meera_fit |
| 5 | rohan.memes |
| 6 | zara_ootd |
friendships
| user_a | user_b | since |
|---|---|---|
| 1 | 2 | 2023-01-10 |
| 1 | 3 | 2023-02-14 |
| 2 | 4 | 2023-03-01 |
| 3 | 4 | 2023-04-22 |
| 2 | 5 | 2023-05-05 |
| 3 | 5 | 2023-06-30 |
| 4 | 6 | 2024-01-01 |
| 5 | 6 | 2024-02-02 |
blocks
| blocker_id | blocked_id |
|---|---|
| 6 | 2 |
Output
| user_id | suggested_id | mutual_friends |
|---|---|---|
| 2 | 3 | 3 |
| 4 | 5 | 3 |
| 1 | 4 | 2 |
| 1 | 5 | 2 |
| 3 | 6 | 2 |
How to solve Friend Suggestions From Two or More Mutual Friends
Storing each friendship once with user_a < user_b saves space but makes "who are x's friends?" awkward, so the first step doubles the edges: a UNION ALL of (user_a, user_b) and (user_b, user_a) gives a directed table f(u, v) meaning "v is a friend of u".
Two users x < y share the mutual friend m exactly when f holds both (x, m) and (y, m). Self-joining f on the friend column (f2.v = f1.v) with f1.u < f2.u produces one row per (pair, mutual friend) and each unordered pair only once, so COUNT(*) grouped by the pair is the number of mutual friends.
Two anti joins remove pairs that must not be suggested: an existing friendship (looked up in the stored orientation, since f1.u < f2.u) and a block in either direction. HAVING COUNT(*) >= 2 keeps strong suggestions. The alternative instead walks all pairs of users and counts mutual friends with a correlated subquery that normalises each lookup with LEAST/GREATEST — clearer, but quadratic in users times friends. The join version only touches pairs that actually share someone.
Reference solution (MySQL)
WITH f AS (
SELECT user_a AS u, user_b AS v FROM friendships
UNION ALL
SELECT user_b AS u, user_a AS v FROM friendships
)
SELECT f1.u AS user_id, f2.u AS suggested_id, COUNT(*) AS mutual_friends
FROM f f1
JOIN f f2 ON f2.v = f1.v AND f1.u < f2.u
WHERE NOT EXISTS (SELECT 1 FROM friendships x WHERE x.user_a = f1.u AND x.user_b = f2.u)
AND NOT EXISTS (SELECT 1 FROM blocks b
WHERE (b.blocker_id = f1.u AND b.blocked_id = f2.u)
OR (b.blocker_id = f2.u AND b.blocked_id = f1.u))
GROUP BY f1.u, f2.u
HAVING COUNT(*) >= 2
ORDER BY mutual_friends DESC, user_id, suggested_idAnother way
SELECT user_id, suggested_id, mutual_friends FROM (
SELECT a.user_id, b.user_id AS suggested_id,
(SELECT COUNT(*) FROM users m
WHERE EXISTS (SELECT 1 FROM friendships x WHERE x.user_a = LEAST(a.user_id, m.user_id) AND x.user_b = GREATEST(a.user_id, m.user_id))
AND EXISTS (SELECT 1 FROM friendships y WHERE y.user_a = LEAST(b.user_id, m.user_id) AND y.user_b = GREATEST(b.user_id, m.user_id))
) AS mutual_friends
FROM users a JOIN users b ON a.user_id < b.user_id
WHERE NOT EXISTS (SELECT 1 FROM friendships x WHERE x.user_a = a.user_id AND x.user_b = b.user_id)
AND NOT EXISTS (SELECT 1 FROM blocks k WHERE k.blocker_id IN (a.user_id, b.user_id) AND k.blocked_id IN (a.user_id, b.user_id))
) t
WHERE mutual_friends >= 2
ORDER BY mutual_friends DESC, user_id, suggested_id← Average Reply Time in Direct Messages · Longest Daily Posting Streak per Creator →