How should I practice Mutual-Friend Recommendations?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Meta onsite interview problems in FastPrep.

Is Mutual-Friend Recommendations associated with Meta?

FastPrep tags this as a Meta onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Mutual-Friend Recommendations

Learn this problem

● Medium

MetaFULLTIMEONSITE INTERVIEW

See Meta hiring insights

Problem statement

An undirected social graph contains n users numbered from 0 to n - 1. Every entry friendships[i] = [a, b] means that users a and b are direct friends.

Recommend users for user according to these rules:

Do not recommend user or anyone already directly connected to user.
A remaining user is eligible only if they share at least one mutual friend with user.
A candidate's score is the number of distinct mutual friends they share with user.
Rank candidates by score from greatest to least. Break equal-score ties by user ID from least to greatest.

Return the first k ranked user IDs, or every eligible candidate if fewer than k exist.

Interview follow-up

To evaluate this rule offline, remove a holdout set of known friendship edges, generate recommendations from the remaining graph, and measure precision at k and recall at k against those held-out connections. This evaluation discussion does not change the judged return value.

Function

recommendFriends(n: int, friendships: int[][], user: int, k: int) → int[]

Examples

Example 1

n = 6friendships = [[0,1],[0,2],[1,3],[2,3],[1,4],[2,5]]user = 0k = 3return = [3,4,5]

User 3 shares friends 1 and 2 with user 0, so its score is 2. Users 4 and 5 each score 1; their tie is ordered by ID.

Example 2

n = 5friendships = [[0,1],[0,2],[1,3],[2,3],[1,4],[2,4]]user = 0k = 1return = [3]

Users 3 and 4 both have score 2. The ID tie-break ranks 3 first, and k = 1.

Example 3

n = 5friendships = [[0,1],[0,2],[1,2],[1,3],[2,4]]user = 0k = 5return = [3,4]

Users 1 and 2 are already direct friends and remain excluded even though they are connected through each other. Candidates 3 and 4 each have one mutual friend.

Example 4

n = 4friendships = [[0,1],[2,3]]user = 0k = 2return = []

User 0 has no friend-of-friend candidate, so the result is empty.

Constraints

1 <= n <= 100000.
0 <= friendships.length <= 200000.
Every friendship contains two distinct valid user IDs.
The graph has no duplicate friendship edges.
0 <= user < n.
0 <= k <= n.