Mutual-Friend Recommendations

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 = 6
friendships = [[0,1],[0,2],[1,3],[2,3],[1,4],[2,5]]
user = 0
k = 3
return = [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 = 5
friendships = [[0,1],[0,2],[1,3],[2,3],[1,4],[2,4]]
user = 0
k = 1
return = [3]
Users 3 and 4 both have score 2. The ID tie-break ranks 3 first, and k = 1.
Example 3
n = 5
friendships = [[0,1],[0,2],[1,2],[1,3],[2,4]]
user = 0
k = 5
return = [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 = 4
friendships = [[0,1],[2,3]]
user = 0
k = 2
return = []
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.

The trick is to count from the user's side, not the candidate's side. Build adjacency lists. Put the user's direct friends in a set. For each friend f, loop over f's neighbors g. Skip g if it equals user or sits in the friend set. Otherwise increment a hash map count for g. Each friend contributes at most once per candidate because edges are unique, so the count is the distinct mutual friend count. Total work is bounded by the sum of friend degrees, which is at most 400000 edge visits. Then sort candidates by (-score, id) and slice the first k. Common pitfalls: forgetting to exclude the user, forgetting to exclude direct friends (Example 3 tests this), and returning wrong output when k is 0. Sorting is fine here. A heap only matters if you want to avoid sorting everything. StealthCoder is the hedge if the live OA rattles you and you lose the thread.

The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.