题目重点：实现前缀加后缀检索、复制文件、按大小淘汰以及压缩解压，保证失败不改变状态。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练文件全局唯一，copy保留源owner并消耗其额度；查询返回所有同时匹配prefix AND suffix的文件，不是隐含TopN。
- 训练保留后缀.compressed，正常add禁止此后缀；压缩仅接受偶数大小并减半，解压翻倍。复制需保持压缩标记类型，容量收缩按(-size,name)删除直到used≤capacity。奇数舍入、后缀字面值和恰好容量时边界需要核对。
解题路线
- 维护files→(owner,size)、capacity与used，所有操作以同一计数不变量为中心。copy必须先检查源存在、目标未占用、目标标记类型及owner容量，再写入；复制dict不能遗漏容量。
- 查询分别检查startswith和endswith，再按大小降序、名字升序。空前/后缀有合法含义。方法名即使含Largest，也不能自动截断为n，合同返回的是全部匹配。
- resize先改变容量，再收集该owner现存文件排序删除到used≤cap。相等已经合法；零容量仍可保留零字节文件。基线全扫描比维护一个未做过期校验的heap更可靠。
- compress从name改成name+.compressed并把size减半；验证owner、偶数、目标名冲突后才改状态。decompress从末尾切掉一次后缀，不能replace删除文件名中间的同样字符。
- 解压需增加原压缩大小这么多额度，检查used+compressedSize≤capacity后执行重命名和更新。失败保留原文件、used与capacity，不先占额后发现名字冲突。
手动走一遍
u容量12，a大小8、b大小4。压缩a成a.compressed(4)，used从12降为8；copy该压缩文件为c.compressed(4)后used=12，解压a失败保持不变。缩容到8时三个文件都4，按名字先删a.compressed；不能按旧大小8再删别的。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class CompressFiles:
"""Training: '.compressed' reserved; even sizes only when compressing.
Copy preserves owner and consumes quota. Capacity shrink stops at used<=cap.
All failed operations leave state unchanged. Sizes are integer >=0.
"""
SUFFIX = '.compressed'
def __init__(self):
self.files = {} # name -> (owner, size)
self.capacity = {'admin': float('inf')}; self.used = {'admin': 0}
def add_user(self, user, cap):
if cap < 0: raise ValueError('negative capacity')
if user in self.capacity: return False
self.capacity[user] = cap; self.used[user] = 0; return True
def add(self, name, size, user='admin'):
if size < 0: raise ValueError('negative size')
if name.endswith(self.SUFFIX): return None
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 copy(self, src, dst):
if src not in self.files or dst in self.files: return False
# Preserve compression marker so reverse rename has unambiguous meaning.
if src.endswith(self.SUFFIX) != dst.endswith(self.SUFFIX): return False
user, size = self.files[src]
if self.used[user]+size > self.capacity[user]: return False
self.files[dst] = (user, size); self.used[user] += size; return True
def matches(self, prefix, suffix):
return sorted(((n, z) for n, (_, z) in self.files.items()
if n.startswith(prefix) and n.endswith(suffix)),
key=lambda p: (-p[1], p[0]))
def resize(self, user, cap):
if cap < 0: raise ValueError('negative capacity')
if user not in self.capacity or user == 'admin': return None
self.capacity[user] = cap; removed = 0
owned = sorted(((n,z) for n,(u,z) in self.files.items() if u==user),
key=lambda p: (-p[1], p[0]))
for name, size in owned:
if self.used[user] <= cap: break
del self.files[name]; self.used[user] -= size; removed += 1
return removed
def compress(self, user, name):
if name not in self.files or name.endswith(self.SUFFIX): return None
owner, size = self.files[name]; dst = name+self.SUFFIX
if owner!=user or size%2 or dst in self.files: return None
del self.files[name]; self.files[dst] = (owner, size//2)
self.used[owner] -= size//2
return self.capacity[owner]-self.used[owner]
def decompress(self, user, name):
if name not in self.files or not name.endswith(self.SUFFIX): return None
owner, size = self.files[name]; dst=name[:-len(self.SUFFIX)]
if owner!=user or dst in self.files: return None
if self.used[owner]+size > self.capacity[owner]: return None
del self.files[name]; self.files[dst]=(owner,size*2); self.used[owner]+=size
return self.capacity[owner]-self.used[owner]
复杂度
复制/压缩/解压均摊O(1)；匹配排序O(F+M log M)，缩容O(F+Fu log Fu)。维护每用户索引能降扫描成本；若用heap需要版本号检查重命名和大小变化留下的旧项。
易错点与追问
容易失分的边界
- 压缩后只减used却把文件实际size仍写旧值，会立即打破计数。
- 用整串replace去掉后缀会损坏中间含compressed的文件名。
- 复制压缩文件成普通名字会让解压语义丢失，接口应明确保留标记。
继续深挖
- 压缩大小可能奇数时，怎样保存originalSize以保证逆操作？直接floor再×2不可逆。
- 每用户有百万文件且频繁缩容，怎样用有序索引/带generation的heap减少排序，又保证tie规则？
