FastPrepMutual-Friend Referral Recommendations
Problem · Graph

Mutual-Friend Referral Recommendations

Learn this problem
● MediumFireworks AI logoFireworks AIFULLTIMEONSITE INTERVIEW

Problem statement

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 = 6friendships = [[0,1],[0,2],[1,3],[2,3],[1,4],[2,5]]user = 0k = 3return = ["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 = 7friendships = [[0,1],[0,2],[0,3],[1,4],[2,4],[3,5],[1,6],[2,6]]user = 0k = 2return = ["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.
drafts saved locally
public String[] recommendReferrals(int n, int[][] friendships, int user, int k) {
    // Write your code here.
}
n6
friendships[[0,1],[0,2],[1,3],[2,3],[1,4],[2,5]]
user0
k3
expected["3:1.000000", "4:0.500000", "5:0.500000"]
checking account