Social Media Suggestions
Learn this problem
CitadelINTERNNEW GRADOAProblem statement
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
getRecommendedFriends(n: int, friendships: int[][]) → int[]
Complete the function getRecommendedFriends in the editor.
getRecommendedFriends has the following parameters:
int n: the number of usersint 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:
૮₍ ˶•⤙•˶ ₎ა All thanks go to Aura Man!𓇼 𓆡⋆.˚
Examples
Example 1
n = 5friendships = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]return = [3, 2, 1, 0, 1]
Example 2
n = 3friendships = [[0, 1], [1, 2], [2, 0]]return = [-1, -1, -1]
Constraints
1 ≤ n ≤ 10^50 ≤ m ≤ 2.5 x 10^50 ≤ 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.