Coding interview: How do you implement a resumable, serializable iterator?

Question and context

Implement an iterator with getstate() and setstate(): start with one list, then extend it to concurrent iteration over multiple sources and asynchronous reads. How do you define state, guarantee no duplicates or skips after recovery, and handle completion, failures, and invalid snapshots?

This matches a public OpenAI coding interview record whose progression covers a list iterator, a multi-file composite iterator, and a coroutine-based version. It fits general coding, infrastructure, data-processing, and machine-learning engineering roles. The challenge is not pausing a generator; it is encoding “what the next call must return” as verifiable, serializable state.

What the interviewer evaluates

• Do you define next() input, output, completion, and error semantics instead of relying on hasNext()?
• Do you separate runtime objects from persistable state?
• Can you prove that recovery neither repeats nor skips a delivered element?
• Do you track each source’s progress and the global scheduling order?
• Do you handle async reads, cancellation, retry, and resource cleanup?
• Do you test empty sources, invalid snapshots, source changes, and idempotent recovery?

Clarifying questions before coding

• Is a source an immutable list, an append-only file, or a mutable external stream? If it can change, the snapshot needs a version or content fingerprint.
• Does recovery repeat the last returned value or start at the next unreturned value? This answer uses the latter and advances the cursor only after successful delivery.
• Is multi-source order round-robin, global time order, or any-ready-source-first? The choice changes the state fields and fairness proof.
• Must get_state() survive a process or schema-version change? If so, store versioned scalars and source IDs only, never file handles, promises, or generator objects.

A 30-second answer

“I first define the checkpoint as the element that the next next() call will return. A single list stores an index and source version; multiple sources store each cursor plus scheduler state. next() advances a cursor only after successful delivery, so restoring the same state returns the same element and does not repeat a confirmed one. The snapshot is versioned JSON, validated against source fingerprints and bounds before restore. The async version separates in-flight I/O from recoverable state, supports cancellation, cleanup, and per-source retry, and never serializes runtime handles.”

Step-by-step deep answer

Step 1: Define the minimal interface and checkpoint

Use next(), getstate(), and setstate(state) without adding hasNext(). A finite iterator returns one consistent done result or raises the agreed completion exception; callers should not probe ahead and guess the state.

Place the checkpoint at the “next item,” not the “last item.” A list source can store {sourceId, version, index, done}. next() reads items[index] and increments the index only after the value is successfully delivered; a read failure leaves the state unchanged for retry.

class ListIterator:
    def __init__(self, items, source_id, version):
        self.items = items
        self.source_id = source_id
        self.version = version
        self.index = 0

    def next(self):
        if self.index == len(self.items):
            return {"done": True}
        value = self.items[self.index]
        self.index += 1
        return {"done": False, "value": value}

    def get_state(self):
        return {
            "schema": 1,
            "sourceId": self.source_id,
            "version": self.version,
            "index": self.index,
        }

    def set_state(self, state):
        if state["schema"] != 1 or state["sourceId"] != self.source_id:
            raise ValueError("incompatible state")
        if state["version"] != self.version or not 0 <= state["index"] <= len(self.items):
            raise ValueError("stale or invalid state")
        self.index = state["index"]

Step 2: State the invariant and prove recovery

The main invariant is that index equals the number of successfully delivered elements; the snapshot index equals the in-memory cursor; and the source version is unchanged. next() advances only after returning a value, while set_state() accepts only a matching version and valid bounds, so the same checkpoint produces the same suffix.

If the business contract is at-least-once rather than exactly-once, repeating the last item between delivery and checkpoint is acceptable, but the state must include an acknowledgement marker or idempotency key. Do not mix both semantics in one set_state() contract.

Step 3: Extend to multiple sources

A composite iterator stores an independent children[sourceId] state and scheduler state such as a round-robin queue, completed-source set, and sequence number. Round-robin chooses the next unfinished source; global ordering requires saving each source’s prefetched head so comparisons can be reproduced after recovery.

A multi-source snapshot can be {schema, children: [{id, state}], scheduler: {kind, cursor}, emitted}. Validate source membership and order first, restore children next, and restore the scheduler last. A single total count is insufficient because source progress diverges.

Step 4: Make state serializable and evolvable

Persist only JSON-shaped scalars, arrays, and objects with a schema version. File handles, network connections, locks, promises, generator stacks, and closures are runtime resources; reopen or rebuild them during recovery instead of writing them into the snapshot.

When a new version reads an old snapshot, run an explicit migration. If compatibility is uncertain, reject recovery and restart from a safe boundary. If source content can change, store an ETag, length, chunk checksum, or logical version so the same index cannot silently refer to different data.

Step 5: Add async reads, cancellation, and retry

An async next() returns a promise and may await several sources concurrently, but state commits still follow “commit after successful delivery.” Cancellation stops new reads, closes files or network resources, and leaves uncommitted cursors unchanged.

Classify failures as retryable I/O, permanent format errors, or source-version changes. Back off and retain the checkpoint for retryable errors; record a source ID and offset before ending a permanently bad source; require revalidation or a new snapshot after a source change instead of silently switching content.

Step 6: Design tests and complexity

For one source, verify that next(), save, continue, and restore produce exactly the same sequence. Test an empty list, boundary index, calling next after the last item, repeated set_state, and an invalid version. Multi-source tests cover one source ending early, completion order differing from scheduling order, cancellation, and one-source failure.

Single-source next and snapshot reads/writes are O(1), with O(1) state size. With m sources, a snapshot is at least O(m). A heap or prefetched heads can make next O(log m); round-robin can be amortized O(1). The complexity must match the chosen scheduler.

High-quality sample answer

“I would first state the recovery contract: the snapshot names the element that the next next() call must return, and the cursor advances only after successful delivery. A list iterator stores source ID, version, and index, then validates the index; a read failure does not commit the cursor, so retry is safe.

For multiple sources, each child keeps its own state, while the composite stores a round-robin cursor, completed sources, and output sequence. If global order is required, it also stores each source’s prefetched head. The snapshot is versioned JSON; file handles, promises, and generator stacks are rebuilt after recovery.

Async next may wait for I/O concurrently, but state commits still happen after delivery. Cancellation closes resources and preserves uncommitted state. Errors are classified as retryable, permanent, or source-version changes. Tests prove that one snapshot yields the same suffix without duplicates or skips, and that changing completion order still satisfies the scheduling contract. Single-source operations are O(1), while an m-source snapshot is O(m), with next complexity determined by round-robin or heap scheduling.”

Common mistakes

• Saving the returned index as the next index → recovery repeats or skips an element → define checkpoint semantics and advance after delivery.
• Serializing file handles or generator objects → the objects do not survive a process restart → store versioned scalars and rebuild resources.
• Probing with hasNext() → an async source can change between probing and consuming → let next() return a value or completion result atomically.
• Saving only a total count for multiple sources → per-source progress and scheduler position disappear → save every child state and scheduler state.
• Advancing after a read failure → retry loses data → commit only after successful delivery.
• Restoring without checking source version → the same offset may identify different content → validate a fingerprint, length, or logical version and reject stale state.

Follow-up questions and responses

What if a snapshot is written after a read succeeds but before delivery is acknowledged?

Define the acknowledgement boundary. If the snapshot can land first, the system is at-least-once and each item needs an idempotency key or acknowledgement marker. For exactly-once behavior, put delivery acknowledgement and cursor commit in one recoverable transaction or external commit log.

How do you keep several ready async sources fair?

Persist the last-selected cursor in a round-robin scheduler and advance it after each successful delivery; the fastest source must not monopolize output. For global time order, use a min-heap of source heads and include the heap head and comparison rule in the snapshot.

Can a file appended while paused be resumed safely?

Only if append-only behavior is part of the contract. Store the version, consumed length, and chunk checksums, then resume from the old length. If the file can be rewritten or reordered, reject the version mismatch and create a new snapshot.

How do you cancel next() while it waits on several I/O operations?

Pass a cancellation signal, stop reads that have not started, and close opened resources. No unresolved promise may advance a cursor. A later next() either retries from the original checkpoint or returns an explicit cancellation state.