588. Design In-Memory File System
Asked at Uber, Snowflake
Difficulty
Hard
Time
O(L) per operation, plus O(k log
Space
O(total characters across all pa
Pattern
Hash Table
Companies
2
Problem
Design a class that behaves like a small file system kept in memory. Paths look like Unix paths: they start with / and use / to separate names, for example /a/b/c.
You must support four operations. ls(path) returns the names inside a directory, sorted in lexicographic (dictionary) order. If path points to a file instead, it returns a list holding just that file's name. mkdir(path) creates a directory, and also creates any missing directories along the way. addContentToFile(filePath, content) creates the file if it is missing, or appends content to the end if the file already exists. readContentFromFile(filePath) returns the full text stored in that file.
A good model is a tree: each node is either a directory (it has children) or a file (it has text). Split a path on / to get its parts, then walk down the tree one part at a time. Directories are created on the way down when they are missing. All inputs are valid, so you never need to list or read something that does not exist.
The file system as a tree
Constraints
- ●
1 <= path.length, filePath.length <= 100 - ●
path and filePath are absolute paths starting with '/', and they do not end with '/' unless the path is just "/" - ●
Directory and file names contain only lowercase letters - ●
The same name never appears twice in the same directory - ●
All operations receive valid parameters; you never list or read a path that does not exist - ●
The parent directory of a file in addContentToFile always exists - ●
1 <= content.length <= 50 - ●
At most 300 calls are made to ls, mkdir, addContentToFile and readContentFromFile
Examples
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]][null, [], null, null, ["a"], "hello"]mkdir("/a/b"); addContentToFile("/a/b/x", "hi"); addContentToFile("/a/b/x", "!"); readContentFromFile("/a/b/x")"hi!"mkdir("/z"); mkdir("/a"); ls("/")["a", "z"]Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Uber | Hard | View all Uber questions → |
| Snowflake | Hard | View all Snowflake 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).
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).
Walk the path, create what is missing
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
O(L) per operation, plus O(k log timeclass 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 runs in O(L) per operation, plus O(k log time and O(total characters across all pa space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Design In-Memory File System?
Design In-Memory File System is asked at Uber, Snowflake. 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.