Amazon Cache 变体：返回某个 Key 的最大时间戳 Value

题意与假设

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

• 训练每key保留最大event timestamp，允许乱序set；同timestamp后一次set胜出。正式题tie未知，留待核。
• get返回(found,value)，存None与缺key区分；不含历史查询、TTL或容量淘汰。

解题路线

1. Map key→(timestamp,value)。set只有新timestamp≥当前才替换；旧事件不能覆盖更晚事件，访问顺序不参与答案。
2. 归纳不变量：处理任意前缀后每key存最大timestamp，同刻保留最后调用。下一条更旧不动、更晚替换、同刻按训练规则替换，保持不变量。
3. LRU按最近访问决定淘汰，timestamp决定事件新旧，两者无相互替代关系。若正式题还有capacity才另加淘汰层并澄清旧值是否允许丢失。
4. 多线程比较与写必须原子，不能读旧timestamp后被另一线程写更大，再无条件覆盖。跨机器要明确timestamp来源与同刻序号，墙钟偏差可能不表达业务因果。
5. 若get要小于某查询时刻的最近value，必须保留有序历史，这与只取全局最大时间戳不同，空间与API都改变。

手动走一遍

训练set(k,A,10)，set(k,B,8)后get仍A；set(k,C,10)按本文同刻last-call策略为C；读取k再读取其他key不会改变k的value。

Python 参考实现

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

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

class LatestValueStore:
    """Per-key maximum timestamp; ties choose the latest set call, no TTL or LRU."""
    def __init__(self):
        self.values={}

    def set(self,key,value,timestamp):
        current=self.values.get(key)
        if current is None or timestamp >= current[0]:
            self.values[key]=(timestamp,value)

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

复杂度

哈希map期望O(1) set/get，空间O(u)不同key；不存在LRU链表或expiry heap。持久或分布式比较成本另算。

易错点与追问

容易失分的边界

• 较晚到达的旧事件覆盖最大时间戳。
• 自动加入LRU容量导致丢掉题目必须返回的值。
• 不声明同timestamp策略。

继续深挖

• 同刻如何按来源序号而非调用顺序？
• 查询历史时刻需怎样改结构？
• 时钟偏差怎么处理？