Top Mutual-Friend Recommendations
Visa● MediumINTERNOAProblem statement
You are given a list of friendships in a social network as an array friends. Each entry [u, v] represents a mutual friendship between users u and v. You are also given a target user t.
Suggest up to three new connections for t. Consider only users who:
- are not the target user
t; and - are not already direct friends of
t.
For each candidate user p, count how many users are common friends of both p and 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"]Alice's direct friends are Bob, Carol, and Dave. The eligible candidates are Eve, Frank, Grace, and Henry. Grace shares two friends with Alice. The other three each share one, so 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 and represents one undirected friendship. - 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.