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 medium 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 Snapshot Iterator Without Order Guarantees

Quick Overview

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.

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: 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 a mutable collection of unique integers that supports snapshot iteration. In a normal object-oriented design, `snapshot` would return an iterator object with methods such as `hasNext()` and `next()`. For this function-based problem, you will process a list of operations instead. A `snapshot` operation creates an iterator over the collection's current state and returns a new iterator id. Later `add` and `remove` calls must not change what older iterator ids will see. `hasNext(id)` reports whether that snapshot still has unconsumed elements. `drain(id)` simulates repeatedly calling `next()` until the iterator is exhausted and returns all remaining elements from that snapshot as a sorted list. The sorting is only for deterministic grading; your actual data structure does not need to preserve any order. Because order does not matter, your design should take advantage of that fact.

Constraints

0 <= len(operations) <= 2 * 10^5
-10^9 <= value <= 10^9
All iterator ids passed to `hasNext` and `drain` are valid.
The sum of collection sizes over all `snapshot` operations is at most 2 * 10^5.

Examples

Input: [('add', 5), ('add', 1), ('add', 5), ('contains', 1), ('contains', 2), ('snapshot',), ('remove', 1), ('add', 3), ('contains', 1), ('hasNext', 0), ('drain', 0), ('hasNext', 0)]

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

Explanation: The duplicate add of 5 is ignored. Snapshot 0 captures {5, 1}. Later removing 1 and adding 3 changes the live collection but not the snapshot.

Input: [('add', 10), ('add', 20), ('snapshot',), ('remove', 10), ('add', 30), ('snapshot',), ('add', 40), ('contains', 10), ('drain', 0), ('hasNext', 0), ('drain', 1), ('snapshot',), ('drain', 2)]

Expected Output: [0, 1, False, [10, 20], False, [20, 30], 2, [20, 30, 40]]

Explanation: Three different snapshots see three different collection states: {10,20}, then {20,30}, then {20,30,40}.

Input: [('snapshot',), ('hasNext', 0), ('drain', 0), ('add', -7), ('snapshot',), ('remove', -7), ('contains', -7), ('hasNext', 1), ('drain', 1), ('drain', 1)]

Expected Output: [0, False, [], 1, False, True, [-7], []]

Explanation: Snapshot 0 is empty. Snapshot 1 still contains -7 even after the live collection removes it. Draining an already exhausted iterator returns an empty list.

Input: [('add', 2), ('add', -1), ('add', 4), ('snapshot',), ('remove', 2), ('remove', 99), ('add', -1), ('snapshot',), ('contains', 4), ('contains', 2), ('drain', 0), ('drain', 1)]

Expected Output: [0, 1, True, False, [-1, 2, 4], [-1, 4]]

Explanation: Removing a missing value does nothing, and adding -1 again does nothing because values are unique. The two snapshots remain independent.

Input: [('add', 1), ('add', 2), ('snapshot',), ('snapshot',), ('remove', 2), ('add', 3), ('hasNext', 1), ('drain', 1), ('hasNext', 0), ('drain', 0)]

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

Explanation: Two iterators created from the same state should both independently return the same snapshot, even after later mutations.

Hints

If order does not matter, store current elements in a dynamic array plus a hash map from value to index. You can remove in O(1) average time by swapping the target with the last element and popping.
A snapshot iterator can simply own a copy of the current array. Then future mutations affect only the live collection, not older snapshots.

Quick Overview