How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Lyft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Lyft during technical interviews.

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.

Input: (["SET a 1", "BEGIN", "SET a 2", "BEGIN", "SET b 2", "COUNT 2", "ROLLBACK", "COUNT 2", "GET b", "ROLLBACK", "GET a"],)

Expected Output: ["2", "1", "NULL", "1"]

Explanation: The inner transaction adds b=2, then it is rolled back. The outer transaction changes a from 1 to 2, then it is rolled back, restoring a=1.

Input: (["BEGIN", "SET a 5", "BEGIN", "SET a 6", "SET b 6", "COMMIT", "GET a", "COUNT 6", "ROLLBACK", "GET b", "COMMIT"],)

Expected Output: ["6", "2", "NO TRANSACTION", "6", "NO TRANSACTION"]

Explanation: COMMIT closes all open transactions and keeps a=6 and b=6. Later ROLLBACK and COMMIT have no open transaction, so both output NO TRANSACTION.

Input: (["DELETE ghost", "BEGIN", "DELETE ghost", "SET ghost x", "DELETE ghost", "ROLLBACK", "GET ghost", "COUNT x"],)

Expected Output: ["NULL", "0"]

Explanation: Deleting a non-existent key has no effect. Inside the transaction ghost is set then deleted; rolling back restores the pre-transaction missing state.

Input: (["SET a 1", "SET a 1", "COUNT 1", "BEGIN", "SET a 2", "SET a 2", "COUNT 1", "COUNT 2", "ROLLBACK", "GET a", "COUNT 2"],)

Expected Output: ["1", "0", "1", "1", "0"]

Explanation: Setting a key to its current value does not change counts. Rolling back restores a from 2 to 1.

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.

Quick Overview

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.