1. One-Liner
LRU evicts the least recently used entry when capacity is exceeded—needs O(1) get and put.
2. The Problem It Solves
Caches in OS, CDNs, databases, and mobile apps bound memory while keeping hot items.
3. The Core Idea
Hash map for key→node; doubly linked list for recency order (front MRU). get/put splice node to front; evict tail.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Map key→list iterator/node |
| 2 | get: if miss return -1; else move to MRU, return value |
| 3 | put: update or insert; if oversize remove LRU |
| 4 | Python/Java may use OrderedDict/LinkedHashMap |
5. Dry Run Example
Capacity 2: put(1), put(2), get(1) (2 LRU), put(3) evicts 2.
6. Key Properties
| Property | Detail |
|---|---|
| O(1) | Hash + list splice |
| Thread safety | Needs locks in prod |
| Approx LRU | Clock/NFU cheaper |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| Redis | Eviction policies |
| CPU | Page replacement analog |
| Mobile | Image caches |
8. Interview Tips
Discuss OrderedDict caveats, C++ list+unordered_map iterator stability, concurrent LRU with locks or sharding.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| FIFO | Ignores frequency |
| LFU | Counts hits, heavier |
| Random | Cheaper eviction |
10. Complexity
| -- | -- |
|---|---|
| Time | O(1) get/put average |
| Space | O(capacity) |
Implementation Example (PYTHON)
from collections import OrderedDict
class LRUCache:
def __init__(self, cap):
self.cap = cap
self.od = OrderedDict()
def get(self, k):
if k not in self.od: return -1
self.od.move_to_end(k)
return self.od[k]
def put(self, k, v):
if k in self.od:
self.od.move_to_end(k)
self.od[k] = v
if len(self.od) > self.cap:
self.od.popitem(last=False)