Design Friend Recommendations for a Large Friendship Graph

Design a friend-recommendation algorithm given a list of users and friendship pairs. Explain a recommendation strategy, its ranking policy, and how you would make it practical for approximately 100000 users and 1.5 million friendship pairs. ### Constraints The task permits designing the strategy; friends-of-friends and popularity are example approaches, not a fixed required ranking. Clarify friendship direction, eligibility, output size, and ties. Do not claim that one strategy is the uniquely correct output for the supplied graph. ### Clarifying Questions - Are friendships undirected, and should existing friends and the requesting user be excluded? - How many users should be recommended, and how are ties resolved? - Is mutual-friend count, popularity, or another objective the primary ranking signal? - Must the system support graph updates or only queries against a fixed snapshot? ```hint Examine high-degree users A two-hop traversal can visit far more relationships than the requesting user's immediate friend count suggests. ``` ### What a Strong Answer Covers - An explicit, explainable ranking strategy and eligibility policy. - Graph representation, candidate generation, score aggregation, and top-result selection. - Degree skew, memory costs, reproducible evaluation, and quality limitations at the stated scale. ### Follow-up Questions - How would you recommend users when the requesting user has no friends? - How would you prevent popularity from overwhelming more relevant local candidates?