How should I practice Nested Transaction Key-Value Store with Value Counts?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Lyft onsite interview problems in FastPrep.

Is Nested Transaction Key-Value Store with Value Counts associated with Lyft?

FastPrep tags this as a Lyft onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Hash Table

Nested Transaction Key-Value Store with Value Counts

Learn this problem

● Hard

LyftFULLTIMEONSITE INTERVIEW

Problem statement

Implement an in-memory string key-value store by processing a finite ordered array commands.

Supported commands are:

SET key value: set or overwrite a key.
GET key: return its visible value, or NULL when absent.
DELETE key: remove the key when present.
COUNTVALUES value: return the number of visible keys whose value equals value.
BEGIN: open a nested transaction.
ROLLBACK: discard only the innermost open transaction.
COMMIT: merge only the innermost transaction into its parent, or into base state when it is outermost.

For this exercise, every command produces one output token. Successful mutations and successful transaction commands return OK; ROLLBACK or COMMIT with no open transaction returns NO_TRANSACTION. Queries see all currently active transaction layers. Keys and values are non-empty case-sensitive strings without spaces.

Function

runNestedKeyValueStore(commands: String[]) → String[]

Examples

Example 1

commands = ["SET a 10","BEGIN","SET a 20","GET a","ROLLBACK","GET a","COUNTVALUES 10"]return = ["OK","OK","OK","20","OK","10","1"]

Rolling back the inner transaction restores a to 10, so exactly one visible key has that value.

Example 2

commands = ["SET x red","BEGIN","SET y red","BEGIN","DELETE x","COUNTVALUES red","COMMIT","ROLLBACK","COUNTVALUES red","COMMIT"]return = ["OK","OK","OK","OK","OK","1","OK","OK","1","NO_TRANSACTION"]

The inner commit remains part of the outer transaction, so the later outer rollback restores the base state containing only x=red.

Constraints

1 <= commands.length <= 2 * 10^5
Every command is well formed and uses one of the supported operation names.
Keys and values are non-empty case-sensitive strings without spaces.
The total number of characters across all commands is at most 2 * 10^5.
Transaction nesting depth is at most 2 * 10^5.