Mutual-Friend Referral Recommendations

An undirected graph contains users 0 through n - 1. Each row [a,b] in friendships means that a and b are direct friends.
Build referral recommendations for user:
Exclude user and every current direct friend.
A remaining user is eligible only when they share at least one mutual friend with user.
If d is the number of direct friends of user, a candidate with m distinct mutual friends has score m / d. Thus every score is in [0,1].
Rank candidates by decreasing score, breaking ties by increasing user ID, and keep the first k.
Return each kept recommendation as "userId:score", with the score rounded to exactly six digits after the decimal point. Return an empty array when no candidate is eligible.
Evaluation follow-up
NDCG can evaluate the ranking against graded relevance labels. Those labels are not part of this input, so NDCG does not change the judged return value.

Function
recommendReferrals(n: int, friendships: int[][], user: int, k: int) → String[]

Examples
Example 1
n = 6
friendships = [[0,1],[0,2],[1,3],[2,3],[1,4],[2,5]]
user = 0
k = 3
return = ["3:1.000000","4:0.500000","5:0.500000"]
User 3 shares both of user 0's friends and scores 2/2. Users 4 and 5 each score 1/2, so their IDs break the tie.
Example 2
n = 7
friendships = [[0,1],[0,2],[0,3],[1,4],[2,4],[3,5],[1,6],[2,6]]
user = 0
k = 2
return = ["4:0.666667","6:0.666667"]
Users 4 and 6 each share two of the target user's three friends. User 5 scores only 1/3, and the first two ranked candidates are returned.

Constraints
1 <= n <= 100000.
0 <= friendships.length <= 200000.
Every friendship contains two distinct valid user IDs, and no undirected edge is repeated.
0 <= user < n.
0 <= k <= n.

Build an adjacency list. Mark user and all direct friends as excluded. For each direct friend f, walk f's neighbors. For every neighbor c not excluded, increment count[c]. Since edges are unique, each friend contributes at most once per candidate, so count[c] is the number of distinct mutual friends. Total work is bounded by the sum of friend degrees, fine for 200000 edges. Then sort candidates by count descending and ID ascending. Since d is the same for everyone, ranking by count is the same as ranking by score, which avoids float comparison bugs. Format with six decimals only at the end. Pitfalls: d equals 0 means no candidates, so return empty before dividing. Handle k = 0 and k larger than the candidate count. Ignore NDCG completely. If the clock is ugly and the sort-plus-format step trips you, StealthCoder is the hedge for the live OA.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.