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

题目描述

实现一个 LRU 过期 KV 缓存。所有键值对的过期时间间隔相同；缓存最多存 n 个键值对。get 时若键已过期视为不存在，写入时若满则淘汰最久未用的键。

解题思路

用 OrderedDict 同时维护插入/访问顺序与键值对。get 前先判断是否过期，过期则删除并返回未命中；命中时把它移到最右表示最近使用。put 时先写值并记录过期时刻，再移到最后；容量超限时从最左淘汰。

from collections import OrderedDict

class ExpiringLRU:
    def __init__(self, capacity, ttl):
        self.capacity = capacity
        self.ttl = ttl
        self.data = OrderedDict()  # key -> (value, expire_at)

    def get(self, key, now):
        if key not in self.data:
            return -1
        value, expire_at = self.data[key]
        if now >= expire_at:
            del self.data[key]
            return -1
        self.data.move_to_end(key)
        return value

    def put(self, key, value, now):
        self.data[key] = (value, now + self.ttl)
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

复杂度与易错点

get/put 均摊 O(1)。过期是惰性检查：只在实际访问时判断，不主动轮询。淘汰时如果队首已过期，也应一并处理；写入已存在的键要刷新过期时间并移到末尾。

FAQ

过期键为什么要惰性删除而不是主动轮询？

主动轮询需要后台定时器，增加复杂度。惰性删除在每次访问时检查，配合 LRU 淘汰时机，能保证过期键最终被清除，且实现简单。

参考来源

• LeetCode 146 — LRU Cache
• LeetCode 460 — LFU Cache

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。