Katkat
Back

Implement Snapshot Iterator Without Order Guarantees

DatabricksSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates data-structure design and iterator semantics—specifically snapshot iteration over a mutable, set-like collection without order guarantees—and tests skills in implementing mutation-isolated iteration and analyzing time and space complexity; it belongs to the Coding & Algorithms domain and emphasizes practical implementation.

Design and implement a mutable collection that supports snapshot iteration.

The collection stores unique values and supports the following operations:

  • add(value): add value to the collection if it is not already present.
  • remove(value): remove value from the collection if it exists.
  • contains(value): return whether value is currently in the collection.
  • iterator(): return an iterator over a snapshot of the collection at the moment iterator() is called.

The snapshot iterator must satisfy:

  • Later calls to add or remove must not change what the iterator returns.
  • Each element that existed in the collection when the iterator was created should be returned exactly once.
  • The iterator does not need to preserve insertion order or any original data order.
  • The iterator should expose standard methods such as hasNext() and next().

Implement the data structure and discuss the time and space complexity of each operation. Pay special attention to how the lack of ordering requirements affects your design.