0

Snapshot set with frozen insertion-order iterators

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Snapshot set with frozen insertion-order iterators

Companies: Databricks

Difficulty: Hard

Problem statement

Implement SnapshotSet, a set of integers whose iterators are frozen at the moment they are created.

API

  • add(value) -> bool: insert value. Return False and do nothing if it is already present.
  • remove(value) -> bool: delete value. Return False if it is not present.
  • contains(value) -> bool: whether value is currently in the set.
  • iterator(): return an iterator over the elements that were in the set when iterator() was called, in insertion order.

Rules

  • Changes made after an iterator is created (adds, removes, re-adds) must never affect what that iterator returns, even if the iterator is only partly consumed when they happen.
  • Insertion order means the order of the most recent add. A value that is removed and added again moves to the end.
  • Many iterators may be open at once, each with its own snapshot.
  • Aim for O(1) add, remove and contains. Creating an iterator should not copy the whole set.

Example 1

s.add(4); s.add(9); s.add(6)
it = s.iterator()
s.remove(9)
s.add(3)
list(it)            -> [4, 9, 6]
list(s.iterator())  -> [4, 6, 3]

Example 2

s.add(1); s.add(2)
a = s.iterator()
next(a)             -> 1
s.remove(1); s.add(1)
list(a)             -> [2]
list(s.iterator())  -> [2, 1]

Approach

The set itself is easy: a hash map gives O(1) add, remove and contains. The hard part is iterator(). It must list exactly the elements present when it was created, in insertion order, and nothing done to the set afterwards may change what it returns. The iterator may also be consumed slowly, with changes happening between its next() calls.

Brute force: copy on snapshot. Keep an insertion-ordered dict (in Python, a plain dict). iterator() copies its keys into a list and iterates over that list. This is correct and a good first answer. But every snapshot costs O(n) time and O(n) memory even if the caller reads one element, and k open snapshots hold k full copies. The interviewer will ask you to make iterator() cheap.

Optimal: versioned append-only log. Never copy. Record history instead, and let each iterator filter it.

  1. Keep a global epoch counter. Creating an iterator takes the current epoch e as its snapshot id and then increments the counter. Every later change is stamped with a larger epoch.
  2. Keep an append-only log of entries (value, added, removed). add(v) appends a new entry stamped with the current epoch. remove(v) does not delete anything. It sets removed on the value's live entry. A value removed and re-added gets a new entry at the end of the log, which is exactly the insertion order the set should report.
  3. A map live: value -> entry gives O(1) contains, duplicate-add checks and removes.
  4. Entry x is visible to snapshot e iff x.added <= e and (x.removed is unset or x.removed > e).
  5. The iterator remembers the log length at creation. Entries appended later are never visited.

Why it works: a change made before the snapshot has stamp <= e, and a change made after has stamp > e. So the visibility test reconstructs the set at time e exactly, while iterator() itself is O(1).

Garbage. Removed entries stay in the log, so memory would grow with the number of operations, not the set size. A removed entry is garbage once no open snapshot is old enough to see it (removed <= oldest open epoch, or no snapshots are open). We count open iterators per epoch. An iterator releases its count when it is exhausted, closed or garbage-collected. When the dead entries pass a budget (half the log), we rebuild the log without them. Compaction builds a new list. Open iterators keep a reference to the old list object, so their indices never shift under them. If old snapshots still pin the garbage, the budget doubles, so compaction stays amortized O(1) per remove.

Invariants. live holds exactly the current elements, each pointing at its unique unremoved entry. The log is in insertion order. Every entry an open snapshot can see is still in the list that snapshot holds.

Code

from __future__ import annotations
from typing import Dict, List, Optional


class _Entry:
    """One insertion of a value. A re-add after a remove is a new entry."""
    __slots__ = ("value", "added", "removed")

    def __init__(self, value: int, added: int) -> None:
        self.value = value
        self.added = added                    # epoch of the add
        self.removed: Optional[int] = None    # epoch of the remove, if any

    def visible_at(self, epoch: int) -> bool:
        return self.added <= epoch and (self.removed is None or self.removed > epoch)


class SnapshotSet:
    def __init__(self) -> None:
        self._log: List[_Entry] = []          # every insertion, in order
        self._live: Dict[int, _Entry] = {}    # value -> its current entry
        self._epoch = 0                       # stamped on every change
        self._open: Dict[int, int] = {}       # snapshot epoch -> open iterators
        self._dead = 0                        # removed entries still in _log
        self._budget = 8                      # compact when _dead exceeds this

    def add(self, value: int) -> bool:
        if value in self._live:
            return False
        entry = _Entry(value, self._epoch)
        self._log.append(entry)
        self._live[value] = entry
        return True

    def remove(self, value: int) -> bool:
        entry = self._live.pop(value, None)
        if entry is None:
            return False
        entry.removed = self._epoch
        self._dead += 1
        self._maybe_compact()
        return True

    def contains(self, value: int) -> bool:
        return value in self._live

    def __len__(self) -> int:
        return len(self._live)

    def iterator(self) -> "SnapshotIterator":
        epoch = self._epoch
        self._epoch += 1                      # later changes get a newer stamp
        self._open[epoch] = self._open.get(epoch, 0) + 1
        return SnapshotIterator(self, self._log, len(self._log), epoch)

    def _release(self, epoch: int) -> None:
        self._open[epoch] -= 1
        if self._open[epoch] > 0:
            return
        del self._open[epoch]
        if not self._open or epoch < min(self._open):
            # The oldest snapshot is gone, so its garbage may be free now.
            self._budget = max(8, len(self._log) // 2)
            self._maybe_compact()

    def _maybe_compact(self) -> None:
        if self._dead <= self._budget:
            return
        oldest = min(self._open, default=None)
        # A removed entry is garbage once no open snapshot can still see it.
        keep = [e for e in self._log
                if e.removed is None or (oldest is not None and e.removed > oldest)]
        self._dead -= len(self._log) - len(keep)
        self._log = keep
        # If old snapshots pin garbage, wait for it to double before retrying,
        # so compaction stays amortized O(1) per remove.
        self._budget = max(8, len(keep) // 2, 2 * self._dead)


class SnapshotIterator:
    """Walks the log as it stood at one epoch. Holds the list object itself,
    so a compaction (which builds a new list) never shifts indices under it."""

    def __init__(self, owner: SnapshotSet, log: List[_Entry], end: int, epoch: int) -> None:
        self._owner: Optional[SnapshotSet] = owner
        self._log, self._end, self._epoch, self._i = log, end, epoch, 0

    def __iter__(self) -> "SnapshotIterator":
        return self

    def __next__(self) -> int:
        while self._i < self._end:
            entry = self._log[self._i]
            self._i += 1
            if entry.visible_at(self._epoch):
                return entry.value
        self.close()
        raise StopIteration

    def close(self) -> None:                  # also runs on exhaustion and GC
        if self._owner is not None:
            owner, self._owner = self._owner, None
            owner._release(self._epoch)

    def __del__(self) -> None:
        self.close()

Usage:

s = SnapshotSet()
s.add(5); s.add(2); s.add(8)
it = s.iterator()
s.remove(2); s.add(2)
list(it)            # [5, 2, 8]
list(s.iterator())  # [5, 8, 2]

Complexity

Let n be the log length (live elements plus removed entries not yet compacted) and k the number of open snapshots.

  • add, contains, len: O(1).
  • remove: O(1) amortized. Compaction is O(n), but it runs only after the dead count passes a budget that is at least half the log, or double the garbage pinned last time.
  • iterator(): O(1) time and O(1) extra space. No copy is made.
  • Full iteration: O(n) for the log length at creation, not just the snapshot's size. Each next() is amortized O(1) when the dead fraction is bounded, which compaction ensures while no old snapshot pins garbage.
  • Closing an iterator: O(k) for min over open epochs, plus a possible compaction. A heap with lazy deletion makes this O(log k).
  • Space: O(live elements + entries removed after the oldest open snapshot).

Test cases

  • add(5), add(2), add(8), it = iterator(), then remove(2), add(1), add(2): list(it) == [5, 2, 8] and a new iterator gives [5, 8, 1, 2] (re-added 2 moves to the end).
  • add(5) twice: the second call returns False. The value appears once in any iterator.
  • remove(7) on an absent value returns False and changes nothing.
  • Iterator on an empty set yields nothing.
  • add(1), remove(1) with no snapshot in between, then iterator(): yields nothing.
  • Partial consumption: set [1, 2, 3], it = iterator(), next(it) == 1, then remove(2), remove(3), add(4): the rest of it is [2, 3].
  • Two snapshots at different times over the same set return their own contents independently.
  • Pinned garbage: add 0..999, open pin = iterator(), remove all of them, then 20,000 add/remove pairs. This finishes quickly (no O(n) compaction per remove), pin still yields 0..999, and once it is exhausted the log shrinks back to a few entries.
  • Randomized check against a brute-force model that copies a sorted-by-insertion list at each snapshot: identical results for thousands of mixed operations with snapshots consumed in random order.

Follow-ups

  1. Make iterators cheap to create first, then talk memory. Most interviews go brute force (copy) to lazy (versioned log). The next question is "what happens to removed entries?" That leads to the reference counting and compaction above. Discuss the two triggers: dead fraction and the oldest snapshot closing.
  2. Thread safety. Writers take a lock around add/remove/iterator(). Readers need no lock to filter entries, because entries are only appended and removed changes from unset to a stamp exactly once. The risk is compaction swapping _log while a writer appends. Do compaction under the writer lock. Copy-on-write snapshots (an immutable persistent structure published through one atomic reference) remove reader locks entirely.
  3. iterator(snapshot_id) / named snapshots. Return an id from snapshot() and allow many iterators per id, or contains(value, snapshot_id). Keep per-value version lists (value -> [(added, removed)]) and binary-search them for point queries in O(log versions).
  4. Sorted iteration instead of insertion order. Replace the log with a persistent balanced BST or treap. Each update copies O(log n) nodes, a snapshot is a pointer to the root, and iteration is an in-order walk. Updates become O(log n).
  5. Iteration cost proportional to the snapshot's size. With heavy churn, a long-lived snapshot scans many dead entries. Options: compact more eagerly per epoch range, or switch to a persistent structure where a snapshot only reaches nodes it contains.

Interviewer expectations

Mid-level (L4)

  • Correct set semantics with a hash map, including duplicate adds and removes of absent values.
  • The copy-on-snapshot solution, correct and tested, with its O(n) cost stated.
  • Moves toward the versioned idea with hints and handles re-add ordering.

Senior (L5)

  • Proposes the epoch-stamped append-only log without prompting and states the visibility rule precisely.
  • Gets the edge cases right: re-add goes to the end, changes during a partially consumed iteration, add and remove inside one epoch.
  • Raises unbounded growth unprompted and sketches reference-counted compaction.

Staff (L6+)

  • Delivers compaction that is safe for open iterators (new list, not in-place) and amortized, and explains why naive "compact when dead > half" degrades to O(n) per remove when an old snapshot pins garbage.
  • Handles iterator lifetime in the language (close, exhaustion, GC) instead of assuming every iterator is drained.
  • Compares log-and-filter with persistent trees and MVCC in databases (Delta Lake time travel, Postgres tuple visibility), and gives a concurrency plan.

Sign in to comment, vote or remix.