Design a social network with snapshots

You are asked to design and implement an in-memory SocialNetwork class that supports users following each other and creating snapshots of the follow graph.

Requirements

Implement an API similar to:

social_network = SocialNetwork()
social_network.add_user("A")
social_network.add_user("B")
social_network.follow("A", "B")

snapshot = social_network.create_snapshot()
assert snapshot.is_follow("A", "B")

A snapshot represents an immutable view of the follow relationships at the moment it was created.

Part 1 — Snapshot follow query

• Support snapshot.is_follow(u, v) which returns whether user u follows user v in that snapshot .

Part 2 — List followers and followees

For a given snapshot and user:

• Return the list/set of followers (who follows this user).
• Return the list/set of followees (whom this user follows).

Part 3 — Recommend users to follow

Given a snapshot, a user u, and an integer k, recommend up to k users for u to follow using this logic:

1. Look at the users that u already follows.
2. For each of those followees, look at whom they follow.
3. Count how many times each candidate user is followed by u ’s followees.
4. Return the top- k candidates by this count.

Assumptions / clarifications (you may choose reasonable defaults)

• What to do if u or v does not exist.
• Whether to allow self-follow.
• Whether repeated follow calls are idempotent.
• Whether to exclude users that u already follows from recommendations.

Describe your design (data structures, snapshot strategy, complexity) and any edge cases.