Katkat
Back

Implement a Snapshot Set Iterator

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a data structure that maintains point-in-time consistency for an iterator despite subsequent modifications to the underlying collection.

Snapshot Set Iterator

Design a SnapshotSet class that supports the following operations:

  • add(value): Adds an integer to the set.
  • remove(value): Removes an integer from the set.
  • contains(value): Returns true if the set contains the value.
  • iterator(): Returns an iterator that reflects the state of the set at the exact moment this method was called, unaffected by future add or remove calls.

The iterator must support the hasNext() and next() methods. You should aim for efficient memory usage and performant operations.

Constraints

  • The set can contain up to 10^5 elements.
  • add, remove, and contains should ideally perform in O(1) or O(log N) time.
  • The iterator() call should be as efficient as possible regarding memory overhead.

Example

ss = SnapshotSet()
ss.add(1)
ss.add(2)
it = ss.iterator()
ss.add(3)
ss.remove(1)

# Expected behavior:
# it.next() -> 1
# it.next() -> 2
# it.hasNext() -> False

Edge Cases

  • Creating an iterator on an empty set.
  • Calling iterator() multiple times, where each iterator remains isolated from the other's timeline.
  • Modifying the set while the iterator is being traversed.

Hints

Hint 1

Consider how you can store a versioned copy of the elements to ensure the iterator is not impacted by later changes.

Hint 2

Using a copy-on-write strategy might be too memory-intensive; think about using data structures that allow for shared state or efficient snapshots.

Hint 3

If you use a simple list of elements for the iterator, how does that handle the requirement that `add` and `remove` operations remain efficient?

Follow-up questions

  • How would your implementation change if you needed to support a 'version' number for each element to track when it was added or removed?
  • What is the space complexity of your `iterator()` method if the set contains N elements?
  • Can you modify your design to support a multi-threaded environment where multiple threads are calling `add` and `iterator` simultaneously?