Design an in-memory store that maps string keys to string values and supports nested transactions.
Implement KVStore with string keys and string values.
set(key, value) stores value under key, overwriting any earlier value.get(key) returns the stored string, or None if the key is absent.delete(key) removes the key and returns True; returns False if the key was absent.count(value) returns how many keys currently map to value (0 if none).count should be O(1): keep a running tally rather than scanning all keys.
10 30 None
s = KVStore()
s.set("a", "10")
s.set("b", "20")
print(s.get("a"))
s.set("a", "30")
print(s.get("a"), s.get("zzz"))Build an in-memory key-value store with set, get, delete and count-by-value, then nested transactions with begin, rollback and commit, then a sorted prefix scan.
Also known as: In-memory database, Simple database with rollback
In-memory database or key-value store shows up in 9.1% of the 1,447 coding interview reports we studied, at 8 companies. Build a small store with get, set and delete, then extend it with transactions, persistence to a file, filtering or TTLs.
Reported at: OpenAI, Databricks, Anthropic, Snowflake, xAI, Cursor, Perplexity, Zip.
This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.
Follow-ups candidates reported on questions with this pattern, in our words. Parts marked “from reports” below are built on them.
Design an in-memory store that maps string keys to string values and supports nested transactions.
Implement KVStore with string keys and string values.
set(key, value) stores value under key, overwriting any earlier value.get(key) returns the stored string, or None if the key is absent.delete(key) removes the key and returns True; returns False if the key was absent.count(value) returns how many keys currently map to value (0 if none).count should be O(1): keep a running tally rather than scanning all keys.
Add transactions. They can be nested.
begin() opens a new transaction inside any that are already open.get, count) always see the latest writes, including writes made in open transactions.rollback() undoes every change made in the innermost open transaction, closes it, and returns True. Returns False if no transaction is open.commit() closes the innermost open transaction and keeps its changes, returning True. If an outer transaction is still open, the changes become part of it, so rolling back the outer one also undoes them. Returns False if no transaction is open.After a rollback, get and count must give the same answers as just before the matching begin(). That includes keys created inside the transaction: they must be absent again. count must stay O(1) and correct through rollbacks.
Add scan(prefix), which returns every current key that starts with prefix, sorted in plain string order (so "user:10" comes before "user:2"). An empty prefix returns all keys; no match returns [].
scan sees the current state, so it reflects writes in open transactions and is restored by rollback like everything else.
Open this page on a laptop or desktop to write and run your code against the tests in the browser.
Spoilers: try each part before reading its walkthrough.
Two dictionaries do all the work. data maps each key to its string, and counts maps each value to how many keys hold it right now. The trick is to send every mutation through one private helper, here _apply(key, value). It looks up the old value, lowers that value's tally, then writes the new value and raises its tally (or removes the key for a delete). Because no other code path touches data, the tally cannot drift, and count becomes a single dictionary lookup. Each operation is O(1) on average. The cost is a little extra memory, one entry per distinct value, which is the usual price for answering an aggregate query without a scan.
Keep a stack with one undo journal per open transaction. A journal is a dict from key to the value that key had before this transaction first changed it, with a private _MISSING marker for keys that did not exist. Only the first write to a key is recorded, so the journal always holds the pre-transaction value. rollback pops the journal and replays each saved value through the same _apply helper, which also repairs counts. commit pops the inner journal and merges it into the parent with setdefault, so the parent keeps its own older entries. With no parent, the changes are simply permanent. Rollback and nested commit cost O(k) for k keys touched, not O(n) for the whole store, which is why a journal beats copying the dictionary at every begin.
Because reads always go to the live data dictionary, a prefix scan needs no knowledge of transactions at all: filter keys with str.startswith and sort them. Rollback already restores data, so the scan is automatically consistent. This version is O(n log n) per call, which is fine for a small store. If scans dominate, keep a sorted list of keys and use bisect to jump to the first key at or after the prefix, then walk forward until keys stop matching; that is O(log n + m) per scan for m matches, at the cost of O(n) inserts. A trie gives similar scan speed with cheaper inserts but more memory.
Keep a second dict from value to how many keys hold it. Route every write through one helper that decrements the old value and increments the new one.
For each open transaction, remember a key's value from before its first change there (or a marker meaning 'was absent'). Rollback writes those old values back through the same helper, so count stays right.
On a nested commit, copy the inner undo entries into the outer one, but keep the outer entry when both have the key: it is the older value.
set, get, delete and count are O(1). begin is O(1); rollback and nested commit are O(k) for the k keys changed in that transaction. scan is O(n log n) for n keys because it filters and sorts.
The company guides collect the questions candidates report, with every part, the follow-ups interviewers added, and how often each one comes up.
Browse the interview guides