Quick Overview

This question evaluates understanding of transactional state management, nested transaction semantics, scope resolution, and data-structure design for an in-memory key–value store.

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).

Overview: 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

  1. Think of each BEGIN as pushing a new write layer onto a stack.
  2. For RETURN, check the newest transaction first and work outward until you find the key.

Loading coding console...

Show the approach

Approach

The store is modeled as a base dictionary plus a stack of "overlay" dictionaries (tx_stack), one per active transaction. Each layer holds only the keys written inside that transaction, so we never copy the whole store when a transaction begins.

Per command:

  • SET key value — write into tx_stack[-1] (the innermost open transaction) if one exists, otherwise into base. Later layers shadow earlier ones, so a write inside a transaction is invisible to its parent until applied.
  • RETURN key — scan layers from innermost outward with for layer in reversed(tx_stack). The first layer containing the key wins (break). The for…else clause is the key trick: else runs only when no break fired, i.e. the key wasn't in any transaction, so we fall back to base.get(key) — which yields None for a key that was never set.
  • BEGIN — push a fresh empty dict, opening a new scope.
  • APPLY — pop the top layer and merge it into its parent with dict.update; if it was the outermost transaction, merge into base. update makes child writes overwrite parent values, which is exactly "commit." Output 'NO TRANSACTION' if the stack is empty.
  • DISCARD — pop and drop the top layer, throwing its writes away. Output 'NO TRANSACTION' if the stack is empty.

Why it's correct: visibility always reflects the current nesting because reads walk layers inner→outer and the base is the final fallback. Commit/rollback are just merge-up vs. discard of a single layer, so arbitrary nesting composes naturally. Only RETURN, invalid APPLY, and invalid DISCARD emit output, preserving the required order.

Time complexity:
O(n · d) worst case, where n = number of commands and d = maximum transaction nesting depth. Most ops are O(1); RETURN scans up to d layers, and a cascade of APPLYs can re-merge a layer's keys up to d times. With shallow nesting it is effectively O(n).
Space complexity:
O(b + u), where b is the number of distinct keys in the base store and u is the total number of key assignments held across all open transaction layers (each layer stores only its own writes, not a copy of the whole store).