Katkat
Back

Design a social network with snapshots

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests your ability to design a memory-efficient versioned graph structure that supports efficient edge retrieval at arbitrary points in time.

Problem Statement

Design a social network service that tracks users and their 'follows' relationships. The system must support two operations: creating snapshots of the network state and querying the network as it existed at any previous snapshot ID.

Assume users are identified by unique integer IDs. Your system should implement the following interface:

class SocialGraph:
    def __init__(self):
        pass

    def follow(self, follower_id: int, followee_id: int) -> None:
        # Adds a directed edge from follower to followee in the current state
        pass

    def take_snapshot(self) -> int:
        # Saves the current state and returns a unique snapshot ID
        pass

    def get_follows(self, user_id: int, snapshot_id: int) -> set[int]:
        # Returns the set of users followed by user_id at the time of snapshot_id
        pass

Constraints

  • follow operations occur sequentially.
  • take_snapshot is called infrequently relative to follow.
  • Memory should be optimized to avoid duplicating the entire graph structure on every snapshot.
  • snapshot_id is monotonic and increases with every call to take_snapshot.

Examples

Example 1:

  1. follow(1, 2)
  2. id1 = take_snapshot()
  3. follow(1, 3)
  4. get_follows(1, id1) -> returns {2}
  5. get_follows(1, id2) (where id2 is current) -> returns {2, 3}

Edge Cases

  • A user follows someone, takes a snapshot, then unfollows them (if unfollows were implemented, how would the data structure handle deletion?).
  • Querying a snapshot_id that does not exist.
  • A user with no followers at a specific snapshot.

Hints

Hint 1

Instead of copying the entire adjacency list, consider storing a list of history for each user's 'follows' set.

Hint 2

Use a data structure that allows you to store a history of changes (additions) associated with specific snapshot IDs, such as a list of (snapshot_id, followee_id) tuples.

Hint 3

Binary search can be used on the history list of a specific user to efficiently find all followees that existed at or before a given snapshot ID.

Follow-up questions

  • How would you modify your design to support an 'unfollow' operation, and how does that affect the time complexity of the snapshot query?
  • If the number of follows per user grows into the millions, how would you partition this data across multiple physical nodes?
  • What are the trade-offs between storing snapshots as full state copies versus storing only the delta of changes?