Quick Overview

This question evaluates understanding of set data structures, iterator and snapshot semantics, and the ability to reason about time and space complexity when providing stable views over mutable collections.

Implement a Snapshot Set Iterator

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Design and implement a set data structure that supports snapshot iteration. The set stores unique values. It must support the following operations: - `add(value)`: Add `value` to the set if it is not already present. - `remove(value)`: Remove `value` from the set if it is present. If it is absent, do nothing. - `contains(value) -> bool`: Return whether `value` is currently in the set. - `iterator()`: Return an iterator over a snapshot of the set at the moment the iterator is created. Snapshot iterator requirements: - The iterator should return exactly the values that were present in the set when the iterator was created. - Later calls to `add` or `remove` must not affect already-created iterators. - The return order of values is not important. - Each value in the snapshot should be returned exactly once. Example: ```text s = SnapshotSet() s.add(1) s.add(2) it = s.iterator() s.remove(1) s.add(3) # The iterator should still return 1 and 2 in any order. # It should not return 3. ``` Implement the data structure and iterator. Discuss the time and space complexity of your approach.

Quick Answer: This question evaluates understanding of set data structures, iterator and snapshot semantics, and the ability to reason about time and space complexity when providing stable views over mutable collections.

You need to implement a set of unique integers that supports snapshot iteration. Since this platform uses a single function instead of classes, you will process a list of operations on a virtual `SnapshotSet`. Supported operations: - `add(x)`: add `x` to the set if it is not already present. - `remove(x)`: remove `x` from the set if it is present. - `contains(x)`: return whether `x` is currently in the set. - `iterator()`: create a snapshot iterator over the set as it exists at that moment, and return its iterator id. - `next(id)`: return the next value from iterator `id`, or `None` if that iterator is exhausted. Snapshot rules: - An iterator must return exactly the values that were in the set when it was created. - Later `add` and `remove` operations must not affect already-created iterators. - Each snapshot value must be returned exactly once. For deterministic judging, every iterator should yield its snapshot values in ascending order. Return a list containing the results of every `contains`, `iterator`, and `next` operation, in the order they appear.

Constraints

  • 1 <= len(operations) == len(args) <= 20000
  • Values are integers in the range [-10^9, 10^9]
  • Every `next(id)` refers to a previously created iterator id
  • The sum of the sizes of all created snapshots does not exceed 200000

Examples

Input: (["add","add","iterator","remove","add","next","next","next","contains","contains"], [[1],[2],[],[1],[3],[0],[0],[0],[1],[3]])

Expected Output: [0, 1, 2, None, False, True]

Explanation: The iterator captures {1, 2}. After removing 1 and adding 3, that iterator still returns 1 and 2, then becomes exhausted. The live set ends as {2, 3}.

Input: (["add","add","iterator","add","iterator","remove","next","next","next","next","contains"], [[5],[1],[],[3],[],[1],[0],[1],[0],[1],[1]])

Expected Output: [0, 1, 1, 1, 5, 3, False]

Explanation: Iterator 0 snapshots {1, 5}; iterator 1 snapshots {1, 3, 5}. Removing 1 later does not change either snapshot.

Hints

  1. A snapshot iterator should not point to the live set directly. Think about what data must be frozen at the moment `iterator()` is called.
  2. If you store each snapshot separately, each iterator only needs a cursor to know which value `next()` should return.

Loading coding console...