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 a Snapshot Set Iterator | Databricks Coding Question

Implement a Snapshot Set Iterator

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design and implement a mutable `SnapshotSet` data structure. The set stores unique keys and supports normal set operations, plus snapshot iterators. Implement the following API: ```text class SnapshotSet: add(key) -> None remove(key) -> None contains(key) -> bool iterator() -> SnapshotIterator class SnapshotIterator: has_next() -> bool next() -> key ``` Semantics: - `add(key)` inserts `key` into the current set if it is not already present. - `remove(key)` removes `key` from the current set if it is present. - `contains(key)` returns whether `key` is currently present. - `iterator()` returns an iterator over a frozen snapshot of the set at the exact time the iterator is created. - Mutations after `iterator()` is called must not affect that iterator. - Multiple iterators may exist at the same time, each with its own snapshot view. - Each iterator should return every key that existed in its snapshot exactly once and should not return keys that were absent from that snapshot. - The iteration order may be arbitrary unless you choose to define a deterministic order. Discuss and implement an efficient approach. Consider tradeoffs between designs such as maintaining a global mutation log versus maintaining per-key version histories, especially for iterator initialization cost, memory usage, and iteration performance when the mutation log becomes large.

Quick Answer: This question evaluates data structure design, versioning, and iterator consistency concepts within the Coding & Algorithms domain, focusing on implementing a mutable set that supports snapshot iterators.

Design a function-based version of a mutable `SnapshotSet` that supports frozen snapshot iterators. The original object-oriented API is: - `add(key)` - `remove(key)` - `contains(key)` - `iterator() -> SnapshotIterator` - `has_next()` / `next()` on each iterator Because this judge is function-based, you must process a batch of operations. Implement `solution(operations, arguments)` where `operations[i]` is one of: - `add` with `arguments[i] = [key]` - `remove` with `arguments[i] = [key]` - `contains` with `arguments[i] = [key]` - `iterator` with `arguments[i] = []` - `has_next` with `arguments[i] = [iterator_id]` - `next` with `arguments[i] = [iterator_id]` When `iterator` is called, create a new snapshot iterator and return its integer id. Iterator ids start at `0` and increase by `1` each time. Snapshot semantics: - An iterator sees the set exactly as it existed when that iterator was created. - Later `add` or `remove` operations must not affect older iterators. - Multiple iterators may exist at the same time, each with its own frozen view. - Each iterator must return every key in its snapshot exactly once. For deterministic judging, every iterator must return keys in ascending numeric order. Return a list of results, one per operation: - `add` / `remove` -> `None` - `contains` / `has_next` -> `bool` - `iterator` -> the new iterator id - `next` -> the next key from that iterator Discussion note: a full copy of the set at every `iterator()` is correct but can be expensive if many snapshots are created. A global mutation log can make iterator creation cheap, but advancing an iterator may become slow when the log grows large. Per-key histories help with membership over time, but full iteration is still awkward. A versioned ordered structure gives a better balance for large inputs.

Constraints

1 <= len(operations) <= 2 * 10^5
Keys are integers in the range [-10^9, 10^9]
All iterator ids used by `has_next` and `next` are valid
`next(iterator_id)` is only called when that iterator still has at least one remaining key

Examples

Input: (['add','add','iterator','remove','add','contains','has_next','next','has_next','next','has_next','iterator','next','contains'], [[1],[2],[],[2],[1],[2],[0],[0],[0],[0],[0],[],[1],[1]])

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

Input: (['iterator','has_next','add','add','remove','remove','iterator','has_next'], [[],[0],[5],[5],[7],[5],[],[1]])

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

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

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

Input: (['add','add','iterator','remove','add','iterator','contains','next','next','has_next','next','has_next','has_next','next','has_next'], [[-1],[4],[],[-1],[2],[],[-1],[0],[1],[0],[0],[0],[1],[1],[1]])

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

Input: (['add','iterator','has_next','next','has_next'], [[42],[],[0],[0],[0]])

Expected Output: [None, 0, True, 42, False]

Input: (['add','add','add','add','iterator','next','next','next','next','has_next'], [[5],[-1000000000],[1000000000],[0],[],[0],[0],[0],[0],[0]])

Expected Output: [None, None, None, None, 0, -1000000000, 0, 5, 1000000000, False]

Input: (['add','add','iterator','remove','iterator','next','next','has_next','next','has_next'], [[7],[3],[],[7],[],[0],[0],[0],[1],[1]])

Expected Output: [None, None, 0, None, 1, 3, 7, False, 3, False]

Input: (['contains','add','contains','remove','contains'], [[9],[9],[9],[9],[9]])

Expected Output: [False, None, True, None, False]

Hints

Copying the whole set into every new iterator works, but it can be too slow when snapshots are frequent. Think about storing immutable versions of the set instead.
If you define iteration order as sorted order, coordinate compression plus a persistent segment tree can support updates and snapshot iteration efficiently.

Quick Overview

This question evaluates data structure design, versioning, and iterator consistency concepts within the Coding & Algorithms domain, focusing on implementing a mutable set that supports snapshot iterators.