LinkedIn Rankable Cache：可变 Rank 淘汰、Last Seen 平局与堆版本

题目重点：HashMap 加最小堆做淘汰，解释 rank 变动如何通知索引及删除后重插的陈旧条目陷阱。

题意与假设

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

训练版有固定 capacity，最小 rank 先淘汰、同 rank 最久未见先淘汰；get 和 put 都更新 last-seen，put 新项后若超容量允许立即淘汰新项。
value.rank() 若在外部原地改变，调用方必须显式 `refresh_rank(key)`；不通知时仅靠旧堆不能保证精确淘汰。以上为训练契约，非原题固定规则。

解题路线

map 存 key→(value,version,last_seen)，min heap 存 (rank,last_seen,key,version)。每次 get/put/refresh 将全局单调版本加一并推新堆项，旧堆项懒失效；淘汰时反复弹出，直到其 version 与 map 当前一致。
版本必须在整个 Cache 生命周期全局唯一：key 删除后重插若版本又从 1 起，旧 heap entry 也可能是 version 1，导致误删。训练验证曾抓到此错误，改用全局序号后修复。
rank 变化是核心接口问题：若能收到通知，refresh 可维护 heap；若 rank 任意时刻无通知地变化，想在 O(log N) 内精确选最低项一般无从保证，只能扫描所有 map 值 O(N) 或改变 value 所有权/约束。
Last Seen 只用于 rank 相等时平局；若 rank 高频变化且 get 高频，堆会积累陈旧项，定期在 stale ratio 高时从 map 重建 heap 控内存。

手动走一遍

容量 2，有 A(rank1,last1)、B(rank1,last2)，插 C(rank2) 时 A 淘汰。A 后来重插必须拿新的全局版本；否则旧 A 的 heap entry 可误被认作当前 A。若 B.rank 从 1 改成 5，必须 refresh 后再做淘汰。

Python 参考实现

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

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

import heapq


class RankableCache:
    """Explicit rank refresh; ties evict least-recently-seen key."""

    def __init__(self, capacity: int):
        if capacity < 0:
            raise ValueError("negative capacity")
        self.capacity = capacity
        self.items = {}  # key -> (value, version, last_seen)
        self.heap = []
        self.clock = 0

    def _publish(self, key, value):
        self.clock += 1
        # Globally unique token prevents stale heap entries matching a reinserted key.
        version = self.clock
        self.items[key] = (value, version, self.clock)
        heapq.heappush(self.heap, (value.rank(), self.clock, key, version))

    def _evict_one(self):
        while self.heap:
            _, _, key, version = heapq.heappop(self.heap)
            if key in self.items and self.items[key][1] == version:
                del self.items[key]
                return key
        raise RuntimeError("heap invariant broken")

    def put(self, key, value):
        if self.capacity == 0:
            return
        self._publish(key, value)
        if len(self.items) > self.capacity:
            self._evict_one()

    def get(self, key):
        if key not in self.items:
            return None
        value = self.items[key][0]
        self._publish(key, value)
        return value

    def refresh_rank(self, key):
        """Caller must invoke this after an in-place rank mutation."""
        if key in self.items:
            self._publish(key, self.items[key][0])

复杂度

每次发布 heap entry O(log H)，懒弹出摊还可按 entry 数计；map O(C)，heap 在长期 get 下可到 O(操作数)，需周期 O(C) 重建。无通知的任意 rank 变化若仍要准确淘汰，保守扫描 O(C)。3,000 组随机操作序列与独立全表最小项模型对照。

易错点与追问

容易失分的边界

认为外部 rank 改变后堆自动重新排序。
key 删除重插时复用旧版本，让陈旧 heap entry 误匹配。
把 last-seen 作为首要排序键而非 rank 平局。
未定义 get 是否更新 last-seen。
heap 惰性条目无限堆积却报空间 O(C)。

继续深挖

rank 改变时怎么通知 Cache？
无通知又要求精确淘汰，有没有 O(log N) 解？
如何支持并发 get/put 而保持次序一致？
last-seen 用墙上时间还是单调序号？