手撕：LRU 缓存。
算法工程师第 6 / 15 题答题框架
参考思路：数据结构组合(哈希表+双向链表)→get/put 的 O(1) 操作与移动到头部→淘汰尾部→虚拟头尾节点简化边界。
五个经典回答示范
回答一 · 思路口述版
「LRU 要求 get 和 put 都是 O(1)，单靠链表查找慢、单靠哈希表无序，所以组合：哈希表存 key 到节点的映射，双向链表维护访问序——最近用的在头，最久未用的在尾。get 命中后把节点移到头部；put 已存在则更新并移头，不存在则建节点插头，超容量删除尾节点并同步删哈希表。」
回答二 · 标准写法
用哑头 dummyHead 和哑尾 dummyTail 简化边界：remove(node) 与 addToHead(node) 两个私有操作写清楚，get/put 只做三件事——查表、调序、维护容量。语言自带的 LinkedHashMap 或 Python 的 OrderedDict 面试可以提，但要能徒手写底层——面试官一定会追问实现。
回答三 · 进阶变体
变体一：LFU——按频次分桶，每个频次一条双向链表，minFreq 指针淘汰，比 LRU 多一层频次管理。变体二：带过期时间的 LRU——节点存过期时间戳，访问与淘汰时惰性删除加后台清理。变体三：分布式 LRU——单机结构作分片，或直接用 Redis 的近似 LRU 策略并讲清它为什么是近似（采样淘汰）。
回答四 · 边界与测试
必测：容量 1、put 淘汰后 get 旧 key 返回 -1、get 更新顺序后淘汰的是真正最久未用的、重复 put 同一 key 不增容。写完画一个容量 2 的操作序列 1,2,1,3 逐步走指针，能当场抓出删除链表时漏更新哈希表这类 bug。
回答五 · 常见错误
错误一：删除尾节点后忘记删哈希表项——内存泄漏与逻辑错。错误二：单链表做移到头部——找不到前驱，O(n)。错误三：不用哑节点，头尾边界一堆判空。点评：这题是数据结构组合设计的代表，讲不清为什么需要双向链表等于没理解。
怎么练这道题
- 打开 模拟练习，选择「算法工程师」方向，限时 3 分钟作答本题。
- 对照上方答题框架，逐点检查：哪些要素没覆盖、哪里表达啰嗦。
- 用自己项目的真实经历替换框架中的占位内容，重讲一遍并录音回听。
这类题在真实面试中常被追问细节，
建议进入限时模式练一遍。