Friend Suggestions Based on Mutual Connections

Problem Statement

You are given a social network represented as an adjacency list (friendships between users). Implement the following:

1. shortestPath(userA, userB) — Return the sequence of users in the shortest path from A to B
2. shortestDistance(userA, userB) — Return the number of hops between A and B
3. suggestFriends(user) — For a given user, suggest friends ranked by number of mutual connections (only suggest users who are NOT already direct friends)

Constraints

• 1 <= users <= 10^4
• Graph is undirected (friendship is mutual)
• Users may be disconnected (handle unreachable case)
• suggestFriends should return top suggestions sorted by mutual count (descending)

Example

Graph:
  Alice — Bob
  Alice — Charlie
  Bob — Charlie
  Bob — Dave
  Charlie — Dave
  Dave — Eve

shortestPath(Alice, Eve) → [Alice, Bob, Dave, Eve]
shortestDistance(Alice, Eve) → 3
suggestFriends(Alice) → [Dave]  
// Dave shares 2 mutual friends (Bob, Charlie) with Alice but isn't directly connected

What the Interviewer Expects

1. Part 1 (BFS with parent tracking): Standard BFS from source, maintain parent map, reconstruct path from destination back to source.
2. Part 2 (reuse BFS): Same BFS, just return depth when destination is found. Show code reusability.
3. Part 3 (mutual connections):
   • Get user's friends (direct neighbors)
   • For each friend-of-friend (2 hops away), count how many mutual friends they share
   • Exclude users who are already direct friends
   • Sort by mutual count descending
4. Code structure — interviewer evaluates how you build incrementally. Don't rewrite BFS for each part.

Follow-ups

1. How would you scale this for LinkedIn's 900M+ users? (Can't load full graph in memory)
2. What if you want 2nd AND 3rd degree suggestions with different weights?
3. How would you handle real-time updates (new friendship added) without recomputing everything?
4. How does this relate to LinkedIn's "People You May Know" feature in production?