In-Memory File System with Versioning

LeetCode 588: Design In-Memory File System is the standard problem matching this description, commonly discussed in Netflix-style design interviews using Trie and Hash Table (or TreeMap) for the directory hierarchy.[1][2]

Full Problem Statement

Design an in-memory file system that supports these operations on files and directories:

• mkdir(path: str) -> None: Make a new directory if it doesn't exist. Implicitly create parent directories.
• addContentToFile(filePath: str, content: str) -> None: If the file doesn't exist, create it with the content. If it exists, append the content (do not overwrite).
• ls(path: str) -> List[str]: List contents of the directory at path in lexicographical order. If path is a file, return [path].
• readContentFromFile(filePath: str) -> str: Read and return the entire concatenated content of the file.[4][1]

Paths use Unix-style format (e.g., /a/b/c.txt), starting with / and using / as separator. Root is /.[2]

Key Examples

` FileSystem fs = new FileSystem();

fs.mkdir("/a/b/c"); // Creates directories /a, /a/b, /a/b/c fs.addContentToFile("/a/b/c/file1.txt", "hello"); // Creates /a/b/c/file1.txt with "hello" fs.ls("/a/b"); // Returns ["c"] (directory) fs.ls("/a/b/c"); // Returns ["file1.txt"] fs.readContentFromFile("/a/b/c/file1.txt"); // Returns "hello" fs.addContentToFile("/a/b/c/file1.txt", "world"); // Appends to file fs.readContentFromFile("/a/b/c/file1.txt"); // Returns "helloworld" fs.ls("/a/b/c"); // Returns ["file1.txt"] (still just the file) Another case:ls("/a/b/c/file1.txt")returns["/a/b/c/file1.txt"]` since it's a file.[7][1]

Constraints

• 1 <= path.length <= 200
• 1 <= filePath.length <= 200
• 1 <= content.length <= 200
• Paths contain only English letters, digits, /, ., _ (no spaces)
• 1 <= number of calls <= 10^4
• ls must return sorted list
• Max path depth not specified, but typically small (~100 segments)
• Total content size per file not bounded, but in-memory so practical limits apply[1][4]

Design Notes (Tags: Design, Trie, Hash Table)

Use a Trie where each node has:

• children: dict[str, Node] (HashMap; sort keys for ls)
• isFile: bool
• content: list[str] (append chunks, concat on read)

Traversal splits path by /, creates nodes lazily. Time: O(D) per op where D is path depth.[2][1]