Key-Value Store with Nested Transactions
Reported by candidates from Rippling's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Rippling reported this one in April 2025, and the detail that trips people is Example 2: a DELETE inside a transaction hides a value, then a nested SET brings it back, and a ROLLBACK reveals the original "1". It's an in-memory key-value store with nested BEGIN, COMMIT and ROLLBACK, and the whole problem is layered state. If your OA is in the next day or two, learn the layer-stack idea tonight. It's short once you see it. StealthCoder sits invisibly on your screen as a safety net if you blank on the live OA, but the design below is simple enough to carry in your head.
The problem
Implement an in-memory key-value store that processes a sequence of operations. Each operation is a string array in one of these forms: ["SET", key, value]: assign value to key in the current transaction, or in the base store when no transaction is active. ["GET", key]: read the value visible in the current transaction context. Append that value to the result, or append "NULL" when the key does not exist. ["DELETE", key]: make key absent in the current transaction context. ["BEGIN"]: begin a new transaction nested inside the current context. ["COMMIT"]: commit the innermost transaction into its parent context. When it is the outermost transaction, commit into the base store. ["ROLLBACK"]: discard the innermost transaction. Only GET operations produce output. Return their results in operation order. A deletion inside a transaction must hide an older value without deleting that older value from the parent context; rolling back must therefore reveal the parent value again. Function processOperations(operations: String[][]) → String[] Examples Example 1 operations = [["SET","theme","light"],["GET","theme"],["BEGIN"],["SET","theme","dark"],["GET","theme"],["ROLLBACK"],["GET","theme"]] return = ["light","dark","light"] The transaction temporarily changes theme to "dark". Rolling it back reveals the base value "light". Example 2 operations = [["SET","a","1"],["BEGIN"],["DELETE","a"],["GET","a"],["BEGIN"],["SET","a","2"],["COMMIT"],["GET","a"],["ROLLBACK"],["GET","a"]] return = ["NULL","2","1"] The outer transaction hides a. The nested transaction restores it as "2" and commits that change into the outer transaction. Rolling back the outer transaction restores the base value "1". Example 3 operations = [["BEGIN"],["SET","x","7"],["BEGIN"],["SET","y","8"],["COMMIT"],["COMMIT"],["GET","x"],["GET","y"],["GET","z"]] return = ["7","8","NULL"] The inner commit merges y into its parent transaction. The outer commit then persists both keys to the base store. Constraints 1 <= operations.length <= 10^5. Keys and values are non-empty strings containing at most 50 printable ASCII characters. Every operation has one of the documented forms. Every COMMIT and ROLLBACK has an active transaction. The transaction nesting depth is at most 10^5.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Keep a base map plus a stack of transaction maps. Each transaction map stores only its own changes. A SET writes the value. A DELETE writes a tombstone marker, not a removal, which is how the parent value stays hidden but intact. GET scans from the top layer down to the base. The first layer that has the key wins. A tombstone means return NULL. ROLLBACK pops the top map. COMMIT merges the top map into its parent, overwriting entries and tombstones alike. At the outermost level, a tombstone deletes the key from the base. The pitfall is copying the whole store on BEGIN, which blows up with 10^5 nesting depth. Another is deleting the key outright, which breaks rollback. GET walks the stack, so a deep stack can be slow. To fix that, merge into the parent on COMMIT and note the tradeoff. StealthCoder is your hedge if the merge logic slips under pressure.
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 Key-Value Store with Nested Transactions 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 Rippling's OA.
Rippling 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.
Key-Value Store with Nested Transactions FAQ
What's the trick in the Rippling key-value store problem?+
Store only deltas per transaction, not full copies. Use a stack of hash maps over a base map. DELETE writes a tombstone so the parent value stays hidden but intact. Rollback pops the top layer and commit merges it down.
How do I handle DELETE inside a transaction?+
Write a special sentinel for that key in the current layer. GET treats the sentinel as absent and stops searching lower layers. Don't remove the key from the parent. That's what lets ROLLBACK reveal the older value again, as in Example 2.
What happens on COMMIT of a nested transaction?+
Pop the top map and copy every entry, including tombstones, into the new top map, overwriting conflicts. If it was the outermost transaction, apply entries to the base store, where a tombstone removes the key.
Will deep nesting cause performance problems?+
Nesting can reach 10^5, so never copy the store on BEGIN. Deltas keep BEGIN, SET, DELETE and ROLLBACK cheap. GET walks the stack, so it can cost O(depth) in a worst case. Most test cases pass with the simple layered scan.
How do I prepare for this in 48 hours?+
Code the stack-of-maps version from scratch and run the three examples by hand. Add tests for delete then rollback, nested commit after delete, and GET on a missing key. Pay attention to the commit-merge step since it's the usual bug.