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.

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.

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.

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.

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.

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