FastPrepFastPrep
Problem Brief

Social Media Suggestions

INTERNNEW 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!𓇼 𓆡⋆.˚

    1Example 1

    Input
    n = 5, friendships = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
    Output
    [3, 2, 1, 0, 1]
    Explanation
    Example 1 illustration

    2Example 2

    Input
    n = 3, friendships = [[0, 1], [1, 2], [2, 0]]
    Output
    [-1, -1, -1]
    Explanation
    Example 2 illustration

    Constraints

    Limits and guarantees your solution can rely on.

    • 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.
    public int[] getRecommendedFriends(int n, int[][] friendships) {
  // write your code here
}
    Input

    n

    5

    friendships

    [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]

    Output

    [3, 2, 1, 0, 1]

    Sign in to submit your solution.