In-Memory File System: Add cd and Relative Path Support

Implement an in-memory file system as a class, in stages. The early stages build a tree of directories and files addressed by absolute paths. The final stage adds a current working directory with a `cd` command and requires every operation to accept relative paths as well. That final stage is where the difficulty lies: path handling written for absolute paths has to change without breaking what already works, and relative-path bugs are easy to introduce. The earlier stages are not specified in detail here, so Part 1 states an assumed baseline API. If your interviewer gives a different one, keep its semantics and apply Part 2 to it. Part 2 is the extension the question builds toward. ### Clarifying Questions - Are file contents plain strings, and does writing to an existing file overwrite it or append to it? - Should `ls` return names in sorted order, and what should it return when the path is a file? - How should errors be reported: exceptions, return values, or silently ignored? - Can paths contain repeated slashes or a trailing slash, or are inputs always well formed? ### Part 1 — Baseline file system over absolute paths Implement this API. Every path is absolute: it starts with `/`, and `/` alone is the root. ```python class FileSystem: def mkdir(self, path: str) -> None: ... def write_file(self, path: str, content: str) -> None: ... def read_file(self, path: str) -> str: ... def ls(self, path: str) -> list[str]: ... ``` - `mkdir` creates the directory and any missing parent directories. It is an error if some component of the path is an existing file. - `write_file` creates the file or overwrites its content. Its parent directory must already exist, and the path must not name a directory. - `read_file` returns a file's content; the path must name an existing file. - `ls` returns the names of a directory's entries in sorted order, or a one-element list with the file's own name when the path names a file. ```hint One tree, one walk Decide how directories and files differ in your representation, and write the walk from the root to a node once, so that every method reuses it instead of splitting paths itself. ``` #### What This Part Should Cover - A tree in which directories map names to children and files hold content - A single traversal helper shared by all methods - Defined behavior for missing paths, a file used as a directory, and the root itself ### Part 2 — Add `cd` and relative paths Add `cd(path)`, which changes the current working directory, and a `pwd()` helper that returns the current directory as an absolute path, so the behavior can be tested. The file system starts in `/`. From now on every method, including `cd` itself, must accept both absolute paths and relative paths such as `docs/a.txt`, `./docs` or `../shared/b.txt`, which are resolved against the current directory. ```hint Count the places that read a path Before writing `cd`, find every place in your Part 1 code that interprets a path string. Relative paths become a small change only if there is exactly one such place. ``` ```hint Test the resolver on its own Write a handful of input and expected-output pairs for path resolution alone, covering `.`, `..`, repeated slashes and attempts to go above the root, before running them through the other methods. ``` #### Clarifying Questions for this Part - What does `..` mean at the root: an error, or stay at the root as a Unix shell does? - If `cd` targets a missing directory or a file, should it fail and leave the current directory unchanged? - Must a path like `missing/../docs` fail because `missing` does not exist, or may `..` be resolved purely by text? #### What This Part Should Cover - One resolution function that turns any absolute or relative input into a canonical path, used by every method - Correct handling of `.`, `..` (including at the root), empty components and trailing slashes - `cd` validates its target before changing any state - Tests that send relative paths through every operation, not only through `cd` ### What a Strong Answer Covers - Working code for both parts, with Part 1 structured so that Part 2 is a small, local change - Path parsing kept separate from tree traversal - Error behavior that is consistent across all methods - A clear explanation of each helper's purpose and design when the interviewer asks mid-implementation - Systematic debugging when a relative-path test fails: isolate the resolver, test it alone, then rerun the operation-level cases - Time complexity in terms of path length and directory size ### Follow-up Questions - Add `rm`. What should happen to a current directory that gets deleted? - Several users share one file system, each with their own current directory. Where does the current directory live now? - Symbolic links are added. Why does resolving `..` purely by text become wrong, and how would you resolve paths instead? - How would you add `~` for a home directory, or a command that returns to the previous directory?