Facebook Pixel

588. Design In-Memory File System 🔒

HardDesignTrieHash TableStringSorting
Leetcode Link

Problem Description

This problem asks you to design an in-memory file system data structure that supports basic file and directory operations.

The file system should support four main operations:

  1. ls(path): List the contents at a given path

    • If the path points to a file, return a list containing only that file's name
    • If the path points to a directory, return all files and subdirectories within it in lexicographic (alphabetical) order

  2. mkdir(path): Create a new directory

    • The path given will not already exist
    • If intermediate directories in the path don't exist, create them automatically (similar to mkdir -p in Unix)

  3. addContentToFile(filePath, content): Add content to a file

    • If the file doesn't exist, create it with the given content
    • If the file already exists, append the new content to the existing content

  4. readContentFromFile(filePath): Read and return all content from a file

The solution uses a Trie (prefix tree) data structure to represent the file system hierarchy. Each node in the Trie can represent either a file or a directory:

  • Directories contain children (other files or directories)
  • Files contain content and have a flag marking them as files

The path parsing works by splitting paths on / characters. For example, /a/b/c would be split into components ['', 'a', 'b', 'c'], where the empty string represents the root directory.

Key implementation details:

  • The insert method navigates through the path components, creating nodes as needed
  • The search method traverses the Trie to find a specific file or directory
  • File content is stored as a list of strings that get concatenated when read
  • Directory listings are automatically sorted to maintain lexicographic order
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

When thinking about how to represent a file system in memory, we need a hierarchical structure that can efficiently store both files and directories. The natural choice is a tree structure since file systems are inherently tree-like - directories can contain other directories and files, forming a parent-child relationship.

A Trie (prefix tree) is particularly well-suited for this problem because:

  1. Path components are naturally shared: Multiple paths like /a/b/c and /a/b/d share the common prefix /a/b. A Trie efficiently stores these shared prefixes without duplication.

  2. Easy navigation: We can traverse from root to any file/directory by following the path components one by one, similar to how we navigate through actual file systems.

  3. Dynamic structure: We can easily add new directories and files at any level without restructuring the entire tree.

The key insight is to treat each path component (the parts between /) as a step in our Trie traversal. For instance, the path /home/user/document.txt becomes a series of steps: root → home → user → document.txt.

To distinguish between files and directories, we use a boolean flag isFile. This is necessary because:

  • Files can have content but cannot have children
  • Directories can have children but don't have content
  • When we ls a path, we need different behavior for files (return just the filename) vs directories (return all children)

For handling file content, using a list of strings rather than a single string is clever because it makes appending new content efficient - we just add to the list rather than creating new string objects each time. When reading, we simply join all the pieces together.

The sorting requirement for ls is handled by using Python's sorted() function on the dictionary keys, which gives us lexicographic ordering automatically.

Learn more about Trie and Sorting patterns.

Solution Approach

The solution implements a file system using a Trie data structure with two main classes: Trie for the tree nodes and FileSystem as the main interface.

Trie Node Structure

Each [Trie](/problems/trie_intro) node contains:

  • name: Stores the filename (only for files)
  • isFile: Boolean flag to distinguish files from directories
  • content: List of strings to store file content
  • children: Dictionary mapping child names to their Trie nodes

Core Methods Implementation

1. Insert Method

def insert(self, path, isFile):
    node = self
    ps = path.split('/')
    for p in ps[1:]:  # Skip empty string from leading '/'
        if p not in node.children:
            node.children[p] = [Trie](/problems/trie_intro)()
        node = node.children[p]
    node.isFile = isFile
    if isFile:
        node.name = ps[-1]
    return node
  • Splits the path by / and traverses/creates nodes as needed
  • Marks the final node as file or directory
  • Returns the final node for further operations

2. Search Method

def search(self, path):
    node = self
    if path == '/':
        return node
    ps = path.split('/')
    for p in ps[1:]:
        if p not in node.children:
            return None
        node = node.children[p]
    return node
  • Handles root directory as special case
  • Traverses the tree following path components
  • Returns None if path doesn't exist

FileSystem Operations

1. ls Operation

def ls(self, path: str) -> List[str]:
    node = self.root.search(path)
    if node is None:
        return []
    if node.isFile:
        return [node.name]
    return sorted(node.children.keys())
  • Searches for the node at given path
  • For files: returns single-element list with filename
  • For directories: returns sorted list of all children names

2. mkdir Operation

def mkdir(self, path: str) -> None:
    self.root.insert(path, False)
  • Simply inserts the path with isFile=False
  • The insert method handles creating intermediate directories automatically

3. addContentToFile Operation

def addContentToFile(self, filePath: str, content: str) -> None:
    node = self.root.insert(filePath, True)
    node.content.append(content)
  • Inserts the path as a file (isFile=True)
  • Appends content to the node's content list
  • Works for both new files and existing files

4. readContentFromFile Operation

def readContentFromFile(self, filePath: str) -> str:
    node = self.root.search(filePath)
    return ''.join(node.content)
  • Finds the file node
  • Joins all content pieces into a single string

Time Complexity Analysis

  • ls: O(p + n log n) where p is path length and n is number of children (due to sorting)
  • mkdir: O(p) where p is path length
  • addContentToFile: O(p) for path traversal
  • readContentFromFile: O(p + c) where c is total content length

Space Complexity

O(total number of nodes + total content size) for storing the entire file system structure and file contents.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a sequence of operations to see how the file system works:

Initial State: Empty file system with just a root node /

Step 1: mkdir("/a/b/c")

  • Path splits into: ['', 'a', 'b', 'c']
  • Starting from root, we traverse/create:
    • Root → create child 'a' → create child 'b' → create child 'c'
  • Each node is marked as directory (isFile=False)

Tree structure:

/
└── a/
    └── b/
        └── c/

Step 2: addContentToFile("/a/b/file1.txt", "Hello")

  • Path splits into: ['', 'a', 'b', 'file1.txt']
  • Traverse: Root → 'a' → 'b' → create 'file1.txt'
  • Mark 'file1.txt' as file (isFile=True)
  • Set name = "file1.txt" and append "Hello" to content list

Tree structure:

/
└── a/
    └── b/
        ├── c/
        └── file1.txt (content: ["Hello"])

Step 3: ls("/a/b")

  • Search for node at path /a/b
  • Node exists and isFile=False, so return sorted children keys
  • Children are: {'c': Trie(), 'file1.txt': Trie()}
  • Return: ["c", "file1.txt"] (already in alphabetical order)

Step 4: addContentToFile("/a/b/file1.txt", " World")

  • Path already exists as a file
  • Append " World" to existing content list
  • Content becomes: ["Hello", " World"]

Step 5: readContentFromFile("/a/b/file1.txt")

  • Search for node at path /a/b/file1.txt
  • Join content list: "Hello" + " World" = "Hello World"
  • Return: "Hello World"

Step 6: ls("/a/b/file1.txt")

  • Search finds the node
  • Node has isFile=True, so return just the filename
  • Return: ["file1.txt"]

This example demonstrates:

  • How directories are created recursively
  • File content is stored as a list for efficient appending
  • The ls command behaves differently for files vs directories
  • The Trie structure efficiently shares common path prefixes (here /a/b is shared between the directory c and file1.txt)

Solution Implementation

1from typing import List, Optional
2
3
4class TrieNode:
5    """
6    Trie node representing a file or directory in the file system.
7    """
8  
9    def __init__(self):
10        # Name of the file (only used for files, not directories)
11        self.name: Optional[str] = None
12        # Flag to indicate if this node represents a file
13        self.is_file: bool = False
14        # Content of the file (list of strings that will be concatenated)
15        self.content: List[str] = []
16        # Children nodes (subdirectories or files)
17        self.children: dict[str, 'TrieNode'] = {}
18
19    def insert(self, path: str, is_file: bool) -> 'TrieNode':
20        """
21        Insert a new file or directory into the trie.
22      
23        Args:
24            path: The full path to insert (e.g., "/a/b/c")
25            is_file: True if inserting a file, False for directory
26          
27        Returns:
28            The node representing the inserted path
29        """
30        node = self
31        # Split path by '/' and skip the empty string from leading '/'
32        path_components = path.split('/')
33      
34        # Traverse/create the path in the trie
35        for component in path_components[1:]:
36            if component not in node.children:
37                node.children[component] = TrieNode()
38            node = node.children[component]
39      
40        # Mark as file if needed and store the file name
41        node.is_file = is_file
42        if is_file:
43            node.name = path_components[-1]
44      
45        return node
46
47    def search(self, path: str) -> Optional['TrieNode']:
48        """
49        Search for a node at the given path.
50      
51        Args:
52            path: The full path to search for
53          
54        Returns:
55            The node at the path, or None if not found
56        """
57        node = self
58      
59        # Handle root directory case
60        if path == '/':
61            return node
62      
63        # Split path and traverse the trie
64        path_components = path.split('/')
65        for component in path_components[1:]:
66            if component not in node.children:
67                return None
68            node = node.children[component]
69      
70        return node
71
72
73class FileSystem:
74    """
75    In-memory file system implementation using a Trie data structure.
76    """
77  
78    def __init__(self):
79        # Initialize root directory
80        self.root = TrieNode()
81
82    def ls(self, path: str) -> List[str]:
83        """
84        List the contents of a directory or return file name if it's a file.
85      
86        Args:
87            path: The path to list
88          
89        Returns:
90            List of file/directory names in sorted order, or single file name
91        """
92        node = self.root.search(path)
93      
94        # Path doesn't exist
95        if node is None:
96            return []
97      
98        # If it's a file, return just the file name
99        if node.is_file:
100            return [node.name]
101      
102        # If it's a directory, return sorted list of children
103        return sorted(node.children.keys())
104
105    def mkdir(self, path: str) -> None:
106        """
107        Create a new directory path (including intermediate directories).
108      
109        Args:
110            path: The directory path to create
111        """
112        self.root.insert(path, is_file=False)
113
114    def addContentToFile(self, filePath: str, content: str) -> None:
115        """
116        Add content to a file. Creates the file if it doesn't exist.
117      
118        Args:
119            filePath: The path to the file
120            content: The content to append to the file
121        """
122        node = self.root.insert(filePath, is_file=True)
123        node.content.append(content)
124
125    def readContentFromFile(self, filePath: str) -> str:
126        """
127        Read all content from a file.
128      
129        Args:
130            filePath: The path to the file to read
131          
132        Returns:
133            The concatenated content of the file
134        """
135        node = self.root.search(filePath)
136        return ''.join(node.content)
137
138
139# Your FileSystem object will be instantiated and called as such:
140# obj = FileSystem()
141# param_1 = obj.ls(path)
142# obj.mkdir(path)
143# obj.addContentToFile(filePath, content)
144# param_4 = obj.readContentFromFile(filePath)
145
1/**
2 * Trie node structure for representing file system hierarchy
3 */
4class Trie {
5    String name;                                    // File name (only used for files)
6    boolean isFile;                                 // Flag to indicate if this node represents a file
7    StringBuilder content = new StringBuilder();    // File content (only used for files)
8    Map<String, Trie> children = new HashMap<>();  // Map of child directories/files
9  
10    /**
11     * Inserts a new path into the trie structure
12     * @param path The absolute path to insert
13     * @param isFile Whether the path represents a file or directory
14     * @return The node representing the inserted path
15     */
16    Trie insert(String path, boolean isFile) {
17        Trie currentNode = this;
18        String[] pathComponents = path.split("/");
19      
20        // Start from index 1 to skip empty string before first "/"
21        for (int i = 1; i < pathComponents.length; ++i) {
22            String component = pathComponents[i];
23          
24            // Create new node if path component doesn't exist
25            if (!currentNode.children.containsKey(component)) {
26                currentNode.children.put(component, new Trie());
27            }
28            currentNode = currentNode.children.get(component);
29        }
30      
31        // Mark as file and store name if this is a file
32        currentNode.isFile = isFile;
33        if (isFile) {
34            currentNode.name = pathComponents[pathComponents.length - 1];
35        }
36      
37        return currentNode;
38    }
39  
40    /**
41     * Searches for a node at the given path
42     * @param path The absolute path to search
43     * @return The node at the path, or null if not found
44     */
45    Trie search(String path) {
46        Trie currentNode = this;
47        String[] pathComponents = path.split("/");
48      
49        // Start from index 1 to skip empty string before first "/"
50        for (int i = 1; i < pathComponents.length; ++i) {
51            String component = pathComponents[i];
52          
53            // Return null if path doesn't exist
54            if (!currentNode.children.containsKey(component)) {
55                return null;
56            }
57            currentNode = currentNode.children.get(component);
58        }
59      
60        return currentNode;
61    }
62}
63
64/**
65 * In-memory file system implementation using Trie data structure
66 */
67class FileSystem {
68    private Trie root = new Trie();  // Root of the file system tree
69  
70    /**
71     * Constructor initializes an empty file system
72     */
73    public FileSystem() {
74    }
75  
76    /**
77     * Lists the contents of a directory or returns file name if path is a file
78     * @param path The absolute path to list
79     * @return List of file/directory names in lexicographic order
80     */
81    public List<String> ls(String path) {
82        List<String> result = new ArrayList<>();
83      
84        // Handle root path special case
85        Trie targetNode = root.search(path);
86        if (targetNode == null) {
87            return result;
88        }
89      
90        // If path points to a file, return only the file name
91        if (targetNode.isFile) {
92            result.add(targetNode.name);
93            return result;
94        }
95      
96        // If path points to a directory, list all children
97        for (String childName : targetNode.children.keySet()) {
98            result.add(childName);
99        }
100      
101        // Sort results lexicographically
102        Collections.sort(result);
103        return result;
104    }
105  
106    /**
107     * Creates a new directory at the given path
108     * @param path The absolute path of the directory to create
109     */
110    public void mkdir(String path) {
111        root.insert(path, false);
112    }
113  
114    /**
115     * Adds content to a file, creating the file if it doesn't exist
116     * @param filePath The absolute path of the file
117     * @param content The content to append to the file
118     */
119    public void addContentToFile(String filePath, String content) {
120        Trie fileNode = root.insert(filePath, true);
121        fileNode.content.append(content);
122    }
123  
124    /**
125     * Reads and returns the content of a file
126     * @param filePath The absolute path of the file to read
127     * @return The content of the file as a string
128     */
129    public String readContentFromFile(String filePath) {
130        Trie fileNode = root.search(filePath);
131        return fileNode.content.toString();
132    }
133}
134
135/**
136 * Your FileSystem object will be instantiated and called as such:
137 * FileSystem obj = new FileSystem();
138 * List<String> param_1 = obj.ls(path);
139 * obj.mkdir(path);
140 * obj.addContentToFile(filePath,content);
141 * String param_4 = obj.readContentFromFile(filePath);
142 */
143
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5#include <sstream>
6
7using namespace std;
8
9/**
10 * Trie node structure for representing file system hierarchy
11 */
12class TrieNode {
13public:
14    string name;                                    // File name (only used for files)
15    bool is_file;                                   // Flag to indicate if this node represents a file
16    string content;                                 // File content (only used for files)
17    unordered_map<string, TrieNode*> children;     // Map of child directories/files
18  
19    /**
20     * Constructor initializes an empty trie node
21     */
22    TrieNode() : is_file(false) {}
23  
24    /**
25     * Destructor to clean up dynamically allocated children
26     */
27    ~TrieNode() {
28        for (auto& pair : children) {
29            delete pair.second;
30        }
31    }
32  
33    /**
34     * Inserts a new path into the trie structure
35     * @param path The absolute path to insert
36     * @param is_file Whether the path represents a file or directory
37     * @return The node representing the inserted path
38     */
39    TrieNode* insert(const string& path, bool is_file) {
40        TrieNode* current_node = this;
41        vector<string> path_components = split(path, '/');
42      
43        // Iterate through path components
44        for (size_t i = 0; i < path_components.size(); ++i) {
45            const string& component = path_components[i];
46            if (component.empty()) continue;  // Skip empty components
47          
48            // Create new node if path component doesn't exist
49            if (current_node->children.find(component) == current_node->children.end()) {
50                current_node->children[component] = new TrieNode();
51            }
52            current_node = current_node->children[component];
53        }
54      
55        // Mark as file and store name if this is a file
56        current_node->is_file = is_file;
57        if (is_file && !path_components.empty()) {
58            // Find last non-empty component as file name
59            for (int i = path_components.size() - 1; i >= 0; --i) {
60                if (!path_components[i].empty()) {
61                    current_node->name = path_components[i];
62                    break;
63                }
64            }
65        }
66      
67        return current_node;
68    }
69  
70    /**
71     * Searches for a node at the given path
72     * @param path The absolute path to search
73     * @return The node at the path, or nullptr if not found
74     */
75    TrieNode* search(const string& path) {
76        TrieNode* current_node = this;
77        vector<string> path_components = split(path, '/');
78      
79        // Iterate through path components
80        for (size_t i = 0; i < path_components.size(); ++i) {
81            const string& component = path_components[i];
82            if (component.empty()) continue;  // Skip empty components
83          
84            // Return nullptr if path doesn't exist
85            if (current_node->children.find(component) == current_node->children.end()) {
86                return nullptr;
87            }
88            current_node = current_node->children[component];
89        }
90      
91        return current_node;
92    }
93  
94private:
95    /**
96     * Helper function to split a string by delimiter
97     * @param str The string to split
98     * @param delimiter The delimiter character
99     * @return Vector of string components
100     */
101    vector<string> split(const string& str, char delimiter) {
102        vector<string> tokens;
103        stringstream ss(str);
104        string token;
105      
106        while (getline(ss, token, delimiter)) {
107            tokens.push_back(token);
108        }
109      
110        return tokens;
111    }
112};
113
114/**
115 * In-memory file system implementation using Trie data structure
116 */
117class FileSystem {
118private:
119    TrieNode* root;  // Root of the file system tree
120  
121public:
122    /**
123     * Constructor initializes an empty file system
124     */
125    FileSystem() {
126        root = new TrieNode();
127    }
128  
129    /**
130     * Destructor to clean up the root node
131     */
132    ~FileSystem() {
133        delete root;
134    }
135  
136    /**
137     * Lists the contents of a directory or returns file name if path is a file
138     * @param path The absolute path to list
139     * @return List of file/directory names in lexicographic order
140     */
141    vector<string> ls(string path) {
142        vector<string> result;
143      
144        // Handle root path special case
145        TrieNode* target_node = (path == "/") ? root : root->search(path);
146        if (target_node == nullptr) {
147            return result;
148        }
149      
150        // If path points to a file, return only the file name
151        if (target_node->is_file) {
152            result.push_back(target_node->name);
153            return result;
154        }
155      
156        // If path points to a directory, list all children
157        for (const auto& pair : target_node->children) {
158            result.push_back(pair.first);
159        }
160      
161        // Sort results lexicographically
162        sort(result.begin(), result.end());
163        return result;
164    }
165  
166    /**
167     * Creates a new directory at the given path
168     * @param path The absolute path of the directory to create
169     */
170    void mkdir(string path) {
171        root->insert(path, false);
172    }
173  
174    /**
175     * Adds content to a file, creating the file if it doesn't exist
176     * @param filePath The absolute path of the file
177     * @param content The content to append to the file
178     */
179    void addContentToFile(string filePath, string content) {
180        TrieNode* file_node = root->insert(filePath, true);
181        file_node->content.append(content);
182    }
183  
184    /**
185     * Reads and returns the content of a file
186     * @param filePath The absolute path of the file to read
187     * @return The content of the file as a string
188     */
189    string readContentFromFile(string filePath) {
190        TrieNode* file_node = root->search(filePath);
191        return file_node->content;
192    }
193};
194
195/**
196 * Your FileSystem object will be instantiated and called as such:
197 * FileSystem* obj = new FileSystem();
198 * vector<string> param_1 = obj->ls(path);
199 * obj->mkdir(path);
200 * obj->addContentToFile(filePath,content);
201 * string param_4 = obj->readContentFromFile(filePath);
202 */
203
1/**
2 * Trie node structure for representing file system hierarchy
3 */
4interface TrieNode {
5    name: string;                           // File name (only used for files)
6    isFile: boolean;                        // Flag to indicate if this node represents a file
7    content: string;                        // File content (only used for files)
8    children: Map<string, TrieNode>;       // Map of child directories/files
9}
10
11/**
12 * Creates a new Trie node
13 */
14function createTrieNode(): TrieNode {
15    return {
16        name: '',
17        isFile: false,
18        content: '',
19        children: new Map<string, TrieNode>()
20    };
21}
22
23/**
24 * Inserts a new path into the trie structure
25 * @param root - The root node of the trie
26 * @param path - The absolute path to insert
27 * @param isFile - Whether the path represents a file or directory
28 * @returns The node representing the inserted path
29 */
30function insertPath(root: TrieNode, path: string, isFile: boolean): TrieNode {
31    let currentNode = root;
32    const pathComponents = path.split('/');
33  
34    // Start from index 1 to skip empty string before first "/"
35    for (let i = 1; i < pathComponents.length; i++) {
36        const component = pathComponents[i];
37      
38        // Create new node if path component doesn't exist
39        if (!currentNode.children.has(component)) {
40            currentNode.children.set(component, createTrieNode());
41        }
42        currentNode = currentNode.children.get(component)!;
43    }
44  
45    // Mark as file and store name if this is a file
46    currentNode.isFile = isFile;
47    if (isFile) {
48        currentNode.name = pathComponents[pathComponents.length - 1];
49    }
50  
51    return currentNode;
52}
53
54/**
55 * Searches for a node at the given path
56 * @param root - The root node of the trie
57 * @param path - The absolute path to search
58 * @returns The node at the path, or null if not found
59 */
60function searchPath(root: TrieNode, path: string): TrieNode | null {
61    let currentNode = root;
62    const pathComponents = path.split('/');
63  
64    // Handle root path special case
65    if (path === '/') {
66        return root;
67    }
68  
69    // Start from index 1 to skip empty string before first "/"
70    for (let i = 1; i < pathComponents.length; i++) {
71        const component = pathComponents[i];
72      
73        // Return null if path doesn't exist
74        if (!currentNode.children.has(component)) {
75            return null;
76        }
77        currentNode = currentNode.children.get(component)!;
78    }
79  
80    return currentNode;
81}
82
83// Root of the file system tree
84let fileSystemRoot: TrieNode = createTrieNode();
85
86/**
87 * Lists the contents of a directory or returns file name if path is a file
88 * @param path - The absolute path to list
89 * @returns List of file/directory names in lexicographic order
90 */
91function ls(path: string): string[] {
92    const result: string[] = [];
93  
94    // Find the target node
95    const targetNode = searchPath(fileSystemRoot, path);
96    if (targetNode === null) {
97        return result;
98    }
99  
100    // If path points to a file, return only the file name
101    if (targetNode.isFile) {
102        result.push(targetNode.name);
103        return result;
104    }
105  
106    // If path points to a directory, list all children
107    for (const childName of targetNode.children.keys()) {
108        result.push(childName);
109    }
110  
111    // Sort results lexicographically
112    result.sort();
113    return result;
114}
115
116/**
117 * Creates a new directory at the given path
118 * @param path - The absolute path of the directory to create
119 */
120function mkdir(path: string): void {
121    insertPath(fileSystemRoot, path, false);
122}
123
124/**
125 * Adds content to a file, creating the file if it doesn't exist
126 * @param filePath - The absolute path of the file
127 * @param content - The content to append to the file
128 */
129function addContentToFile(filePath: string, content: string): void {
130    const fileNode = insertPath(fileSystemRoot, filePath, true);
131    fileNode.content += content;
132}
133
134/**
135 * Reads and returns the content of a file
136 * @param filePath - The absolute path of the file to read
137 * @returns The content of the file as a string
138 */
139function readContentFromFile(filePath: string): string {
140    const fileNode = searchPath(fileSystemRoot, filePath);
141    return fileNode ? fileNode.content : '';
142}
143

Time and Space Complexity

Time Complexity

ls(path): O(m + n*log(n)) where m is the length of the path (number of directories in the path) and n is the number of files/directories in the target directory.

  • Searching the path takes O(m) time to traverse through the trie
  • If it's a file, returning the name is O(1)
  • If it's a directory, sorting the children keys takes O(n*log(n))

mkdir(path): O(m) where m is the length of the path (number of directories in the path).

  • The insert operation traverses through each component of the path, creating nodes as needed
  • Splitting the path takes O(p) where p is the string length of path
  • Traversing and creating nodes takes O(m) where m is the number of path components

addContentToFile(filePath, content): O(m) where m is the length of the file path (number of directories in the path).

  • The insert operation takes O(m) to traverse/create the path
  • Appending content to the list is O(1)

readContentFromFile(filePath): O(m + c) where m is the length of the file path and c is the total length of content stored in the file.

  • Searching the path takes O(m)
  • Joining all content strings takes O(c) where c is the total character count

Space Complexity

Overall Space: O(n*k + c) where:

  • n is the total number of nodes (files and directories) in the trie
  • k is the average length of file/directory names
  • c is the total content stored across all files

Per Operation Space:

  • ls(path): O(n) for storing and returning the sorted list of children
  • mkdir(path): O(m*k) for creating new trie nodes along the path, where k is the average name length
  • addContentToFile(filePath, content): O(m*k) for potentially creating new nodes, plus the content is stored permanently
  • readContentFromFile(filePath): O(c) for creating the joined string of all content pieces

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Path Splitting Leading to Empty String Issues

One of the most common pitfalls is mishandling the path splitting, particularly with the empty string that results from splitting a path that starts with /.

The Problem: When you split a path like /a/b/c by /, you get ['', 'a', 'b', 'c']. The first element is an empty string. If you don't skip it properly, you might:

  • Create an unwanted empty-named node in the trie
  • Cause index out of bounds errors
  • Return incorrect results for root directory operations

Incorrect Implementation:

def insert(self, path, is_file):
    node = self
    ps = path.split('/')
    for p in ps:  # Wrong! This includes the empty string
        if p not in node.children:
            node.children[p] = TrieNode()
        node = node.children[p]
    # ...

Correct Implementation:

def insert(self, path, is_file):
    node = self
    ps = path.split('/')
    for p in ps[1:]:  # Skip the first empty string
        if p not in node.children:
            node.children[p] = TrieNode()
        node = node.children[p]
    # ...

2. Not Handling Root Directory as a Special Case

The root directory / needs special handling in the search method.

The Problem: When searching for /, splitting it results in ['', ''], and trying to iterate through this can cause issues or return incorrect results.

Incorrect Implementation:

def search(self, path):
    node = self
    ps = path.split('/')
    for p in ps[1:]:  # This would skip both empty strings for "/"
        if p not in node.children:
            return None
        node = node.children[p]
    return node

Correct Implementation:

def search(self, path):
    node = self
    if path == '/':  # Handle root specially
        return node
    ps = path.split('/')
    for p in ps[1:]:
        if p not in node.children:
            return None
        node = node.children[p]
    return node

3. Overwriting Existing File Content Instead of Appending

The problem specifically states that addContentToFile should append content if the file exists, not replace it.

The Problem: Using assignment instead of append would overwrite existing content.

Incorrect Implementation:

def addContentToFile(self, filePath, content):
    node = self.root.insert(filePath, True)
    node.content = [content]  # Wrong! This overwrites existing content

Correct Implementation:

def addContentToFile(self, filePath, content):
    node = self.root.insert(filePath, True)
    node.content.append(content)  # Correctly appends to existing content

4. Not Preserving File State When Re-inserting

When addContentToFile is called on an existing file, the insert method shouldn't reset the file's properties.

The Problem: If insert always resets the content list or other properties, you'll lose existing data.

Better Implementation with State Preservation:

def insert(self, path, is_file):
    node = self
    ps = path.split('/')
    for p in ps[1:]:
        if p not in node.children:
            node.children[p] = TrieNode()
        node = node.children[p]
  
    # Only set is_file if creating new node or converting directory to file
    if not node.is_file:  # Preserve existing file state
        node.is_file = is_file
        if is_file:
            node.name = ps[-1]
  
    return node

5. Forgetting to Sort Directory Listings

The problem requires directory contents to be returned in lexicographic order.

Incorrect Implementation:

def ls(self, path):
    node = self.root.search(path)
    if node is None:
        return []
    if node.is_file:
        return [node.name]
    return list(node.children.keys())  # Wrong! Not sorted

Correct Implementation:

def ls(self, path):
    node = self.root.search(path)
    if node is None:
        return []
    if node.is_file:
        return [node.name]
    return sorted(node.children.keys())  # Correctly sorted

6. Memory Inefficiency with Content Storage

Storing content as a list of strings and joining them every read can be inefficient for frequently read files.

Alternative Approach for Optimization:

class TrieNode:
    def __init__(self):
        self.content_builder = []  # For building content
        self.cached_content = None  # Cache the joined content
  
    def add_content(self, content):
        self.content_builder.append(content)
        self.cached_content = None  # Invalidate cache
  
    def get_content(self):
        if self.cached_content is None:
            self.cached_content = ''.join(self.content_builder)
        return self.cached_content

These pitfalls are subtle but critical for correct implementation. The key is careful handling of edge cases, particularly around path parsing and root directory operations.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Trie Introduction

Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More