Implement Social Graph Snapshot Queries

Problem Statement

You are building an analytics service for a social network. The network can be modeled as a directed graph where an edge from A to B represents that A follows B. The graph is static (no updates once loaded).

Implement a class SocialGraph that supports efficient queries:

1. get_following(user_id): Returns a list of users that user_id follows.
2. get_second_degree_suggestions(user_id): Returns a list of potential accounts to follow. A 'second-degree suggestion' is defined as a user that a person user_id follows also follows, excluding users user_id already follows and the user_id themselves. Suggestions should be ranked by the number of mutual connections (i.e., how many people user_id follows who also follow the suggestion).

Implementation Signature

class SocialGraph:
    def __init__(self, follows: list[tuple[int, int]]):
        # Initialize the graph structure
        pass

    def get_following(self, user_id: int) -> list[int]:
        # Return list of user_ids followed by user_id
        pass

    def get_second_degree_suggestions(self, user_id: int) -> list[int]:
        # Return ranked list of suggestions
        pass

Constraints

• N (number of users) up to 10^5.
• E (number of edges) up to 10^6.
• Time limit: 2 seconds per query for suggestions.

Example

Input: [(1, 2), (1, 3), (2, 4), (3, 4), (3, 5)]

• get_following(1) -> [2, 3]
• get_second_degree_suggestions(1) -> [4 (score 2), 5 (score 1)] Explanation: 1 follows 2 and 3. Both 2 and 3 follow 4 (score 2). Only 3 follows 5 (score 1).