Implement a Set with Readable Snapshots

Problem Description

Implement a SnapshotSet data structure that maintains a collection of unique elements while supporting instantaneous snapshots. Users can query current membership as well as historical membership at any previous snapshot.

Implement the SnapshotSet class with the following methods:

• __init__(): Initializes the object with an empty set. The initial state before any snapshot is called can be considered epoch 0.
• add(val: int) -> bool: Adds val to the set. Returns True if val was not already in the set, or False if it was already present.
• remove(val: int) -> bool: Removes val from the set. Returns True if val was in the set, or False if it was not present.
• contains(val: int) -> bool: Returns True if val is currently in the set, False otherwise.
• snapshot() -> int: Takes a snapshot of the set's current state and returns a unique snapshot_id. The first call to snapshot() returns 0, the second returns 1, and so on.
• contains_at(snapshot_id: int, val: int) -> bool: Returns True if val was present in the set at the time snapshot_id was taken, False otherwise. If snapshot_id is invalid, raise an IndexError.

Your solution should avoid deep-copying the entire set on each snapshot() call. Aim for O(1) snapshot creation and efficient historical queries.

Interface

class SnapshotSet:
    def __init__(self):
        pass

    def add(self, val: int) -> bool:
        pass

    def remove(self, val: int) -> bool:
        pass

    def contains(self, val: int) -> bool:
        pass

    def snapshot(self) -> int:
        pass

    def contains_at(self, snapshot_id: int, val: int) -> bool:
        pass

Example

ss = SnapshotSet()
ss.add(1)                 # Returns True, set: {1}
ss.add(2)                 # Returns True, set: {1, 2}
snap0 = ss.snapshot()     # snap0 = 0 (captures {1, 2})

ss.remove(1)              # Returns True, set: {2}
ss.add(3)                 # Returns True, set: {2, 3}
snap1 = ss.snapshot()     # snap1 = 1 (captures {2, 3})

ss.contains(1)            # Returns False
ss.contains_at(snap0, 1)  # Returns True (1 was in snap0)
ss.contains_at(snap1, 1)  # Returns False (1 was not in snap1)
ss.contains_at(snap0, 3)  # Returns False (3 was added after snap0)
ss.contains_at(snap1, 3)  # Returns True

Constraints & Edge Cases

• Total operations: up to 2 * 10^5 across all method calls.
• Element values: -10^9 <= val <= 10^9.
• snapshot_id must be non-negative and strictly less than the total number of snapshots taken so far.
• Multiple additions or removals of the same element within the same snapshot interval should not create redundant history entries.
• Adding an element, removing it, and re-adding it across different snapshots must maintain a correct timeline of intervals.