PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches

Quick Overview

This question evaluates design and implementation skills for mutable graph data structures with point-in-time snapshotting and recommendation ranking, testing knowledge of data structures, versioning, graph traversal, and algorithmic time/space complexity analysis.

  • medium
  • OpenAI
  • Coding & Algorithms
  • Software Engineer

Implement follow graph with snapshots and recommendations

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement an in-memory “social network” component that supports following/unfollowing, point-in-time (snapshot) queries, and a simple recommendation API. You are given users identified by integers `1..N` (assume `N` can be large). Implement the following operations: 1. `follow(u, v)`: user `u` starts following user `v`. 2. `unfollow(u, v)`: user `u` stops following user `v`. 3. `snap() -> sid`: creates a snapshot of the current follow graph and returns a monotonically increasing snapshot id `sid`. 4. `isFollowing(u, v, sid) -> bool`: returns whether `u` was following `v` at the time snapshot `sid` was taken. 5. `recommend(u, k) -> list[v]`: recommend up to `k` users that `u` does **not** currently follow (and excluding `u`). Rank candidates by the number of users that `u` currently follows who also follow the candidate (i.e., “friends-of-friends” count). Break ties by smaller user id. Clarifications/assumptions you should state and handle: - Repeated `follow(u, v)` when already following should be a no-op; similarly `unfollow` when not following. - Snapshots are immutable; `isFollowing` must reflect state at that snapshot. - Analyze time and space complexity of your approach, especially for large numbers of operations and snapshots.

Quick Answer: This question evaluates design and implementation skills for mutable graph data structures with point-in-time snapshotting and recommendation ranking, testing knowledge of data structures, versioning, graph traversal, and algorithmic time/space complexity analysis.

Part 1: Basic Follow/Unfollow Graph

Implement a small social-network follow graph. There are `n` users labeled from `0` to `n - 1`. Process a list of operations: - `('follow', a, b)`: user `a` starts following user `b` - `('unfollow', a, b)`: user `a` stops following user `b` - `('check', a, b)`: ask whether user `a` is currently following user `b` Rules: - A user cannot follow themself. Such a `follow` operation should be ignored. - Repeating `follow` on an existing relation does nothing. - Repeating `unfollow` on a missing relation does nothing. Return the answers to all `check` operations in order.

Constraints

  • 0 <= n <= 10^5
  • 0 <= len(operations) <= 2 * 10^5
  • All user ids in operations are integers in the range [0, n - 1]
  • Average O(1) set operations are acceptable

Examples

Input: (4, [('follow', 0, 1), ('check', 0, 1), ('unfollow', 0, 1), ('check', 0, 1), ('follow', 0, 0), ('check', 0, 0)])

Expected Output: [True, False, False]

Explanation: User 0 first follows 1, then unfollows 1. Self-follow is ignored, so checking (0, 0) is False.

Input: (3, [('follow', 1, 2), ('follow', 1, 2), ('check', 1, 2), ('unfollow', 1, 2), ('unfollow', 1, 2), ('check', 1, 2)])

Expected Output: [True, False]

Explanation: Repeated follow and unfollow operations should not break the state.

Input: (2, [])

Expected Output: []

Explanation: Edge case: no operations means no check results.

Input: (5, [('follow', 0, 1), ('follow', 0, 2), ('follow', 2, 1), ('check', 0, 2), ('check', 2, 0), ('unfollow', 0, 2), ('check', 0, 2)])

Expected Output: [True, False, False]

Explanation: Checks should always reflect the current graph after each update.

Hints

  1. A hash set for each user is enough to represent who they currently follow.
  2. Make `follow` and `unfollow` idempotent so repeated operations do not cause errors.

Part 2: Follow Graph with Snapshots and Historical Queries

Extend the follow graph to support snapshots. There are `n` users labeled from `0` to `n - 1`. Process operations: - `('follow', a, b)`: user `a` starts following user `b` - `('unfollow', a, b)`: user `a` stops following user `b` - `('snapshot',)`: save the current follow graph and return its snapshot id - `('check', snap_id, a, b)`: ask whether user `a` was following user `b` in the saved state identified by `snap_id` Rules: - Snapshot ids start at `0` and increase by `1` each time `snapshot` is called. - Snapshots are immutable: later changes do not affect older snapshots. - A user cannot follow themself. Such a `follow` operation should be ignored. - Repeated `follow` and `unfollow` operations are allowed and should behave idempotently. - Every `check` query is guaranteed to use a valid snapshot id that was previously returned by `snapshot`. Return the result of every `snapshot` and every `check` in order. For a `snapshot`, append the snapshot id. For a `check`, append a boolean.

Constraints

  • 0 <= n <= 10^5
  • 0 <= len(operations) <= 2 * 10^5
  • All user ids are in [0, n - 1]
  • Each `check` uses a valid snapshot id that has already been created

Examples

Input: (3, [('follow', 0, 1), ('snapshot',), ('unfollow', 0, 1), ('snapshot',), ('check', 0, 0, 1), ('check', 1, 0, 1)])

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

Explanation: At snapshot 0, 0 follows 1. After unfollow and snapshot 1, the relation no longer exists.

Input: (2, [('follow', 0, 1), ('unfollow', 0, 1), ('follow', 0, 1), ('snapshot',), ('check', 0, 0, 1)])

Expected Output: [0, True]

Explanation: Multiple changes before the same snapshot should collapse into the final state seen by that snapshot.

Input: (1, [])

Expected Output: []

Explanation: Edge case: no operations.

Input: (2, [('follow', 0, 0), ('snapshot',), ('check', 0, 0, 0)])

Expected Output: [0, False]

Explanation: Self-follow is ignored, so even the snapshot records no such relation.

Input: (3, [('follow', 1, 2), ('snapshot',), ('snapshot',), ('check', 1, 1, 2)])

Expected Output: [0, 1, True]

Explanation: If nothing changes between snapshots, the old state should still be visible in later snapshots.

Hints

  1. You do not need to copy the whole graph at every snapshot. Store only when a specific follow relation changes.
  2. For each pair `(a, b)`, keep a sorted history of `(snapshot_id, state)` and binary-search it during historical queries.

Part 3: Recommend Top-K Users by Two-Hop Follow Count

Implement user recommendations on a follow graph. There are `n` users labeled from `0` to `n - 1`. Process operations: - `('follow', a, b)`: user `a` starts following user `b` - `('unfollow', a, b)`: user `a` stops following user `b` - `('recommend', u, k)`: recommend up to `k` users for user `u` Recommendation rule: - A candidate user `c` gets 1 point for each user `x` such that: - `u` follows `x`, and - `x` follows `c` - In other words, the score is the number of already-followed users of `u` who follow `c`. - Do not recommend `u` themself. - Do not recommend users that `u` already follows. - Only users with positive score should appear in the output. Ranking rule: - Higher score first - If scores tie, smaller user id first Return one recommendation list for each `recommend` query.

Constraints

  • 0 <= n <= 10^5
  • 0 <= len(operations) <= 2 * 10^5
  • All user ids are in [0, n - 1]
  • Self-follow should be ignored
  • If fewer than k candidates have positive score, return all of them

Examples

Input: (5, [('follow', 0, 1), ('follow', 0, 2), ('follow', 1, 3), ('follow', 2, 3), ('follow', 2, 4), ('recommend', 0, 2)])

Expected Output: [[3, 4]]

Explanation: User 3 gets score 2 because both followed users 1 and 2 follow 3. User 4 gets score 1.

Input: (6, [('follow', 0, 1), ('follow', 0, 2), ('follow', 1, 4), ('follow', 2, 3), ('recommend', 0, 2)])

Expected Output: [[3, 4]]

Explanation: Users 3 and 4 both have score 1, so the smaller id 3 comes first.

Input: (5, [('follow', 0, 1), ('follow', 1, 2), ('follow', 1, 3), ('recommend', 0, 3), ('unfollow', 0, 1), ('recommend', 0, 3)])

Expected Output: [[2, 3], []]

Explanation: After unfollowing 1, user 0 has no two-hop recommendation source left.

Input: (3, [('recommend', 0, 2), ('follow', 0, 1), ('recommend', 0, 0)])

Expected Output: [[], []]

Explanation: Edge cases: no followees means no recommendations, and k = 0 should return an empty list.

Input: (3, [('follow', 1, 1), ('follow', 0, 1), ('recommend', 0, 2)])

Expected Output: [[]]

Explanation: Self-follow is ignored, so user 1 contributes no second-hop candidates.

Hints

  1. For a recommendation query on user `u`, iterate through everyone `u` follows, then through each of their follow sets, and count candidate frequencies.
  2. After counting, sort candidates by `(-score, user_id)` and take the first `k`.
Last updated: Apr 19, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement IP Address Arithmetic - OpenAI (hard)
  • Simulate Infection Spread on a Grid - OpenAI (hard)
  • Implement Social Follow Recommendations - OpenAI (medium)
  • Build a Compose Rating Card - OpenAI (medium)
  • Generate Data Labeling Schedules - OpenAI (medium)