Build a Constant-Time Snapshot Set Iterator

Problem Statement

Design a mutable set of integers, SnapshotSet, that supports adding, removing, and querying elements in O(1) time, while also supporting snapshot-based iterators.

An iterator created via get_iterator() must traverse the elements that were present in the set at the exact moment the iterator was created, ordered by their insertion order at that time. Later mutations (additions or deletions) to the set must not affect existing iterators, and creating an iterator must take O(1) time (i.e., no deep-copying of the underlying set).

If an element is removed and later re-added, its new insertion order position reflects the most recent addition.

Implement the SnapshotSet and SnapshotIterator classes:

class SnapshotSet:
    def __init__(self):
        pass

    def add(self, val: int) -> bool:
        """Adds val to the set. Returns True if val was not already present, False otherwise."""
        pass

    def remove(self, val: int) -> bool:
        """Removes val from the set. Returns True if val was present, False otherwise."""
        pass

    def contains(self, val: int) -> bool:
        """Returns True if val is currently in the set, False otherwise."""
        pass

    def get_iterator(self) -> "SnapshotIterator":
        """Returns an iterator over elements present at this moment, in insertion order."""
        pass

class SnapshotIterator:
    def has_next(self) -> bool:
        """Returns True if there are more elements in this snapshot."""
        pass

    def next(self) -> int:
        """Returns the next element in this snapshot."""
        pass

Constraints

• Values are integers in the range [-10^9, 10^9].
• Total operations across add, remove, contains, and get_iterator <= 2 * 10^5.
• add, remove, contains, and get_iterator must run in O(1) time.
• next() and has_next() should run in O(1) amortized time per call.
• Calling has_next() multiple times consecutively without calling next() must be idempotent.

Example

s = SnapshotSet()
s.add(10)
s.add(20)
it1 = s.get_iterator()
s.remove(10)
s.add(30)
s.add(10)  # Re-added after being removed
it2 = s.get_iterator()

# it1 reflects the state when only [10, 20] were added
res1 = []
while it1.has_next():
    res1.append(it1.next())
# res1 == [10, 20]

# it2 reflects the state: 20 was kept, 30 was added, 10 was re-added
res2 = []
while it2.has_next():
    res2.append(it2.next())
# res2 == [20, 30, 10]

Edge Cases to Consider

• An element is removed before any iterator is created, then never re-added.
• Multiple active iterators iterating at different paces while mutations continue.
• Iterators created when the set is empty.