FastPrep
Problem · Graph

Social Media Suggestions

● MediumCitadelINTERNNEW GRADOA

Implement a prototype of a friend recommendation system for a social media application.

There are n users indexed from 1 to n, and m friends represented as a 2d array, friendships, where the ith friendship is a connection between users friendships[i][0] and friendships[i][1].

User x is suggested as a friend to user y if x and y are not friends and have the maximum number of common friends, i.e. a friend of both x and y. If there are multiple possible such users x, the one with the minimum index is suggested.

Given n and friendships, for each of the n users, find the index of the friend that should be recommended to them. If there is no recommendation available, report -1.

Function Description

Complete the function getRecommendedFriends in the editor.

getRecommendedFriends has the following parameters:

  1. int n: the number of users
  2. int friendships[m][2]: the friendships between the users

Returns

int[]: an array of integers where the ith integer is the index of the recommended friend for the ith user, or -1 if no recommendation is available.

Key insight:

  • _handle edge cases_
  • No friends, no friends of friends (This is so true irl 🙂‍↕️)

    • ૮₍ ˶•⤙•˶ ₎ა All thanks go to Aura Man!𓇼 𓆡⋆.˚

    Examples
    01 · Example 1
    n = 5
friendships = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
return = [3, 2, 1, 0, 1]
    Example 1 illustration
    02 · Example 2
    n = 3
friendships = [[0, 1], [1, 2], [2, 0]]
return = [-1, -1, -1]
    Example 2 illustration
    Constraints
    • 1 ≤ n ≤ 10^5
    • 0 ≤ m ≤ 2.5 x 10^5
    • 0 ≤ friendships[i][0], friendships[i][1] < n
    • There are no self-loops or multiple edges.
    • Each user has a maximum of 15 friends.
    • The network of friends might be disconnected.
    More Citadel problems
    drafts saved locally
    public int[] getRecommendedFriends(int n, int[][] friendships) {
  // write your code here
}
    n5
    friendships[[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
    expected[3, 2, 1, 0, 1]
    sign in to submit