Oracle OCI LFU Cache：频次桶与同频 LRU

题意与假设

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

• 训练接口为 get(key)、put(key,value)，容量为非负整数；get 未命中返回 None。
• 先淘汰最低访问频次；同频时淘汰最久未访问或更新的键，是训练约定，不冒称面试原题规则。
• 成功 get 与更新已有键的 put 都令频次加一；新键初始频次为一；容量零时 put 无效。

解题路线

1. 用 key→value、key→frequency 两个索引，并用 frequency→有序键桶表示每个频次里的 LRU 顺序；保存当前 minimum_frequency。
2. get 命中或 put 更新时，把 key 从旧桶移到频次加一的新桶末尾；若旧桶空且它是最小频次，最小频次加一。
3. 插入新键且满容量时，从最小频次桶头部移除最久未使用项；新键进入频次一桶，重设 minimum_frequency=1。
4. 核心不变量：每个现存 key 恰在与频次相同的一个桶内；最小频次桶非空。若用 Python OrderedDict，平均操作时间是 O(1)；其他语言可用双向链表实现。

手动走一遍

容量 2：put(A,1)、put(B,2)、get(A) 后频次 A=2、B=1；put(C,3) 淘汰 B。若 A、B 同为频次 1，再插入 C，则按训练约定淘汰更早插入的 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(C)，C 为容量；频次可持续增长，长期运行需考虑计数溢出或衰减策略。此通用 LFU 训练代码也用于 Salesforce 同考点，不代表两家公司共享原题接口。

易错点与追问

容易失分的边界

• 把 LFU 误做 LRU； 题目补充特别更正过。
• 只用一个按频次排序的堆却声称更新频次 O(1)。
• 漏处理最小频次桶变空后的更新，淘汰时找不到正确桶。
• 把训练用同频 LRU 规则当成题目已公开要求。

继续深挖

• 热点键频次非常高导致旧热点长期驻留时，如何做频次衰减？
• 多线程下移动频次桶和淘汰必须如何同步？