Friend Recommender
Recommend people by shared connections, graph search with a bug → feature → scale arc.
Problem
A social graph tracks user → friends[]. The starter code has a bug in how it counts shared connections.
Phase 1 — Fix the bug
mutualCount(a, b) is wrong: it double-counts when two people share more than one mutual friend through different paths, and it can include a or b themselves. Count distinct mutual friends, excluding the endpoints.
Phase 2 — Feature
Add recommend(user, k): people reachable from user within k hops who are not already friends with user, ranked by number of mutual friends (descending), then by user id.
Phase 3 — Scale
The graph has millions of edges. Recommendations must avoid exploding over the whole graph when k is small.
What interviewers watch
Distinct counting, excluding immediate friends and self, and a BFS that stops at depth k — the AI often forgets the visited set and the depth bound.