TikTok LRU Cache：O(1) 链表操作与 TTL 追问的复杂度边界

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 示例容量为正整数、按entry数量计算；value不使用None，None表示miss，真实接口可改(found,value)。
• 每次成功get与put使key成为最近使用；更新现有key不新增容量。
• 普通LRU的代码复用同一份已独立验证实现；TTL是独立追问，过期区间/刷新规则需额外定义。

解题路线

1. 哈希表key→节点解决定位，双向链表解决任意节点O(1)摘除/放到头部。头尾哨兵使空表/单节点操作与一般操作一致，不用扫描找前驱。
2. 不变量：哈希表每个key恰好对应一个真实链表节点，链表真实节点数等于表大小；head之后最新，tail之前最旧。get命中先摘再放头，不创建另一个节点。
3. put已有key时更新value并移头；新key插入头部后若超容量，摘tail.prev并同步删表。只删表或只删链会让下一次get和淘汰读到不同状态。
4. TTL先确定[写入,deadline)有效、get是否续期、更新是否重置TTL。惰性get只检查当前key会使过期冷key继续占容量，put要有清理/淘汰政策；过期与最近访问顺序是两个不同索引。
5. 用到期minheap主动清理时给每次写入版本号，旧到期事件不能删掉新值。heap成本O(log C)，一轮批量到期可更多；不能保留此实现又宣称每个带TTL操作严格O(1)。时间轮需接受精度/分桶与均摊条件。
6. 并发get也会改链表，整段定位→移动/更新→淘汰必须在同一原子区。分布式缓存通常每分片LRU，全局精确最近顺序需要协调；使用Redis不意味着拥有跨实例全局本地链表顺序。

手动走一遍

容量2：put(a,1)、put(b,2)顺序b,a；get(a)变a,b；put(c,3)淘汰b。更新a为4后仍两个entry，a最新。TTL追问中a原deadline=10、t=8被改写至deadline=30，旧t=10事件需凭版本识别后忽略。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class Node:
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None


class LRUCache:
    """Capacity in entries; get miss returns None; head is most recent."""
    def __init__(self, capacity: int):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.nodes = {}
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _front(self, node: Node) -> None:
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return None
        self._unlink(node)
        self._front(node)
        return node.value

    def put(self, key, value) -> None:
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._front(node)
            return
        node = Node(key, value)
        self.nodes[key] = node
        self._front(node)
        if len(self.nodes) > self.capacity:
            victim = self.tail.prev
            self._unlink(victim)
            del self.nodes[victim.key]

复杂度

普通LRU get/put期望O(1)，空间O(C)。哈希碰撞最坏界由语言实现决定。带heap过期版索引更新O(log C)，批量清理及陈旧事件需单列；全局并发锁与网络等待不属于单机容器成本。

易错点与追问

容易失分的边界

• get只读值却不更新顺序。
• 同key更新增加容量。
• 哨兵被错误淘汰。
• 把TTL追问的heap说成严格O(1)。

继续深挖

• 容量为0应禁止还是所有put丢弃？
• None值与miss怎样区分？
• TTL与idle timeout有何区别？
• 大量更新造成陈旧到期事件怎样压缩？