题目重点：把 Netflix VO 的 execute/undo class 题拆为命令协议、最小撤销令牌、成功后入栈与失败时保留历史；区分单机内存撤销和外部副作用补偿。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版状态为 dict，示例 command 是 SetValue；真实题目未明确命令集合和状态模型。
- execute 成功才入历史；undo_last 只撤销最近一次成功命令，空历史返回 False。撤销自身抛错时历史保留，便于重试/诊断。
- 示例单线程；外部网络写入、不可逆动作与并发执行不由普通内存栈自动解决。
解题路线
- 定义命令协议 `execute(state)→undo_token` 与 `undo(state,token)`。执行时保存最小必要的旧状态，例如 set 操作保存 key 是否原本存在和旧值，不能只保存旧值，否则旧值 None 与不存在混淆。
- 执行成功后把 `(command,token)` 压栈；undo 先看栈顶，成功调用撤销后才弹栈。不要先弹栈再撤销，避免撤销失败后丢失恢复信息。
- 如果命令可以部分修改后抛错，要设计 execute 的原子提交或内部 rollback；真实文件/网络命令需补偿日志或 saga，undo 可能失败且不能保证时间倒流。多线程情况下 execute 与 undo 的顺序应由一个锁或串行执行器定义。
手动走一遍
训练例状态为空，执行 SetValue(x,1) 得旧状态‘不存在’，再执行 SetValue(x,2) 得旧值 1。undo 一次恢复 x=1；再 undo 一次删除 x。若只记录旧值 None，第一次创建与原来存在且值为 None 无法区分。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class CommandHistory:
"""Commands implement execute(state)->undo_token and undo(state, undo_token)."""
def __init__(self, state):
self.state = state
self._history = []
def execute(self, command):
token = command.execute(self.state)
self._history.append((command, token))
def undo_last(self):
if not self._history:
return False
command, token = self._history[-1]
command.undo(self.state, token)
self._history.pop()
return True
class SetValue:
def __init__(self, key, value):
self.key, self.value = key, value
def execute(self, state):
existed = self.key in state
previous = state.get(self.key)
state[self.key] = self.value
return existed, previous
def undo(self, state, token):
existed, previous = token
if existed:
state[self.key] = previous
else:
state.pop(self.key, None)
复杂度
单个内存 dict 的 SetValue 执行和撤销预期 O(1)，历史空间 O(H) 个成功命令与各自令牌大小；若令牌是整个对象快照，空间可能随状态大小增长，故尽量存差量。
易错点与追问
容易失分的边界
- 先压栈再执行，失败命令也可被 undo。
- 先弹栈后撤销，撤销失败时丢历史。
- 未记录 key 原先是否存在。
- 命令调用外部服务后简单回写旧值，忽略其他客户端已作的新更改。
- 多个线程同时执行/撤销时无统一顺序。
继续深挖
- 支持 redo 时需要怎样移动两个栈？
- 组合命令执行到一半失败如何整体回滚？
- 历史量过大时如何压缩快照与差量？
- 外部付款等副作用如何定义可补偿而非真正撤销？
