Design and Implement a Thread-Safe LRU Cache

# Design and Implement a Thread-Safe LRU Cache Design an in-memory cache with fixed positive capacity and operations `get(key)` and `put(key, value)`. - `get` returns the value when present and marks the key most recently used; otherwise it returns a defined miss result. - `put` updates and refreshes an existing key, or inserts a new key as most recently used. - Inserting beyond capacity evicts the least recently used key. - Both operations should be `O(1)` average time. After explaining the single-threaded data structure, make the cache safe for concurrent callers. Define the consistency guarantee and identify the exact linearization point of `get`, `put`, and eviction. ### Clarifying Questions to Ask - Are keys and values immutable, and may a stored value be null? - Is strict linearizability required, or is approximate recency acceptable for higher concurrency? - Can a value require cleanup when evicted? - Is one cache instance small enough for a single lock, or is contention already measured? ### What a Strong Answer Covers - A hash map from key to node plus a doubly linked recency list. - Correct updates for empty, singleton, existing-key, capacity-one, and eviction cases. - Why `get` is a write to recency state even when the value is already present. - A simple linearizable locking design and the invariants protected by the lock. - Trade-offs of read-write locks, sharding, approximate policies, callbacks, and testing concurrent histories. ### Follow-up Questions 1. Why can a read-write lock fail to improve concurrency when every hit changes recency? 2. How would you invoke an eviction callback without deadlocking the cache? 3. What semantics would you choose if two threads update the same key concurrently?