Katkat
Back

Build a Friend Recommender

MetaMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to implement a graph-based recommendation algorithm using common neighbors and popularity constraints to rank potential connections.

Friend Recommender

You are tasked with building a function to recommend friends on a social network. You are given a list of existing friendships, represented as a list of pairs (user_a, user_b).

Implement the function recommend_friends(friendships, target_user) which returns a list of candidate user IDs. A candidate is defined as a user who is not currently a friend of the target_user and is not the target_user themselves.

Recommendation Logic

  1. Candidates should be ranked by the number of mutual friends they share with the target_user in descending order.
  2. If two candidates have the same number of mutual friends, the candidate with the higher total degree (number of friends) in the network should be ranked higher.
  3. If ties persist, the candidate with the smaller user ID should be ranked higher.

Constraints

  • friendships contains between 0 and 10,000 pairs.
  • User IDs are non-negative integers.
  • The graph is undirected.

Example

# Input:
friendships = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4)]
target_user = 0

# Reasoning:
# 0's friends are {1, 2}.
# Potential candidates:
# User 3: Mutual friends {1}. Count: 1. Total degree: 2.
# User 4: Mutual friends {2}. Count: 1. Total degree: 2.
# Ties (3 and 4): Both have 1 mutual friend, degree 2. 
# 3 < 4, so 3 comes first.

# Output: [3, 4]

Hints

Hint 1

Represent the graph as an adjacency list (using a dictionary of sets) to allow O(1) friend lookups.

Hint 2

For the target user, identify all friends of friends, then filter out those who are already direct friends or the target user.

Hint 3

Calculate the degree of every user once before ranking candidates to avoid redundant calculations.

Follow-up questions

  • How would you optimize this if the graph was massive (e.g., billions of edges) and did not fit in memory?
  • If we wanted to incorporate a 'recency' factor (friends added recently carry more weight), how would you modify the data model and the recommendation score?
  • How would you evaluate the quality of these recommendations offline versus online?