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:
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!𓇼 𓆡⋆.˚
Example 1:
Input: n = 5, friendships = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]
Output: [3, 2, 1, 0, 1]
Explanation:
Example 2:
Input: n = 3, friendships = [[0, 1], [1, 2], [2, 0]]
Output: [-1, -1, -1]
Explanation:
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.
input:
output: