Nested Transaction Key-Value Store with Value Counts
Reported by candidates from Lyft's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The mistake that sinks a first attempt at this Lyft OA, reported September 2026, is copying the whole map on every BEGIN. With 2 * 10^5 commands and nesting depth that deep, that blows up fast. This is a nested transaction key-value store with a COUNTVALUES query, and it's really a design problem built on a hash table plus an undo log. You have SET, GET, DELETE, COUNTVALUES, BEGIN, COMMIT and ROLLBACK, and every command returns exactly one token. If you've got an OA invite, know the shape before you open it. StealthCoder is the safety net if you blank on the live OA.
The problem
Implement an in-memory string key-value store by processing a finite ordered array commands. Supported commands are: SET key value: set or overwrite a key. GET key: return its visible value, or NULL when absent. DELETE key: remove the key when present. COUNTVALUES value: return the number of visible keys whose value equals value. BEGIN: open a nested transaction. ROLLBACK: discard only the innermost open transaction. COMMIT: merge only the innermost transaction into its parent, or into base state when it is outermost. For this exercise, every command produces one output token. Successful mutations and successful transaction commands return OK; ROLLBACK or COMMIT with no open transaction returns NO_TRANSACTION. Queries see all currently active transaction layers. Keys and values are non-empty case-sensitive strings without spaces. Function runNestedKeyValueStore(commands: String[]) → String[] Examples Example 1 commands = ["SET a 10","BEGIN","SET a 20","GET a","ROLLBACK","GET a","COUNTVALUES 10"] return = ["OK","OK","OK","20","OK","10","1"] Rolling back the inner transaction restores a to 10, so exactly one visible key has that value. Example 2 commands = ["SET x red","BEGIN","SET y red","BEGIN","DELETE x","COUNTVALUES red","COMMIT","ROLLBACK","COUNTVALUES red","COMMIT"] return = ["OK","OK","OK","OK","OK","1","OK","OK","1","NO_TRANSACTION"] The inner commit remains part of the outer transaction, so the later outer rollback restores the base state containing only x=red. Constraints 1 <= commands.length <= 2 * 10^5 Every command is well formed and uses one of the supported operation names. Keys and values are non-empty case-sensitive strings without spaces. The total number of characters across all commands is at most 2 * 10^5. Transaction nesting depth is at most 2 * 10^5.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is an undo log, not snapshots. Keep one live map of key to value and one map of value to count. Keep a stack of transactions, each holding a list of undo records: key, previous value or absent. On SET or DELETE inside a transaction, push the old state, then mutate the live map and adjust counts. ROLLBACK pops the innermost list and replays it in reverse. COMMIT is the subtle one. Merge the inner list into the parent by appending it, so an outer rollback still restores the base. If there's no parent, just discard it. Pitfalls: forgetting to decrement the old value's count on overwrite, dropping zero counts, and returning NO_TRANSACTION for the wrong commands. Everything stays O(1) amortized per command. If you freeze mid-assessment, StealthCoder is the hedge that reads the problem and hands you a working structure.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Nested Transaction Key-Value Store with Value Counts cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Lyft's OA.
Lyft reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Nested Transaction Key-Value Store with Value Counts FAQ
What's the trick to the Lyft nested transaction key-value store?+
Use an undo log instead of copying state. Mutate one live map directly, record the previous value of each touched key on a stack of transaction logs, and replay the top log in reverse on ROLLBACK. That keeps every command near O(1) amortized.
How do I make COUNTVALUES fast?+
Maintain a second hash map from value to count, updated on every SET, DELETE and undo. On overwrite, decrement the old value's count before incrementing the new one. Then COUNTVALUES is a single lookup, with missing values returning 0.
How should COMMIT behave with nested transactions?+
COMMIT only merges the innermost transaction into its parent. Append its undo records to the parent's log so an outer ROLLBACK still restores the base state. With no parent, the changes are simply final, so discard the log. With no open transaction, return NO_TRANSACTION.
Why does copying the map on BEGIN fail?+
Depth can hit 2 * 10^5, and each copy could be large. Snapshotting turns the run into roughly quadratic time and memory, which times out or overflows. Undo records only cost something for keys actually changed inside the transaction.
How do I prepare for this in 48 hours?+
Write the undo-log version once from scratch and test both examples by hand. Check overwrite, delete of a missing key, rollback after a nested commit, and empty-stack COMMIT or ROLLBACK. Then confirm your counts never go stale after any undo.