Design an LRU Cache

Problem Statement

Design a data structure for a Least Recently Used (LRU) cache. It should support:

1. get(key) — Return the value if the key exists, else -1. Accessing a key makes it "recently used."
2. put(key, value) — Insert or update the value. If the cache exceeds capacity, evict the least recently used item.

Both operations must run in O(1) time.

Constraints

• 1 <= capacity <= 3000
• 0 <= key, value <= 10^5
• At most 2 * 10^5 calls to get and put

Example

LRUCache cache = new LRUCache(2);
cache.put(1, 1);      // cache: {1=1}
cache.put(2, 2);      // cache: {1=1, 2=2}
cache.get(1);         // returns 1, cache: {2=2, 1=1}
cache.put(3, 3);      // evicts key 2, cache: {1=1, 3=3}
cache.get(2);         // returns -1 (not found)

What the Interviewer Expects

1. HashMap + Doubly Linked List — the standard optimal design.
   • HashMap: key → node for O(1) lookup
   • Doubly Linked List: maintains usage order (most recent at head, least recent at tail)
2. get(key) — look up in map, move node to head, return value.
3. put(key, value) — if exists, update + move to head. If new, add to head. If over capacity, remove tail node and delete from map.
4. Why doubly linked list — O(1) removal of any node (need prev pointer). Singly linked would be O(n).
5. Sentinel head/tail nodes — simplify edge cases (empty list, single element).

Follow-ups

1. How would you make this thread-safe for concurrent access?
2. How would you implement LFU (Least Frequently Used) instead? What changes?
3. How would you add a TTL (time-to-live) so entries expire?
4. How does this scale to a distributed cache like Redis?
5. Can you implement it using Java's LinkedHashMap or an ordered dict? What are the trade-offs?