Friend Suggestions From Two or More Mutual Friends

Hard
442.

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

ColumnType
user_idint
handlevarchar

Primary key: user_id.

One row per account.

Table: friendships

ColumnType
user_aint
user_bint
sincedate

Primary key (together): user_a, user_b.

One row per friendship, always with user_a < user_b; both are rows of users.

Table: blocks

ColumnType
blocker_idint
blocked_idint

Primary key (together): blocker_id, blocked_id.

blocker_id has blocked blocked_id. A block in either direction rules a suggestion out.

Example

The rows must come back in the order shown.

users

user_idhandle
1aarav.eats
2diya_travels
3kabir.codes
4meera_fit
5rohan.memes
6zara_ootd

friendships

user_auser_bsince
122023-01-10
132023-02-14
242023-03-01
342023-04-22
252023-05-05
352023-06-30
462024-01-01
562024-02-02

blocks

blocker_idblocked_id
62

Output

user_idsuggested_idmutual_friends
233
453
142
152
362
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.

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

ColumnType
user_idint
handlevarchar

Primary key: user_id.

One row per account.

Table: friendships

ColumnType
user_aint
user_bint
sincedate

Primary key: user_a, user_b.

One row per friendship, always with user_a < user_b; both are rows of users.

Table: blocks

ColumnType
blocker_idint
blocked_idint

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_idhandle
1aarav.eats
2diya_travels
3kabir.codes
4meera_fit
5rohan.memes
6zara_ootd

friendships

user_auser_bsince
122023-01-10
132023-02-14
242023-03-01
342023-04-22
252023-05-05
352023-06-30
462024-01-01
562024-02-02

blocks

blocker_idblocked_id
62

Output

user_idsuggested_idmutual_friends
233
453
142
152
362

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_id

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