Coding Interview: How Do You Design a Resumable Batched Iterator?

Prompt and context

Design an iterator that walks a paginated remote API one item at a time. Each page has at most 100 items and uses a pageToken; requests may fail or return duplicates, and the caller saves a cursor at arbitrary points to resume later. Explain the interface, invariants, buffering, deduplication, recovery semantics, complexity, and tests.

Iterator design appears in public interview material; the Java API defines hasNext() as checking for another element and next() as returning it or throwing when none remains. This question extends the familiar in-memory pattern to a resumable, batched remote iterator and focuses on state boundaries.

What interviewers assess

An average answer writes one array index. A strong answer separates the page token, in-page index, delivered item, and checkpoint acknowledged by the caller, then explains why retries cannot skip or duplicate silently. Follow-ups cover duplicate pages, data changing during pagination, a crash after hasNext(), and concurrent calls.

The core signal is using invariants to control an external side effect instead of treating remote pagination like a local array.

Clarifying questions

• Is ordering stable? Assume an immutable (createdAt, id) order; without it, exact recovery cannot be promised.
• Is recovery at-least-once or exactly-once? Choose at-least-once reads and let the caller deduplicate by stable ID; the remote service has no cross-request transaction.
• Can rows be inserted or deleted? Assume a snapshot or consistency token fixes the result set; otherwise promise only a weak traversal.
• Are concurrent calls allowed? Default to single-threaded use; concurrent calls need a lock or an explicit state error.
• Can iteration continue after failure? Retry transient network errors within a limit; propagate authentication, parameter, and expired-snapshot errors immediately.

30-second answer

“I split the cursor into a snapshot version, next-page token, and in-page index. The iterator caches one page; hasNext() does not advance delivery state, while next() consumes one item and advances the index. The persisted cursor represents the last delivered item acknowledged by the caller, so recovery may repeat a boundary and is at-least-once; downstream code deduplicates by stable ID. The API needs stable ordering and a snapshot, otherwise I state weaker consistency. Network failures have bounded retries and permanent errors propagate.”

Step-by-step answer

Step 1: Define state and the interface contract

The interface can expose hasNext(), next(), checkpoint(), and close(). hasNext() may inspect the buffer or prefetch one page, but it must not mark an item delivered. next() returns one item and advances index. checkpoint() creates a serializable token; the caller decides when that progress is acknowledged.

Step 2: Establish the invariants

0 <= index <= len(buffer)
next() returns buffer[index], then increments index
replace buffer and pageToken only after a whole page succeeds
the recovery token represents only the caller-acknowledged prefix
permanent errors are never swallowed by a retry loop

If the next-page request fails, keep the old buffer and delivery position. If a new page succeeds but the process crashes before saving a checkpoint, recovery repeats a suffix, which is at-least-once. Saving the checkpoint before delivery could skip an item, so the order matters.

Step 3: Implement page reads and bounded retries

class ResumableIterator:
    def __init__(self, client, checkpoint=None, page_size=100):
        self.client = client
        self.page_size = page_size
        self.snapshot = checkpoint.snapshot if checkpoint else None
        self.token = checkpoint.page_token if checkpoint else None
        self.index = checkpoint.index if checkpoint else 0
        self.buffer = []
        self.done = False

    def has_next(self):
        self._ensure_buffer()
        return self.index < len(self.buffer)

    def next(self):
        self._ensure_buffer()
        if self.index == len(self.buffer):
            raise StopIteration
        item = self.buffer[self.index]
        self.index += 1
        return item

    def checkpoint(self):
        return Checkpoint(self.snapshot, self.token, self.index)

ensurebuffer() requests the next page when the current page is exhausted, using exponential backoff and a maximum attempt count. A timeout may follow a successful server-side request, so the retry must use the same snapshot/token and the server must return a stable page or an observable duplicate boundary.

Step 4: Handle duplicates, inserts, and deletes

A page token alone may not prevent duplicate data after a retry. If the API returns a stable id, discard the prefix at a recovery boundary where id <= lastId; for a compound sort, compare the complete (createdAt, id) cursor. Do not grow an unbounded deduplication set; a server snapshot and boundary token keep deduplication local to the recovery window.

Without a snapshot, a new row can appear before the current page and a deletion can make the next page skip an item. Promise only a best-effort traversal of the visible result, not exactly-once or strong consistency. In an interview, lower the guarantee explicitly or require a snapshot version.

Step 5: Define checkpoint and recovery semantics

A checkpoint should contain the version, snapshot, token, in-page index, last stable ID, a filter digest, and an expiration time. The filter digest prevents restoring a cursor for one query into another; expiration prevents silently reading a different result after the server reclaims a snapshot.

Rebuild the iterator from the checkpoint. If the caller saves immediately after consuming item, recovery may repeat that item, so downstream writes should be idempotent by stable ID. If the business requires no duplicates, progress and the business result must share a transaction or the downstream store must provide a deduplication table; the iterator cannot create exactly-once by itself.

Step 6: Complexity, backpressure, and close

Buffer space is O(pagesize) and local advancement is O(1) per item. Remote reads are about ceil(N / pagesize), excluding retries. hasNext() may issue a network request, so callers should not treat it as free. Prefetch can hide latency but must cap itself at one page or a byte budget.

close() cancels outstanding work and releases the connection; server snapshots need a TTL. If a consumer is slower than the producer, the API should rate-limit or return an expired-snapshot error rather than extending a snapshot forever. Concurrent calls must be rejected or serialized, or two next() calls can observe the same index.

High-quality sample answer

“I would model the remote iterator as a small state machine with snapshot, pageToken, buffer, index, and lastId. hasNext() only ensures that a buffer item exists; next() advances index; checkpoint() stores the caller-acknowledged prefix. Replace the buffer only after a whole page succeeds, retry transient timeouts with a bound, and propagate permanent errors.

“For recovery I require stable ordering and a snapshot token. The checkpoint also contains the query digest, in-page index, last stable ID, and expiration. Recovery may repeat the boundary, so I promise at-least-once and make downstream writes idempotent by ID. Without a snapshot, inserts and deletes weaken the guarantee.

“The buffer is O(pagesize), each next is O(1), and remote pages are about ceil(N/pagesize). Tests cover empty pages, duplicate pages, expired tokens, a timeout after server success, checkpoint crashes, mutations, repeated recovery, concurrent next, backpressure, and close. Exactly-once requires a shared transaction or a deduplication store.”

Common mistakes

• Symptom → Treating the remote API as an array and restoring one integer index → Why it fails → Page boundaries and mutations point that index at different items → Fix → Persist the snapshot, token, in-page index, and stable ID.
• Symptom → Advancing the token in hasNext() → Why it fails → A caller can inspect without consuming and then crash, skipping data → Fix → Advance delivery state only after next() returns an item.
• Symptom → Moving to the next page after a timeout → Why it fails → A whole page may be lost or a successful request may be duplicated → Fix → Retry the same token and deduplicate by stable ID.
• Symptom → Claiming exactly-once from the iterator → Why it fails → Checkpoint persistence and business side effects are not one atomic transaction → Fix → Promise at-least-once and make the sink idempotent or transactional.
• Symptom → Unlimited prefetch and retries → Why it fails → Slow consumers exhaust memory and outages block forever → Fix → Bound buffers, attempts, timeouts, and snapshot TTL.

Follow-ups and responses

What if the server provides only a page number, not a snapshot token?

Require a stable compound-key cursor or state that only weakly consistent traversal is possible. Page numbers move after inserts and deletes, so they cannot prove no skips or duplicates.

What if the sink accepts each item only once and cannot deduplicate?

The iterator cannot guarantee exactly-once alone. Put progress, the business write, and the checkpoint in one transaction, or require an idempotent sink; otherwise write possible duplicates into the contract.

What if one page keeps timing out?

Keep the old buffer and do not advance the token. After the retry limit, raise a classified error so the caller chooses pause, skip, or restart. A skip must record a gap and cannot silently move to the next page.