Q4 - People You May Know (Ranking Friend Suggestions)

Scenario: You are given a social graph as a list of undirected friendships, each [a, b] meaning users a and b are friends, plus one user id. Build the feature that suggests People You May Know: other users this person likely knows but is not yet friends with.

Part 1. Return a ranked list of suggested user ids for user, ordered by the number of mutual friends they share (friends the two have in common), most first. Exclude the user themselves and anyone already their friend, and only suggest someone with at least one mutual friend. Break ties by smaller id.

Input:  friendships = [[0,1],[0,2],[0,3],[1,4],[2,4],[3,4],[1,5],[2,5],[3,6],[3,7],[3,8]]
        user = 0
Output: [4, 5, 6, 7, 8]
Why: You (0) are friends with 1, 2, 3. Candidate 4 shares all three (3 mutual),
        candidate 5 shares 1 and 2 (2 mutual), and 6, 7, 8 each share only friend 3
        (1 mutual). Ranked by mutual count, ties by id: [4, 5, 6, 7, 8].

Part 1: Count Mutual Friends, Then Rank

The suggestions live two hops out (friends of your friends), and getting there takes three small steps.

Step 1: Build the friend map

Turn the flat edge list into an adjacency map: friendsOf[x] is the set of everyone x is friends with. Each [a, b] adds b to a's set and a to b's, since friendship goes both ways.

build friendsOf from the edges:

   0  ->  {1, 2, 3}          (you)
   1  ->  {0, 4, 5}
   2  ->  {0, 4, 5}
   3  ->  {0, 4, 6, 7, 8}    (friend 3 is friends with a crowd)
   4  ->  {1, 2, 3}
   5  ->  {1, 2}
   6, 7, 8  ->  {3}

Step 2: Walk two hops and tally mutual friends

Your friends are friendsOf[user], here {1, 2, 3}. For each friend, look at their friends. Anyone who is not you and not already your friend is a candidate, and every time you reach them you have found one more friend you share, so bump their tally.

tally each stranger reachable through a friend:

   through friend 1 (friends 4, 5):     4 -> 1,  5 -> 1
   through friend 2 (friends 4, 5):     4 -> 2,  5 -> 2
   through friend 3 (friends 4,6,7,8):  4 -> 3,  6 -> 1,  7 -> 1,  8 -> 1

   mutualCount = { 4: 3, 5: 2, 6: 1, 7: 1, 8: 1 }

That is two nested loops: your friends, then their friends, bumping a tally for every stranger you reach.

for friend in my_friends:                        # a friend of yours
    for candidate in friends_of[friend]:         # a friend of your friend
        if candidate != user and candidate not in my_friends:
            mutual_count[candidate] = mutual_count.get(candidate, 0) + 1   # one more shared friend

Step through that walk frame by frame. Each of your friends lights up in turn, and the strangers they connect you to climb the tally on the right:

1 / 5

Step 3: Rank the candidates

Sort the tallied candidates by mutual count (descending), breaking ties by smaller id.

sort mutualCount by (count desc, id asc):

   { 4:3, 5:2, 6:1, 7:1, 8:1 }  ->  [4, 5, 6, 7, 8]

Notice that 6, 7, and 8 already look like weak suggestions: your only link to them is the single friend 3, who happens to be connected to a crowd. Hold that thought, it is exactly what Part 2 fixes.

# O(F) time, F = total friendship links | O(V) space
def suggestions(friendships, user):
    friends_of = {}
    for a, b in friendships:
        friends_of.setdefault(a, set()).add(b)
        friends_of.setdefault(b, set()).add(a)
    my_friends = friends_of.get(user, set())
    mutual_count = {}
    for friend in my_friends:                        # a friend of yours
        for candidate in friends_of[friend]:         # a friend of your friend
            if candidate != user and candidate not in my_friends:
                mutual_count[candidate] = mutual_count.get(candidate, 0) + 1
    # most mutual friends first; ties broken by smaller id
    return sorted(mutual_count, key=lambda c: (-mutual_count[c], c))

Part 2: Ignore the Friend Who Knows Everyone

The interviewer raises the real-world problem: a hub, someone connected to thousands of people, a celebrity, a brand page, a bot, makes everyone look like a "mutual friend" of everyone else. In Example 1, candidates 6, 7, and 8 were suggested only because you both know user 3, who is friends with a crowd. That is noise, not a real connection.

So add a threshold maxDegree: a shared friend only counts as a mutual connection if their own friend count is at most maxDegree. A hub above that line is skipped entirely, for every candidate. Everything else is the same ranking as Part 1.

Input:  friendships = [[0,1],[0,2],[0,3],[1,4],[2,4],[3,4],[1,5],[2,5],[3,6],[3,7],[3,8]]
        user = 0,  maxDegree = 3
Output: [4, 5]
Why: Friend 3 has 5 friends, above maxDegree = 3, so 3 is a hub and no longer
        counts. That erases 6, 7, 8 (their only link to you was hub 3) and drops
        candidate 4 from 3 mutual to 2 (via friends 1 and 2). Result: [4, 5].

Concretely, it is Part 1 with one extra guard slotted in.

Step 1: Measure each friend's degree

A friend's degree is simply how many friends they have, the size of their set in friendsOf. Compute it once, and any friend whose degree tops maxDegree is a hub.

degree = size of each friend set, with maxDegree = 3:

   friend 1: degree 3   (ok)
   friend 2: degree 3   (ok)
   friend 3: degree 5   (hub, 5 > 3)

Step 2: Skip the hubs while you tally

Now run the exact same two-hop walk as Part 1, with one guard: before counting a friend's friends, skip that friend entirely if its degree is above maxDegree. A hub then contributes to no candidate at all, and computing each degree is O(1) (the set's size), so the filter is free.

It is the Part 1 walk with a single guard added at the top of the outer loop.

for friend in my_friends:
    if len(friends_of[friend]) > max_degree:     # a hub is not a meaningful signal, skip it
        continue
    for candidate in friends_of[friend]:         # otherwise, tally exactly as before
        if candidate != user and candidate not in my_friends:
            mutual_count[candidate] = mutual_count.get(candidate, 0) + 1

Watch friend 3 get skipped, and the noise it created, candidates 6, 7, and 8, vanish:

1 / 5

Ranking the survivors then works exactly as in Part 1.

# O(F) time | O(V) space
def suggestions_ignoring_hubs(friendships, user, max_degree):
    friends_of = {}
    for a, b in friendships:
        friends_of.setdefault(a, set()).add(b)
        friends_of.setdefault(b, set()).add(a)
    my_friends = friends_of.get(user, set())
    mutual_count = {}
    for friend in my_friends:
        if len(friends_of[friend]) > max_degree:     # a hub is not a meaningful signal, skip it
            continue
        for candidate in friends_of[friend]:
            if candidate != user and candidate not in my_friends:
                mutual_count[candidate] = mutual_count.get(candidate, 0) + 1
    return sorted(mutual_count, key=lambda c: (-mutual_count[c], c))

Complexity Analysis

• Both parts: O(F) time, where F is the total number of friendship links (each edge is added twice to the adjacency map, then walked when its endpoints are visited). Concretely, the two-hop scan touches each of the user's friends and each of their friends once, which sums to the degrees of the user's friends. Ranking the candidates adds O(k log k) for k candidates.
• Space: O(V + F) for the adjacency map, plus O(k) for the candidate tallies.
• The two-hop walk is the whole efficiency story: you never compare the user against the whole network, only against the neighborhood two steps out, which is where every real suggestion lives.

Final Notes

1. Suggestions live two hops out. You do not score the whole graph, only the friends of your friends. Building the adjacency map and walking out two steps is the entire engine, and saying "I only need the two-hop neighborhood" is the efficiency insight.
2. A mutual-friend count is just a tally on that walk. Every time a friend-of-a-friend shows up, you have found one more shared friend. No set intersections per candidate, one pass does it.
3. Exclude yourself and your existing friends, and demand at least one mutual. These three filters are easy to forget and are exactly what a careless answer gets wrong. State them before you code.
4. Hubs are noise. The person connected to everyone makes strangers look related. Capping the degree of a shared friend, or weighting it down, is the refinement that turns a toy into something you would actually ship. It is the same instinct behind ranking real recommendation systems. 🚀