OA: Key-value store with nested transactions and rollback

medium 2 levels ~35 min

Level 1 Set, get, unset and count

Build the storage layer of a small in-memory database, KeyValueStore, with string keys and string values:

set(key, value) -> None: store value under key, replacing any old value.
get(key) -> str | None: the value, or None if the key isn't set.
unset(key) -> None: remove the key (doing nothing if it isn't set).
count(value) -> int: how many keys currently hold exactly value.

All four must be O(1): count must not scan the keys.

kv = KeyValueStore()
kv.set("a", "10"); kv.set("b", "10")
kv.count("10")     # 2
kv.set("b", "20")
kv.count("10")     # 1
kv.unset("a")
kv.get("a")        # None
kv.count("10")     # 0

Show hint

Keep a second dict, value -> number of keys holding it, and update it on every set (remember to decrement the old value) and unset.

Level 2 unlocks when level 1 passes.

Topic: In-memory database. CRUD with fields, range scans, TTL expiry, time-travel reads.