How should I practice LRU Cache for Query Results?

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

Is LRU Cache for Query Results associated with Amazon?

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

LRU Cache for Query Results

Amazon● MediumNEW GRADFULLTIMEPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

Maintain a cache with positive integer capacity. Process each operation atomically in the supplied completed serialization order:

[1, key] performs get(key). Return the stored value, or -1 when the key is absent. A successful get makes the key most recently used.
[2, key, value] performs put(key, value). Insert or update the key and make it most recently used. Updating an existing key does not change the cache size. If an insertion exceeds capacity, evict exactly the least recently used key.

Return one string per operation: the decimal result of each get and the literal string "null" for each put. Implement both operations in O(1) expected time.

The supplied order is a deterministic linearization of completed concurrent operations; an implementation exposed to threads would guard each public operation as one atomic critical section.

Function

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

Examples

Example 1

capacity = 2operations = [[2,1,10],[2,2,20],[1,1],[2,3,30],[1,2],[1,3]]return = ["null","null","10","null","-1","30"]

Reading key 1 makes it recent, so inserting key 3 evicts key 2.

Example 2

capacity = 2operations = [[2,1,5],[2,2,6],[2,1,7],[2,3,8],[1,1],[1,2],[1,3]]return = ["null","null","null","null","7","-1","8"]

Updating key 1 changes its value and recency without growing the cache, so key 2 is evicted next.

Constraints

1 <= capacity <= 100000.
1 <= operations.length <= 100000.
Every operation has one of the two documented forms.
Keys and values are signed 32-bit integers. The value -1 may be stored and remains distinguishable only by whether the key is present.