Salesforce LFU Cache：频次桶与同频 LRU 淘汰

题意与假设

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

• 训练版支持 LFUCache(capacity)、get(key)、put(key,value)；每次成功 get 或更新已有键使频次 +1，新键频次 1；缺失 get 返回 None。
• 容量按条数，满时先淘汰使用频次最低的键；若同频，淘汰该频次中最久未被访问的键。题目未明确同频规则，选择 LRU 只是明确的训练约定。
• 单线程、键可哈希，使用 Python OrderedDict 的插入顺序维持同频访问顺序；复杂度按字典操作均摊 O(1)。

解题路线

1. 三个索引协作：values 保存键值，frequency 保存键当前频次，buckets[f] 是该频次按旧到新排列的键；minimum_frequency 指向当前最小非空桶。
2. get 命中后从旧桶删除键并追加到 f+1 桶；若旧桶空了且它是最小频次，minimum_frequency 变为 f+1。put 更新已有键也触发同样晋级；插入新键前若满，从最小频次桶头部弹出最久键，并删除两个索引，再将新键放入频次 1 桶、重置最小频次为 1。
3. 不变量：每个在 values 中的键恰好存在于 frequency 指定的一个桶；桶内顺序是该频次上次进入桶的时间顺序；minimum_frequency 总是最小非空桶。由此淘汰不需遍历全部键。

手动走一遍

capacity=2：put(A,1)、put(B,2)，两键频次均 1，顺序 A→B。get(A) 后 A 频次 2、B 仍 1；put(C,3) 淘汰 B。此时 C 频次 1、A 频次 2；再 get(C) 后两键均为 2，但 A 更早进入频次 2 桶，下一次满容量插入先淘汰 A。

Python 参考实现

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

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

from collections import OrderedDict, defaultdict


class LFUCache:
    """Least frequency first, LRU among keys with equal frequency."""

    def __init__(self, capacity: int):
        if capacity < 0:
            raise ValueError("capacity must be nonnegative")
        self.capacity = capacity
        self.values = {}
        self.frequency = {}
        self.buckets = defaultdict(OrderedDict)
        self.minimum_frequency = 0

    def _touch(self, key) -> None:
        old_frequency = self.frequency[key]
        del self.buckets[old_frequency][key]
        if not self.buckets[old_frequency]:
            del self.buckets[old_frequency]
            if self.minimum_frequency == old_frequency:
                self.minimum_frequency += 1
        new_frequency = old_frequency + 1
        self.frequency[key] = new_frequency
        self.buckets[new_frequency][key] = None

    def get(self, key):
        if key not in self.values:
            return None
        self._touch(key)
        return self.values[key]

    def put(self, key, value) -> None:
        if self.capacity == 0:
            return
        if key in self.values:
            self.values[key] = value
            self._touch(key)
            return
        if len(self.values) == self.capacity:
            oldest_key, _ = self.buckets[self.minimum_frequency].popitem(last=False)
            del self.values[oldest_key]
            del self.frequency[oldest_key]
            if not self.buckets[self.minimum_frequency]:
                del self.buckets[self.minimum_frequency]
        self.values[key] = value
        self.frequency[key] = 1
        self.buckets[1][key] = None
        self.minimum_frequency = 1

复杂度

get/put 各做有限次哈希查询、桶内 O(1) 删除/追加/弹头，均摊时间 O(1)，空间 O(capacity)。频次可持续增长，长生命周期系统可能需要衰减、重标定或有界计数；若加这些策略，频次语义和复杂度需重新定义。

易错点与追问

容易失分的边界

• 每次淘汰都遍历所有键找最低频，退化为 O(capacity)。
• 晋级后旧桶空了却未修 minimum_frequency，下一次淘汰从空桶取值。
• 更新已有键时不确定是否增加频次，导致测试与实现口径不一致。
• 把同频规则默认为任意键，却在文章或测试里声称 LRU；题目未明确规则，应显式标训练约定。
• 把标准 LFU 复杂度用作多线程保证；并发下多个索引更新必须同步。

继续深挖

• 若热点旧键永不淘汰，新热点难以进入缓存，怎样做频次衰减或 TinyLFU 类 admission？
• 若值大小不等、按字节限额，插入时可能要连续淘汰多个最小频次键；如何避免超大对象冲掉整个缓存？
• 若需要 TTL，过期键在桶中如何惰性/主动清理，minimum_frequency 如何保持正确？