Design a nested transaction store
Company: Applied Intuition
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement an in-memory key–value store that supports nested transactions with the operations: SET key value, RETURN key, BEGIN, APPLY (commit current transaction into its parent), and DISCARD (rollback current transaction). Reads and writes should reflect the most recent value visible in the current transactional context. Transactions can be arbitrarily nested. Example sequence: SET X=20; BEGIN; BEGIN; SET X=10; RETURN X; APPLY; DISCARD; RETURN X. The first RETURN should yield 10 and the second 20. Describe the data structures, APIs, and the time/space complexity of each operation, and consider edge cases (e.g., RETURN on unset keys, APPLY/DISCARD with no active transaction).
Quick Answer: This question evaluates understanding of transactional state management, nested transaction semantics, scope resolution, and data-structure design for an in-memory key–value store.
Implement an in-memory key-value store that supports arbitrarily nested transactions. You are given a list of commands and must execute them in order.
Commands:
- ('SET', key, value): Store an integer value for key in the current transaction if one exists; otherwise store it in the base store.
- ('RETURN', key): Read the most recent visible value for key from the current transaction scope. Search from the innermost active transaction outward, then the base store. If the key has never been set, output None.
- ('BEGIN',): Start a new empty transaction.
- ('APPLY',): Commit the current transaction into its parent context and remove it. If it is the outermost transaction, commit into the base store. If there is no active transaction, output 'NO TRANSACTION'.
- ('DISCARD',): Roll back the current transaction and remove it. If there is no active transaction, output 'NO TRANSACTION'.
Return a list containing every value produced by RETURN, plus 'NO TRANSACTION' for invalid APPLY or DISCARD operations, in the order they occur.
Example:
SET X=20; BEGIN; BEGIN; SET X=10; RETURN X; APPLY; DISCARD; RETURN X
The outputs are [10, 20].
Constraints
- 0 <= len(commands) <= 10^4
- Keys are non-empty strings of length at most 20
- Values are integers in the range [-10^9, 10^9]
- Transactions may be nested arbitrarily within the command list
Examples
Input: [('SET', 'X', 20), ('BEGIN',), ('BEGIN',), ('SET', 'X', 10), ('RETURN', 'X'), ('APPLY',), ('DISCARD',), ('RETURN', 'X')]
Expected Output: [10, 20]
Explanation: The inner transaction changes X to 10, so the first RETURN sees 10. APPLY merges that change into its parent transaction. DISCARD then rolls back the parent transaction, so the base value 20 is visible again.
Input: [('RETURN', 'A'), ('APPLY',), ('DISCARD',)]
Expected Output: [None, 'NO TRANSACTION', 'NO TRANSACTION']
Explanation: A was never set, so RETURN gives None. There is no active transaction for APPLY or DISCARD, so both produce 'NO TRANSACTION'.
Hints
- Think of each BEGIN as pushing a new write layer onto a stack.
- For RETURN, check the newest transaction first and work outward until you find the key.