LRU Cache | OOD & LLD Reference

Problem framing

Design a cache with get(key) and put(key, value), capacity-bounded, evicting least recently used entry. Canonical because it demands O(1) operations and a clean class API.

Component	Role
`HashMap<K, Node>`	O(1) lookup to list node
`DoublyLinkedList`	Access order: head = MRU, tail = LRU
`get(key)`	Hit: move node to head, return value. Miss: -1 or null
`put(key, value)`	Exists: update + move to head. New: insert at head; if over capacity, evict tail

Class API design

Cache (interface)
  get(key), put(key, value), size(), clear()
LRUCache implements Cache
EvictionPolicy (optional Strategy)
  evict(), onAccess(node), onInsert(node)

Separating EvictionPolicy lets you discuss LFU or TTL without rewriting the linked-list machinery — senior extensibility point.

Complexity and invariants

Both operations O(1) average. Invariant: map size == list size; every map entry points to a valid list node. Use dummy head/tail sentinels to simplify edge cases (empty cache, single element).

Common implementation pitfalls

Forgetting to update the map when moving nodes; evicting without removing from map; single-element list edge case. Walk through put when at capacity on a new key vs existing key — only the former triggers eviction.

Senior-level signal

Draw the list + map on the whiteboard before coding. Mention LinkedHashMap in Java as the "interview shortcut" but implement manually to show DSA fluency. For thread-safety: ReadWriteLock or synchronized methods — note throughput cost.

Where this goes next

Task Scheduler & Job Queue combines priority queues, worker pools, and Command pattern — scheduling at the component level.

Practice Tasks (Optional)

Design or implement locally in any language — no autograding. Focus on class structure, extensibility, and being able to explain trade-offs out loud.

Implement LRUCache class
Implement get(key) and put(key, value) with O(1) average. Capacity eviction. Then extend: discuss how you'd swap eviction policy via Strategy pattern without rewriting core logic.
50m