Design a transactional in-memory key–value store

Q: Design a transactional in-memory key–value store

This is a Coding & Algorithms interview question from Applied Intuition for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

SET key value — assign or overwrite a key; (
GET key — print the current value or NULL if absent; (
BEGIN — start a new transaction block; (
ROLLBACK — revert all changes made in the most recent open transaction; (
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.

Design a transactional in-memory key–value store

Comments (0)