实现 LFU 缓存
哪些公司问过
答案要点
- 淘汰频率最低的节点,频率相同时按 LRU 淘汰
- key 到节点的哈希表 + 频率到双向链表的哈希表
- 维护最小频率 minFreq,淘汰时直接定位
- 访问时节点移到频率加一的链表头部,必要时更新 minFreq
- 新节点频率为 1,并把 minFreq 重置为 1
易错点
- 新插入节点后忘记把最小频率重置为 1
- 淘汰时用了最小频率链表的头部而不是尾部
- 容量为 0 时没有特殊处理
面试官常见追问
- LFU 和 LRU 各适合什么场景?
- LFU 的缓存污染问题怎么缓解?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。