Implement command-driven in-memory key-value database
Company: Lyft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
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(
1) 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).
Quick Answer: 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.