Design Snapshot Set Iteration and Clarify Durable Writes

Problem Overview

High-performance storage engines frequently decouple point-in-time reads from ongoing mutations while managing strict durability guarantees on the write path. In this two-part systems problem, you will design the core in-memory snapshot iteration mechanism and define the specifications for a durable write pipeline.

Part 1: Snapshot Set Iteration

Implement an in-memory mutable set SnapshotSet that supports insertions, deletions, membership checks, and snapshot iterators. When an iterator is created, it must traverse an exact point-in-time view of the set at the instant of creation, unaffected by subsequent additions or removals.

Naively copying the entire collection upon iterator creation is prohibited (O(1) iterator instantiation required).

class SnapshotIterator:
    def has_next(self) -> bool:
        """Returns True if elements remain in the snapshot view."""
        pass

    def next(self) -> int:
        """Returns the next distinct element in the snapshot."""
        pass

    def close(self) -> None:
        """Explicitly releases resources held by this iterator."""
        pass

class SnapshotSet:
    def __init__(self):
        pass

    def add(self, val: int) -> bool:
        """Adds val. Returns True if val was not already present."""
        pass

    def remove(self, val: int) -> bool:
        """Removes val. Returns True if val was present."""
        pass

    def contains(self, val: int) -> bool:
        """Returns True if val is currently present."""
        pass

    def iterator(self) -> SnapshotIterator:
        """Returns an iterator representing the snapshot of the set at call time."""
        pass

Requirements & In-Memory Constraints:

• Time Complexity: add, remove, and contains must run in O(1) average time. iterator() must instantiate in O(1) time.
• Space & Garbage Collection: Elements deleted while an active iterator exists must not be physically discarded until all iterators that can view them are closed or exhausted. Memory for stale versions must be reclaimable once no active iterator references them.

Part 2: Durable Write Contract

Imagine this SnapshotSet is backed by a persistent journal or Write-Ahead Log (WAL). Specify the operational contracts and failure-handling model:

1. Acknowledgment Boundary: Exactly when can an add/remove call return success to the client (e.g., in-memory buffer vs. fsync / storage lease)?
2. Ordering & Idempotency: How does the system handle concurrent out-of-order writes and client retries during network partitions or process restarts?
3. Crash Recovery: How are uncommitted updates or torn writes handled during recovery without corrupting the snapshot timeline?