Follow Graph with Cheap Snapshots and Top-K Follow Recommendations

Implement the core of a social network's follow graph. Users are identified by integer IDs, and following is one-directional: user `a` following user `b` does not mean `b` follows `a`. The interview has two stages: a follow graph that supports snapshots, then top-k recommendations of whom to follow. ### Clarifying Questions - Can a user follow themselves? What should follow do if the edge already exists, and unfollow if it does not? - Does a snapshot capture every change made before the `snapshot()` call that created it? - How should recommendation candidates be scored, and how are ties broken? - Should recommendations exclude people the user already follows, and the user themselves? - Roughly how many users and follow edges are there, and how skewed are the follower counts? - Are snapshots taken rarely (daily) or frequently (every few seconds)? ### Part 1 — Follow graph with snapshots Support these operations: - `follow(a, b)` and `unfollow(a, b)` - `snapshot()`, which returns a snapshot ID (0 for the first call, then 1, 2, and so on) that captures the graph as it is at that moment - `is_following(a, b, snap_id)` and `following(a, snap_id)`, which answer questions about the graph as it was when snapshot `snap_id` was taken Taking a snapshot must be cheap even when the graph is large. ```hint Store changes, not copies Rather than copying the graph at every snapshot, consider recording each edge's changes along with when they happened, then working out an edge's state at any snapshot. ``` #### What This Part Should Cover - A snapshot operation whose cost does not grow with the graph size - Correct answers for edges that change several times between two snapshots - Time and space complexity of each operation - A comparison with copying the graph at every snapshot ### Part 2 — Top-k recommendations Implement `recommend(user, k)`, which returns up to `k` users that `user` might want to follow, best first. Then make it work against a past snapshot as well. ```hint Look two steps away Think about which accounts are close to the user in the graph and what evidence ranks one above another, then how to pick the best `k` without sorting every candidate. ``` #### What This Part Should Cover - A clearly stated scoring rule and a deterministic tie-break - Correct exclusions: the user, and accounts already followed - Efficient top-k selection and its complexity - What happens when a followee follows a very large number of accounts ### What a Strong Answer Covers - Clean data structures chosen for the operations that are actually frequent - Precise snapshot semantics, including multiple changes between snapshots - A scalable recommendation approach, with its limits acknowledged - Tests for unfollow-then-follow sequences, snapshots with no changes and ties in scores ### Follow-up Questions - How would you serve recommendations for hundreds of millions of users with low latency? - How would you store snapshots durably, and delete old ones? - How would you change the scoring to prefer accounts followed by closer or more active connections? - Snapshots are now taken every few seconds. What in your design changes?