Katkat
Back

Implement command-driven in-memory key-value database

LyftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's ability to design efficient in-memory data structures and implement transactional semantics for operations like SET/GET/DELETE/COUNT, including handling nested transactions, rollbacks, and commits.

Implement a command-driven in-memory key–value database. Supported commands (one per line):

  1. SET key value
  2. GET key → print value or NULL
  3. DELETE key
  4. COUNT value → print how many keys currently map to this value
  5. BEGIN → start a transaction
  6. ROLLBACK → undo changes in the most recent open transaction; if none, print NO TRANSACTION
  7. COMMIT → make all open transaction changes permanent. Constraints: up to 100,000 commands; keys and values are ASCII strings; average O(
  8. per operation; memory must remain within reasonable bounds. Design data structures to support COUNT efficiently and implement transactional semantics using an undo log or equivalent. Specify I/O format precisely and discuss edge cases (nested transactions, deleting non-existent keys, multiple keys sharing a value).