Design In-Memory File System

Design In-Memory File System is the classic "build a data structure behind an API" problem. The whole thing is one idea: a file system is just a tree of nodes, and every operation is a walk down that tree splitting the path on /.

The slow way first

You could imagine storing every full path string in a flat dictionary, like {"/a": dir, "/a/b": dir, "/a/b/file.txt": "hi"}. It "works," but ls becomes painful: to list /a you must scan every key and string-match the prefix, which is O(total paths) per call. Creating /a/b/c also forces you to check each ancestor by re-building its string. The flat map fights the natural shape of the data.

The question to ask: what structure already mirrors a file system? A tree. Parent points to children. That makes ls a local lookup instead of a global scan.

The idea: every component is a node

Model each path component as a node. A node is both a directory and a file: it carries a children map (name → Node) and a content string. The root / is the only node that exists at the start. To run any operation, split the path on / and walk from the root, hopping into node.children[name] for each component — creating nodes along the way when the operation builds (mkdir, addContentToFile).

The key insight: all four operations share the same walk. They differ only in two knobs — whether a missing node is created (make=True) and what you do once you reach the end (list children, or touch content).

Walk through it

Step through the animation. mkdir("/a/b") walks root and creates a, then b. addContentToFile("/a/b/file.txt", "hi") re-walks the same path and creates the file leaf, appending "hi". readContentFromFile walks to that same leaf and returns the string. A second file readme.txt is created directly under root. Finally ls("/") lands on root (a directory) and returns its sorted child names.

Pseudocode

node = { children: {}, content: "" }   # one type for dirs and files
 
walk(parts, make):
    cur = root
    for name in parts:
        if name not in cur.children:
            if not make: return None        # path missing on a read
            cur.children[name] = new node    # build it
        cur = cur.children[name]
    return cur
 
ls(path):        n = walk(parts(path), make=False)
                 return sorted(n.children) if it is a dir else [last name]
mkdir(path):     walk(parts(path), make=True)
addContent:      walk(..., make=True).content += content
readContent:     return walk(..., make=False).content

The Python solution

class Node:
    def __init__(self):
        self.children = {}   # name -> Node (directory)
        self.content = ""    # file body (files only)
 
def walk(root, parts, make=False):
    node = root
    for name in parts:
        if name not in node.children:
            if not make:
                return None
            node.children[name] = Node()
        node = node.children[name]
    return node
 
def add_content(root, path, text):
    node = walk(root, split(path), make=True)
    node.content += text
 
def read_content(root, path):
    node = walk(root, split(path), make=False)
    return node.content

• Node is one class for both directories and files: a children map plus a content string. Whichever field is used depends on how the node is reached.
• walk is the shared engine. It hops node = node.children[name] for each component.
• The make flag is the only behavioral switch: when building (mkdir, add_content) a missing component is created; when reading it short-circuits with None.
• add_content walks with make=True so the file is created if absent, then appends.
• read_content walks with make=False and returns the stored body. ls and mkdir are the same walk with a different final action.

Complexity

A walk touches only the components on the path, not the whole tree — so each operation is O(p) in the path length (plus a sort for ls on a directory). That is the payoff of matching the data structure to the data shape.

When this pattern shows up

Practice