Design In-Memory File System
Hard · Design · Design · Trie · Hash Table · String · Sorting
Problem
Build a file system that lives entirely in memory. Paths are absolute, like /a/b/c, and / is the root.
- FileSystem() starts with an empty root directory.
- ls(path) if path is a file, returns a list holding just that file's name. If it is a directory, returns the names of everything directly inside it, files and directories together. Either way the list is in lexicographic order.
- mkdir(path) creates the directory at path, along with any missing directories on the way to it.
- addContentToFile(filePath, content) creates the file with content if it does not exist yet, and otherwise appends content to the end of what it already holds.
- readContentFromFile(filePath) returns everything the file holds.
Every call is valid: you are never asked to list or read a path that does not exist, mkdir never names an existing directory, and a new file's parent directory already exists.
Your tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: ls("/"), mkdir("/a/b/c"), addContentToFile("/a/b/c/d", "hello"), ls("/"), readContentFromFile("/a/b/c/d")
Output: [], then ["a"], then "hello"The root starts empty. mkdir builds a, b and c in one call, and d becomes a file inside c. Listing the root shows only a, the one entry directly inside it.
Input: mkdir("/docs"), addContentToFile("/docs/todo", "buy"), addContentToFile("/docs/todo", " milk"), ls("/docs/todo"), ls("/docs"), readContentFromFile("/docs/todo")
Output: ["todo"], then ["todo"], then "buy milk"The second add appends to the existing file. Listing a file path returns just its own name.
Constraints
- 1 <= path.length, filePath.length <= 100
- Paths start with "/" and do not end with "/", except the root "/" itself
- Names are lowercase letters; no directory holds two entries with the same name
- 1 <= content.length <= 50
- At most 300 calls in total
- Consider what changes if one directory holds a million files, or one file grows to gigabytes
Approaches
- Hash map from full path to directory entries — time O(L·d) mkdir, O(L) add and read, O(L + k log k) ls, space O(directories · L + total content)
Follow-up
What if one directory holds a million entries and is listed constantly, or a file grows by millions of small appends? Sorting on every ls and rebuilding a string on every append both become the bottleneck; keep children in a sorted structure and content as a list of chunks.
Related problems
Start free on Cariara · Coding problems · System design studio
