题目重点：两篇 Phone 面经都提到内存文件系统，其中一篇标 LC 588；本文用明确的训练接口处理目录树、路径冲突、文件追加和有序列举。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 路径必须是绝对路径；根为 /，其他路径不能有尾斜杠、重复斜杠、. 或 ..。文件和目录名字在同一父目录下互斥。
- mkdir 递归创建缺失的目录；add_content 仅在父目录已存在时创建文件或追加文本；ls(文件) 返回该文件名，ls(目录) 返回字典序子项。
- 缺失路径报 FileNotFoundError；路径中途遇文件也报错；根不能作为文件。该异常约定只是训练选择，面试须先确认。
解题路线
- 把文件系统建成以根 Directory 开始的树，目录保存 name→File/Directory 映射；切分路径时先验证格式，避免 /a//b、/a/../b 隐式归一造成冲突。
- _directory 从根逐段查找；mkdir 允许创建缺失段，其他操作只读取已有目录。中途碰到 File 就拒绝继续向下。
- ls 先定位父目录再看最后一个节点：文件返回自身名，目录对直接子项排序；read_content 只接受 File。
- add_content 查父目录，不存在则拒绝；叶子缺失时新建 File，存在 File 时追加，存在 Directory 时抛错；不把内容写进目录节点。
- 用独立的完整路径→类型/内容映射随机对照 100,000 次创建、追加、读取与列举，覆盖根、同名冲突、缺失父目录和排序。
手动走一遍
mkdir('/a/b') 后 add_content('/a/b/f','hi')，再追加 '!'：read_content('/a/b/f') 为 'hi!'；ls('/a/b') 为 ['f']，ls('/a/b/f') 为 ['f']。试图 mkdir('/a/b/f/x') 会因 f 是文件而失败。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training file system: ls, mkdir, append content, and read content."""
class Directory:
def __init__(self):
self.children = {}
class File:
def __init__(self, content: str = ""):
self.content = content
class FileSystem:
def __init__(self):
self.root = Directory()
def _parts(self, path: str) -> list[str]:
if not path.startswith("/") or (path != "/" and (path.endswith("/") or "//" in path)):
raise ValueError("invalid absolute path")
parts = [] if path == "/" else path[1:].split("/")
if any(part in ("", ".", "..") for part in parts):
raise ValueError("invalid path segment")
return parts
def _directory(self, parts: list[str], create: bool = False) -> Directory:
node = self.root
for part in parts:
child = node.children.get(part)
if child is None and create:
child = Directory()
node.children[part] = child
if not isinstance(child, Directory):
raise FileNotFoundError("directory missing or path is a file")
node = child
return node
def ls(self, path: str) -> list[str]:
parts = self._parts(path)
if not parts:
return sorted(self.root.children)
parent = self._directory(parts[:-1])
child = parent.children.get(parts[-1])
if isinstance(child, File):
return [parts[-1]]
if isinstance(child, Directory):
return sorted(child.children)
raise FileNotFoundError(path)
def mkdir(self, path: str) -> None:
self._directory(self._parts(path), create=True)
def add_content(self, path: str, text: str) -> None:
parts = self._parts(path)
if not parts:
raise ValueError("root is not a file")
parent = self._directory(parts[:-1])
child = parent.children.get(parts[-1])
if child is None:
child = File()
parent.children[parts[-1]] = child
if not isinstance(child, File):
raise IsADirectoryError(path)
child.content += text
def read_content(self, path: str) -> str:
parts = self._parts(path)
if not parts:
raise IsADirectoryError(path)
parent = self._directory(parts[:-1])
child = parent.children.get(parts[-1])
if not isinstance(child, File):
raise FileNotFoundError(path)
return child.content
复杂度
路径有 d 段、目标目录有 c 个直接子项，mkdir/read/add_content 平均 O(d) 字典查找；ls(目录) 为 O(d+c log c)，ls(文件) 为 O(d)。树节点空间 O(目录与文件数+内容字符数)；Python 字符串追加在最坏情况下会复制已有内容，若高频大文件追加可改成分块缓冲。
易错点与追问
容易失分的边界
- 把文件当目录自动创建子项，破坏路径类型不变量。
- ls 对文件返回空列表，或把整个子树都递归列出来。
- 用操作系统路径归一函数悄悄接受 ..，却没有定义安全边界。
- 每次列举都扫描全局路径 Map，规模大时成本随文件总数增长。
- 称 Python 的 content += text 在所有追加模式下都有摊还 O(1) 时间。
继续深挖
- 如果支持 rm/mv，如何处理非空目录、原子移动与环？
- 并发读写时，目录级锁或复制快照如何保证 ls 一致性？
- 百万文件且路径很深时，如何分页 ls、限制深度并持久化？
- 如果题面允许自动建立 addContent 的父目录，代码哪些地方要改？
