Условие

Таблица friendship(user_id, friend_id) — симметричная: если A друг B, есть две строки (A, B) и (B, A). Для пользователя X верните рекомендации: пользователи, которые не являются его друзьями, но имеют ≥ 2 общих друзей с X. Сортировка по убыванию числа общих друзей.

Решение

WITH X_friends AS (
  SELECT friend_id AS fid FROM friendship WHERE user_id = :X
),
candidates AS (
  SELECT f.friend_id AS candidate, COUNT(*) AS mutual_count
  FROM friendship f
  WHERE f.user_id IN (SELECT fid FROM X_friends)
    AND f.friend_id <> :X
    AND f.friend_id NOT IN (SELECT fid FROM X_friends)
  GROUP BY f.friend_id
)
SELECT candidate, mutual_count
FROM candidates
WHERE mutual_count >= 2
ORDER BY mutual_count DESC;

Идея

X_friends — все друзья пользователя X.
Для каждого «друга X» смотрим его друзей (потенциальные кандидаты).
Кандидат — не сам X и не уже друг X.
Считаем сколько друзей X указывают на одного кандидата (=число общих друзей).

Если граф несимметричен

Если в таблице хранится только одна сторона — нужно UNION ALL прямых и обратных:

WITH undirected AS (
  SELECT user_id AS a, friend_id AS b FROM friendship
  UNION
  SELECT friend_id AS a, user_id AS b FROM friendship
)
-- дальше та же логика

Подводные камни

Дубли пар. Если граф симметричный, у одной дружбы две строки — COUNT(*) корректен. Если хранится односторонне — нужно нормализовать.
NOT IN (SELECT ...) и NULL. Если в X_friends есть NULL — NOT IN вернёт пусто. NOT EXISTS или WHERE fid IS NOT NULL.
Сам X. Без friend_id <> :X X сам себе попадёт в рекомендации (через цепочку Y → X).
>= 2. Граница «как минимум 2 общих» — частая.

Эталонный ответ

friendship JOIN X_friends ON user_id = X_friend → COUNT(*) GROUP BY friend_id ≥ 2, исключая уже друзей и самого X. Друг друга — friend-of-friend pattern.

Glassdoor (Meta) — рекомендации друзей через общих знакомых