TikTok LFU Cache：频率桶、最小频率与同频 LRU

题意与假设

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

• 训练get命中与已有key的put均将频率加1，新key频率1；缺失get返回None，存值避免None歧义。
• 淘汰最低频率，同频淘汰最久未被touch者；capacity非负，0不存。
• 无TTL、显式delete、容量调整或并发要求；这些操作会改变最小频率维护逻辑。

解题路线

1. 哈希表保存value与frequency，另一个映射把每个频率对应到按最近使用排序的OrderedDict桶。每个key恰好位于自己频率桶一次，最旧在桶首。
2. touch时从频率f桶删除key，将频率改为f+1并放到新桶尾；这是同频的最新访问。空桶删除，避免长期累积空频率结构。
3. minimum_frequency记录当前最小非空桶。touch若搬空最小桶，最小值可以直接加1，因为刚被搬走的key必在f+1形成非空桶，且之前没有低于f的key。这个论证依赖只有+1增长。
4. 插新key且满容量时，从最小桶首popitem(last=False)淘汰，删value/frequency映射；新key进频率1，所以minimum_frequency必须重置1，不能沿用旧高频值。
5. 已有key的put按训练视为一次访问，改值并touch，不需要腾位置；若正式更新不计频率，操作应另实现并明确是否刷新同频LRU位置。
6. 正确性由桶成员与frequency一致、桶顺序按touch时间、minimum定位最小非空桶三条不变量保证。淘汰两级排序等价于先按频率再按时间扫描，但不需要每次遍历全部key。
7. LFU保留长期热门，热点变迁后旧高频key可能难被替换。实际系统可用衰减/近似计数或窗口策略，但这些已偏离本训练精确LFU；频率整数增长的位数和长期行为也应说明。
8. TTL或任意删除可能一次删掉最低桶且没有f+1元素，不能简单minimum+=1。并发下映射与桶必须原子更新，可锁保护或分片并接受局部策略。

手动走一遍

容量2：put(a,1),put(b,2),get(a)后a频率2、b频率1，put(c,3)淘汰b。随后get(c)使a/c同频2，若a更早touch，put(d,4)淘汰a。更新已有c也会增频，不当作新插入。

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

复杂度

在哈希和OrderedDict操作平均O(1)假设下get/put平均O(1)，非空桶和key共O(capacity)结构空间。频率数值随访问次数增长，其大整数位数另计；未承诺严格最坏O(1)。

易错点与追问

容易失分的边界

• 同频随机淘汰而合同要求LRU。
• 新key未把minimum设1。
• 搬空最小桶不更新minimum。
• 任意delete仍套最低频率加1。

继续深挖

• TTL与delete怎样找下一个非空频率？
• 热点迁移后如何衰减计数？
• 更新值不计访问怎样改？
• 多线程或分片如何保持桶不变量？