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.

Implement the behavior of a SnapshotSet of integers by processing a sequence of operations. The set supports add, remove, contains, and snapshot iterator creation. Because this platform evaluates a function rather than a class, you must write a function that processes operations in order. Operations: - ("add", x): add x to the set. - ("remove", x): remove x from the set if it exists. - ("contains", x): check whether x is currently in the set. - ("iterator", name): create a snapshot iterator identified by name. - ("iterate", name): fully consume the snapshot iterator identified by name. Important snapshot rule: - The snapshot is taken when the "iterator" operation is executed, not when "iterate" happens later. - Later modifications to the set must not affect previously created snapshot iterators. - Since iteration order does not matter, return snapshot contents as a sorted list for deterministic grading. - Duplicate adds must not create duplicates. - Removing a non-existent element is a no-op. Return a list containing the result of every "contains" and "iterate" operation, in the order they appear.

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]]

Explanation: The first iterator snapshots the set after 5 was removed, so it sees {2, 8}. Later changes do not affect it. The second iterator is created after 1 and 2 are both present, so it sees {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]

Explanation: Removing 10 does nothing. Snapshot a is taken on an empty set. Adding 4 twice still leaves one copy. Snapshot b keeps [4] even though 4 is removed later.

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]]

Explanation: Each iterator captures a different moment in time: x sees {1,2}, y sees {2}, and z sees {1,2} after 1 is added back.

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

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

Explanation: This checks negative numbers and empty snapshots. Iterator s keeps -3 even after it is removed. Iterator t is created after the set becomes empty.

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