Implement Social Graph Snapshot Queries
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a read-only snapshot of a social network. The snapshot is represented as a directed graph where an edge `(u, v)` means user `u` follows user `v`.
Implement a data structure or set of functions that supports the following operations efficiently:
1. `follows(a, b)` -> return whether user `a` follows user `b` in this snapshot.
2. `followers(user)` and `followees(user)` -> return the list of users who follow `user`, and the list of users that `user` follows.
3. `recommend(user, k)` -> return the top `k` recommended users for `user` based on second-degree connections.
For the recommendation query:
- A candidate is a user reachable by exactly two follow steps: `user -> x -> candidate`.
- Exclude the user themself.
- Exclude users already directly followed by `user`.
- If the same candidate is reached through multiple intermediate users, rank that candidate higher.
- Break ties by smaller user id first.
You may assume the graph snapshot is static after construction, and there can be many queries after the snapshot is loaded. Describe the expected time and space complexity of your approach.
Quick Answer: This question evaluates understanding of graph data structures, query-efficient indexing, and algorithmic trade-offs for static directed graphs, including handling neighborhood queries and recommendation ranking based on second-degree connections.
You are given a static snapshot of a social network with users labeled from 0 to n-1. The snapshot is a directed graph where an edge (u, v) means user u follows user v.
Implement a function `solution(n, edges, queries)` that builds the snapshot once and answers many queries efficiently.
Each query is one of the following:
- `('follows', a, b)`: return whether user `a` follows user `b`.
- `('followers', user)`: return the list of users who follow `user`, sorted in ascending order.
- `('followees', user)`: return the list of users that `user` follows, sorted in ascending order.
- `('recommend', user, k)`: return up to `k` recommended users for `user`.
Recommendation rules:
- A candidate must be reachable by exactly two follow steps: `user -> x -> candidate`.
- Exclude the user themself.
- Exclude users already directly followed by `user`.
- If the same candidate is reached through multiple different intermediate users `x`, that candidate ranks higher.
- Break ties by smaller user id first.
- Return only the user ids, in ranked order.
The graph is read-only after construction. Duplicate edges may appear in the input and should be treated as a single follow relationship.
Constraints
- 1 <= n <= 100000
- 0 <= len(edges) <= 200000