Implement follow graph with snapshots
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
## 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()`.
Quick Answer: This question evaluates a candidate's ability to design efficient persistent data structures and versioned state management for time-travel queries in an in-memory directed follow graph, including handling large user IDs and operation-volume-driven space/time trade-offs.
You are building a simplified social network follow system that supports time-travel queries via snapshots.
There are four operations:
- follow(a, b): user a follows user b (effective immediately in the current state)
- unfollow(a, b): user a unfollows user b (if they were not following, nothing changes)
- snap(): takes a snapshot of the current follow graph and returns a snapId (0, 1, 2, ...)
- is_following(a, b, snapId): returns whether a was following b at the time snapshot snapId was taken
You are given a sequence of operations. Execute them in order and return a list of outputs where:
- follow/unfollow produce None
- snap produces its returned snapId (an integer)
- is_following produces True/False
Snapshot semantics:
- snap() returns the current snapId and then increments it.
- All follow/unfollow operations performed since the last snap() are reflected in the next snap().
- If multiple follow/unfollow operations for the same (a, b) happen before the next snap(), only the final state in that interval matters for that snapshot.
Constraints
- 1 <= len(operations) <= 200000
- User ids a, b are integers in range [0, 10^9]
- 0 <= snapId < number of times snap() has been called
- The number of distinct (a, b) pairs touched is at most len(operations)