FastPrep
Problem · Graph

Social Media Friend Recommendation

Learn this problem
● MediumGoogleINTERNOA
See Google hiring insights

Problem statement

Design a prototype for a friend recommendation system for a social media platform.

You have n users labeled from 1 to n, and m friendships represented as a 2D array called friendships. Each entry friendship[i] is a connection between users friendship[i][0] and friendship[i][1]. For any user y, another user x is recommended as a friend if x and y are not currently friends and have the highest number of mutual friends (friends in common). In case of ties (multiple users x with the same number of mutual friends), recommend the user with the smallest index. Given n and friendships, determine the friend recommendation for each user from 1 to n. If no recommendation can be made, return -1 for that user.

Function

friendRecommendations(n: int, m: int, friendships: int[][]) → int[]

Examples

Example 1

n = 3m = 2friendships = [[0, 1], [0, 2]]return = [-1, 2, 1]

Since 0 is friends with both users, no recommendation can be made. As common friends of 0, 1 and 2 can be recommended to one another.

Constraints

  • n <= 10^5
  • m <= 2.5 * 10^5
  • Each user has at most 15 friends.

More Google problems

drafts saved locally
public int[] friendRecommendations(int n, int m, int[][] friendships) {
  // write your code here
}
n3
m2
friendships[[0, 1], [0, 2]]
expected[-1, 2, 1]
checking account