Design and Implement a Thread-Safe LRU Cache

Approach 1: Hash Map + Doubly Linked List The core challenge is making get and put both run in constant average time while keeping a strict recency ordering. A hash map alone gives constant lookups, but it cannot preserve insertion/usage order because its iteration order is not meaningful for LRU semantics. A linked list alone preserves order, but finding a key would require a linear scan. The standard solution combines both: A hash map stores each key as a direct pointer to…