Design In-Memory File System

Table of Contents +

This question feels big the first time you see it. A whole file system in code? But it is really just a tree of folders and files. Once you see that shape, the rest is walking the tree. The interviewer wants to see if you can pick the right structure and keep the code clean.

🎯 The Problem

You build a tiny file system that lives in memory. It supports a few commands.

The commands:

ls(path) lists what is at a path. A file returns its own name. A folder returns the names inside it, sorted.
mkdir(path) makes a folder, building any missing folders along the way.
addContentToFile(path, content) creates a file or adds text to an existing one.
readContentFromFile(path) returns the full text of a file.

The path rules:

A path looks like /a/b/c.
The single / is the root, the top folder that holds everything.
Adding content appends. It does not replace.

mkdir("/a/b/c")                        -> creates folders a, b, c
ls("/")                                -> ["a"]
addContentToFile("/a/b/c/d", "hello")  -> creates file d with "hello"
readContentFromFile("/a/b/c/d")        -> "hello"
addContentToFile("/a/b/c/d", "world")  -> appends, file is now "helloworld"
ls("/a/b/c")                           -> ["d"]
ls("/a/b/c/d")                         -> ["d"]   (path is a file, return its name)

So ls on a folder lists its children. ls on a file returns just that file’s name. And content adds on, it does not replace.

Here is the tree the example builds. Notice folders hold other folders, and a file sits at a leaf.

🐢 Approach 1: Flat Map of Full Paths (Brute Force)

The idea in one line: store every full path as a key in one hash map.

The idea:

One hash map. The full path /a/b/c/d maps to its content.
Reading a single file is a direct lookup of the whole path.

How it works:

addContentToFile writes to the key for that path.
readContentFromFile reads the key for that path.
ls scans every key to find the ones that start with the folder path.

Why it is weak:

Listing a folder means scanning every key in the map.
Nested folders need extra tracking of which prefixes are folders.
The flat map fights the tree shape the problem really has.

Here is the flat-map code:

class FileSystem:
    def __init__(self):
        self.dirs = {"/": set()}
        self.files = {}

    def ls(self, path):
        if path in self.files:
            return [path.split("/")[-1]]
        return sorted(self.dirs.get(path, set()))

    def mkdir(self, path):
        parts = path.strip("/").split("/")
        cur = "/"
        for part in parts:
            self.dirs.setdefault(cur, set()).add(part)
            cur = cur.rstrip("/") + "/" + part
            self.dirs.setdefault(cur, set())

    def addContentToFile(self, filePath, content):
        parent, name = filePath.rsplit("/", 1)
        parent = parent or "/"
        self.mkdir(parent)
        self.dirs[parent].add(name)
        self.files[filePath] = self.files.get(filePath, "") + content

    def readContentFromFile(self, filePath):
        return self.files[filePath]

⚡ Approach 2: Trie of Nodes (Best)

The idea in one line: model the file system as a tree, where each node is one folder or file.

The idea:

A trie is a tree where each node holds a map from a name to a child node.
Each node is one folder or one file.
A folder node has children. A file node has content text.

How it works:

Split the path by / and walk down the tree one name at a time.
mkdir creates missing nodes as it walks.
addContentToFile walks to the file node and appends text.
readContentFromFile walks to the file node and returns its content.
ls walks to the node. A file returns its name. A folder returns its sorted child names.

Why it is fast:

Each step down the path is one quick map lookup.
Listing a folder is just reading the keys of one node’s children map.
One walk method is reused by every command.

Here is the inside of a node and how we walk the path for ls("/a/b/c").

Steps to Solve

Make a node type that has a children map, a content string, and an isFile flag.
Keep one root node that holds everything.
To walk a path, split it by / and drop empty parts. Move down child by child from the root.
For mkdir, walk the path and create any missing child node along the way.
For addContentToFile, walk to the parent, then find or create the file node and append the content.
For readContentFromFile, walk to the file node and return its content.
For ls, walk to the node. If it is a file return its name. If it is a folder return its children’s names, sorted.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a small class for each node, with a dictionary of children that we sort when listing.

class Node:
    def __init__(self):
        self.children = {}   # name -> child node
        self.content = ""    # file text
        self.is_file = False


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

    def _walk(self, path, make_file):
        cur = self.root
        parts = [p for p in path.split("/") if p]   # drop empty parts
        for i, name in enumerate(parts):
            if name not in cur.children:
                cur.children[name] = Node()         # create missing node
            cur = cur.children[name]
            if make_file and i == len(parts) - 1:
                cur.is_file = True
        return cur

    def ls(self, path):
        cur = self._walk(path, False)
        if cur.is_file:                             # path is a file
            return [path.split("/")[-1]]
        return sorted(cur.children.keys())          # sorted folder names

    def mkdir(self, path):
        self._walk(path, False)

    def add_content_to_file(self, path, text):
        self._walk(path, True).content += text      # append text

    def read_content_from_file(self, path):
        return self._walk(path, True).content


fs = FileSystem()
fs.mkdir("/a/b/c")
print("ls(/) ->", fs.ls("/"))
fs.add_content_to_file("/a/b/c/d", "hello")
print("read(/a/b/c/d) ->", fs.read_content_from_file("/a/b/c/d"))
fs.add_content_to_file("/a/b/c/d", "world")
print("read(/a/b/c/d) ->", fs.read_content_from_file("/a/b/c/d"))
print("ls(/a/b/c) ->", fs.ls("/a/b/c"))
print("ls(/a/b/c/d) ->", fs.ls("/a/b/c/d"))

The output of the above code will be:

ls(/) -> ['a']
read(/a/b/c/d) -> hello
read(/a/b/c/d) -> helloworld
ls(/a/b/c) -> ['d']
ls(/a/b/c/d) -> ['d']

Let us walk through the Python _walk method line by line, because every command leans on it.

    def _walk(self, path, make_file):
        cur = self.root
        parts = [p for p in path.split("/") if p]
        for i, name in enumerate(parts):
            if name not in cur.children:
                cur.children[name] = Node()
            cur = cur.children[name]
            if make_file and i == len(parts) - 1:
                cur.is_file = True
        return cur

The line cur = self.root starts us at the top of the tree. Every path starts from the root, so we always begin there.

The line parts = [p for p in path.split("/") if p] cuts the path into names. Splitting /a/b/c on / gives empty strings at the ends. The if p filter drops those, so we keep only real names.

The loop for i, name in enumerate(parts) moves down the tree one name at a time. The index i lets us know when we hit the last name in the path.

The line if name not in cur.children checks if the next folder or file exists yet. If not, the next line cur.children[name] = Node() creates it. This is how mkdir builds missing folders for free.

The line cur = cur.children[name] steps into that child. Now cur points one level deeper.

The line if make_file and i == len(parts) - 1 only fires on the very last name, and only when we are adding a file. It marks that final node as a file. The folders along the way stay folders.

The line return cur hands back the node we landed on. The caller then reads its content, appends text, or lists its children. One walk method, every command.

⏱️ Time and Space Complexity

The flat map makes single reads fast but ls slow, because listing a folder means scanning every key. The trie makes each command cost only the path length plus the work to sort the listing. If the path has L parts, walking it is O(L). Sorting a folder with k children for ls is O(k log k). Space is the size of the tree, which is every folder and file you created.

Approach	ls a folder	walk a path	Space
Flat map of full paths	O(total keys)	O(L) for path length L	O(total entries)
Trie of nodes	O(L + k log k) for k children	O(L) for path length L	O(total nodes)

Tip

Whenever a problem talks about paths, folders, or prefixes, think trie. A trie is just a tree of maps. The path becomes a walk down the tree, and most of the code is that one walk method reused.

🧩 Key Takeaways

✅ A file system is a tree, so model it as a trie of nodes, not a flat map of paths.
✅ Each node holds a children map, its content, and a flag for file or folder.
✅ One walk method splits the path and moves down the tree, creating missing nodes.
✅ ls on a folder returns its sorted child names, and on a file returns the file name.
✅ addContent appends text, so calling it twice joins the strings together.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Snapshot Array
Insert Delete GetRandom O(1)

Previous Insert Delete GetRandom O(1) Next Design Hit Counter

Design In-Memory File System

Follow Us

Follow Us