Implement and Analyze an LRU Query Cache

Problem

Implement a fixed-capacity least-recently-used cache for database query results. A successful get and every put make the key most recently used. When insertion exceeds capacity, evict the least recently used key.

Function Contract

Implement runLRU(capacity, operations):

• ["get", key]: return the stored integer value, or null if absent.
• ["put", key, value]: insert or update and return null.

Constraints & Assumptions

• 1 <= capacity <= 100,000.
• At most 500,000 operations are supplied.
• Keys and values are signed 32-bit integers.
• Updating an existing key does not increase cache size.
• Each operation should be O(1) expected time.

Clarifying Questions to Ask

• Does a cache hit refresh recency? Yes.
• Does updating an existing key refresh recency? Yes.
• What is returned on a miss? null.
• Is concurrent access part of the implementation? No, discuss it as a follow-up.

Example

capacity = 2
operations = [["put",1,10], ["put",2,20], ["get",1],
 ["put",3,30], ["get",2], ["get",3]]
output = [null, null, 10, null, null, 30]

Key 2 is evicted because the hit on key 1 refreshed it.

Evaluation Focus

• Keeps map and linked-list state consistent on every path.
• Moves hits and updates to the most-recent end.
• Evicts exactly one least-recent entry when necessary.
• Delivers expected O(1) get and put.

Extensions to Discuss

1. How would a sequential scan of unique user IDs affect the hit rate?
2. Which locking or sharding strategies support concurrency?
3. How would rising traffic change capacity, admission, and cache topology?