题目重点：实现全局文件名、前缀TopN、用户容量、合并以及用户文件快照，维护空间与归属不变量。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练合同：文件名全局唯一、大小为非负整数；admin无容量限制。add返回剩余额度，失败None；get/delete返回大小或None，TopN返回(name,size)对，展示格式可再适配。
- backup覆盖该用户的旧快照；restore先删除该用户当前文件，再恢复快照中未被他人占用的名字。无快照则清空并返回0。合并保留survivor旧快照、删除absorbed快照，禁止合并admin；这些第四阶段细则需练习前确认。
解题路线
- 用files[name]=(owner,size)、capacity[user]和used[user]三张表。不变量used等于该用户所有现存文件大小之和，且used≤capacity。不要一处存总容量、另一处却把同字段解释成剩余额度。
- add先校验用户、名字、容量，再一次写文件并增加used；delete只按实际owner释放额度，失败删除不能重复释放。管理员入口复用同一add方法，避免前两阶段与用户阶段表现不同。
- 前缀候选按(-size,name)排序取前n；大小相等要按文件名稳定比较，n=0返回空。前缀空串可匹配全部，不能把其当缺参。
- merge把absorbed所有文件owner改成survivor，容量和used分别相加，最后删除旧用户。总文件大小不变、剩余额度是双方原剩余额度之和，不能只把balance相加却漏转owner。
- backup复制name→size，而非持有现存dict引用。restore通过标准delete/add路径恢复计数，名字被另一个用户占用时跳过，不覆盖别人文件。survivor备份文件总量不超过其原容量，合并只会扩大容量，因此恢复不会超额。
手动走一遍
u容量10添加a(6)，备份后删除a。v占用了全局名字a(3)，u再添加b(4)。恢复u时删除b并跳过a，返回0、used[u]=0，v的a仍为3。重复恢复仍是0，不应把v文件删除。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class CloudFiles:
"""Training: global names, integer nonnegative sizes, admin has no quota.
restore removes current owner files; skips names occupied by another owner.
A saved snapshot fits its unchanged owner's quota. Shrinking is not offered.
Merge retains survivor snapshot and deletes absorbed user's snapshot.
"""
def __init__(self):
self.files = {} # name -> (owner, size)
self.capacity = {'admin': float('inf')}
self.used = {'admin': 0}
self.snapshots = {}
def add_user(self, user, capacity):
if capacity < 0: raise ValueError('negative quota')
if user in self.capacity: return False
self.capacity[user] = capacity; self.used[user] = 0
return True
def add(self, name, size, user='admin'):
if size < 0: raise ValueError('negative size')
if user not in self.capacity or name in self.files: return None
if self.used[user] + size > self.capacity[user]: return None
self.files[name] = (user, size); self.used[user] += size
return self.capacity[user] - self.used[user]
def get(self, name):
return self.files[name][1] if name in self.files else None
def delete(self, name):
if name not in self.files: return None
owner, size = self.files.pop(name); self.used[owner] -= size
return size
def largest(self, prefix, n):
if n < 0: raise ValueError('negative count')
return sorted(((name, size) for name, (_, size) in self.files.items()
if name.startswith(prefix)), key=lambda p: (-p[1], p[0]))[:n]
def merge(self, survivor, absorbed):
if survivor == absorbed or 'admin' in (survivor, absorbed): return None
if survivor not in self.capacity or absorbed not in self.capacity: return None
for name, (owner, size) in list(self.files.items()):
if owner == absorbed: self.files[name] = (survivor, size)
self.capacity[survivor] += self.capacity.pop(absorbed)
self.used[survivor] += self.used.pop(absorbed)
self.snapshots.pop(absorbed, None)
return self.capacity[survivor] - self.used[survivor]
def backup(self, user):
if user not in self.capacity: return None
self.snapshots[user] = {n: z for n, (u, z) in self.files.items() if u == user}
return len(self.snapshots[user])
def restore(self, user):
if user not in self.capacity: return None
for name, (owner, _) in list(self.files.items()):
if owner == user: self.delete(name)
restored = 0
for name, size in self.snapshots.get(user, {}).items():
if self.add(name, size, user) is not None: restored += 1
return restored
复杂度
F个文件、U个用户，add/get/delete均摊O(1)，前缀TopN基线O(F+M log M)，M为匹配数；merge/backup/restore扫描O(F)。快照空间按保存文件数量计，不能因当前文件数少就忽略备份成本。
易错点与追问
容易失分的边界
- restore直接写storage而不重算used，会使后续容量判断错误。
- 合并后用旧owner删除文件会释放不存在用户的额度。
- 恢复冲突不等于改名恢复；名字冲突政策必须明确。
继续深挖
- 若容量允许缩小，旧快照大于新容量时怎样恢复？先定拒绝/部分恢复/按规则淘汰，不能套用当前不变量证明。
- 并发添加同名文件与合并要怎样原子化？名字唯一性与用户额度需要处于同一事务或锁协议。
