Social Graph with Follow/Unfollow, Snapshots, History Queries and Recommendations

Implement an in-memory social graph in which users follow and unfollow other users. Besides the current relationships, the class must take snapshots of the graph, answer questions about follow relationships as of an earlier snapshot, and recommend users to follow. The report names these capabilities only; method names, the recommendation rule and the expected scale were not given, so the interface below is an assumption to confirm with the interviewer. ```python class SocialGraph: def follow(self, follower: int, followee: int) -> None: ... def unfollow(self, follower: int, followee: int) -> None: ... def snapshot(self) -> int: ... # returns the new snapshot's id: 0, 1, 2, ... def is_following(self, follower: int, followee: int, snapshot_id: int) -> bool: ... def following(self, follower: int, snapshot_id: int) -> list[int]: ... # ascending ids def recommend(self, user: int, k: int) -> list[int]: ... ``` Following is one-way: `follow(1, 2)` means user 1 follows user 2, not the reverse. A snapshot records the graph exactly as it is when `snapshot()` is called; changes made afterwards do not affect it. ```text g.follow(1, 2); g.follow(1, 3) s0 = g.snapshot() # 0 g.unfollow(1, 2); g.follow(2, 4); g.follow(3, 4) s1 = g.snapshot() # 1 g.is_following(1, 2, s0) -> True g.is_following(1, 2, s1) -> False g.is_following(2, 4, s0) -> False g.following(1, s0) -> [2, 3] g.following(1, s1) -> [3] ``` ### Clarifying Questions - Must users be registered before they follow, and what should happen on a self-follow, a repeated follow, or an unfollow of someone not followed? - Besides snapshots, do queries need the current state that has not been snapshotted yet? - Which historical queries matter: one pair, the full list a user follows, or a user's followers too? - How should recommendations be ranked, how are ties broken, and are they computed on the current graph or on a snapshot? - Roughly how many users, follow edges and snapshots are there, and how often is each operation called? ### Part 1 — Follow and unfollow Implement `follow` and `unfollow`, plus queries on the current state. ```hint Store what the later parts ask for Choose the adjacency representation with the snapshot and recommendation queries in mind, and decide which direction, or both, of each edge you need to look up. ``` #### What This Part Should Cover - Data structures and the cost of each operation - Behavior for self-follows, repeated follows and unfollowing someone not followed - Tests ### Part 2 — Snapshots and historical queries Implement `snapshot`, `is_following` and `following` for any snapshot id taken so far. ```hint Do not copy the whole graph Copying every edge at each snapshot makes snapshots expensive when the graph is large and most edges never change. Think about what you could record at the moment an edge changes instead, and how a query would then find that edge's state at a given snapshot. ``` #### What This Part Should Cover - The cost of `snapshot()` against the cost of a historical query, and the memory used - Correct answers when an edge changes several times between two snapshots, or flips back and forth across snapshots - Validation of snapshot ids ### Part 3 — Recommend users to follow Implement `recommend(user, k)`, returning up to `k` users that `user` does not follow yet. The rule was not reported: propose one, confirm it, and make the output deterministic. ```hint Use the neighborhood The follow graph itself is the signal you have. Decide which accounts are candidates, which must be excluded, and how candidates are ranked and tied. ``` #### What This Part Should Cover - A clear ranking rule with exclusions and a tie-break - The cost of a recommendation for a user who follows many accounts, or whose followees follow many - Behavior when there are fewer than `k` candidates ### What a Strong Answer Covers - Confirms edge direction, duplicate and self-follow behavior, snapshot semantics and the recommendation rule before coding - Data structures with the cost of every operation stated, and snapshots that avoid copying the graph - Historical answers that stay correct when an edge changes several times between or across snapshots - A deterministic recommendation with exclusions, a tie-break and a stated cost for high-degree users - Tests for the edge cases of each part ### Follow-up Questions - Snapshots are taken often and most are never queried again. How do you discard history that no remaining snapshot needs? - Return the followers of a user as of a snapshot. - One of the user's followees follows millions of accounts. How do you keep `recommend` fast? - Make `recommend` answer as of a snapshot instead of the current graph.