DSA problem
Design In-Memory File System
Design an in-memory file system that supports the four operations of a minimal POSIX shell: ls(path), mkdir(path), addContentToFile(filePath, content), and readContentFromFile(filePath). ls returns the sorted contents of a directory or the file name itself if the path is a file. mkdir creates every missing intermediate directory along the path. The file APIs create the file if it does not yet exist and append-or-read its raw text content.
The natural representation is a tree of nodes where each node is either a directory or a file. A directory holds a map from child name to child node, sorted lexicographically on read. A file holds a string of accumulated content. Because operations are path-based, every method first splits the input path on / into parts, then walks from the root creating intermediate directories on demand.
The single helper that ties everything together is walk(parts, create): starting at the root, descend one part at a time, optionally creating a new directory node if the part is missing. mkdir calls walk(parts, create=True) and ignores the return value. addContentToFile calls walk(parts[:-1], create=True) to get the parent directory, then either fetches the existing file child or creates a new file node and appends the content. readContentFromFile walks to the file node and returns its content.
ls is the only operation that distinguishes between files and directories. If the resolved node is a file, return the single-element list containing the last path component (the file name). If it is a directory, return the sorted list of its child names — which can contain both file and directory names without distinction. The whole design is essentially a hash-trie with two node types and a recursive splitter — small in code, broad in functionality.
Examples
ls("/"); mkdir("/a/b/c"); addContentToFile("/a/b/c/d", "hello"); ls("/")[]; []; []; ["a"]addContentToFile("/a/b/c/d","hello"); ls("/a/b/c"); readContentFromFile("/a/b/c/d")["d"]; "hello"addContentToFile("/x","aa"); addContentToFile("/x","bb"); readContentFromFile("/x")"aabb"Constraints
- 1 <= path.length, filePath.length <= 100
- path and filePath are absolute paths which begin with '/' and do not end with '/' except that the path is just '/'.
- 1 <= content.length <= 50
- At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile.
- You can assume different operations will be in a valid order — no listing a file that does not exist, etc.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.