面试背景
面试中被要求实现一个类似 Linux 中 rm -rf 功能的函数，题目链接：Datadog onsite: rm -rf。
系统提供以下函数：
Delete(path) -> bool：删除一个文件或空目录。IsDirectory(path) -> bool：判断路径是否为目录。GetAllFiles(path) -> List[string]：获取目录下所有文件和子目录的绝对路径。
要求实现
def DeleteAllFilesAndDir(path):
# 实现类似于 rm -rf 的功能
初始实现：递归 DFS 版本
面试时我首先写出了一个递归实现的 DFS（深度优先搜索）版本。
面试官追问：递归实现可能导致 OOM 问题？
面试官进一步询问了递归实现的潜在问题，即是否会导致 OOM（Out Of Memory）。经过深入讨论，我指出递归实现可能引发 OOM 的主要原因包括：
- 每一层递归调用都会占用调用栈内存，尤其是目录结构很深时容易栈溢出。
- 当目录结构“宽”且文件数量巨大时，每次递归调用可能会持有大量的文件路径数据，导致内存爆炸。
具体讨论与场景分析
面试官补充说明了他们的实际应用场景特点：
- 目录结构深度有限，最多 10 层。
- 每个目录的宽度（即目录内文件或子目录数量）非常大，可能达到百万级别。
基于此信息，我进一步分析指出：
- 深度较浅时，递归带来的栈溢出风险相对较低。
- 但宽度巨大时，递归获取所有文件路径的中间数据集合会迅速膨胀，占用过多内存。
改进方案：迭代的 BFS 实现
为了规避上述问题，我提出了使用基于迭代的 BFS（广度优先搜索）方式来实现：
- 使用队列数据结构逐层遍历。
- 每次只处理当前层次的文件和目录，处理完即释放。
- 显著降低内存占用，不再受调用栈的深度和中间数据规模的限制。
迭代 BFS 实现的优势
- 控制内存使用，每次处理的路径数量有限。
- 避免调用栈溢出问题。
- 特别适用于目录结构“浅而宽”的场景。
面试结果
面试官对 BFS 迭代实现方案表示认可，并且认可了我对 OOM 问题的深入分析和合理优化方案。
顺利通过，进入下一轮面试 ✅
