How should I practice LRU Key-Value Cache Operations?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Nvidia phone screen problems in FastPrep.

Is LRU Key-Value Cache Operations associated with Nvidia?

FastPrep tags this as a Nvidia phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Design

LRU Key-Value Cache Operations

Learn this problem

● Medium

NvidiaFULLTIMEPHONE SCREEN

Problem statement

Process a finite ordered sequence of operations on a key-value cache with capacity capacity.

["PUT", key, value] inserts or updates key. A successful put makes the key most recently used.
["GET", key] returns the stored value, or the empty string when the key is absent. A successful get makes the key most recently used.

Keys and values are non-empty strings. Whenever an insertion makes the cache exceed capacity, evict the least recently used key. Return one result for each GET operation, in operation order.

Function

processKvCache(capacity: int, operations: String[][]) → String[]

Examples

Example 1

capacity = 2operations = [["PUT","a","1"],["PUT","b","2"],["GET","a"],["PUT","c","3"],["GET","b"],["GET","c"]]return = ["1","","3"]

Reading a makes it recent, so inserting c evicts b.

Example 2

capacity = 1operations = [["PUT","x","old"],["PUT","x","new"],["GET","x"],["PUT","y","2"],["GET","x"]]return = ["new",""]

Updating x changes its value without increasing the cache size. Inserting y later evicts it.

Constraints

1 <= capacity <= 10^5.
1 <= operations.length <= 2 * 10^5.
Every operation has one of the valid shapes described above.
1 <= key.length, value.length <= 100.