# Implement an In-Memory File System Design and implement an in-memory hierarchical file system. It starts with an empty root directory and a current working directory of `/`. Paths may be absolute or relative and may contain `.` or `..`. Names are non-empty strings without `/`. ### Clarifying Questions to Ask - Should `mkdir` create missing parents, and may `touch` create a file that already exists? - Is `rmdir` allowed on a non-empty directory? - What should `ls` return for a file path versus a directory path? - How should attempts to traverse above root behave? ### Solving Hints Keep path normalization separate from mutation. Define node invariants and method failure behavior before writing individual operations. ### Part 1: Creation and Listing Implement `mkdir(path)`, `touch(path)`, and `ls(path=".")`. Assume `mkdir` creates one directory whose parent must exist, `touch` creates an empty file whose parent must exist, and `ls` returns sorted child names for a directory or the file's own name for a file. #### What This Part Should Cover - Tree representation, path resolution, type checks, duplicate-name behavior, and deterministic listing. ### Part 2: Removal Implement `rm(path)` for files and `rmdir(path)` for empty directories. Root may not be removed. Both methods should reject a missing path or the wrong node type. #### What This Part Should Cover - Parent lookup, safe mutation, non-empty-directory checks, and current-directory edge cases. ### Part 3: Changing Directory Implement `cd(path)`, updating the current working directory only when the fully resolved destination exists and is a directory. #### What This Part Should Cover - Absolute and relative paths, `.`, `..`, repeated separators, atomic failure, and canonical current-directory state. ### What a Strong Answer Covers - A coherent node model with explicit file/directory invariants. - One reusable resolver instead of duplicated path parsing in every operation. - Defined error semantics and no partial mutation after a failed operation. - Correct root, collision, empty-directory, and relative-path behavior. - Complexity and a test plan covering sequences of dependent operations. ### Follow-up Questions - How would you add file contents and `mv` without violating tree invariants? - How would symbolic links change path resolution and cycle handling? - What synchronization would be needed for concurrent callers?