Tree-Backed In-Memory File System with ls, mkdir, Append and Read

Implement a file system that keeps directories and files in memory and supports four operations: listing a path, creating a directory, appending content to a file, and reading a file back. ```python fs = FileSystem() fs.ls("/") # [] fs.mkdir("/a/b/c") fs.add_content_to_file("/a/b/c/d", "hello") fs.ls("/") # ["a"] fs.read_content_from_file("/a/b/c/d") # "hello" fs.add_content_to_file("/a/b/c/d", " world") fs.read_content_from_file("/a/b/c/d") # "hello world" fs.ls("/a/b/c/d") # ["d"] ``` ```hint Paths are walks Think about which structure lets every operation follow a path one name at a time. ``` ```hint Where the cost goes Consider which operation pays for sorting, and how appends to a file that keeps growing stay cheap. ``` ### Constraints and Clarifications - `ls(path)`: if `path` is a file, return a list holding only the file's name. If it is a directory, return the names of the files and directories directly inside it, in lexicographic order. - `mkdir(path)`: create the directory, along with any missing parent directories. Directories that already exist are left as they are. - `add_content_to_file(path, content)`: if the file does not exist, create it, along with any missing parent directories, holding `content`; otherwise append `content` to the end of the file. - `read_content_from_file(path)`: return the file's whole content. - Paths are absolute: they start with `/`, have no trailing slash except the root `/` itself, and every name consists of lowercase letters and digits. ### Clarifying Questions - Should invalid calls, such as reading a missing file or creating a directory where a file exists, raise an error, or may I assume every call is valid? - Is `ls` called much more often than `mkdir` and file creation? That decides where the sorting cost should go. - How large can files get, and are appends small and frequent? - Is the file system used by several threads at once? ### What a Strong Answer Covers - A tree of directory nodes keyed by name, with files as leaves that hold their content - Correct `ls` for a file path versus a directory path, with sorted output - Path parsing that handles the root and creates missing directories - The cost of each operation in terms of path length, directory size and content size - Explicit handling, or an explicit assumption, for invalid calls ### Follow-up Questions - Add `rm` for files and directories, and `mv` to move a subtree. What changes? - Report the total size of any directory in constant time after every update. - Several threads use the file system at once. Where do the locks go? - Files grow to gigabytes. How do you store them and read them back?