Implement Social Follow Recommendations

Problem Statement

You are tasked with building a 'Follow Recommendations' feature for a social media platform. You are given a directed graph represented by a dictionary where keys are User IDs and values are sets of User IDs that the user is currently following.

Your goal is to implement a function get_recommendations(user_id, graph, n) that returns a list of the n most recommended users. A user Candidate is recommended for user_id if:

1. Candidate is not the user_id and is not already followed by user_id.
2. Candidate is followed by at least one person that user_id follows (a 'friend-of-a-friend').

The recommendation score is defined as the number of followed users that also follow the Candidate. If two candidates have the same score, rank them by their User ID in ascending order.

Function Signature

def get_recommendations(user_id: int, graph: dict[int, set[int]], n: int) -> list[int]:

Examples

Example 1:

• graph = {1: {2, 3}, 2: {4}, 3: {4, 5}, 4: {5}}
• get_recommendations(1, graph, 2)
• Output: [4, 5]
• Explanation: User 1 follows 2 and 3. User 2 follows 4; User 3 follows 4 and 5. Candidate 4 is followed by 2 and 3 (score 2). Candidate 5 is followed by 3 (score 1).

Constraints

• Number of users: up to 10,000.
• Total number of follows: up to 100,000.
• n is a positive integer.

Edge Cases

• The user_id does not exist in the graph.
• No common followees exist.
• The recommended list size is smaller than n.