Leetcode 588. Design In-Memory File System
Asked at:
Uber
DESCRIPTION
Implement an in-memory file system that supports hierarchical directory structures with operations for creating directories (mkdir), listing contents (ls), creating/appending to files (addContentToFile), and reading file contents (readContentFromFile). The system must handle path parsing (e.g., /a/b/c), distinguish between files and directories, and return listings in lexicographical order. For example, calling mkdir("/a/b/c") should create nested directories, and addContentToFile("/a/b/file.txt", "hello") should create the file with content.
Input:
mkdir("/a/b/c") addContentToFile("/a/b/file.txt", "hello") ls("/a/b") readContentFromFile("/a/b/file.txt")
Output:
["c", "file.txt"] "hello"
Explanation: Create nested directories, add a file with content, list directory contents in lexicographical order, and read the file content
Constraints:
- All paths are absolute (start with /)
- Path components contain only alphanumeric characters, dots, and underscores
- File and directory names are case-sensitive
- ls on a file path returns a list containing only that filename
- ls on a directory returns all direct children in lexicographical order
- mkdir creates all intermediate directories if they don't exist
- addContentToFile creates the file and parent directories if they don't exist, otherwise appends content
Understanding the Problem
The core challenge is designing a tree structure that efficiently represents the file system hierarchy while distinguishing files from directories. You must implement path parsing to traverse from root to target nodes, handle implicit directory creation for operations like mkdir and addContentToFile, and maintain file contents as strings. The ls operation requires lexicographical sorting of children, which influences whether to use hash maps (requiring sorting) or tree maps (maintaining order). Correctly handling edge cases like listing a file path versus a directory path is critical.
Building Intuition
A naive approach uses nested hash maps where each node stores children in a Map<String, Node>, requiring sorting on every ls call. A better approach uses a trie-like tree where each node contains a TreeMap<String, Node> to maintain children in sorted order automatically, plus a boolean isFile flag and String content field. For example, path /a/b/c.txt creates nodes a → b → c.txt where c.txt has isFile=true and stores content.
File systems are fundamental to operating systems, databases, and cloud storage (S3, Google Drive). Understanding hierarchical data structures with mixed node types (files vs directories) applies to DOM trees, organizational charts, and package managers. Efficient path traversal and sorted listings are critical for autocomplete, file explorers, and search indexing.
Common Pitfalls
Implementation
Node Structure and Path Parsing
Define a Node class representing both files and directories with a TreeMap<String, Node> for children (maintains lexicographical order), a boolean isFile flag, and a StringBuilder content for file data. Implement a path parsing helper that splits paths by /, skips empty strings, and traverses/creates nodes as needed. For example, parsing /a/b/c returns ["a", "b", "c"], and traversal creates missing intermediate nodes. This foundation enables all file system operations.
class Node:def __init__(self):self.children = {} # dict maintains insertion order in Python 3.7+, use sorted() for lex orderself.is_file = Falseself.content = []def parse_path(path):return [part for part in path.split('/') if part]def traverse_or_create(root, parts, create=True):node = rootfor part in parts:if part not in node.children:if not create:return Nonenode.children[part] = Node()node = node.children[part]return node
Directory Operations (mkdir and ls)
Implement mkdir by parsing the path and creating all intermediate nodes with isFile=false. Implement ls by parsing the path to find the target node: if it's a file, return a list containing only the filename (last path component); if it's a directory, return all children keys from the TreeMap (already sorted). For example, ls("/a/b") on a directory returns ["c", "file.txt"], while ls("/a/b/file.txt") returns ["file.txt"]. These operations use the path parser from Section 1.
class FileSystem:def __init__(self):self.root = Node()def mkdir(self, path):parts = parse_path(path)traverse_or_create(self.root, parts, create=True)def ls(self, path):parts = parse_path(path)if not parts:return sorted(self.root.children.keys())node = traverse_or_create(self.root, parts, create=False)if node is None:return []if node.is_file:return [parts[-1]]return sorted(node.children.keys())
File Content Operations
Implement addContentToFile by parsing the path, creating intermediate directories and the target file node if missing (set isFile=true), then appending content to the node's StringBuilder. Implement readContentFromFile by parsing the path, navigating to the file node, and returning content.toString(). For example, calling addContentToFile("/a/b/c.txt", "hello") twice with different content appends both strings. These operations leverage the path parser and node structure from previous sections.
def addContentToFile(self, path, content):parts = parse_path(path)if not parts:returnnode = traverse_or_create(self.root, parts, create=True)node.is_file = Truenode.content.append(content)def readContentFromFile(self, path):parts = parse_path(path)if not parts:return ""node = traverse_or_create(self.root, parts, create=False)if node is None or not node.is_file:return ""return ''.join(node.content)
Complete File System Integration
Combine the Node structure, path parser, directory operations, and file operations into a unified FileSystem class with a root node initialized as a directory. The class exposes public methods mkdir, ls, addContentToFile, and readContentFromFile that coordinate the components. For example, instantiate FileSystem fs = new FileSystem(), then call fs.mkdir("/a/b") (uses Section 2), fs.addContentToFile("/a/b/file.txt", "data") (uses Section 3), and fs.ls("/a/b") (uses Section 2) to demonstrate the complete workflow from path parsing through operation execution.
# All components already integrated in previous sections# Demonstration of complete workflow:fs = FileSystem()fs.mkdir("/a/b/c")fs.addContentToFile("/a/b/file.txt", "hello")fs.addContentToFile("/a/b/file.txt", " world")print(fs.ls("/a/b")) # ['c', 'file.txt']print(fs.readContentFromFile("/a/b/file.txt")) # 'hello world'print(fs.ls("/a/b/file.txt")) # ['file.txt']
What We've Learned
- Pattern: Use trie-like trees with TreeMap for hierarchical data requiring sorted traversal and mixed node types
- Use Case: File systems, DOM manipulation, package dependency trees, organizational hierarchies
- Optimization: `TreeMap` maintains sorted order automatically, avoiding O(n log n) sorting on every query
- Design: Separate path parsing logic from operations for cleaner code and reusability across methods
Problems to Practice
Tries are tree-based data structures specifically designed for efficient prefix-based operations and hierarchical string storage, which directly parallels the file system's hierarchical path structure. This lesson covers the fundamental trie concepts needed to implement the file system's directory tree.
medium
This problem requires implementing core trie operations (insert, search, startsWith) which are essential building blocks for the file system design. The path parsing and directory traversal in the file system problem uses the same tree navigation patterns as trie operations.
medium
File system paths are essentially prefix-based hierarchies where each directory level represents a prefix. This problem reinforces the prefix matching and traversal skills needed to navigate and query the file system's tree structure efficiently.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early April, 2025
Uber
Senior
Early August, 2024
Uber
Mid-level
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.