Design In-Memory File System
Asked at Uber
Problem
Design an in-memory file system that supports ls, mkdir, addContentToFile, and readContentFromFile. Paths are Unix-style (/ separated). This tests your ability to model hierarchical structures with tries or nested hash maps.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | Hard | View all Uber questions → |
How to Think About It
Brute force: use a single hash map with full paths as keys. That works for read/write but makes ls and mkdir awkward because you need to enumerate prefixes. Not elegant.
Key insight: model the file system as a tree. Each node is either a directory (children) or a file (content). Use a trie-like structure where each level of the trie corresponds to a path component.
The trie approach: each node has a children map (name → node), a boolean is_file flag, and content (for files). ls lists children of a directory. mkdir creates intermediate directories. addContentToFile navigates to the file node, creates it if needed, appends content.
Parsing paths: split by "/". Skip empty strings from leading slash. For example, "/a/b/c" splits into ["a", "b", "c"]. Navigate the tree node by node, creating directories as needed.
Edge cases: mkdir on existing path (do nothing), addContent to existing file (append), ls on file path (return filename), root "/" ls (return children of root), nested mkdir (create all intermediate dirs).
Visual walkthrough:
mkdir("/a/b/c"): root → a (dir) → b (dir) → c (dir)
ls("/") → ["a"]
addContentToFile("/a/b/c/hello.py", "print(123)"):
Navigate root→a→b→c. c has no child "hello.py", create it as file.
Set content = "print(123)".
ls("/a/b/c") → ["hello.py"]
readContentFromFile("/a/b/c/hello.py") → "print(123)"
Optimal Approach
class TrieNode:
children = {} # name -> TrieNode
is_file = False
content = ""
ls(path):
Split path by "/". Navigate to the target node.
If node is a file, return its name.
If node is a directory, return sorted list of its children names.
mkdir(path):
Split path by "/". Navigate from root, creating intermediate directories.
addContentToFile(filePath, content):
Split path by "/". Navigate to the file node, creating it if needed.
Set is_file = True. Append content.
readContentFromFile(filePath):
Split path by "/". Navigate to the file node. Return content.
Time: O(L) per operation where L is the path length (number of components). Space: O(total characters across all paths + total content).
What Trips People Up in Real Interviews
Using a flat hash map with full paths as keys. This works for file operations but makes ls() require filtering all keys by prefix - O(n) instead of O(1) for directory listing.
Forgetting to handle the root directory. The path "/" splits into empty parts after filtering. The root node is the starting point and its children are the top-level entries.
Not sorting the ls output. The problem requires returning results in lexicographic order. Always sort the children names before returning.
Confusing mkdir with addContentToFile. mkdir creates directory nodes (no content, not a file). addContentToFile creates or appends to a file node. They create different types of nodes.
Not appending content to existing files. When addContentToFile is called on an existing file, concatenate the new content to the existing content, don't overwrite it.
Solution Code
class TrieNode:
def __init__(self):
self.children = {}
self.is_file = False
self.content = ""
class FileSystem:
def __init__(self):
self.root = TrieNode()
def _navigate(self, path):
node = self.root
parts = [p for p in path.split("/") if p]
for part in parts:
if part not in node.children:
node.children[part] = TrieNode()
node = node.children[part]
return node
def ls(self, path):
node = self._navigate(path)
if node.is_file:
return [path.split("/")[-1]]
return sorted(node.children.keys())
def mkdir(self, path):
self._navigate(path)
def addContentToFile(self, filePath, content):
node = self._navigate(filePath)
node.is_file = True
node.content += content
def readContentFromFile(self, filePath):
return self._navigate(filePath).contentFrequently Asked Questions
What is the Design In-Memory File System problem?
Design an in-memory file system that supports ls, mkdir, addContentToFile, and readContentFromFile. Paths are Unix-style (/ separated). This tests your ability to model hierarchical structures with tries or nested hash maps.
How do you solve Design In-Memory File System?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design In-Memory File System?
Design In-Memory File System is asked at Uber. It is a hard difficulty problem.
What are common mistakes on Design In-Memory File System?
- Using a flat hash map with full paths as keys. This works for file operations but makes ls() require filtering all keys by prefix - `O(n)` instead of `O(1)` for directory listing.
- Forgetting to handle the root directory. The path "/" splits into empty parts after filtering. The root node is the starting point and its children are the top-level entries.
- Not sorting the ls output. The problem requires returning results in lexicographic order. Always sort the children names before returning.
- Confusing mkdir with addContentToFile. mkdir creates directory nodes (no content, not a file). addContentToFile creates or appends to a file node. They create different types of nodes.
- Not appending content to existing files. When addContentToFile is called on an existing file, concatenate the new content to the existing content, don't overwrite it.