LeetCode 588: Design In-Memory File System

Problem Restatement

We need to design an in-memory file system.

The file system must support four operations:

All paths are absolute paths that begin with /. The root directory is /. Directory and file names contain lowercase letters. Operations are valid, so we do not need to handle invalid reads or invalid listings. The official statement defines this as a file-system simulation problem with design, trie, hash table, string, and sorting tags.

Input and Output

The class shape is:

class FileSystem:

    def __init__(self):
        ...

    def ls(self, path: str) -> list[str]:
        ...

    def mkdir(self, path: str) -> None:
        ...

    def addContentToFile(self, filePath: str, content: str) -> None:
        ...

    def readContentFromFile(self, filePath: str) -> str:
        ...

The methods return:

Example

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"]

Step by step:

fs = FileSystem()
fs.ls("/")                         # []
fs.mkdir("/a/b/c")                 # creates /a, /a/b, /a/b/c
fs.addContentToFile("/a/b/c/d", "hello")
fs.ls("/")                         # ["a"]
fs.readContentFromFile("/a/b/c/d") # "hello"

The file d is created under /a/b/c.

The root directory now has one child: a.

First Thought: Store Full Paths in Dictionaries

A simple idea is to store directories and files by their full paths.

For example:

directories = {"/", "/a", "/a/b", "/a/b/c"}
files = {
    "/a/b/c/d": "hello"
}

This can work, but ls(path) becomes awkward.

If we call:

ls("/a")

we need to find only direct children of /a, not every path that starts with /a.

That means we must parse and compare many full path strings.

A real file system is hierarchical, so a hierarchical data structure is cleaner.

Key Insight

A path is naturally a sequence of components.

For example:

/a/b/c/d

has components:

["a", "b", "c", "d"]

This suggests a tree.

Each node represents either a directory or a file.

A directory node has children.

A file node stores content.

This is often described as a trie over path components. Each edge is one directory or file name, and each node stores metadata for that path.

Data Structure

Use a Node class.

Each node stores:

The root node represents /.

class Node:
    def __init__(self):
        self.children = {}
        self.is_file = False
        self.content = []

Using a list for content lets us append strings efficiently.

When reading, we join the list:

"".join(node.content)

Path Parsing

We need a helper to split paths.

For root:

"/"

there are no components.

For a normal path:

"/a/b/c"

the components are:

["a", "b", "c"]

A helper can be:

def parts(self, path: str) -> list[str]:
    if path == "/":
        return []
    return path.split("/")[1:]

We skip the first empty string caused by the leading slash.

Algorithm for ls

If path is /, return the sorted names of root’s children.

Otherwise:

1. Split the path into components.
2. Walk from root to the target node.
3. If the target node is a file, return a list containing only the last component.
4. If the target node is a directory, return sorted child names.

The file case is special.

For example:

ls("/a/b/c/d")

should return:

["d"]

not the file content and not its children.

Algorithm for mkdir

To create:

/a/b/c

we walk through:

["a", "b", "c"]

At each component:

1. If the child does not exist, create a new directory node.
2. Move to that child.

This behaves like mkdir -p.

Algorithm for addContentToFile

To add content to:

/a/b/c/d

we walk through all components.

At each component:

1. If the node does not exist, create it.
2. Move to it.
3. At the last component, mark it as a file.
4. Append content to the file node.

The problem guarantees valid operations, and addContentToFile may create the file if it does not exist.

Algorithm for readContentFromFile

1. Split the file path.
2. Walk from root to the target file node.
3. Return "".join(node.content).

Correctness

The tree contains one node for every directory or file path that has been created. Each edge corresponds to exactly one path component. Therefore, walking from the root through the components of a path reaches exactly the node represented by that path.

For mkdir, the algorithm creates every missing component on the path and moves through existing components when they already exist. Thus, after mkdir(path), the directory path exists.

For addContentToFile, the algorithm reaches the node for filePath, creating missing nodes if needed. It marks the final node as a file and appends the new content. Therefore, repeated calls preserve old content and add new content at the end.

For readContentFromFile, the algorithm reaches the file node and joins all appended content pieces in insertion order. This returns exactly the file content.

For ls, if the target node is a file, the required result is only the file name. The algorithm returns the final path component. If the target node is a directory, the required result is its direct children in lexicographic order. The algorithm returns the sorted child names. Therefore, every operation matches the required behavior.

Complexity

Let:

L = number of components in the path
C = number of children in the listed directory
S = total content length of the file being read

The sort in ls is needed because directory contents must be returned in lexicographic order.

Implementation

class Node:
    def __init__(self):
        self.children = {}
        self.is_file = False
        self.content = []

class FileSystem:

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

    def _parts(self, path: str) -> list[str]:
        if path == "/":
            return []
        return path.split("/")[1:]

    def _walk(self, path: str, create: bool = False) -> Node:
        node = self.root

        for name in self._parts(path):
            if create and name not in node.children:
                node.children[name] = Node()
            node = node.children[name]

        return node

    def ls(self, path: str) -> list[str]:
        node = self._walk(path)

        if node.is_file:
            return [self._parts(path)[-1]]

        return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        self._walk(path, create=True)

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self._walk(filePath, create=True)
        node.is_file = True
        node.content.append(content)

    def readContentFromFile(self, filePath: str) -> str:
        node = self._walk(filePath)
        return "".join(node.content)

Code Explanation

The Node class is the core structure:

class Node:
    def __init__(self):
        self.children = {}
        self.is_file = False
        self.content = []

A directory is a node with is_file = False.

A file is a node with is_file = True.

The constructor creates the root directory:

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

The helper _parts converts a path into names:

def _parts(self, path: str) -> list[str]:
    if path == "/":
        return []
    return path.split("/")[1:]

The helper _walk moves through the tree:

def _walk(self, path: str, create: bool = False) -> Node:
    node = self.root

    for name in self._parts(path):
        if create and name not in node.children:
            node.children[name] = Node()
        node = node.children[name]

    return node

When create is true, missing nodes are created.

When create is false, the method assumes the path already exists, which is valid for the given operations.

The ls method handles files and directories differently:

def ls(self, path: str) -> list[str]:
    node = self._walk(path)

    if node.is_file:
        return [self._parts(path)[-1]]

    return sorted(node.children.keys())

The mkdir method only needs to walk with creation enabled:

def mkdir(self, path: str) -> None:
    self._walk(path, create=True)

The addContentToFile method creates the path if needed, marks the final node as a file, and appends content:

def addContentToFile(self, filePath: str, content: str) -> None:
    node = self._walk(filePath, create=True)
    node.is_file = True
    node.content.append(content)

The readContentFromFile method joins all appended chunks:

def readContentFromFile(self, filePath: str) -> str:
    node = self._walk(filePath)
    return "".join(node.content)

Testing

def run_tests():
    fs = FileSystem()

    assert fs.ls("/") == []

    fs.mkdir("/a/b/c")
    fs.addContentToFile("/a/b/c/d", "hello")

    assert fs.ls("/") == ["a"]
    assert fs.ls("/a/b/c") == ["d"]
    assert fs.ls("/a/b/c/d") == ["d"]
    assert fs.readContentFromFile("/a/b/c/d") == "hello"

    fs.addContentToFile("/a/b/c/d", " world")
    assert fs.readContentFromFile("/a/b/c/d") == "hello world"

    fs.mkdir("/a/b/e")
    fs.addContentToFile("/a/b/file", "x")
    assert fs.ls("/a/b") == ["c", "e", "file"]

    print("all tests passed")

run_tests()

Test meaning: