面试题库 › C++ / 后端 › LRU 缓存的实现

LRU 缓存的实现

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

哪些公司问过

腾讯27字节跳动17百度10美团7快手7拼多多6阿里巴巴5四方继保5滴滴4京东3小红书3深信服3

常见岗位:Java 后端、C/C++ 软件开发、C++ 后端、Go 后端、后端开发

答案要点

  1. 哈希表提供 O(1) 查找,双向链表维护访问顺序(头部最近、尾部最久未使用)
  2. get 命中:把节点移到链表头部
  3. put:key 已存在则更新并移到头部;不存在则插入头部,容量满时淘汰尾节点并删除哈希表中的 key
  4. 哈希表存 key 到链表节点(C++ 里是 list 迭代器)的映射,get/put 均为 O(1)
  5. C++ 用 std::list::splice 在 O(1) 内移动节点,不拷贝元素

易错点

面试官常见追问

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

相关面试题