手写 LFU 缓存
哪些公司问过
答案要点
- 哈希表一:key → 节点(key、value、freq)
- 哈希表二:freq → 双向链表,同频次按访问时间排序
- 访问时节点移到 freq+1 链表头部;原链表空且等于 minFreq 时 minFreq 加一
- 满了淘汰 minFreq 链表尾部节点;新节点 freq 为 1,minFreq 重置为 1
- 边界:容量为 0;put 已有 key 要更新值并提升频次
易错点
- 新节点插入后忘记把 minFreq 重置为 1
- 淘汰时只删链表节点,忘记删哈希表里的 key
面试官常见追问
- LFU 和 LRU 有什么区别?各有什么问题?
- LFU 历史热点难以淘汰怎么解决?
- 如果不要求 O(1),有没有更简单的实现?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。