Debug and Extend Cursor Queries

You are in an AI-assisted coding interview. You may consult AI-generated suggestions, but you are expected to validate them, explain your reasoning out loud, and share your screen while you work. The interviewer is judging how you use AI — whether you read, test, and challenge its output — as much as the final code.

You are given a small in-memory database abstraction. A table is a list of rows, where each row is a dictionary from column name to value. A query returns a cursor object that supports incremental, forward-only iteration over the matching rows via has_next() / next().

A simplified implementation is shown below:

class Cursor:
 def __init__(self, rows):
 self.rows = rows
 self.index = 0

 def has_next(self):
 self.index += 1
 return self.index < len(self.rows)

 def next(self):
 if not self.has_next():
 return None
 return self.rows[self.index]

class Table:
 def __init__(self):
 self.rows = []

 def insert(self, row):
 self.rows.append(row)

 def query(self, predicate=lambda row: True):
 return Cursor([row for row in self.rows if predicate(row)])

The intended idiom for consuming a cursor is the standard iterate-until-exhausted loop:

cursor = table.query(lambda r: r["active"])
while cursor.has_next():
 row = cursor.next()
 process(row)

You will work through four parts: debug the cursor, design a new feature, review a proposed pull request, and debug a production incident. Treat any AI suggestion you reach for as a draft to be verified, not an answer.

Constraints & Assumptions

• Single-process, in-memory store; rows are plain Python dicts. Assume CPython unless you state otherwise. No real SQL engine, no network.
• A cursor is forward-only (no rewind) and single-pass unless you justify changing the contract.
• Tables can range from a handful of rows to roughly $10^5$–$10^6$; your answers should note where an approach stops scaling (when "copy everything per query" becomes a real cost).
• "Concurrency" in Parts 2–4 means other threads or async tasks calling insert / delete / update on the same Table while a cursor is being consumed. State the concurrency model you assume (single-threaded, GIL-protected threads, snapshot isolation, etc.) — that choice is part of the answer.

Clarifying Questions to Ask

• What is the expected end-of-stream behavior — return None, raise StopIteration, or support both?
• Is a cursor meant to observe a point-in-time snapshot, or a live view that reflects writes made after the query started?
• Can one cursor be consumed by multiple threads, or is it owned by a single consumer?
• For pagination, is page size fixed by the server or chosen by the client, and is exactly-once delivery across pages a requirement?
• Are callers allowed to mutate row dictionaries in place, or should the store guarantee they can't alter persisted state?
• What ordering, if any, does query() guarantee today — insertion order or none?

Part 1 — Bug finding & cursor semantics

Identify the cursor-iteration bug(s) in the implementation above. State the cursor contract you'd expect, explain concretely what the current code does wrong, and fix it. Demonstrate the failure with a trace — show what the canonical while has_next(): next() loop actually yields for a small table — and show your fix returns every matching row exactly once, in order.

What This Part Should Cover

• A precise cursor contract: has_next() is pure / idempotent (repeated calls don't advance), next() advances exactly once, and a single, documented end-of-stream behavior.
• A concrete trace of the original code that shows why it skips rows and double-advances (the index moves two positions per consumed row) — not just an assertion that it is buggy.
• A clean fix verified against the edge cases: empty result, single row, past-the-end, and repeated has_next() before a next().

Part 2 — New feature design

Add support for one of the following and walk through the design — API surface, data structure / algorithm, time / space cost, where it stops scaling, and which class owns the logic (cursor vs. table vs. query):

• limit(n) — stop after at most n rows.
• order_by(column) — return rows sorted by a column.
• Pagination with a stable resume token — fetch a page, hand back a token, resume the next page from that token.

What This Part Should Cover

• Correct behavior for the chosen feature, including its edge cases (e.g. limit(0) and limit > len(rows), an order_by tie-breaker, a deleted boundary row in pagination).
• Honest time / space complexity and the scaling cliff — the point at which "re-scan / re-sort / re-copy per query" stops being acceptable, and what replaces it (maintained index, heap, keyset seek).
• A clear decision about which class owns the new logic (cursor vs. table vs. query) and how it composes with the existing API.

Part 3 — Pull request review

An AI agent proposes a change that, on every query() call, eagerly copies all matching rows into the cursor, storing mutable references to the original row dictionaries. Review it: what correctness, performance, and maintainability concerns would you raise, and what would you ask the author to change before approving?

What This Part Should Cover

• The isolation insight: copying the list of references is not a snapshot when the row dicts still alias the live store, so a caller (or a concurrent write) can mutate persisted state mid-iteration.
• The performance cost: $O(n)$ time and memory per query, GC churn at scale, and how eager materialization defeats early-exit consumers (a limit(1) still pays to copy everything).
• Concrete review outcomes: name the undocumented contract (snapshot vs. live vs. isolated) and the specific changes and tests required before approval.

Part 4 — Production debugging

Users report that some paginated queries return duplicate rows or skip rows while writes happen concurrently. Explain how you'd investigate, reproduce, instrument, and fix this — as a structured methodology, not just the final answer.

What This Part Should Cover

• A disciplined methodology: symptom → hypothesis → instrumentation → deterministic repro → root-cause fix → regression test — rather than jumping straight to a patch.
• Correctly fingering the root cause (offset drift and / or a non-unique sort key) and the diagnostic signal that distinguishes them (a per-page first / last key plus a table-version log line).
• A root-cause fix (keyset paging over a stable total order, or a versioned snapshot) plus the regression tests that prove it (concurrent writes, duplicate keys, deleted boundary row).