Top Mutual-Friend Recommendations
Superhuman● MediumNEW GRADINTERNOAProblem statement
You are given a simple undirected friendship graph as an array friends. Each entry contains the two user names joined by one friendship. You are also given a target user t.
A recommendation candidate must not be t, must not already be a direct friend of t, and must share at least one direct friend with t.
Rank candidates by these rules:
- A higher number of mutual friends comes first.
- When counts tie, the lexicographically smaller user name comes first.
Return the first three user names in that order, or every candidate when fewer than three exist.
Function
recommendFriends(friends: String[][], t: String) → String[]Examples
Example 1
friends = [["Alice","Bob"],["Alice","Carol"],["Alice","Dave"],["Bob","Carol"],["Bob","Eve"],["Bob","Frank"],["Carol","Dave"],["Carol","Grace"],["Dave","Grace"],["Dave","Henry"],["Eve","Frank"],["Eve","Grace"],["Frank","Grace"]]t = "Alice"return = ["Grace","Eve","Frank"]Grace shares two friends with Alice. Eve, Frank, and Henry each share one; lexical order selects Eve and Frank for the remaining positions.
Example 2
friends = [["A","B"],["B","C"],["B","D"]]t = "A"return = ["C","D"]C and D each share B with A, so both are returned in lexical order.
Constraints
2 <= friends.length <= 2 * 10^5- Every
friends[i]contains exactly two user names. - Every user name has length at most
10and contains only Latin letters. - The graph has no self-loops or duplicate undirected edges.
- The target user
tappears in at least one friendship pair.
Source note: The source slide shows the ranking rules, Alice example, mutual counts, and graph constraints.