The coding question
Build a set with add, remove and contains, plus iterator(), which returns an iterator over the set as it was at that moment, in sorted order. Later adds and removes mustn't change what an existing iterator returns.
Ask a few questions first
| Ask | What we'll assume |
|---|---|
| What can the items be? | Anything that can be compared and hashed, like numbers or strings. |
| Does the iterator see the set when it's created, or when you start reading it? | When it's created. Calling iterator() is the snapshot moment. |
| Which operations happen most? | Assume add, remove and contains are frequent, iterators are common, and most of them don't get read all the way through. |
| Can the set change while someone's halfway through an iterator? | Yes. The iterator should still return exactly what was there when it was made. |
| Do I need to support removing through the iterator? | No, it's read only. |
A couple of examples
| Input | Output |
|---|---|
| add(5), add(2), add(8), it1 = iterator(), remove(5), add(1), it2 = iterator() | Two iterators |
| list(it1) | [2, 5, 8] |
| list(it2), then contains(5) | [1, 2, 8], then False |
Start with brute force
Every time iterator() is called, copy the set into a sorted list and return an iterator over the copy. Later changes can't touch it.
Cost: Each iterator costs O(n log n) time and O(n) memory up front, even if the caller only reads the first item or nothing changed since the last one. With lots of iterators over a big set, that adds up fast.
A better way
Most items don't change between iterators, so copying them is wasted work. Instead, store each item's history: a list of (version, present or not) changes. Making an iterator just remembers the current version and bumps the counter, which is O(1).
To ask 'was x in the set at version v?', find the last change to x made at or before v. The versions are sorted, so that's a binary search. A hash map from item to history gives you contains in O(1).
For sorted order, keep a sorted list of every item that's ever been added. The iterator walks it lazily and only yields items that were present at its version. Since it's a generator, nobody pays for items they never read.
- Keep a version number. Changes made now belong to the current version.
- On add or remove, append (version, present) to the item's history. If the item already changed in this version, overwrite that entry instead.
- The first time an item is added, insert it into the sorted key list.
- iterator() saves the current version, adds 1 to the counter, and returns a generator for the saved version.
- The generator walks the sorted keys and yields each one whose last change at or before its version says 'present'.
The code
from bisect import bisect_right, insort
class SnapshotSet:
def __init__(self):
self.version = 0 # changes made now belong to this version
self.history = {} # item -> ([versions], [present?]), oldest first
self.keys = [] # every item ever added, sorted
def _set(self, item, present):
if item not in self.history:
if not present:
return
self.history[item] = ([], [])
insort(self.keys, item)
versions, states = self.history[item]
if states and states[-1] == present:
return # nothing changed
if versions and versions[-1] == self.version:
states[-1] = present # changed twice since the last iterator
else:
versions.append(self.version)
states.append(present)
def add(self, item):
self._set(item, True)
def remove(self, item):
self._set(item, False)
def contains(self, item):
entry = self.history.get(item)
return bool(entry) and entry[1][-1]
def iterator(self):
# Freeze the current version now. Changes after this get a higher one.
snap = self.version
self.version += 1
return self._walk(snap)
def _present_at(self, item, snap):
versions, states = self.history[item]
i = bisect_right(versions, snap) # changes made at or before snap
return i > 0 and states[i - 1]
def _walk(self, snap):
i = 0
while i < len(self.keys):
item = self.keys[i]
if self._present_at(item, snap):
yield item
# Find the next key by value, not position, so adds made
# while we're iterating can't make us skip or repeat one.
i = bisect_right(self.keys, item)| Cost | Why | |
|---|---|---|
| add / remove | O(1), or O(u) the first time | Appending to a history is O(1). Inserting a brand new item into the sorted list of u items shifts the list |
| contains | O(1) | Look up the item and check its latest state |
| iterator() | O(1) | Just a counter. The work happens as you read |
| Reading a whole iterator | O(u log h) | u items ever added, each with a binary search over its history of length h |
| Memory | O(total changes) | One entry per real change, not per iterator |
Test it
Walk through one of the examples out loud, then check the cases that tend to break things:
- An iterator over an empty set, then add items. It should still return nothing.
- Add, remove, add the same item between two iterators. Only the final state should count.
- Removing something that was never added.
- Reading an old iterator halfway, adding and removing items, then reading the rest.
- Two iterators made back to back with no changes in between.
Common mistakes
- Returning an iterator over the live set, so later changes leak into it, or Python complains the set changed size.
- Being off by one on versions, so a change made right after iterator() shows up in it. Changes after the call get a higher version than the iterator's.
- Walking the key list by position while new keys are being inserted. Positions shift, so you skip or repeat items. Find the next key by value instead.
- Recording a change when nothing changed, like adding an item that's already there, which bloats the history.
Follow-up questions
Can you make reading an old iterator faster when few items were present back then?
Yes, with a persistent balanced tree: every change makes a new root that shares most of its nodes with the old tree. An iterator just holds a root, and it only visits items that were really there.
History grows forever. How would you clean it up?
Track which versions still have a live iterator, for example with a count per version that drops when an iterator finishes or is closed. Anything older than the oldest live version can be collapsed into its latest state, and items removed before then can go.
How would you make it safe to use from several threads?
A lock around writes is the simple answer. Iterators only read history at or before their version, which never changes, so they need very little locking. That's a nice property to point out.
How the time adds up
| Minutes | What you're doing |
|---|---|
| 0–5 | Ask questions and agree on examples |
| 5–10 | Talk through the brute force |
| 10–20 | Find the better approach |
| 20–35 | Write the code |
| 35–40 | Test it out loud |
| 40–45 | Follow-up questions |
Key concepts used here
- Binary searchCut the search in half, even when you're searching for an answer.
- Hash maps and sliding windowsSwap nested loops for a single pass.
- Object-oriented designSplit a small program into classes that are easy to change.
We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Databricks.