Design a Transactional In-Memory Key-Value Store

# Design a Transactional In-Memory Key-Value Store Design an in-memory key-value store with `get`, `set`, and `delete`, transaction support, and an efficient way to report how many keys currently hold a requested value. State transaction semantics explicitly because the source does not prescribe nested behavior. ### Constraints & Assumptions - Keys and values are strings. - A transaction sees its own writes. - `begin`, `commit`, and `rollback` are required; nested transactions are optional but must be defined if supported. - Counting must reflect the transaction's visible state. - The process is single-threaded unless concurrency is introduced as a follow-up. ### Clarifying Questions to Ask - Are transactions nested, and what does an inner commit mean? - Does deleting a missing key produce an error or a no-op? - Is durability outside scope? - What complexity is expected for rollback and value counts? ### Part 1 - API and visible-state semantics Define each command, miss behavior, transaction isolation within the process, and the meaning of count before and after commit or rollback. #### What This Part Should Cover - Unambiguous state transitions - Read-your-writes behavior - Delete and overwrite semantics - Count consistency ### Part 2 - Data structures and transactions Propose data structures for key lookup, value counts, and reversible changes. Compare a full snapshot with an undo log or layered writes. #### What This Part Should Cover - Average constant-time ordinary operations - Correct count updates on overwrite and delete - Rollback without scanning the whole store - Clear treatment of repeated writes to one key ### Part 3 - Tests and extensions Cover commits, rollbacks, misses, repeated values, and failure cases. Discuss how concurrency or persistence would change the design. #### What This Part Should Cover - State-machine and model-based tests - Transaction boundary edge cases - Isolation and locking implications - Separation of in-memory semantics from durability ```hint Log the prior visible value For rollback, record enough information on the first relevant change to restore both the key mapping and the value-count index. ``` ### What a Strong Answer Covers - A precise command and transaction contract - Key and reverse-count indexes that remain consistent - A rollback strategy that handles overwrites, deletes, and repeated writes - Tests plus an honest discussion of concurrency and durability boundaries ### Follow-up Questions 1. How would nested transactions merge or discard their change logs? 2. What invariant detects corruption between the key map and the value-count map? 3. How would snapshot isolation change the memory model?