面试题库 › C++ / 后端 › LRU 变种:访问达到 k 次才进入缓存(LRU-K)

LRU 变种:访问达到 k 次才进入缓存(LRU-K)

难度 ★★★在 1 场真实面经中被问到 方向:C++ / 后端考点:数据结构设计

哪些公司问过

腾讯1

常见岗位:后端开发

答案要点

  1. 访问次数未达 k 的 key 只记录在历史表,不占缓存空间
  2. 历史表也需设容量上限,可用 LRU 或 FIFO 淘汰旧记录
  3. 正式缓存用哈希表加双向链表,与 LC146 相同
  4. 计数达到 k 时从历史表迁入缓存头部,缓存满则淘汰尾部
  5. 各操作 O(1);k=1 时退化为普通 LRU

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题