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 Microsoft.

What role is this question designed for?

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

Implement a Snapshot Set Iterator | Microsoft Coding Question

Quick Overview

This question evaluates proficiency in data structure design, iterator semantics, and managing snapshot consistency for mutable collections. It is commonly asked in the Coding & Algorithms domain to assess practical implementation skills and conceptual understanding of producing an iterator that reflects the set's state at the moment iterator() is called, testing practical application with reasoning about immutability, consistency, and complexity.

Implement a Snapshot Set Iterator

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a data structure `SnapshotSet<T>` with the following interface: ```java interface SnapshotSet<T> { void add(T e); void remove(T e); boolean contains(T e); Iterator<T> iterator(); } ``` Requirements: - `add(e)`: adds `e` to the set. - `remove(e)`: removes `e` from the set. - `contains(e)`: returns whether `e` is currently in the set. - `iterator()`: returns an iterator over a **snapshot** of the set at the moment `iterator()` is called. Important behavior: - The returned iterator must continue to iterate over the elements that existed when it was created, even if the set is later modified. - The snapshot is taken when `iterator()` is called, not when iteration begins. - Iteration order does not matter. - Because this is a set, duplicate adds should not create duplicate elements. - Removing a non-existent element can be treated as a no-op. Example: 1. `add(5)`, `add(2)`, `add(8)` 2. `remove(5)` 3. `it = iterator()` → snapshot should represent `{2, 8}` 4. `add(1)` 5. `contains(2)` returns `true` 6. `remove(2)` 7. `contains(2)` returns `false` 8. `add(2)` 9. `it2 = iterator()` → snapshot should represent `{1, 2, 8}` 10. Iterating `it` should still return `{2, 8}` in any order, for example `[2, 8]` Design and implement this data structure.

Quick Answer: This question evaluates proficiency in data structure design, iterator semantics, and managing snapshot consistency for mutable collections. It is commonly asked in the Coding & Algorithms domain to assess practical implementation skills and conceptual understanding of producing an iterator that reflects the set's state at the moment iterator() is called, testing practical application with reasoning about immutability, consistency, and complexity.

Simulate a **snapshot-able set of integers** by replaying a sequence of operations, and return the results produced along the way. Conceptually you are modeling a set that supports `add`, `remove`, and `contains`, plus the ability to create **snapshot iterators** that capture the set's contents at a moment in time. Because this platform grades a function (not a class), implement everything inside a single function that processes the operations in order. ## Function ```python def solution(operations): ... ``` - **`operations`** is a list. Each element is a 2-item operation of the form `(command, value)`, where `command` is a string and `value` is either an integer element or a snapshot name (a string), depending on the command. ## Operations Process the operations from first to last: - **`("add", x)`** — Add integer `x` to the set. Adding a value already present is a **no-op** (the set never holds duplicates). - **`("remove", x)`** — Remove integer `x` from the set if present. Removing a value that is **not** in the set is a **no-op**. - **`("contains", x)`** — Determine whether integer `x` is currently in the set. **Append a boolean** (`True`/`False`) to the result. - **`("iterator", name)`** — Create a snapshot iterator identified by `name`. This **freezes a snapshot** of the set's current contents at this moment. Nothing is appended to the result here. - **`("iterate", name)`** — Consume the snapshot iterator identified by `name` and **append its frozen contents** to the result (see output format below). ## Snapshot rule (key behavior) - A snapshot captures the set **at the moment the `("iterator", name)` operation runs** — not when the later `("iterate", name)` runs. - Modifications (`add`/`remove`) made **after** a snapshot was created must **not** affect that snapshot. Each snapshot is independent. ## Output format Return a list containing the result of **every `"contains"` and every `"iterate"` operation**, in the order those operations appear. Other operations contribute nothing to the result. - A `"contains"` result is a **boolean**. - An `"iterate"` result is the snapshot's contents returned as a **sorted list of integers** (ascending). Iteration order is otherwise irrelevant; sorting is used so grading is deterministic. An empty snapshot yields `[]`. ## Examples - After `("add", 5), ("add", 2), ("add", 8), ("remove", 5)`, an `("iterator", "it")` freezes `{2, 8}`. A later `("iterate", "it")` returns `[2, 8]` even if more elements were added afterward. - `("add", 3), ("add", 3), ("add", 3)` followed by `("iterator", "d"), ("iterate", "d")` returns `[3]` (duplicates collapse). - `("remove", 10)` on an empty set is a no-op; a snapshot taken immediately after iterates to `[]`. ## Constraints - `0 <= len(operations) <= 10^4` - Element values are integers in the range `[-10^9, 10^9]`. - Snapshot names are unique across `"iterator"` operations. - Each `"iterate"` refers to a previously created snapshot name, and each snapshot name is iterated **at most once**. - The sum of snapshot sizes over all `"iterator"` operations is at most `10^5`.

Constraints

0 <= len(operations) <= 10^4
Element values are integers in the range [-10^9, 10^9]
Snapshot names are unique across "iterator" operations
Each "iterate" refers to a previously created snapshot name, and each snapshot name is iterated at most once
The sum of snapshot sizes over all "iterator" operations is at most 10^5

Examples

Input: ([("add", 5), ("add", 2), ("add", 8), ("remove", 5), ("iterator", "it"), ("add", 1), ("contains", 2), ("remove", 2), ("contains", 2), ("add", 2), ("iterator", "it2"), ("iterate", "it"), ("iterate", "it2")],)

Expected Output: [True, False, [2, 8], [1, 2, 8]]

Input: ([("remove", 10), ("iterator", "a"), ("iterate", "a"), ("add", 4), ("add", 4), ("contains", 4), ("iterator", "b"), ("remove", 4), ("iterate", "b"), ("contains", 4)],)

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

Input: ([("add", 1), ("add", 2), ("iterator", "x"), ("remove", 1), ("iterator", "y"), ("add", 1), ("iterator", "z"), ("iterate", "x"), ("iterate", "y"), ("iterate", "z")],)

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

Input: ([("add", -3), ("contains", -3), ("iterator", "s"), ("remove", -3), ("contains", -3), ("iterate", "s"), ("iterator", "t"), ("iterate", "t")],)

Expected Output: [True, False, [-3], []]

Input: ([],)

Expected Output: []

Input: ([("add", 3), ("add", 3), ("add", 3), ("iterator", "d"), ("iterate", "d")],)

Expected Output: [[3]]

Input: ([("add", 1000000000), ("add", -1000000000), ("add", 0), ("iterator", "big"), ("remove", 0), ("iterate", "big"), ("contains", 0)],)

Expected Output: [[-1000000000, 0, 1000000000], false]

Hints

A hash set is enough to maintain the current live set efficiently for add, remove, and contains.
The key is that an iterator must not depend on the live set after it is created. Store a separate snapshot when the "iterator" operation happens.

Last updated: Apr 19, 2026

Loading coding console...