Design a File System (LLD): The Composite Pattern

"Design an in-memory file system" is a low-level design prompt with a hidden test. Anyone can write a File class and a Folder class. The question is whether a caller can ask "how big is this?" without caring which one it holds, whether a folder inside a folder inside a folder needs any extra code, and what happens to the design when the interviewer adds "and make size() fast" or "now add symlinks". The pattern that answers all three is the composite.

The problem it solves

A typical version of the prompt asks for a handful of operations on paths like /logs/2026/app.log:

• mkdir(path), creating missing parents along the way.
• write(path, size) to create or overwrite a file.
• ls(path), the names in a folder, sorted.
• size(path), a file's bytes or a folder's total.
• delete(path) and find(predicate), for example every .log file.

Folders nest to any depth, and every operation except mkdir must treat files and folders uniformly where it can. That last requirement is what separates a design from a pile of isinstance checks.

The intuition

Name one contract: an Entry is anything with a name that can report its size. A File answers from its own bytes. A Folder answers by asking every entry it holds and adding up the answers. The caller never checks which kind it has, and nesting costs nothing: a folder of folders is just a folder whose children answer the same question. That is the composite pattern: a leaf and a container share one interface, and the container implements it by delegating to its children.

Three design decisions come up next:

• Children in a dict, not a list. Names in a folder are unique and every path step is a lookup, so dict[name] → Entry makes each step O(1).
• Path resolution in one place. Split the path on / and walk from the root. Every operation calls the same helper, so "missing folder" and "file where a folder was expected" are handled once.
• Where the cost of size() lives. The pure composite walks the whole subtree on every call. If sizes are read often, each folder can cache its total and every write adjusts the cached totals of its ancestors, which needs a parent pointer. Reads become O(1); writes pay O(depth).

A symlink tests whether the contract holds. It is one new class that answers size() with the size of the link itself, and neither Folder nor any caller changes. Following links is where the danger is: a link that points at its own ancestor turns a tree into a graph with a cycle, which is why tools like du do not follow symbolic links by default.

Watch it run

The animation follows the lesson's tree: a root holding a.txt and a logs folder with x.log inside. One contract comes first: an Entry is anything that can report its own size. A File answers from its own bytes; nothing recursive about it. A Folder answers the same call by asking everything it holds: same contract, different reply. Then root.size(): the caller asks once, at the top, and knows nothing about the shape below. The folder asks its first entry; a.txt answers 12 and stops there. The second entry is itself a folder, so the question simply repeats, with no extra code. One level deeper, x.log answers 30, and logs hands that straight back up. The root adds up what came back, 42, and the recursion lived entirely inside the container. The last frame is the extension test: add a symlink tomorrow, one new class, and every caller that only speaks Entry is untouched.

The code

The composite with dict children, a single path resolver, and cached folder sizes kept correct by walking parent pointers on every change:

class Entry:
    def __init__(self, name, parent=None):
        self.name, self.parent = name, parent
    def size(self):
        raise NotImplementedError

class File(Entry):
    def __init__(self, name, parent, nbytes):
        super().__init__(name, parent)
        self.nbytes = nbytes
    def size(self):
        return self.nbytes                       # a leaf answers from its own bytes

class Folder(Entry):
    def __init__(self, name, parent=None):
        super().__init__(name, parent)
        self.children = {}                       # name -> Entry: each path step is O(1)
        self.total = 0                           # cached size of everything below
    def size(self):
        return self.total
    def add_to_total(self, delta):               # O(depth): walk up the parent pointers
        node = self
        while node is not None:
            node.total += delta
            node = node.parent

class FileSystem:
    def __init__(self):
        self.root = Folder("")

    def _walk(self, path, create=False):
        node = self.root
        for part in [p for p in path.split("/") if p]:
            if not isinstance(node, Folder):
                raise NotADirectoryError(path)
            if part not in node.children:
                if not create:
                    raise FileNotFoundError(path)
                node.children[part] = Folder(part, node)
            node = node.children[part]
        return node

    def mkdir(self, path):
        folder = self._walk(path, create=True)
        if not isinstance(folder, Folder):
            raise NotADirectoryError(path)

    def write(self, path, nbytes):
        parent_path, name = path.rsplit("/", 1)
        folder = self._walk(parent_path, create=True)
        if not isinstance(folder, Folder):
            raise NotADirectoryError(path)
        old = folder.children.get(name)
        if isinstance(old, Folder):
            raise IsADirectoryError(path)
        folder.children[name] = File(name, folder, nbytes)
        folder.add_to_total(nbytes - (old.size() if old else 0))

    def delete(self, path):
        entry = self._walk(path)
        entry.parent.add_to_total(-entry.size())
        del entry.parent.children[entry.name]

    def size(self, path):
        return self._walk(path).size()           # the caller never asks which kind it got

    def ls(self, path):
        entry = self._walk(path)
        return sorted(entry.children) if isinstance(entry, Folder) else [entry.name]

fs = FileSystem()
fs.write("/a.txt", 12)
fs.write("/logs/x.log", 30)                      # creates /logs on the way
print(fs.size("/"), fs.ls("/"), fs.size("/logs"))    # 42 ['a.txt', 'logs'] 30
fs.write("/logs/x.log", 50)                      # overwrite: the delta is +20
fs.delete("/a.txt")
print(fs.size("/"), fs.ls("/"))                  # 50 ['logs']

A search that works on any entry, and the symlink extension: a new class, no change to Folder or FileSystem.size. It reports its own size, the length of the path it stores, and the walk does not follow it, so a link to its own ancestor cannot loop:

def find(entry, keep, prefix=""):
    """Yield the path of every entry below `entry` for which keep(entry) is true."""
    path = prefix + "/" + entry.name if entry.name else prefix
    if keep(entry):
        yield path or "/"
    if isinstance(entry, Folder):
        for name in sorted(entry.children):
            yield from find(entry.children[name], keep, path)

class Symlink(Entry):
    def __init__(self, name, parent, target):
        super().__init__(name, parent)
        self.target = target
    def size(self):
        return len(self.target)                  # the link itself, not what it points to

fs.write("/logs/2026/app.log", 7)
logs = fs._walk("/logs")
logs.children["loop"] = Symlink("loop", logs, "/logs")
logs.add_to_total(logs.children["loop"].size())
print(list(find(fs.root, lambda e: e.name.endswith(".log"))))
# ['/logs/2026/app.log', '/logs/x.log']
print(fs.size("/logs"), fs.ls("/logs"))          # 62 ['2026', 'loop', 'x.log']

Checked on 500 seeded random runs of 60 operations against a brute force that keeps a flat path → bytes table and computes a folder's size by summing every file under its prefix. The cached totals are also compared with an uncached recursive sum:

import random

def recompute(entry):
    """The pure composite: ask every child, no cache."""
    if isinstance(entry, Folder):
        return sum(recompute(child) for child in entry.children.values())
    return entry.size()

rng = random.Random(31)
ok = True
for _ in range(500):
    fs, flat, dirs = FileSystem(), {}, {"/"}
    names = ["a", "b", "c"]
    for _ in range(60):
        depth = rng.randint(1, 3)
        path = "/" + "/".join(rng.choice(names) for _ in range(depth))
        op = rng.random()
        try:
            if op < 0.5:
                n = rng.randint(0, 100)
                fs.write(path, n)
                flat[path] = n                       # brute force: a flat path -> bytes table
                parts = path.split("/")[1:-1]
                dirs.update("/" + "/".join(parts[:i]) for i in range(1, len(parts) + 1))
            elif op < 0.7:
                fs.mkdir(path)
                parts = path.split("/")[1:]
                dirs.update("/" + "/".join(parts[:i]) for i in range(1, len(parts) + 1))
            else:
                fs.delete(path)
                flat = {p: v for p, v in flat.items() if p != path and not p.startswith(path + "/")}
                dirs = {d for d in dirs if d != path and not d.startswith(path + "/")}
        except (FileNotFoundError, NotADirectoryError, IsADirectoryError):
            pass                                     # the flat table was not touched either
    for d in dirs:
        under = sum(v for p, v in flat.items() if d == "/" or p.startswith(d + "/"))
        ok &= fs.size(d) == under == recompute(fs._walk(d))
    ok &= sorted(p for p in find(fs.root, lambda e: isinstance(e, File))) == sorted(flat)
print(ok)                                            # True

The complexity

With d the depth of a path and k the number of entries in a folder:

• Path resolution: O(d) dictionary lookups.
• write and delete: O(d), including the walk up to update cached totals.
• size: O(d) to find the entry, then O(1) with the cache; the pure composite is O(subtree).
• ls: O(k log k) to sort the names.
• find: O(n) over the subtree, unavoidable without an index.

Where it goes wrong

• isinstance checks in every caller. If size, find and printing each branch on the type, the contract has leaked. Put the behaviour in the classes.
• A stale cache. Cached totals must change on write, overwrite and delete, including subtracting the old size on overwrite.
• Following symlinks blindly. A link to an ancestor makes the recursion infinite. Report the link, or track visited folders.
• Lists of children. Scanning a list for a name makes every path step O(k) and allows duplicate names.

The same composite idea shows up with different names in SOLID, and the preference for delegation over subclassing in composition vs inheritance.

When it shows up in interviews

As "design an in-memory file system", often with the operations above spelled out, and as a warm-up before a parking lot or an elevator. Expect follow-ups on making size fast, adding symlinks or permissions, and how the flat alternative compares: a table keyed by full path makes lookups one step but turns every folder size and rename into a prefix scan.

How to say it in an interview

"I'd use the composite pattern: an Entry interface with name and size, a File leaf that returns its own bytes, and a Folder that holds children in a dict keyed by name and answers size by delegating to them. One resolver walks a path from the root and raises for missing or non-folder steps, and every operation uses it. If size is read often, each folder caches its total and writes update ancestors through parent pointers, so reads are constant time and writes cost the path depth. New kinds like symlinks are new classes, and I wouldn't follow links during traversal, so a link to an ancestor can't loop."