In-Memory Transactional Key-Value Store

Question

The round: the second-round Cursor screen in one report (March 2026, on CoderPad): design an in-memory transactional key-value database. The candidate calls it an object-oriented class design, not system design. One report, with the interface given verbatim:

class InMemoryDB:
    def __init__(): ...
    def begin(): ...
    def get(txid, key): ...
    def set(txid, key, value): ...
    def commit(txid): ...
    def rollback(txid): ...

The round is interactive: the follow-ups depend on the design you implement, and the interviewer had test cases ready that found a corner case at once. Two follow-ups were asked, and the candidate believes a third was coming when time ran out.

Part 1 — transactions: implement InMemoryDB with the methods above (as methods, with self). begin() returns a transaction id. A transaction reads its own writes; other transactions do not see them until it commits. commit(txid) makes its writes visible; rollback(txid) discards them. A key that was never written reads as None. Whether a transaction that is already open sees another transaction's commit made after it began (read committed or a snapshot) is not reported, so the tests do not depend on it; ask.

Part 2 — concurrent transactions: ConflictCheckingDB builds on Part 1 and answers the two reported follow-ups. First, two transactions writing the same key concurrently, the race condition. Second, the swap: one transaction moves s1 into s2 while another moves s2 into s1; the report says this must raise an error, and in the report's words, if both went through it would be as if nothing had been done. (If both commit from the same starting values, the two keys simply trade places, which matches neither order of running them one after the other.) The report says a small change to the implementation fixed it. How you refuse is your design: optimistic checks at commit, locks, or anything else. The tests check the outcome, not the mechanism. A refused transaction either has commit return False or raises at any step; either way it is rolled back and its writes never appear. Two transactions that do not conflict must both succeed. The tests run one step at a time, so a lock that makes a transaction wait for another would hang here: lock without waiting (refuse at once), or check at commit.

AceOffer · Accepted Answer

The round: the second-round Cursor screen in one report (March 2026, on CoderPad): design an in-memory transactional key-value database. The candidate calls it an object-oriented class design, not system design. One report, with the interface given verbatim:

class InMemoryDB:
    def __init__(): ...
    def begin(): ...
    def get(txid, key): ...
    def set(txid, key, value): ...
    def commit(txid): ...
    def rollback(txid): ...

The round is interactive: the follow-ups depend on the design you implement, and the interviewer had test cases ready that found a corner case at once. Two follow-ups were asked, and the candidate believes a third was coming when time ran out.

Part 1 — transactions: implement InMemoryDB with the methods above (as methods, with self). begin() returns a transaction id. A transaction reads its own writes; other transactions do not see them until it commits. commit(txid) makes its writes visible; rollback(txid) discards them. A key that was never written reads as None. Whether a transaction that is already open sees another transaction's commit made after it began (read committed or a snapshot) is not reported, so the tests do not depend on it; ask.

Part 2 — concurrent transactions: ConflictCheckingDB builds on Part 1 and answers the two reported follow-ups. First, two transactions writing the same key concurrently, the race condition. Second, the swap: one transaction moves s1 into s2 while another moves s2 into s1; the report says this must raise an error, and in the report's words, if both went through it would be as if nothing had been done. (If both commit from the same starting values, the two keys simply trade places, which matches neither order of running them one after the other.) The report says a small change to the implementation fixed it. How you refuse is your design: optimistic checks at commit, locks, or anything else. The tests check the outcome, not the mechanism. A refused transaction either has commit return False or raises at any step; either way it is rolled back and its writes never appear. Two transactions that do not conflict must both succeed. The tests run one step at a time, so a lock that makes a transaction wait for another would hang here: lock without waiting (refuse at once), or check at commit.

Reported follow-ups:
1. How would you handle a race condition when two concurrent transactions write to the same key? (when: After basic implementation is working)
2. How do you handle a concurrent read/write swap scenario — e.g., tx1 reads s1 and writes it to s2, while tx2 reads s2 and writes it to s1 — where if both succeed, the net effect is a no-op? (when: After discussing concurrent writes)

Common mistakes: Running out of time before all follow-ups could be addressed; the report notes the candidate felt there was likely at least one more follow-up that was never reached due to time.

Interviewer hints: The interviewer had prepared test cases and immediately found a corner case in the candidate's implementation, then followed up on that design.

What passers do: The one report: the interviewer had test cases ready and found a corner case immediately, then asked follow-ups based on the implementation the candidate had built.

Why people fail: Running out of time before completing follow-ups on concurrency; Interviewer immediately finding corner cases with pre-prepared test cases, suggesting the base implementation had logical gaps

Edge cases probed: Rollback when a key has been written multiple times within the same transaction; Concurrent swap: tx1 s1→s2, tx2 s2→s1 — both committing would be a no-op, but should be flagged as a conflict/error; Concurrent writes to the same key from two different transactions; Reading a key within a transaction that hasn't been set yet (fall through to committed store)

Alternative approaches: MVCC (Multi-Version Concurrency Control) (Each write creates a new version; readers see a snapshot from transaction start time. Allows higher read concurrency but more complex version management and garbage collection.); 2PL (Two-Phase Locking) (Acquire locks on keys before read/write; release all at commit/rollback. Prevents conflicts by blocking rather than detecting them, but risks deadlock and reduces concurrency.); OCC (Optimistic Concurrency Control) (Allow concurrent reads/writes without locks; validate for conflicts only at commit time and abort if detected. Good for low-contention workloads; retry overhead under high contention.)

In-Memory Transactional Key-Value Store

Problem Overview

Follow-up Arc

Approach Trade-offs

What Reports Emphasize

Practice

Approach	Notes
MVCC (Multi-Version Concurrency Control)	Each write creates a new version; readers see a snapshot from transaction start time. Allows higher read concurrency but more complex version management and garbage collection.
2PL (Two-Phase Locking)	Acquire locks on keys before read/write; release all at commit/rollback. Prevents conflicts by blocking rather than detecting them, but risks deadlock and reduces concurrency.
OCC (Optimistic Concurrency Control)	Allow concurrent reads/writes without locks; validate for conflicts only at commit time and abort if detected. Good for low-contention workloads; retry overhead under high contention.