Key-Value Store with Transactions
Problem statement
Start with an empty store of string keys and values. Process the operations from first to last. The three input arrays match by index: operations[i], keys[i] and values[i] describe one call.
SET: store the nonempty value under its key.GET: return the key’s current value, or the empty string if the key is missing.DELETE: remove the key. If it is already missing, do nothing.BEGIN: start a transaction. No other transaction is active at this point.COMMIT: keep every change made since the active transaction began, then end it.ROLLBACK: discard every change made since the active transaction began, then end it.
Return one string for every operation. For GET, return its value or the empty string. For every other operation, return the literal string "null". During a transaction, reads include the sets and deletions made in that transaction. If a key changes more than once, use its latest value or deletion. Outside a transaction, sets and deletions take effect permanently right away.
For this practice exercise, at most one transaction can be active; every COMMIT and ROLLBACK has a matching active BEGIN. No other caller changes the store. The input may end while a transaction is still open. Return only the results of the listed operations. For GET and DELETE, the corresponding value is empty. For transaction-control operations, both key and value are empty and ignored.
Use a hash-based representation so ordinary key reads, writes and deletions take expected constant time. Transaction-control work may depend on the number of keys copied or changed; the exercise does not require every operation to have worst-case constant cost.
Unscored follow-up discussion: explain how concurrent callers, value expiration and historical reads would change the design. Those are reported extension topics, not extra operations in this judged batch. Their isolation, clock, expiration and history policies must be specified before implementing them. Nested transactions are also outside this chosen one-active-transaction practice contract.
Function
runTransactions(operations: String[], keys: String[], values: String[]) → String[]Examples
Example 1
operations = ["SET","BEGIN","SET","GET","ROLLBACK","GET"]keys = ["x","","x","x","","x"]values = ["old","","new","","",""]return = ["null","null","null","new","null","old"]A transaction reads its own overwrite, and rollback restores the value visible before BEGIN.
Example 2
operations = ["SET","BEGIN","DELETE","GET","SET","COMMIT","GET","GET"]keys = ["x","","x","x","y","","x","y"]values = ["old","","","","green","","",""]return = ["null","null","null","","null","null","","green"]The transaction deletion hides x immediately. Commit keeps that deletion and the new y value.
Example 3
operations = ["GET","DELETE","BEGIN","SET","SET","COMMIT","GET"]keys = ["missing","missing","","a","a","","a"]values = ["","","","first","last","",""]return = ["","null","null","null","null","null","last"]Missing reads return the empty string; removing an absent key is harmless, and the last transaction write wins.
Constraints
1 <= operations.length <= 2000, and all three arrays have equal length.- Every operation is exactly
SET,GET,DELETE,BEGIN,COMMITorROLLBACK, with the arguments described above. - Keys for key operations contain 1 to 16 case-sensitive English letters or decimal digits.
- Every SET value contains 1 to 16 case-sensitive English letters or decimal digits; it is never empty.
- Transactions do not nest. BEGIN occurs only while no transaction is active; COMMIT and ROLLBACK occur only while one is active.