Implement an in-memory key-value store that supports transactions.
Implement an in-memory key-value store that supports transactions. Core operations: set(key, field, value), get(key, field), delete(key, field). Transaction operations: begin/start a transaction, commit, and rollback. The key constraint is nested transaction semantics: a begin inside an active transaction creates an inner transaction; reads within any transaction must reflect writes made in that same transaction (read-your-write isolation); and outer-transaction rollback must also discard inner commits. Observed variants add TTL expiration and backup/restore on top of the transactional core. This is xAI's most-reported coding question (9 reports across a year), typically run in a CodeSignal-style staged format where requirements arrive level by level.
How would you productionize this solution?
If the outer transaction rolls back after inner transactions have committed, what happens to those inner commits?
Can a transaction read its own uncommitted writes?
What is the practical difference between nested transactions with cascading rollback versus flattening all writes into a single transaction?
How do you handle TTL expiration on backup and restore?
| Approach | Notes |
|---|---|
| Copy-on-write snapshot per transaction | take a full snapshot at each begin — simple to reason about but O(N) memory per transaction |
| Undo log / undo buffer | record the previous value of each key before overwriting; on rollback, replay the undo log in reverse — O(writes) memory, the production-grade answer). |
Common mistakes: One candidate noted that adding their own test cases exposed a bug in a different coding round (LRU), suggesting self-testing was expected but risky if it reveals problems under time pressure.
Interviewer hints: Interviewers explicitly called out the cascading rollback rule: 'if the outer txn rollbacks, the already-committed inner txns must also be rolled back' — this was stated as a hard requirement, not inferred.; At least one interviewer (or commenter acting as proxy) asked directly: 'what is the difference between nested transactions with cascading rollback and just flattening everything into a single transaction?' — implying candidates should be prepared to articulate why nesting matters.; No concurrency is required — the model is explicitly single-threaded, per interviewer clarification.
What passers do: Candidates who passed were familiar with the nested-transaction KV store problem from other companies beforehand — one report noted 'this problem has been asked at other companies too, you can search for it.'; Correctly implementing read-your-write isolation inside a transaction (get reflects in-transaction sets before commit) was expected as a baseline.; Correctly implementing cascading rollback — inner committed transactions are undone when outer transaction rolls back — was the key differentiating constraint interviewers emphasized.
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 16 xAI questions, refreshed monthly from new candidate reports.