Social Network with Snapshots

Instructions

Design and implement an in-memory social network, built up over four levels:

1. Follow graph — users follow and unfollow each other.
2. Snapshots — freeze the current state and query it later.
3. Time travel — record follows/unfollows with timestamps and ask about any past moment.
4. Recommendations — suggest new users to follow based on the follow graph.

Follow relationships are directed: A following B does not mean B follows A.

Interfaces

class SocialNetwork:
    def add_user(self, user_id: str) -> None: ...
    def follow(self, follower_id: str, followee_id: str) -> None: ...
    def unfollow(self, follower_id: str, followee_id: str) -> None: ...
    def get_followers(self, user_id: str) -> list[str]: ...   # who follows user_id
    def get_followees(self, user_id: str) -> list[str]: ...   # who user_id follows
    def create_snapshot(self) -> "Snapshot": ...              # freeze current state

    def follow_at(self, follower_id: str, followee_id: str, timestamp: int) -> None: ...
    def unfollow_at(self, follower_id: str, followee_id: str, timestamp: int) -> None: ...
    def is_following_at(self, follower_id: str, followee_id: str, timestamp: int) -> bool: ...


class Snapshot:
    def is_following(self, follower_id: str, followee_id: str) -> bool: ...

Level 1: Follow Graph

Implement add_user, follow, unfollow, get_followers, and get_followees.

sn.follow("A", "B")
sn.follow("C", "B")

sn.get_followees("A")    # ["B"]        — A follows B
sn.get_followers("B")    # ["A", "C"]   — B is followed by A and C

sn.unfollow("A", "B")
sn.get_followees("A")    # []           — A no longer follows anyone
sn.get_followers("B")    # ["C"]        — only C still follows B

unfollow on a relationship that doesn't exist is a no-op.

Result will appear here after submission.

Level 2: Snapshots

Add create_snapshot(), which returns an immutable Snapshot of the current state. A snapshot keeps the state it captured, even as the network keeps changing.

sn.follow("A", "B")
s1 = sn.create_snapshot()      # captures: A -> B

sn.unfollow("A", "B")
s2 = sn.create_snapshot()      # captures: (nothing)

s1.is_following("A", "B")      # True  — s1 still remembers the old state
s2.is_following("A", "B")      # False — s2 reflects the unfollow

Result will appear here after submission.

Level 3: Time Travel

Add follow_at, unfollow_at, and is_following_at. A follow is active from its follow_at timestamp (inclusive) until its unfollow_at timestamp (exclusive).

sn.follow_at("A", "B", 10)     # follows at t=10
sn.unfollow_at("A", "B", 20)   # unfollows at t=20

sn.is_following_at("A", "B", 9)    # False — before the follow
sn.is_following_at("A", "B", 10)   # True  — start is inclusive
sn.is_following_at("A", "B", 15)   # True  — in between
sn.is_following_at("A", "B", 20)   # False — end is exclusive

Each relationship is tracked independently, and a relationship can be re-followed after being unfollowed.

Result will appear here after submission.

Follow-up: User Recommendation

Extend the network with a "who to follow" service that suggests new accounts for a user and how it scales...