Katkat
Back

Build Friend Recommendations

MetaMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate graph-like data structures to perform neighbor analysis and efficient set operations to rank potential connections.

Problem Statement

You are building a "People You May Know" feature for a social media platform. You are given a list of friendships in the form of a list of pairs friendships, where friendships[i] = [u, v] means user u and user v are already friends.

Your task is to recommend one friend to a target user target_id. The recommendation logic must follow these rules:

  1. A candidate must NOT be the target_id and must NOT already be a friend of the target_id.
  2. You must recommend the candidate who has the highest number of mutual friends with the target_id.
  3. If there is a tie in the number of mutual friends, recommend the user with the smallest user_id.
  4. If the target_id has no friends or there are no eligible candidates, return None.

Function Signature

def recommend_friend(friendships: list[list[int]], target_id: int) -> int | None:

Constraints

  • Number of friendships: up to 10^5.
  • user_id: non-negative integer.
  • The graph is undirected.

Examples

Example 1: Input: friendships = [[1, 2], [1, 3], [2, 4], [3, 4], [3, 5]], target_id = 1

  • Friends of 1: {2, 3}.
  • Friends of 2: {1, 4}, Friends of 3: {1, 4, 5}.
  • Mutual friends for 4: 2 and 3 (Count: 2).
  • Mutual friends for 5: 3 (Count: 1).
  • Output: 4

Example 2: Input: friendships = [[1, 2], [1, 3]], target_id = 1

  • Output: None (No one is a friend-of-a-friend).

Hints

Hint 1

Represent the friendships as an adjacency list using a hash map or dictionary for O(1) lookups.

Hint 2

Iterate through the target user's friends, and for each friend, look at their own friends (the potential candidates) to count occurrences.

Hint 3

Use a dictionary to track the count of mutual friends for each candidate, and ensure you filter out users who are already direct friends or the target themselves.

Follow-up questions

  • How would your implementation change if the graph is extremely large and does not fit into memory?
  • If the number of users is 100 million, how can you optimize the search for mutual friends without iterating through all users?
  • How would you adjust the ranking logic if you wanted to include a 'recency' factor, where connections made more recently are weighted more heavily?