Nested-Transaction KV Store
Build an in-memory key-value store:
get(key) -> value or None set(key, value) delete(key) begin() -> open a transaction commit() -> apply the innermost open transaction rollback() -> discard the innermost open transaction
Transactions nest: a begin inside a transaction opens an inner one. Reads must see uncommitted writes. Committing an inner transaction makes its writes visible to the outer transaction only; rolling back the outer transaction must undo them too. commit and rollback return true, or false when no transaction is open; deleting a missing key does nothing.
set a 1 · begin · set a 2 · get a -> 2 · begin · delete a · get a -> None rollback · get a -> 2 · commit · get a -> 2
Hints
Hint 1
Don't copy the store per transaction — record how to undo. Every write inside a transaction logs (key, previous value) once; rollback replays the log backwards.
Hint 2
Nesting falls out of a stack of logs: begin pushes an empty log, rollback pops and replays, commit pops and appends the log onto the parent's — so the parent's rollback can still undo the child's committed writes.
Hint 3
The alternative design is a stack of overlay dicts (get walks top-down). Know both: undo-log reads are O(1), overlay rollback is O(1) — name the trade-off you're taking.