LRU Cache for Query Results

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 = 2
operations = [[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 = 2
operations = [[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.

The trick is two structures working together. A hash map takes key to node in O(1). A doubly linked list orders nodes by recency, with the head as most recent and the tail as least recent. Every get that hits moves the node to the head. Every put either updates and moves the node, or inserts at the head and evicts the tail if size passes capacity. Use sentinel head and tail nodes so you never special-case empty lists. The common pitfalls: forgetting that updating an existing key must not grow size or trigger eviction, forgetting that a get hit refreshes recency, and treating -1 as "missing" when -1 can be a stored value. Check map membership, not the value. Output strings, so a put is the literal "null". If you blank on pointer rewiring live, StealthCoder can hand you the clean implementation as a hedge.

If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.