Implement LRUCache with O(1) Operations and Thread Safety

Scenario

High-traffic API needs constant-time eviction cache.

Question

Implement an LRUCache supporting get(key) and put(key,val) in O(1). Describe thread-safety considerations for concurrent access.

Hints

Combine hash map with doubly-linked list; lock striping or concurrent linked hash map for threads.

LRU Cache Operations Simulator

Implement lru_ops(ops, capacity) to simulate an LRU cache with the given capacity. Each operation is either ["put", key, value] or ["get", key]. get(key) returns the value for key or -1 if absent, and marks the key as most-recently-used. put(key, value) inserts or updates key, marking it most-recently-used; if capacity is exceeded, evict the least-recently-used key. Return a list of integers containing the results of get operations in order. Assume single-threaded execution for testing.

Constraints

• 1 <= capacity <= 100000
• 0 <= len(ops) <= 200000
• Each op is ["get", key] or ["put", key, value]
• Keys and values are 32-bit signed integers
• Average O(1) time per operation
• Space O(capacity)

Examples

Example 1

Input: capacity = 2, ops = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]
Output: [1,-1,-1,3,4]

Explanation: After put(1,1), put(2,2): cache has {1=1,2=2}. get(1)=1 makes 1 MRU. put(3,3) evicts 2. get(2)=-1. put(4,4) evicts 1. get(1)=-1, get(3)=3, get(4)=4.

Example 2

Input: capacity = 1, ops = [["put",2,1],["get",2],["put",3,4],["get",2],["get",3],["put",3,9],["get",3]]
Output: [1,-1,4,9]

Explanation: Capacity 1: put(2,1). get(2)=1. put(3,4) evicts 2. get(2)=-1, get(3)=4. Updating put(3,9) keeps 3; get(3)=9.

Hints

1. Combine a hash map (key -> node) with a doubly linked list to track recency.
2. Move a node to the list head on every get/put; evict from the tail.
3. For thread-safety in real systems, guard the cache with a single mutex; for higher concurrency, consider a read-write lock or segmenting (lock striping) while keeping list and map updates atomic.

Approach

Use a doubly linked list to maintain recency and a hash map to locate nodes in O(1). On get(key), if present, move the node to the list head (MRU) and return its value; otherwise return -1. On put(key, value), if the key exists, update and move it to the head; if it does not exist, create a new node at the head and, if capacity is exceeded, remove the tail's previous node (LRU) and delete it from the map. Thread-safety (not enforced in tests): protect get/put with a single mutex to maintain list and map consistency. For higher concurrency, consider a read-write lock (many readers, exclusive writers) or sharding the cache (lock striping) across multiple segments while ensuring that updates to list and map remain atomic within each shard.

• Time complexity: O(1) average per operation
• Space complexity: O(capacity)