以下来自于我们CSOahelp真实客户的面试记录,CSOahelp面试辅助老师全程提供解题思路、Follow up 以及详细完整代码; 不用刷题轻松进大厂。
题目原文
Design a data structure that simulates an in-memory file system.
Implement the FileSystem class:
- FileSystem() Initializes the object of the system
- List<String> ls(String path)
-- returns the list of directory names in this directory. The answer should be in lexicographic order.
- void mkdir(String path)
-- Makes a new directory according to the given path. If the middle directories in the path do not exist, you should create them as well.
Example:
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/"); // return []
fileSystem.mkdir("/a/b/c");
fileSystem.ls("/"); // return ["a"]
面试还原 + 解题攻略
场景背景:
这是一道典型的“模拟系统设计”类题目,通常会出现在 TikTok 或其他大厂的 system design 或面向对象设计面试中。考点不仅在于你是否能构建正确的数据结构,还在于你如何组织代码架构、接口清晰性和边界条件的处理。
一、Clarification 阶段:一定要问清楚的问题
应该确认:
- ls(path) 是否可能是文件(这道题暂时只涉及目录,不涉及文件创建,所以默认全是目录)。
- 路径一定以
/
开头吗? ls("/")
是列出当前目录下的所有子目录名,返回值是否排序?(题目中明确要求字典序排序)
这些问题问得越细致,面试官越容易觉得你在认真分析系统边界。
二、设计思路讲解
我们可以把整个文件系统抽象为一棵“前缀树 Trie”,每一个节点代表一个目录。
每个目录节点包含:
- 子目录名 -> 子节点(用
Map<String, Node>
来表示) - 一个标识符:是否是文件(这题不需要)
- 节点名称(可选)
class Node {
Map<String, Node> children;
}
整体类结构:
class FileSystem {
Node root;
FileSystem()
ls(path)
mkdir(path)
}
三、函数细节拆解
mkdir(path)
- 将路径用
/
分割,例如/a/b/c
→ ["a", "b", "c"] - 从 root 开始逐级查找或创建子节点
- 如果不存在某一级目录,就自动新建一个 Node 节点插入进去
ls(path)
- 类似于 mkdir 的路径遍历逻辑
- 找到最后一级目录,返回它的所有
children.keySet()
,按字典序排序返回
四、隐含坑点与注意事项
- 路径前导
/
的处理一定要谨慎,空字符串会被 split 出来,需要跳过 ls("/")
是个特殊情况,它返回的是 root 下的所有一级目录- 排序使用
List.sort()
或TreeMap
等方式都可,但最好在ls()
时统一处理
五、面试对话
面试官:你怎么建这个类的结构?
候选人:我倾向于使用一棵 Trie 结构来模拟文件系统,每一个节点代表一个文件夹,它有一个字典保存所有子目录。ls 和 mkdir 都是基于这棵树的遍历。
面试官:如果路径是
/a/b/c
,你如何实现 mkdir?
候选人:我会 split 成 ["a", "b", "c"],从 root 开始一级一级往下找,如果某一级目录不存在,就创建一个新的节点插入进去。
面试官:ls 要求按字典序怎么办?
候选人:我会在 ls 函数中获取当前目录的子节点的 keySet,然后用 sort 排序返回。
六、总结建议
这道题考察了面向对象设计、字符串处理、数据结构建模和边界处理,最重要的是你能否清晰表达每一步设计意图并应对 follow-up。
建议:
- 熟悉 Trie(字典树)的建模技巧
- 多练几次类似文件系统类题目(例如 LeetCode 上的 FileSystem 系列)
- 回答时保持有条理,尽量口述出 class、属性和函数签名结构
如果你也在准备Amazon、Meta、TikTok等大厂的算法与系统设计面试,却不清楚如何拆题和应对各种边界,欢迎添加微信,即可领取北美面试求职通关秘诀。我们也有代面试,面试辅助,OA代写等服务助您早日上岸~
