How should I practice Globally Versioned Key-Value Store?

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

Is Globally Versioned Key-Value Store 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

Globally Versioned Key-Value Store

Learn this problem

● Medium

LyftFULLTIMEONSITE INTERVIEW

Problem statement

Implement a versioned key-value store by processing the finite array operations from left to right. The store starts empty, and its global version starts at 0.

Each operation has one of these forms:

SET key value: increment the global version by one, then store value for key at that new version.
GET key: return the latest value stored for key, or NULL when the key has no value.
GET_AT key version: return the value stored for key at the greatest global version less than or equal to version, or NULL when no such value exists.

Return one string for every GET or GET_AT operation, in command order. SET operations do not produce output.

Function

runVersionedStore(operations: String[]) → String[]

Examples

Example 1

operations = ["SET color red","SET size small","SET color blue","GET_AT color 2","GET_AT size 1","GET color","GET_AT color 3"]return = ["red","NULL","blue","blue"]

The writes receive global versions 1, 2, and 3. At version 2, color still has value red; size did not yet exist at version 1.

Example 2

operations = ["SET a one","SET b two","SET b three","SET a four","GET_AT a 3","GET_AT b 4","GET_AT c 10"]return = ["one","three","NULL"]

Key a has history entries only at global versions 1 and 4, so its read at version 3 returns one.

Constraints

1 <= operations.length <= 100000.
Every operation is exactly one documented command with single spaces between tokens.
Keys and values contain 1 to 100 ASCII letters, digits, underscores, or hyphens.
A stored value is never the reserved token NULL.
Every requested historical version is an integer in [0, 10^9].
At least one operation is GET or GET_AT.