Rectangle Board：原子批量删除、点选与Undo

题意与假设

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

• 矩形用唯一ID和正面积半开范围[x1,x2)×[y1,y2)，允许重叠。removeAt删除所有包含点的矩形，不是最上层一项；正式要求层序时需改此合同。
• batch_remove要求ID存在且不重复，全部校验成功才修改。空批量/没有命中不入历史；undo无历史返回false，示例不含redo。

解题路线

1. add记录逆操作remove(ID)，删除记录被删矩形的完整ID→geometry映射，undo从栈弹出并执行一次逆操作。批量删除共用一个history条目，避免撤销只恢复其中一个。
2. 先把keys转list并验证重复和缺失，随后保存全部old再删。边删边检查会在中途遇未知ID时残留部分删除，违反原子命令语义。
3. removeAt先只读扫描找完整命中列表，再调用同一batch_remove；共享原子和撤销逻辑。半开边界使贴边矩形点选不重复，重叠允许删除多个不是几何错误。
4. 逆命令只在完整命令之后入栈；生产复杂编辑可使用Command.apply/undo，redo需要新的栈，新命令清空redo。UI拖动一百个事件是否合成一次历史必须另定交互合同。

手动走一遍

矩形a=[0,2)×[0,2)，b=[1,3)×[0,2)，点(1,1)删a/b；一次undo恢复两者。点(2,1)不命中a但命中b。batch_remove([a,unknown])应报错且a仍在，历史长度不变。

Python 参考实现

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

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

class Board:
    def __init__(self):self.rectangles={};self.history=[]
    def add(self,key,rectangle):
        if key in self.rectangles:raise ValueError("duplicate ID")
        x1,y1,x2,y2=rectangle
        if x1>=x2 or y1>=y2:raise ValueError("positive rectangle")
        self.history.append(('remove',key));self.rectangles[key]=tuple(rectangle)
    def remove(self,key):return self.batch_remove([key])
    def batch_remove(self,keys):
        keys=list(keys)
        if len(set(keys))!=len(keys) or any(k not in self.rectangles for k in keys):raise ValueError("unknown or duplicate ID")
        if not keys:return []
        old={key:self.rectangles[key] for key in keys};self.history.append(('restore',old))
        for key in keys:del self.rectangles[key]
        return keys
    def remove_at(self,x,y):
        matches=[key for key,(x1,y1,x2,y2) in self.rectangles.items() if x1<=x<x2 and y1<=y<y2]
        return self.batch_remove(matches)
    def undo(self):
        if not self.history:return False
        action,payload=self.history.pop()
        if action=='remove':del self.rectangles[payload]
        else:self.rectangles.update(payload)
        return True

复杂度

n矩形、k删除项：add平均O(1)，batch O(k)，removeAt O(n+k)，undo O(k)恢复或O(1)撤销add；存当前O(n)，历史空间为所有删除记录累计大小，不能笼统写O(n)。

易错点与追问

容易失分的边界

• 将每个删除当独立命令会破坏批量undo。
• 记录矩形对象引用后又原地改geometry，会使历史内容改变。
• 未知ID失败时不能先入一个空/半成品history。

继续深挖

• R-tree优化点选后，删除和undo如何同步索引？
• 加入move/resize及redo时，怎样记录前后状态并保持命令边界？