How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Implement a Snapshot Set Iterator | Databricks Coding Question

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.

Input: (["remove","iterator","next","add","add","iterator","remove","next","contains"], [[10],[],[0],[-1],[-1],[],[-1],[1],[-1]])

Expected Output: [0, None, 1, -1, False]

Explanation: Removing from an empty set does nothing. The first iterator is over an empty snapshot, so `next(0)` is `None`. Adding -1 twice keeps only one copy.

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

Expected Output: [0, 1, -3, -3, 0, None, 2, None]

Explanation: Iterator 0 snapshots {-3, 0, 2}. After removing 0 and 2, iterator 1 snapshots only {-3}. The older iterator still returns all of its original values.

Input: (["add","add","iterator","next","remove","next","add","next","contains"], [[7],[7],[],[0],[7],[0],[8],[0],[8]])

Expected Output: [0, 7, None, None, True]

Explanation: Adding 7 twice keeps one copy. The iterator over {7} still returns 7 even after 7 is removed from the live set, and later adding 8 does not affect that iterator.

Hints

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

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.