Recommend Connections Through Mutual Friends and Evaluate the Ranking

A social network is represented by users and undirected friendship edges. Design a recommendation approach that suggests other users to connect with based on mutual friends. Do not recommend someone who is already directly connected to the target user, and do not recommend the target user themself. ### Part 1 — Generate connection candidates Explain how you would find and deduplicate eligible users who share at least one mutual friend with the target. Describe the graph representation and the cost of generating candidates. #### What This Part Should Cover - Two-hop traversal that excludes the target and existing friends. - Distinct mutual-friend counts without duplicate edges inflating the result. - Behavior for an isolated user and a highly connected neighborhood. ### Part 2 — Score candidates and evaluate the list Propose a score between 0 and 1 for each recommendation and explain what it means. Then explain whether NDCG is suitable for assigning that individual score or for evaluating a ranked list, and identify the extra data required to calculate it. No particular normalization formula, relevance labels, output ordering, tie policy, or recommendation limit is supplied. Treat those as design choices to explain, not as a hidden exact-output contract. AI coding tools may assist implementation; describe what you would independently verify. #### What This Part Should Cover - A justified bounded affinity score and the difference between a normalized heuristic and a calibrated probability. - The role of relevance labels, discounting by rank, ideal ranking, and zero-relevance cases in NDCG. - Separation between generating predictions and evaluating them against independent outcomes. ### What a Strong Answer Covers - An explicit path from the friendship graph to eligible candidates, scores, and a ranking. - Clear ownership of unspecified score and tie semantics instead of treating NDCG as a per-user probability. - Tests that validate exclusion, deduplication, normalization, and evaluation assumptions even when an AI tool writes the implementation. ### Follow-up Questions - How can a high-degree user distort raw mutual-friend counts, and how does your score respond? - Why is evaluating a ranking with the same mutual-friend heuristic used to generate it potentially circular?