Katkat
Back

Implement follow graph with snapshots

OpenAISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a versioned, immutable, or persistent data structure that supports efficient graph modifications and point-in-time snapshot queries.

Problem Statement

Design a data structure FollowGraph that represents a directed graph where nodes are user_ids (integers) and edges represent 'follows'. The system must support operations that create versions, allowing queries on the state of the graph at any historical timestamp.

You need to implement the following interface:

  • follow(follower_id, followee_id): Adds a directed edge at the current global timestamp. Returns the new version ID.
  • unfollow(follower_id, followee_id): Removes a directed edge at the current global timestamp. Returns the new version ID.
  • is_following(follower_id, followee_id, version_id): Returns True if follower_id followed followee_id as of version_id, else False.

Constraints

  • user_id can be up to 10^9.
  • The number of operations is up to 10^5.
  • version_id must be non-decreasing.
  • Memory should be managed efficiently to avoid storing a full copy of the graph for every operation.

Examples

# Operations:
# 1. follow(1, 2) -> v1
# 2. follow(1, 3) -> v2
# 3. unfollow(1, 2) -> v3

# Queries:
# is_following(1, 2, v1) -> True
# is_following(1, 2, v3) -> False
# is_following(1, 3, v3) -> True

Edge Cases

  • Checking is_following for a version_id before any operations occurred.
  • Removing an edge that does not exist.
  • Handling sparse graph connectivity.

Hints

Hint 1

Consider using a versioned adjacency list where each list stores a sorted history of changes or a persistent structure like a persistent segment tree.

Hint 2

Instead of full snapshots, store the delta of edges (add/remove) for each user and use binary search on the history timestamps to determine the state at a specific version.

Hint 3

For space efficiency, map each user to a persistent dynamic array or a balanced BST that stores their 'followee' set.

Follow-up questions

  • How would you optimize the memory footprint if the number of operations reaches 10^7?
  • If we wanted to retrieve the entire list of followees for a user at a given `version_id`, how would your chosen data structure perform?
  • How would this design change if you needed to support persistence across process restarts, requiring the data to be backed by a disk-based storage?