Google CoolMap 题详解：如何让 putAll 保持 O(1)

题意与假设

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

• put(key,value) 写单个键，get(key) 读当前值，putAll(value) 将调用时已经存在的所有键的当前值统一改为 value。未来新增键不会自动继承旧 putAll。
• 缺失键返回 None，因此示例不允许把 None 作为值；操作在单线程里按顺序发生。
• O(1) 指哈希表期望时间与不随键数量增长；不包含输出全部键的遍历操作。

解题路线

1. 每次写入递增逻辑时钟。单键条目保存局部值及最近 put 时间；另存最近一次 putAll 的全局值及时间。
2. get 先判断键是否存在，再比较局部写入时间与全局更新时间；更晚的那次操作决定可见值。
3. putAll 只更新一个全局二元组，不逐键改写。训练版 delete 直接移除键；如果要做历史时间点查询，则必须保留版本，不能继续假设同样 O(1)。

手动走一遍

put(A,1)、put(B,2) 后，putAll(9) 只记录全局值 9；此时读 A、B 都是 9。再 put(A,3)，读 A 为 3、B 为 9。删除 B 后，旧的 putAll 不会把 B 复活；之后新建 C=4，读 C 为 4。

Python 参考实现

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

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

class CoolMap:
    """Current-state put/get/putAll in expected O(1) per operation."""

    def __init__(self):
        self.clock = 0
        self.entries = {}  # key -> (local_value, last_put_time)
        self.all_value = None
        self.all_time = -1

    def put(self, key, value):
        if value is None:
            raise ValueError("None is reserved for missing keys")
        self.clock += 1
        self.entries[key] = (value, self.clock)

    def get(self, key):
        if key not in self.entries:
            return None
        value, written_at = self.entries[key]
        return self.all_value if written_at < self.all_time else value

    def put_all(self, value):
        if value is None:
            raise ValueError("None is reserved for missing keys")
        self.clock += 1
        self.all_value = value
        self.all_time = self.clock

    def delete(self, key):
        """Optional training extension; deleting an absent key is a no-op."""
        self.entries.pop(key, None)

复杂度

put、get、putAll 与训练版 delete 都只做固定次数的哈希操作和时间比较，期望 O(1)；空间 O(当前存在的键数)。如果要求历史时间点读取，需保存每个键和全局更新的版本序列，并讨论 O(log V) 二分或其他索引；当前代码不声称支持该接口。

易错点与追问

容易失分的边界

• putAll 遍历所有键会变成 O(n)，即使 get 很快也不满足题目要求。
• 只保存全局值、不保存时间，会在 putAll 后无法判断某个键的后续 put 是否应覆盖它。
• 删除键后仍把它当作存在，会在后续 get 时错误地返回全局 putAll 的值。

继续深挖

• 如果要区分‘键存在但值为 None’与‘键不存在’，返回带存在标记的结果或使用专门哨兵。
• 并发实现需要使时钟递增与数据更新保持原子顺序；仅把 clock 设成线程安全计数器仍不足以保护整个 get/put 语义。