题目重点：从组招缓存题的 get/put API 出发，明确半开有效期、覆盖写、空值区分和闲置键回收。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练 API 为 put(key,value,ttl,now) 和 get(key,now)，调用方传单调时间；ttl≥0。
- 在 put 的 now 写入后有效区间为 [now,now+ttl)，恰好到期时 miss；同 key put 覆盖旧值和旧到期时刻。
- get 返回 (found,value)，允许 value=None 而不会与 miss 混淆；容量无限，暂不做 LRU 淘汰。
- 示例假定同一调用序列的 now 非递减；倒流时间对已懒删的键不提供历史查询。
解题路线
- 哈希表 key→(value,expiresAt)。put 根据 TTL 计算到期时间并覆盖；get 读取条目，若 now≥expiresAt 就删掉并返回 miss，否则返回值。
- 半开区间让 ttl=0 的写入立即不可读，也避免到期瞬间同时有效和无效两种口径。
- 懒清理保证访问到过期键时释放内存，却不能释放永不再访问的键；生产版可加小根堆按到期时刻后台回收，覆盖写时用版本号跳过旧堆记录。
- 并发下 put/get 与删除必须按键原子化，否则旧 get 可能删除刚覆盖的新值；单线程代码不冒充并发安全。
手动走一遍
put(a,4,ttl=3,now=10) 后 get(a,12) 命中 4，get(a,13) miss；再 put(a,None,ttl=5,now=20)，get(a,21) 返回 (True,None)，可与 (False,None) 区分。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class TTLCache:
"""Training API with caller-supplied monotonic time and lazy expiration."""
def __init__(self) -> None:
self.data: dict[object, tuple[object, float]] = {}
def put(self, key: object, value: object, ttl: float, now: float) -> None:
if ttl < 0:
raise ValueError("negative TTL")
self.data[key] = (value, now + ttl)
def get(self, key: object, now: float) -> tuple[bool, object | None]:
entry = self.data.get(key)
if entry is None:
return False, None
value, expires_at = entry
if now >= expires_at:
del self.data[key]
return False, None
return True, value
if __name__ == "__main__":
cache = TTLCache()
cache.put("a", 4, 3, 10)
assert cache.get("a", 12) == (True, 4) and cache.get("a", 13) == (False, None)
复杂度
哈希表 put/get 预期 O(1) 时间；空间 O(历史写入过但尚未被访问清理的不同 key 数)。没有后台清理时，逻辑上过期的闲置键仍占内存；堆清理可使写入/回收 O(log n)。
易错点与追问
容易失分的边界
- 在 t=expiresAt 仍返回旧值，与训练版半开边界相反。
- 把值 None 当未命中，无法缓存空值。
- 以 wall-clock 直接做 TTL 且不考虑时钟回拨；训练代码显式由调用方提供单调时间。
- 声称懒删除能自动回收所有闲置过期键。
- 把 LRU 逐出规则补成原题要求；题目只说 TTL cache。
继续深挖
- 容量也有限时，TTL 与 LRU 的逐出优先级如何定义？
- 覆盖 put 后旧过期事件如何避免删掉新值？
- 多线程或多机共享 cache 时，时钟源和原子更新怎样处理？
