Design In-Memory File System - Video Solutions
DESIGN IN-MEMORY FILE SYSTEM | LEETCODE # 588 | PYTHON SOLUTION
Design In-Memory File System - Video Solution
Watch 8 video solutions for Design In-Memory File System, a hard level problem involving Hash Table, String, Design. This walkthrough by Cracking FAANG has 17,341 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Design a data structure that simulates an in-memory file system.
Implement the FileSystem class:
FileSystem()Initializes the object of the system.List<String> ls(String path)- If
pathis a file path, returns a list that only contains this file's name. - If
pathis a directory path, returns the list of file and directory names in this directory.
- If
void mkdir(String path)Makes a new directory according to the givenpath. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well.void addContentToFile(String filePath, String content)- If
filePathdoes not exist, creates that file containing givencontent. - If
filePathalready exists, appends the givencontentto original content.
- If
String readContentFromFile(String filePath)Returns the content in the file atfilePath.
Example 1:
Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]
Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/"); // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/"); // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"
Constraints:
1 <= path.length, filePath.length <= 100pathandfilePathare absolute paths which begin with'/'and do not end with'/'except that the path is just"/".- You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
- You can assume that all operations will be passed valid parameters, and users will not attempt to retrieve file content or list a directory or file that does not exist.
- You can assume that the parent directory for the file in
addContentToFilewill exist. 1 <= content.length <= 50- At most
300calls will be made tols,mkdir,addContentToFile, andreadContentFromFile.
Approach Overview
Problem Overview: Design a file system that runs entirely in memory. You must support directory listing (ls), creating directories (mkdir), adding content to files (addContentToFile), and reading file content (readContentFromFile) while maintaining lexicographically sorted directory listings.
Approach 1: HashMap-Based Directory Tree (Trie Structure) (Time: O(p + k log k), Space: O(n))
Treat the file system as a tree where each directory is a node and edges represent path segments. Split the path by / and traverse the tree one segment at a time. Each node stores a hash map of children (name → node), a flag indicating whether it is a file, and a string builder for file content. Directory operations like mkdir simply create missing nodes during traversal. For ls, return the file name if the path is a file, otherwise collect child keys and sort them lexicographically. Traversal takes O(p) where p is the number of path components, and sorting the directory listing costs O(k log k) where k is the number of entries.
This approach behaves like a simplified Trie where each level represents a folder name instead of a character. Using a hash table for children ensures constant-time lookup during traversal. File content appends are efficient because you only modify the node representing the file.
Approach 2: Trie with File Metadata and Lazy Sorting (Time: O(p) average, O(k log k) for listing, Space: O(n))
Another implementation models directories and files explicitly with a Trie node class containing metadata such as isFile, content, and a children map. Path traversal works the same way: split the path, iterate through segments, and create nodes when necessary. Instead of sorting every time ls is called, some implementations maintain directory entries in sorted containers or cache sorted results when modifications occur. This reduces repeated sorting overhead when directories are listed frequently.
The Trie structure naturally represents hierarchical file paths, making operations predictable and easy to reason about. String parsing of paths relies on standard string operations, and node traversal handles all file system operations consistently.
Recommended for interviews: The HashMap-backed Trie is the expected solution. It directly models the hierarchical file system and keeps each operation near O(p). Interviewers mainly check whether you design a clean node structure, correctly parse paths, and handle the lexicographic ordering requirement for ls. A simpler map-only idea can show understanding, but the Trie-style directory tree demonstrates solid system design thinking.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Directory Tree (Trie) | O(p + k log k) | O(n) | General case; simple design with fast path traversal and flexible directory growth |
| Trie with Cached/Ordered Children | O(p) average, O(k log k) for listing | O(n) | When directories are listed frequently and sorting repeatedly becomes expensive |