抖音电商一面:只聊了实习,手撕 LRU 缓存
- 轮次
- 一面
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 简单讲讲你的实习经历。
- 手撕:实现一个 LRU 缓存。
《参考解析》
LRU 的写法。 get 和 put 都要 O(1),所以结构固定是「哈希表 + 双向链表」:哈希表存 key → 节点指针 用于定位,双向链表按访问时间排序,头部最新、尾部最旧。
class Node:
__slots__ = ("k", "v", "prev", "next")
def __init__(self, k=0, v=0):
self.k, self.v, self.prev, self.next = k, v, None, None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.map = {}
self.head, self.tail = Node(), Node() # 哨兵,省掉所有空指针判断
self.head.next, self.tail.prev = self.tail, self.head
def _remove(self, node):
node.prev.next, node.next.prev = node.prev, node.next
def _add_front(self, node):
node.next, node.prev = self.head.next, self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_front(node)
return node.v
def put(self, key, value):
if key in self.map: # 已存在:更新值并前置,不能新建节点
node = self.map[key]
node.v = value
self._remove(node)
self._add_front(node)
return
node = Node(key, value)
self.map[key] = node
self._add_front(node)
if len(self.map) > self.cap: # 超容:摘掉尾部真实节点
old = self.tail.prev
self._remove(old)
del self.map[old.k]
伪代码级的关键点就三条:访问后把节点移到头部、写入已存在的 key 时是更新不是新增、超容删尾并同步删哈希表。有哨兵头尾能省掉一堆 if node.prev is None 的判断,这是手写时最容易漏、也最能体现基本功的地方。
常见坑。 ① capacity 为 0 或 1 的边界,容量 0 时 put 不能留下任何元素,写测试用例时要专门覆盖;② 只改链表不删哈希表(或反过来),内存泄漏且 get 会命中已淘汰的节点;③ res.append 之外的另一类引用错误——把节点对象直接返回给调用方,调用方改了就破坏结构,工程里应返回值而不是节点;④ 双链表摘链时先存 prev/next 再改指针,顺序写错会把自己指成环;⑤ 手写时忘了 __slots__ 或用了 dict 做链表,复杂度掉到 O(n)。写完主动报「时间 O(1),空间 O(capacity)」并口述三个用例,能省下面试官挑刺的时间。
语言与工程延伸。 Java 可以用 LinkedHashMap 的 accessOrder=true 加 removeEldestEntry 十行写完,但面试要的是手写,提一句「知道标准库有现成的」即可;生产环境要考虑线程安全,常见做法是 ConcurrentHashMap 加分段锁,或直接用 Caffeine 这类带 W-TinyLFU 的库。Redis 的 LRU 是近似实现——采样若干个 key 淘汰最久未用的,换来内存开销可控,这个取舍值得在答完题后补一句。如果面试官继续问「怎么加过期时间」,答案是在节点里存 expireAt,get 时惰性删除,再加一个定时任务或 Redis 那样的定期抽样清理。
遇到疑似 KPI 面怎么办。 流程短、问题浅的时候,能控的只有自己:把手上这道题写到无懈可击(边界、异常、复杂度、测试用例全说到),再主动往深处引一两句(并发、淘汰策略、命中率统计),把二十分钟的面谈撑成有效信号。面试官不深挖项目,往往是简历项目同质化太高——下次准备时换一个「有真实数据、有你独立决策、有踩坑」的项目讲,比换一家公司更有效。