LeetCode Solutions Blog

Design In-Memory File System

Number: 588

Difficulty: Hard

Paid? Yes

Problem Description

Design an in-memory file system that supports the following operations: listing directory contents, creating directories, adding content to files (with the ability to append), and reading file content. Directories and files are managed in a tree-like structure starting from the root directory.

Key Insights

Use a tree (trie) to represent directories and files.
Each node can be either a directory or a file; directories maintain a mapping of names to child nodes.
For ls, if the given path is a file, return only its name. If it's a directory, return the sorted list of names of its children.
mkdir must create all intermediate directories if they do not already exist.
File nodes store content and support content appending.

Space and Time Complexity

Time Complexity:

ls: O(k log k) where k is the number of entries in the directory (due to sorting), or O(n) if traversing a long path.
mkdir, addContentToFile, readContentFromFile: O(d) where d is the depth of the file path. Space Complexity:
O(T) where T is the total number of characters stored in directory names and file contents.

Solution

The solution uses a tree-based approach where each node represents either a directory or a file. Each directory node stores its children in a hash table (or dictionary) mapping names to node objects. File nodes store their content as a string and carry a flag indicating they are files. For the ls operation, check if the node is a file—if so, return its name; otherwise, list and sort the names of all children in that directory. The mkdir operation traverses (or creates) nodes for each segment of the provided path. The addContentToFile method accesses or creates the file node and appends the content. Finally, readContentFromFile retrieves the stored content from the file node.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with descriptive, line-by-line comments.

class Node:
    def __init__(self):
        # Indicates whether this node represents a file or a directory
        self.is_file = False
        # For directories, mapping from name to Node
        self.children = {}
        # For files, store content
        self.content = ""

class FileSystem:

    def __init__(self):
        # Root directory node initialization
        self.root = Node()

    def ls(self, path: str) -> list:
        # Traverse the path to obtain the target node
        node, name = self.traverse(path)
        # If the node is a file, return the single element list containing its name
        if node.is_file:
            return [name]
        # Otherwise, list all keys (names) in the directory, sorted lexicographically
        return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        # Create directory by traversing the path and creating nodes if necessary
        self.traverse(path)

    def addContentToFile(self, filePath: str, content: str) -> None:
        # Traverse to the file's node; if it does not exist, create necessary nodes along the path
        node, name = self.traverse(filePath)
        # If not already a file, mark the node as a file
        if not node.is_file:
            node.is_file = True
            node.content = ""
        # Append the new content to the file's content
        node.content += content

    def readContentFromFile(self, filePath: str) -> str:
        # Traverse to the file's node
        node, _ = self.traverse(filePath)
        # Return the content of the file
        return node.content

    def traverse(self, path: str):
        # Start from the root node
        node = self.root
        if path == "/":
            # Special case for root path
            return node, ""
        # Split the path by "/" and traverse the nodes
        parts = path.split("/")[1:]
        for part in parts:
            # Create the node if it does not exist
            if part not in node.children:
                node.children[part] = Node()
            node = node.children[part]
        # Return the target node and its name (last part of the path)
        return node, parts[-1]
        
# Example usage:
# fs = FileSystem()
# print(fs.ls("/"))           # prints []
# fs.mkdir("/a/b/c")
# fs.addContentToFile("/a/b/c/d", "hello")
# print(fs.ls("/"))           # prints ['a']
# print(fs.readContentFromFile("/a/b/c/d"))  # prints "hello"