模拟 LRU 并统计缓存缺失次数
哪些公司问过
答案要点
- 先确认改版规则:命中是否更新、淘汰依据、容量为 0 等边界
- 哈希表加双向链表,查找与移动都是 O(1)
- 命中:节点移到头部;未命中:miss 加一,满则淘汰尾部再插入头部
- 总时间 O(n),空间 O(容量)
- 改版只需替换命中调整和淘汰选择逻辑,如 LFU 或 FIFO
易错点
- 命中时忘记把节点移到最近使用位置
- 淘汰尾节点后忘记同步删除哈希表中的 key
- 不确认改版规则就套用标准 LRU
面试官常见追问
- 为什么用双向链表而不是单链表?
- LFU 怎么实现 O(1)?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。