Practice/Databricks/SnapshotSet with Iterator

SnapshotSet with Iterator

CodingMust

Problem Overview

Design and implement a SnapshotSet<T> data structure that extends a standard set with snapshot-based iterators.

The key requirement is that iterators capture a read-only snapshot of the set at the time of their creation. These iterators remain immune to subsequent modifications (add/remove operations) performed on the set after the iterator is created.

Required Operations

• add(x): Add element x to the set (no effect if already present)
• remove(x): Remove element x from the set (no effect if not present)
• contains(x): Return true if element x is currently in the set
• iterator(): Return an iterator over the current snapshot of the set

Iterator Requirements

• Snapshot Isolation: The iterator captures the set's state at creation time
• Insertion Order: Iterator returns elements in the order they were first added
• Immutable View: Subsequent add or remove operations do not affect the iterator's view
• Standard Interface: Support hasNext() and next() methods

Important: The contains() method always reflects the current state of the set, not any snapshot.

Example

`

Initialize set with elements [1, 2, 3]

ss = SnapshotSet([1, 2, 3])

Add element 4

ss.add(4) # Set is now {1, 2, 3, 4}

Create first iterator (snapshot: {1, 2, 3, 4})

iter1 = ss.iterator() print(iter1.next()) # Output: 1 print(iter1.next()) # Output: 2

Remove element 3 from the actual set

ss.remove(3) # Set is now {1, 2, 4}

iter1 still sees the snapshot from creation time

print(iter1.next()) # Output: 3 (still in snapshot!) print(iter1.next()) # Output: 4

Create second iterator (snapshot: {1, 2, 4})

iter2 = ss.iterator()

Add element 6 to the actual set

ss.add(6) # Set is now {1, 2, 4, 6}

iter2 sees its snapshot, not the new element 6

print(iter2.next()) # Output: 1 print(iter2.next()) # Output: 2 print(iter2.next()) # Output: 4 print(iter2.hasNext()) # Output: False (6 not in snapshot)

contains() always reflects current state

print(ss.contains(3)) # Output: False (was removed) print(ss.contains(6)) # Output: True (was added) `

Constraints

• Elements are comparable and hashable
• 1 <= number of operations <= 10^5
• All operations should be efficient (avoid O(n) operations where possible)
• Multiple iterators may exist simultaneously