Key-value store with transactions
An interviewer hands you this store in three parts. Each part keeps every rule from the parts before it.
Part 1. Build a class KVStore:
KVStore()starts empty.set(key, value)storesvalueunderkey, replacing any value already there.get(key)returns the value stored underkey, orNoneif there is none.delete(key)removeskeyand its value. Deleting a key that holds nothing does nothing.
Part 2. Add transactions. A transaction is a group of changes that is kept or undone as a whole.
begin()opens a transaction.rollback()undoes everysetanddeletemade since thatbegin, then closes the transaction.commit()closes the transaction and keeps its changes.rollback()andcommit()returnTrue. When no transaction is open, they change nothing and returnFalse.getalways returns the newest value, including changes made inside an open transaction.
Part 3. Transactions nest. A begin() while a transaction is open opens an inner one, and rollback() and commit() act on the innermost open transaction only. When an inner transaction commits, its changes join the transaction around it, so a later rollback() of the outer transaction undoes them too.
set, get, delete and begin must take O(1) time on average. rollback() and commit() may take time in proportion to the number of keys the closing transaction changed, but not to the size of the whole store.
set("a", 1), set("b", 2), get("a"), delete("a"), get("a"), get("b")Outputget("a") returns 1, then get("a") returns None, get("b") returns 2Part 1 only: after the delete, a holds nothing.
set("x", 10), begin(), set("x", 20), set("y", 5), get("x"), rollback(), get("x"), get("y"), rollback()Outputget("x") returns 20, rollback() returns True, get("x") returns 10, get("y") returns None, rollback() returns FalseInside the transaction, get sees 20. The rollback puts x back to 10 and removes y, which did not exist before. The second rollback finds no open transaction.
set("x", 1), begin(), set("x", 2), begin(), set("x", 3), commit(), get("x"), rollback(), get("x")Outputcommit() returns True, get("x") returns 3, rollback() returns True, get("x") returns 1The inner commit hands x = 3 to the outer transaction, so rolling the outer one back restores 1, the value from before the first begin.
Keys and values are strings or integers. A value is never
None.Up to 106 calls in total.
The store can hold hundreds of thousands of keys while each transaction changes only a few.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.