TikTok VO 面试真题解析：LRU Expiring KV Cache（KV Cache / LRU / 过期删除）

Implement an LRU expiring KV cache. All key-value pairs have the same expiration interval, with the following rules:

• The cache stores at most n key-value pairs.
• If inserting a new pair would make the cache exceed n, evict one expired key-value pair at random.
• If there is no expired key-value pair, evict one key-value pair according to the LRU rule.
• When querying a key, if it has already expired, return empty.

这道题要求设计一个支持统一过期时间的 LRU KV cache。核心思路通常是把“过期判断”和“最近最少使用”结合起来：一方面需要能快速判断某个 key 是否过期，另一方面要维护访问顺序以便在容量超限时按 LRU 淘汰。实现时常见做法是使用哈希表配合双向链表来维护缓存项和访问顺序，同时为每个 KV 记录过期时间；在查询和插入时先处理过期项，再根据容量决定是删除过期项还是按照 LRU 删除最久未使用的项。