Katkat
Back

Design a transactional in-memory key–value store

Applied IntuitionSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of transactional state management, nested transaction semantics, scope shadowing, and efficient data-structure design for an in-memory key–value store, assessing competency in correctness, consistency, and algorithmic complexity under nested BEGIN/ROLLBACK/COMMIT operations.

Implement an in-memory key–value store that supports transactions. The system must process these commands: (

  1. SET key value — assign or overwrite a key; (
  2. GET key — print the current value or NULL if absent; (
  3. BEGIN — start a new transaction block; (
  4. ROLLBACK — revert all changes made in the most recent open transaction; (
  5. COMMIT — persist all open transactions so they can no longer be rolled back. Requirements: support arbitrarily nested transactions; allow multiple reassignments of the same key within the same or nested transactions, ensuring reads always see the most recent value within the active transactional context; handle shadowing of values across nested scopes; and ensure ROLLBACK restores prior values correctly. Define the core data structures (e.g., a main map plus a stack of change logs or another efficient scheme), describe the algorithms for each command, and explain the trade-offs between iterative stack-based management and a recursive approach. Specify time and space complexities for each operation, and handle edge cases such as ROLLBACK or COMMIT when no transaction is active and GET on a missing key. Provide a brief example interaction demonstrating correctness across nested BEGIN/ROLLBACK/COMMIT operations.