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.
Implement an in-memory key-value database that processes commands in order. The database stores string keys and string values. Some commands produce output; return those output lines as a list of strings. The database must also support nested transactions. Changes made inside a transaction are visible immediately. ROLLBACK undoes only the most recent open transaction. COMMIT permanently applies all currently open transactions and closes them all. If ROLLBACK or COMMIT is issued with no open transaction, output NO TRANSACTION.
Constraints
- 0 <= len(commands) <= 100000
- Keys and values are non-empty ASCII strings without whitespace
- The total number of key mutations across all commands is at most 100000
- Operations should be O(1) average/amortized, with ROLLBACK proportional to the number of reverted changes
Examples
Input: ([],)
Expected Output: []
Explanation: No commands produce no output.
Input: (["SET a 10", "SET b 10", "COUNT 10", "GET a", "DELETE a", "GET a", "COUNT 10", "DELETE missing", "COUNT 10"],)
Expected Output: ["2", "10", "NULL", "1", "1"]
Explanation: Two keys initially map to 10. After deleting a, GET a is NULL and only b still maps to 10. Deleting a missing key has no effect.
Hints
- Keep one hash map from key to value, and another hash map from value to the number of keys currently mapped to that value.
- For transactions, apply changes immediately but push the previous state of each changed key onto the current transaction's undo log. Roll back by replaying that log in reverse.