Implement follow graph with snapshots

Problem

You are building an in-memory social network relationship store that supports time-travel queries.

Users are identified by integers. A directed edge (a -> b) means user a follows user b.

Implement a data structure with the following API:

• follow(int a, int b) : record that a follows b (idempotent).
• unfollow(int a, int b) : record that a no longer follows b (idempotent).
• int snap() : take a snapshot of the current follow graph and return a snapId (starting from 0 , increasing by 1 each time).
• bool is_following(int a, int b, int snapId) : return whether a was following b as of that snapshot .

Requirements / Notes

• is_following(a,b,snapId) must reflect the state at the moment snap() returned that snapId .
• Assume calls can be interleaved arbitrarily.
• You may assume 0 <= snapId < number_of_snaps .

Constraints (reasonable interview assumptions)

• Up to ~200k operations.
• User IDs can be large (use hash-based storage).
• Aim for better than copying the entire graph on every snap() .