Problem
Design a console key-value store with set, get, unset, value count, begin, commit and rollback operations. For this practice version, transactions may be nested and rollback undoes the most recent open transaction.
Worked examples
Input: SET a 1; BEGIN; SET a 2; ROLLBACK; GET a
Output: 1
Rollback restores the value before the transaction began.
Hints
Hint 1
Distinguish absent keys from keys with a null-like value.
Hint 2
An undo log avoids copying the entire store for each write.
Solution approach
- Start with a map for committed/current state and a stack of transaction undo logs.
- On the first modification of a key in a transaction, remember its old value or absence. Restore these entries during rollback.
- When committing a nested transaction, merge its earliest old values into the parent log. Define commit-all versus commit-most-recent before coding.
- Maintain a value-frequency map if COUNT must be constant time; update it on writes and rollback.
Complexity
Map operations average O(1); rollback is O(number of modified keys). Storage is O(keys + outstanding undo entries).
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗