How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at OpenAI during technical interviews.

Implement follow graph with snapshots | OpenAI Coding Question

Quick Overview

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.

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)

Examples

Input: ([('follow', 1, 2), ('snap',), ('is_following', 1, 2, 0), ('unfollow', 1, 2), ('is_following', 1, 2, 0), ('snap',), ('is_following', 1, 2, 1)],)

Expected Output: [None, 0, True, None, True, 1, False]

Explanation: After snap 0, (1->2) is True. Unfollow happens after snap 0 (in snap 1 interval), so snap 0 remains True, but snap 1 becomes False.

Input: ([('follow', 1, 2), ('unfollow', 1, 2), ('follow', 1, 2), ('snap',), ('is_following', 1, 2, 0)],)

Expected Output: [None, None, None, 0, True]

Explanation: All changes occur before the first snap; the final state before snap 0 is following.

Input: ([('unfollow', 5, 6), ('snap',), ('is_following', 5, 6, 0), ('is_following', 7, 8, 0)],)

Expected Output: [None, 0, False, False]

Explanation: Unfollowing a non-existent follow is a no-op. Unseen edges are not followed in any snapshot.

Input: ([('snap',), ('is_following', 1, 1, 0), ('follow', 1, 1), ('snap',), ('is_following', 1, 1, 0), ('is_following', 1, 1, 1)],)

Expected Output: [0, False, None, 1, False, True]

Explanation: The self-follow is created after snap 0 and is included starting at snap 1.

Input: ([],)

Expected Output: []

Explanation: No operations produce no outputs.

Input: ([('follow', 1, 2), ('follow', 1, 3), ('snap',), ('unfollow', 1, 2), ('snap',), ('is_following', 1, 2, 0), ('is_following', 1, 2, 1), ('is_following', 1, 3, 1), ('follow', 1, 2), ('is_following', 1, 2, 1), ('snap',), ('is_following', 1, 2, 2)],)

Expected Output: [None, None, 0, None, 1, True, False, True, None, False, 2, True]

Explanation: Edge (1->2) is True at snap 0, becomes False at snap 1, then is re-followed and becomes True again at snap 2. Edge (1->3) stays True.

Hints

Store, for each directed edge (a, b), a history of (snapId, state) changes; then queries become a binary search for the latest change at or before snapId.
If multiple updates occur for the same (a, b) within the same snapId interval, you can overwrite the last recorded value instead of appending a new one.

Quick Overview