Low-Level Design of an In-Memory File System with mkdir and ls

Design a basic file system that supports two operations, `mkdir` and `ls`. The interviewer cares about the design and the approach rather than complete running code: draw an entity/class diagram and explain it. The discussion must cover the File and Directory entities, the directory hierarchy, how parent-child relationships are represented, how `mkdir` creates a directory, how `ls` traverses and lists contents, and the relationships between the entities and classes. Assume an in-memory file system in a single process, with paths written as `/`-separated strings that start at the root `/`. ### Clarifying Questions - Does `mkdir` create missing intermediate directories, like `mkdir -p`, or fail when the parent does not exist? What if the directory already exists? - What should `ls` return for a directory, for a file, and for a path that does not exist, and in what order? - Can a file and a directory have the same name inside the same directory? - Are relative paths, `.` and `..` in scope? - Will several threads call the file system at the same time? ### Part 1 — Entities, hierarchy and relationships Identify the entities and classes, draw the class diagram, and explain how the directory hierarchy and the parent-child relationships are represented. ```hint Shared and distinct List what a file and a directory have in common and what only a directory has. Let that decide whether they share a base type and where the children are stored. ``` #### What This Part Should Cover - The File and Directory entities and what they share - How the tree and its parent-child links are stored, in both directions - The kind of each relationship (inheritance, composition, association), and which class owns path handling ### Part 2 — mkdir Explain, step by step, how `mkdir(path)` creates a directory, including its error cases. ```hint One component at a time Walk the path from the root one component at a time, and decide what happens at each step when the component is missing, is a directory, or is a file. ``` #### What This Part Should Cover - Path parsing and resolution from the root - Behavior for missing parents, an existing directory, and path components that are files - The cost of one call in terms of path length ### Part 3 — ls Explain how `ls(path)` finds its target and lists the contents. ```hint Two kinds of target `ls` on a directory and `ls` on a file behave differently. Decide where that difference lives in your classes, and how the order of the output is guaranteed. ``` #### What This Part Should Cover - Resolving the target, and the directory and file cases - The output order and what it costs - Errors for missing paths ### What a Strong Answer Covers - A clean diagram whose classes match the entities discussed - Clear, stated semantics for both operations before going into detail - Data structures chosen for lookup by name and for listing - Room to add operations such as `rm`, `mv` and file content without a redesign - Edge cases and, if raised, thread safety ### Follow-up Questions - Add `mv` for directories. Which parts of your design make it cheap or expensive? - Add file content with a `cat` operation. What changes? - How would you support a directory with millions of entries that `ls` must page through? - How would you persist this file system so it survives a restart?