How do you design a thread-safe LRU (least recently used) cache?

The simplest approach wraps a LinkedHashMap configured for access-order with Collections.synchronizedMap(), overriding removeEldestEntry() to evict the oldest entry once the cache exceeds its capacity -- this is correct but coarse-grained, since it serializes every single access, including reads, behind one lock. A better approach for higher concurrency combines a ConcurrentHashMap for O(1) key lookups with a separate doubly linked list that tracks recency order, with a ReentrantReadWriteLock protecting the linked-list updates that reordering on each access requires. For genuinely high-concurrency production use, a library like Caffeine is usually the right answer: it implements a Window TinyLFU eviction algorithm, uses lock striping to minimize contention across threads, achieves O(1) amortized performance, and handles frequency-based eviction more intelligently than a strict recency-only policy. In an interview setting, a good way to present this is to start with the simple LinkedHashMap-based approach, explain clearly why it doesn't scale under concurrency, and then describe the ConcurrentHashMap-plus-linked-list design as the natural next step.