Implement a Snapshot Set Iterator

Q: Implement a Snapshot Set Iterator

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Implement a data structure SnapshotSet<T> with the following interface:

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:

add(5) , add(2) , add(8)
remove(5)
it = iterator() → snapshot should represent {2, 8}
add(1)
contains(2) returns true
remove(2)
contains(2) returns false
add(2)
it2 = iterator() → snapshot should represent {1, 2, 8}
Iterating it should still return {2, 8} in any order, for example [2, 8]

Design and implement this data structure.

Implement a Snapshot Set Iterator

Quick Overview

Comments (0)