LRU Cache
lru-cache
Data Structures
LRU Cache (Hash Map + DLL)
Hold a fixed number of recently used items, evict the least-recently-touched one when you run out of room, and answer both `get(key)` and `put(key, value)` in `O(1)`. No single primitive does that: a hash map gives `O(1)` lookup but no recency order, and a doubly linked list gives `O(1)` recency moves but no key index. The classical **LRU Cache** wires the two together so each compensates for what the other lacks. This lesson designs the composite from scratch: a hash map that points keys to DLL nodes, and a doubly linked list that orders nodes by recency with most-recent at the head and least-recent at the tail. You will trace `get` and `put` through both structures, handle the capacity-of-one and update-existing-key edge cases, and see why this design appears in browser caches, database query caches, OS page replacement, and CDNs. In **Hash Map (Dictionary) Basics**, you used a hash map for `O(1)` lookup by key. **Doubly Linked List** added the `prev` pointer that makes mid-list deletion `O(1)` once you hold the node, plus the sentinel pattern that erases null checks at the boundaries; both are load-bearing here. The LRU pattern (one structure for indexing, another for ordering, kept consistent on every operation) is the gateway to a wider family of composite designs covered in later lessons.
Not Started
0%
Practice Problems
LRU Cache
Design a data structure that follows the Least Recently Used (LRU) cache constraints, supporting get and put operations in O(1) time.
Code Snippets
LRU Cache (Map-Backed)
An LRU (Least Recently Used) cache evicts the entry that has been untouched the longest when capacity overflows. The trick that makes both `get` and `put` O(1) is JavaScript's `Map` preserving insertion order. This snippet covers the Map-backed implementation, an explicit doubly-linked-list version that mirrors what other languages need, and a TTL-aware variant that evicts entries that are too old.
OrderedDict Quirks Worth Knowing
Regular dicts have preserved insertion order since Python 3.7, so most modern code never reaches for `OrderedDict`. But OrderedDict still has a niche: it ships with `move_to_end` and `popitem(last=False)` methods that plain dicts do not, and its equality semantics differ from dict equality. This snippet covers the move-to-end LRU primitive, the order-sensitive equality, and when you should still pick OrderedDict in 2025.
LRU Cache via OrderedDict
An LRU (least-recently-used) cache evicts whichever entry has been untouched the longest when it hits its capacity. `collections.OrderedDict` makes the implementation tiny: `move_to_end` keeps the most-recently-used key at the back, and `popitem(last=False)` evicts the front. This entry covers the get/put loop, the `@functools.lru_cache` shortcut, and a mini benchmark.
Community
LRU Cache From Scratch in 50 Lines
A working LRU cache built from a hash map plus a doubly linked list, the part interview answers leave out (concurrency, eviction callbacks, byte budgets), and when LRU is the wrong eviction policy.
Memoize With TTL and Bounded Cache Size
The official memoize is unbounded and has no TTL, which works in tests and leaks memory in production. This is the version I ship: bounded LRU + per-entry expiry, in 40 lines.