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