Recommending Friends: Suggest New Connections Based on Mutual Friends in a Social Graph

Question

## Problem

Given a social network as an adjacency list, recommend friends to a user based on the number of mutual connections. Return the top `k` non-friends sorted by mutual friend count descending, then by user id ascending on ties.

```python
def recommend_friends(
    graph: dict[int, list[int]],
    user: int,
    k: int
) -> list[int]:
    pass
```

**Example:**
```
graph = {1:[2,3], 2:[1,3,4], 3:[1,2,4,5], 4:[2,3], 5:[3]}
user=1, k=2
# Candidates: 4 (mutual: 2,3 -> 2), 5 (mutual: 3 -> 1)
output -> [4, 5]
```

## Approach

For each non-friend candidate, count `|neighbors(user) INTERSECT neighbors(candidate)|`. Use sets for O(1) lookup. O(n * avg_degree) total.

## Follow-ups
1. The graph has 100 million users. How do you scale this beyond a single machine?
2. Beyond mutual friends, name two other signals you would incorporate into a production recommendation score.
3. A user may block others -- how do you exclude blocked users and users who have blocked the query user?
4. How often should recommendations be recomputed? What triggers an invalidation?

Recommending Friends: Suggest New Connections Based on Mutual Friends in a Social Graph

Question Details

Full Details

Topics

More from Square/Block