Design an in-memory file system

01The design, in the six-step framework

1. Requirements and use cases

A program creates directories with their missing parents, lists a directory in sorted order (listing a file gives its name), creates or appends to a file, reads it back, removes files and directories, and asks for the total size of any path. All paths are absolute. Operations on impossible paths fail with a specific error: a missing component, a file used as a directory, a directory read as a file, a non-empty directory removed without the recursive flag.

Out of scope: permissions, links (see the size and validation variant), relative paths with dots, and persistence.

Constraints: a path lookup costs its depth, not the number of files; appending must not copy the whole file; adding a new entry type, such as a symbolic link, should not edit every method. Single-threaded by default, with locking discussed in section 6.

2. Core entities and relationships

• Entry: the abstract base with a name, size and is_dir.
• File: content held as appended chunks plus a running size.
• Directory: a dict of children by name.
• FileSystem: the facade. It splits paths, walks the tree and turns failures into typed errors.
• FsError and its subclasses: one per failure a caller can react to.

This is a composite: Directory both is an Entry and composes Entries, so size on a directory is the sum of size on its children without asking what each child is. Composition is the right word, because deleting a directory deletes everything beneath it.

3. Interfaces and key methods

class Entry(ABC):
    name: str
    @abstractmethod
    def size(self) -> int: ...
    @abstractmethod
    def is_dir(self) -> bool: ...

class FileSystem:
    def mkdir(self, path: str) -> None:
        """Create the directory and any missing parents."""
    def ls(self, path: str) -> list[str]:
        """Sorted names in a directory, or [name] for a file."""
    def add_content(self, path: str, content: str) -> None:
        """Create the file if needed; append content."""
    def read_content(self, path: str) -> str: ...
    def rm(self, path: str, recursive: bool = False) -> None: ...
    def du(self, path: str) -> int: ...

Invariants: a name is unique within a directory; a child's name equals its key in children; the root always exists and cannot be removed; a File's _size equals the length of its joined chunks.

4. Design patterns and the choices behind them

Composite over a flat map of paths

A dictionary from full path to content makes read_content one lookup. It also makes ls a scan of every key, and a rename of a directory touches every descendant. A tree makes those operations local. Polymorphism on size removes the type check that would otherwise sit in du.

A tree of dicts is already a trie

Each directory's children map is a trie keyed by path segment, so lookup is proportional to depth. Sorting happens at ls time, O(k log k) for k children. Keeping a sorted structure would make inserts slower for a read that may never occur.

Specific errors at the facade

Callers need to tell "does not exist" from "is a file", in the same way an operating system returns different error codes. A single generic error or a None return was rejected because it pushes that logic onto every caller (see errors and validation).

Chunks for appends

Python strings are immutable, so appending to one copies it: n appends cost O(n²) in total. A list of chunks makes append O(1), and read joins and compacts. The running _size keeps size O(1) on files.

5. Core flow and code

1. mkdir("/a/b"): split yields a and b; each is created under the previous directory if absent.
2. add_content("/a/b/f.txt", "hello"): _parent walks to b, no entry exists, a File is created and the content appended.
3. add_content("/a/b/f.txt", " world") finds the File and appends a second chunk without touching the first.
4. read_content("/a/b/f.txt") walks to the File, joins the chunks, stores the joined text and returns it.
5. ls("/a") returns the sorted child names of a; ls("/a/b/f.txt") returns the single file name.
6. du("/a") calls size on Directory a, which recurses into b and reaches File.size, giving 11.
7. rm("/a") raises DirectoryNotEmpty; rm("/a", recursive=True) deletes the entry from the root's children, and the whole subtree goes with it.

from __future__ import annotations
from abc import ABC, abstractmethod

class FsError(Exception):
    pass
class NotFound(FsError):
    pass
class NotADirectory(FsError):
    pass
class IsADirectory(FsError):
    pass
class DirectoryNotEmpty(FsError):
    pass

class Entry(ABC):
    def __init__(self, name: str) -> None:
        self.name = name

    @abstractmethod
    def size(self) -> int: ...

    @abstractmethod
    def is_dir(self) -> bool: ...

class File(Entry):
    def __init__(self, name: str) -> None:
        super().__init__(name)
        self._chunks: list[str] = []
        self._size = 0

    def append(self, content: str) -> None:
        self._chunks.append(content)
        self._size += len(content)

    def read(self) -> str:
        if len(self._chunks) > 1:              # compact lazily so repeated reads are cheap
            self._chunks = ["".join(self._chunks)]
        return self._chunks[0] if self._chunks else ""

    def size(self) -> int:
        return self._size

    def is_dir(self) -> bool:
        return False

class Directory(Entry):
    def __init__(self, name: str) -> None:
        super().__init__(name)
        self.children: dict[str, Entry] = {}

    def size(self) -> int:
        return sum(child.size() for child in self.children.values())

    def is_dir(self) -> bool:
        return True

    def child_dir(self, name: str) -> "Directory":
        entry = self.children.get(name)
        if entry is None:
            raise NotFound(name)
        if not isinstance(entry, Directory):
            raise NotADirectory(name)
        return entry

def split(path: str) -> list[str]:
    if not path.startswith("/"):
        raise FsError(f"path must be absolute: {path!r}")
    return [p for p in path.split("/") if p]

class FileSystem:
    def __init__(self) -> None:
        self._root = Directory("")

    def _walk(self, parts: list[str]) -> Entry:
        node: Entry = self._root
        for part in parts:
            if not isinstance(node, Directory):
                raise NotADirectory(node.name)
            if part not in node.children:
                raise NotFound(part)
            node = node.children[part]
        return node

    def _parent(self, parts: list[str]) -> Directory:
        if not parts:
            raise FsError("the root has no parent")
        node = self._walk(parts[:-1])
        if not isinstance(node, Directory):
            raise NotADirectory(node.name)
        return node

    def mkdir(self, path: str) -> None:
        node = self._root
        for part in split(path):
            entry = node.children.get(part)
            if entry is None:
                entry = node.children[part] = Directory(part)
            if not isinstance(entry, Directory):
                raise NotADirectory(part)
            node = entry

    def ls(self, path: str) -> list[str]:
        entry = self._walk(split(path))
        if isinstance(entry, Directory):
            return sorted(entry.children)
        return [entry.name]

    def add_content(self, path: str, content: str) -> None:
        parts = split(path)
        parent = self._parent(parts)
        entry = parent.children.get(parts[-1])
        if entry is None:
            entry = parent.children[parts[-1]] = File(parts[-1])
        if not isinstance(entry, File):
            raise IsADirectory(path)
        entry.append(content)

    def read_content(self, path: str) -> str:
        entry = self._walk(split(path))
        if not isinstance(entry, File):
            raise IsADirectory(path)
        return entry.read()

    def rm(self, path: str, recursive: bool = False) -> None:
        parts = split(path)
        parent = self._parent(parts)
        entry = self._walk(parts)
        if isinstance(entry, Directory) and entry.children and not recursive:
            raise DirectoryNotEmpty(path)
        del parent.children[parts[-1]]

    def du(self, path: str) -> int:
        return self._walk(split(path)).size()

6. Extensions, concurrency and what interviewers probe

• Fast du: size on a directory is O(subtree). Caching a total on each directory needs parent pointers and an update walk on every change.
• Search: a find by name or size pattern is a tree walk with a pluggable predicate, a natural use of a specification object.
• Rename and move: re-attach the entry under a new parent, O(depth), which is the payoff of the tree. Guard against moving a directory into itself.
• Symbolic links: a third Entry subclass holding a target path. _walk must follow it with a hop limit, because a link can point at its own ancestor and loop forever.
• Thread safety: one global read-write lock is simple and correct. Per-directory locks allow more concurrency and need a strict top-down order to avoid deadlock.
• Test first: mkdir of a deep path; ls on a file and on an empty directory; add_content under a missing parent; mkdir through a file; rm of the root; appending twice then reading.
• Common mistake: isinstance checks spread through the size logic, and letting split("a/b") pass as if it were absolute.

02Where this question was reported

• Hello Interview · Hello Interview breakdown (Medium, premium)
• LLD Mastery · Google-tagged (Easy, free); hierarchical structures, path resolution; plus 'File Manager' (Hard)
• ByteByteGo · ByteByteGo OOD chapter 6 'Unix File Search System'
• Codemia · Codemia Hard
• System Design Handbook · System Design Handbook OOD example
• PracHub · PracHub OOD practice prompt
• thita.ai · thita.ai 'In-Memory File System', advanced
• LeetCode Discuss · LeetCode 588 (Hard), Google-tagged, freq 12.8; also in TechPrep's Google LLD list
• techprep.app · TechPrep Google LLD: https://www.techprep.app/problems/design-in-memory-file-system?topic=low-level-design
• LeetCode Discuss · LeetCode 1166 (Medium), Google-tagged, freq 12.8
• techprep.app · Typical Google LLD prompt; model directories vs files
• techprep.app · Same prompt listed for Google