Recommend New Friends from a Mutual-Friendship Graph and Scale the Approach

This round is framed as problem solving rather than pure coding. The interviewer asks you to work out how a social product should suggest new friends to a user, using the graph of existing friendships. Expect the session to be mostly conversation: you reason about the approach together, write a small amount of real code for the core logic, and sketch the surrounding pieces in pseudocode near the end. ### Constraints and Clarifications - Friendships are mutual, so the graph is undirected. Assume it is available as an adjacency map from a user ID to the set of that user's friends' IDs. - A suggestion must never be the user themself or someone who is already their friend. - The story does not specify the graph's size, how many suggestions to show, or how fresh they must be; settle those with the interviewer rather than assuming them silently. ### Clarifying Questions - How many suggestions should be returned, and are they computed when the page loads or ahead of time? - Besides the graph, which rules apply: blocked users, pending friend requests, suggestions the user already dismissed? - How large is the graph, and are there accounts with enormous friend counts? - When two candidates are equally good, which should come first? ### Part 1 — Core recommendation logic Write a function that returns the top `k` friend suggestions for one user from the friendship graph. Explain how you score candidates, how you break ties, and the time and memory cost in terms of the graph's structure. ```hint Evidence in the graph Start from the people the user already knows and ask what the graph can tell you about whether a stranger belongs in the same circle. ``` #### What This Part Should Cover - Bounded candidate generation that excludes the user and existing friends - A scoring rule with an explicit, deterministic tie-break - Correct top-k selection and its cost expressed through node degrees - Behavior for users with no friends or very small networks ### Part 2 — Make it production-ready Now discuss how you would improve suggestion quality and run the recommender on a graph far too large to expand on every request. Close with pseudocode for the end-to-end flow, from computing suggestions to showing them. ```hint Weak and strong evidence Consider which connections in the graph are weak evidence of a real relationship, and which parts of the work could happen before the user ever opens the page. ``` #### What This Part Should Cover - Richer ranking signals, and how very well-connected users distort a naive score - Exclusion rules and user feedback such as dismissals - Precomputing versus computing on demand, and keeping results fresh as friendships change - How you would measure whether suggestions are good ### What a Strong Answer Covers - Starts from a correct, simple baseline and refines it, rather than opening with a complex system - Keeps the code short and correct while narrating the trade-offs - States cost in terms of degrees and spots the skew problem without being prompted - Applies exclusion and privacy rules consistently, including at serving time - Uses pseudocode deliberately for the parts not worth fully implementing in the round ### Follow-up Questions - A user's friends include several accounts with millions of connections. How do you keep the per-user work bounded without losing good suggestions? - How would you explain to the user why a particular person was suggested? - What would you show a brand-new user who has no friends yet? - Suggestions computed overnight are stale after a user adds several friends in the morning. How do you refresh only the users affected?