Условие

В таблице friends(user_id, friend_id) каждая дружба представлена двумя строками: (A, B) и (B, A). Для каждой пары пользователей (u1, u2) посчитайте число общих друзей. Выведите топ-10 пар по числу общих друзей. Пары (A, B) и (B, A) считать одной.

Решение

Подход

«Общие друзья» = пользователи, дружащие и с u1, и с u2. Через self-join таблицы friends находим пересечение «друзей u1» с «друзей u2». Чтобы пары не дублировались — условие u1 < u2.

Реализация

WITH pairs AS (
    SELECT
        f1.friend_id AS u1,
        f2.friend_id AS u2,
        f1.user_id   AS common_friend
    FROM friends f1
    JOIN friends f2
      ON f1.user_id = f2.user_id      -- общий друг = same user_id в обеих строках
     AND f1.friend_id < f2.friend_id  -- избегаем дубли пар и self-pairs
)
SELECT
    u1, u2,
    COUNT(DISTINCT common_friend) AS mutual_friends
FROM pairs
GROUP BY u1, u2
ORDER BY mutual_friends DESC
LIMIT 10;

Альтернативный вид через подзапросы

WITH friend_of AS (
    SELECT user_id, friend_id FROM friends
)
SELECT
    LEAST(a.friend_id, b.friend_id) AS u1,
    GREATEST(a.friend_id, b.friend_id) AS u2,
    COUNT(*) AS mutual_friends
FROM friend_of a
JOIN friend_of b
  ON a.user_id = b.user_id
 AND a.friend_id <> b.friend_id
GROUP BY 1, 2
HAVING COUNT(*) > 0
ORDER BY mutual_friends DESC
LIMIT 10;
-- Здесь каждая пара посчитается дважды (a→b и b→a),
-- но LEAST/GREATEST схлопывает их в одну группу.

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

Self-pairs. Без условия friend_id <> user_id (если таковое есть в данных) или f1.friend_id <> f2.friend_id получите «у меня самого со мной 100 общих друзей».
Дубль пары. Без u1 < u2 (или LEAST/GREATEST) каждая пара появится дважды.
Симметричность таблицы. Если у вас только одна сторона дружбы ((A,B) без (B,A)), self-join найдёт не все общие связи. Заранее уточняйте структуру.
COUNT(DISTINCT) vs COUNT(*). Если дружба может быть записана несколько раз (исторические дубликаты) — DISTINCT обязателен.
Производительность. На графе с миллионами рёбер self-join по user_id даёт большой shuffle. Индексы (user_id, friend_id) и партиционирование по user_id существенно ускоряют.

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

Self-join friends f1 ON f1.user_id = f2.user_id находит общих друзей пары. Дополнительно f1.friend_id < f2.friend_id убирает дубли пар и self-pairs. Группировка по паре, COUNT(DISTINCT common_friend) для устойчивости к дубликатам.

Aafreen29/SQL-Interview-Prep: число общих друзей у пары