TikTok 面试真题：实现带过期时间的 LRU KV Cache – 字节跳动 – 抖音 – VO help – 面经 – 一亩三分地 – 代面试

这道 TikTok 面试题考察的是一个带过期机制的 KV Cache，本质上是在普通 LRU Cache 的基础上，增加 TTL 过期判断。

实现一个 LRU 过期算法的 KV cache,所有 KV 过期时间间隔相同,满足如下性质:
1.最多存储 n对 KV;
2.如果大于 n个,则随意删除一个已经过期的 KV;
3.如果没有过期的 KV, 则按照 LRU 的规则删除一个 KV;
4.查询时如果已经过期,则返回空;

这类题在面试中很常见，因为它不是单纯考察 LRU 模板，而是看候选人能不能把缓存淘汰、时间过期、查询更新顺序结合起来。

核心思路可以用：

HashMap + Doubly Linked List

HashMap 用来做到 O(1) 查找 key；双向链表用来维护访问顺序，最近访问的节点放到头部，最久未使用的节点放到尾部。

每个节点需要保存：

key
value
expireTime
prev
next

当执行 get(key) 时：

先判断 key 是否存在。不存在直接返回空。
如果存在，再判断当前时间是否超过 expireTime。如果已经过期，就从 HashMap 和链表中删除，并返回空。
如果没有过期，就把该节点移动到链表头部，表示最近使用过，然后返回 value。

当执行 put(key, value) 时：

如果 key 已存在，先删除旧节点，再插入新节点，并刷新过期时间。
如果 key 不存在，直接插入新节点到链表头部。

插入后如果容量超过 n，需要先尝试删除一个过期节点。这里可以从链表尾部开始扫描，因为尾部是最久未使用的节点，通常也是更可能被淘汰的节点。如果找到过期节点，就删除它。
如果没有找到过期节点，再删除链表尾部节点，也就是标准 LRU 淘汰。

这道题的易错点主要有三个：

第一，过期 key 在查询时不能直接返回 value，必须删除并返回空。

第二，更新已有 key 时，过期时间应该刷新，否则可能出现刚更新就过期的问题。

第三，容量满时不能直接 LRU，需要先看有没有过期 KV。题目明确要求优先删除过期 KV。

整体复杂度上，get 可以做到 O(1)。
put 在最理想情况下也是 O(1)，但如果要扫描过期节点，最坏情况可能是 O(n)。如果面试官继续追问优化，可以再引入最小堆或按过期时间组织的数据结构。但因为题目说明所有 KV 过期时间间隔相同，很多情况下用链表扫描已经足够解释清楚。

这道题非常适合 TikTok、Meta、Amazon 这类高频系统设计 + 编码混合面试。它看起来是 LRU Cache，真正考察的是候选人能否在经典题基础上处理真实业务中的缓存过期逻辑。

面试官继续追问：

如果 get 到过期 key 怎么处理？
put 已存在 key 是否刷新过期时间？
容量满时先删过期还是先删 LRU？
如果大量 key 过期，如何优化？

如果这些细节没有说清楚，即使代码能跑，也很容易被认为设计不完整。

csoahelp 长期整理 TikTok、Amazon、Google、Meta 等公司的真实面试题，并提供面试辅助、真题讲解、模拟面试和代码思路训练。很多题并不难，真正的差距在于面试中能不能把思路讲清楚、边界条件补完整、代码写得稳定。

如果你正在准备北美大厂或 TikTok 面试，可以关注 csoahelp，我们会持续更新真实面试题和高频解法。