LeetCode 588 - Design In-Memory File System

Difficulty: 🔴 Hard
Topics: Hash Table, String, Design, Trie, Sorting

Solution

Problem Understanding

The problem asks us to design an in-memory file system that simulates basic file system operations without interacting with the real filesystem. We need to implement a FileSystem class that supports creating directories, adding and reading file content, and listing files or directories in a given path.

The input consists of paths, which are absolute (starting with /) and only contain lowercase letters. Each operation affects or queries the virtual file system structure. The expected output varies depending on the operation: ls returns a list of file or directory names, mkdir and addContentToFile modify the system with no return, and readContentFromFile returns the file content as a string.

Constraints indicate that paths are valid, their length is reasonable, and there are at most 300 operations. This suggests that our solution should focus on clarity and correctness, rather than extreme optimization. Edge cases include querying the root /, adding content to existing files, and paths that involve nested directories.

The key challenge is maintaining an efficient and easy-to-traverse representation of the filesystem, supporting fast lookups, insertions, and content storage.

Approaches

The brute-force approach would be to use a flat list or array to store every path and file content. Every ls, mkdir, or addContentToFile operation would involve scanning the entire list to find the matching directory or file. While this would work functionally, it would be slow for nested paths or frequent operations, with O(n) complexity per operation.

The optimal approach is to use a trie-like tree structure where each node represents a directory or file. Each directory node stores a dictionary mapping names to child nodes. File nodes store their content as a string. This allows O(k) operations, where k is the number of components in the path, for creation, lookup, or content reading. Lexicographic ordering for ls can be handled by sorting keys of the dictionary when returning results.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per operation	O(n)	Store paths in a list; requires linear scans for lookups
Optimal	O(k log k) for ls, O(k) for other ops	O(total nodes + total content)	Use trie/tree structure; k is number of path components

Algorithm Walkthrough

Define a Node class that represents either a directory or a file. Directory nodes have a dictionary for children, file nodes have a string for content.
Initialize the root of the filesystem as an empty directory node.
Implement mkdir(path) by splitting the path into components and traversing the trie, creating any missing directories along the path.
Implement addContentToFile(filePath, content) by traversing to the file path, creating a new file node if it does not exist, and appending the content.
Implement readContentFromFile(filePath) by traversing to the file node and returning its content.
Implement ls(path) by traversing to the given path. If it is a file, return its name in a list. If it is a directory, return the sorted list of child names.

Why it works: The trie structure preserves the hierarchical nature of file systems. Each operation works by following the path components from root to the target node. Creating directories or files along the path guarantees the structure remains consistent. The invariant is that the trie always accurately represents the filesystem.

Python Solution

from typing import List, Dict

class Node:
    def __init__(self):
        self.children: Dict[str, Node] = {}
        self.content: str = ""
        self.is_file: bool = False

class FileSystem:

    def __init__(self):
        self.root = Node()

    def ls(self, path: str) -> List[str]:
        node = self.root
        if path != "/":
            parts = path.split("/")[1:]
            for part in parts:
                node = node.children[part]
            if node.is_file:
                return [parts[-1]]
        return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        node = self.root
        parts = path.split("/")[1:]
        for part in parts:
            if part not in node.children:
                node.children[part] = Node()
            node = node.children[part]

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self.root
        parts = filePath.split("/")[1:]
        for part in parts[:-1]:
            node = node.children[part]
        if parts[-1] not in node.children:
            node.children[parts[-1]] = Node()
            node.children[parts[-1]].is_file = True
        node.children[parts[-1]].content += content

    def readContentFromFile(self, filePath: str) -> str:
        node = self.root
        parts = filePath.split("/")[1:]
        for part in parts[:-1]:
            node = node.children[part]
        return node.children[parts[-1]].content

The Python implementation defines a Node class for directories and files. ls handles the root directory, files, and lexicographic ordering. mkdir and addContentToFile traverse the path, creating intermediate nodes if missing. readContentFromFile simply follows the path to the file and returns content.

Go Solution

package main

import (
    "sort"
    "strings"
)

type Node struct {
    children map[string]*Node
    content  string
    isFile   bool
}

type FileSystem struct {
    root *Node
}

func Constructor() FileSystem {
    return FileSystem{root: &Node{children: make(map[string]*Node)}}
}

func (this *FileSystem) Ls(path string) []string {
    node := this.root
    if path != "/" {
        parts := strings.Split(path, "/")[1:]
        for _, part := range parts {
            node = node.children[part]
        }
        if node.isFile {
            return []string{parts[len(parts)-1]}
        }
    }
    res := make([]string, 0, len(node.children))
    for name := range node.children {
        res = append(res, name)
    }
    sort.Strings(res)
    return res
}

func (this *FileSystem) Mkdir(path string) {
    node := this.root
    parts := strings.Split(path, "/")[1:]
    for _, part := range parts {
        if _, ok := node.children[part]; !ok {
            node.children[part] = &Node{children: make(map[string]*Node)}
        }
        node = node.children[part]
    }
}

func (this *FileSystem) AddContentToFile(filePath string, content string) {
    node := this.root
    parts := strings.Split(filePath, "/")[1:]
    for _, part := range parts[:len(parts)-1] {
        node = node.children[part]
    }
    if _, ok := node.children[parts[len(parts)-1]]; !ok {
        node.children[parts[len(parts)-1]] = &Node{children: make(map[string]*Node), isFile: true}
    }
    node.children[parts[len(parts)-1]].content += content
}

func (this *FileSystem) ReadContentFromFile(filePath string) string {
    node := this.root
    parts := strings.Split(filePath, "/")[1:]
    for _, part := range parts[:len(parts)-1] {
        node = node.children[part]
    }
    return node.children[parts[len(parts)-1]].content
}

The Go implementation mirrors Python, but uses explicit map initialization and type declarations. Sorting is done using the standard sort package. Go requires careful handling of slices and maps, especially when creating new nodes.

Worked Examples

Example 1:

Operations: ["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
Arguments:  [[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]

Step by step:

Initialize filesystem. Root node is empty directory.
ls("/") → root has no children → return [].
mkdir("/a/b/c") → create nodes for a → b → c.
addContentToFile("/a/b/c/d", "hello") → create file d in c and set content.
ls("/") → root has child a → return ["a"].
readContentFromFile("/a/b/c/d") → return "hello".

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k log k) for ls, O(k) for others	k is number of path components
Space	O(total nodes + total content)	Each directory and file uses one node

The main cost is traversing the path components. Sorting in ls requires O(k log k) where k is the number of entries in the directory.

Test Cases

fs = FileSystem()

# basic operations
assert fs.ls("/") == []  # root initially empty
fs.mkdir("/a/b/c")
fs.addContentToFile("/a/b/c/d", "hello")
assert fs.ls("/") == ["a"]  # directory listing
assert fs.readContentFromFile("/a/b/c/d") == "hello"  # file content

# append content
fs