Skip to content

Design an in-memory file system

TL;DR

  • You build a Composite tree (Node → File | Directory), a PathResolver that owns every string edge case, and a FileSystem service that holds the lock ordering.
  • Three decisions carry the interview: traversals are Visitors, not methods on Node (search, du and tree never touch the node classes), locks are per node with a fixed order by absolute path (so mv between two directories cannot deadlock), and rm unlinks rather than deletes (an open handle keeps the bytes alive, exactly like POSIX).
  • It is LeetCode 588 with the parts that matter added: mv into its own subtree is rejected, permissions sit behind a Proxy, and every operation is thread-safe.

Problem statement

"Design an in-memory file system. Support mkdir -p, creating and writing and appending and reading files, a sorted ls, recursive delete, move, copy, recursive size, and find by name or extension. Paths are absolute, with relative paths resolved against a working directory. Files and directories carry an owner, permission bits and timestamps. It has to behave correctly when several threads work on the tree at once, and you should be explicit about what happens at the awkward path cases."

Requirements

Functional

  • mkdir -p: create intermediate directories, idempotently.
  • Create, write (replace), append and read files; create fails if the file exists.
  • ls returning sorted names; a path that names a file lists that file (LeetCode 588 semantics).
  • rm, refusing a non-empty directory unless recursive.
  • mv (rename or move into a directory) and cp (deep copy).
  • Absolute path resolution, plus relative paths against a working directory.
  • find by name or by extension; recursive size; stat with owner, mode and timestamps.
  • Permission bits for the owner and for everyone else, enforced per user.
  • Timestamps from an injected clock.

Non-functional and constraints

  • Correct under concurrency: two threads calling mkdir -p on the same path both succeed and create one directory.
  • No global tree lock. Contention is per directory.
  • mv must never be able to detach a subtree from the root.
  • In-memory, single process, standard library only. Time is injected, so timestamp assertions are exact.

Out of scope: real persistence, symbolic and hard links, byte-range reads, extended attributes, and quotas. The distributed version is Design Dropbox or Google Drive.

Clarifying questions and assumptions

Question to ask Assumption taken here
Is ls on a file an error or does it list the file? It lists the file, matching LeetCode 588 — and it is the kind of question that shows you have read the spec.
What does .. at the root do? It stays at the root. /.. is /, not an error; that is what every real shell does.
Does a trailing slash matter? No. /a/b/ and //a///b both normalise to /a/b.
Where does mv /a /a/b land? Nowhere: it is rejected. Allowing it orphans the subtree, and the check is one string comparison.
Does rm free the bytes immediately? Only if nobody has the file open. Otherwise the node becomes UNLINKED and is released when the last handle closes.
One global lock or many? One lock per node. mv and cp take two, always ordered by absolute path.
Should permission checks live in FileSystem? No. They live in a SecureFileSystem proxy with the same surface, so the core stays readable.

Core entities and relationships

  • Node (abstract) — name, parent, owner, two permission masks, timestamps, status and its own RLock. Declares size(), accept(visitor) and is_directory().
  • File — a leaf. Content is a list of chunks so append is O(1) rather than O(size). Tracks open handles.
  • Directory — a composite: name → Node, with add, get_or_add (the atomic step behind mkdir -p), remove and a sorted children(). 1 → * children.
  • FileHandle — keeps an unlinked file alive; close() releases it when it is the last one.
  • PathResolver — pure string handling: normalize, split, parent, basename, join, is_ancestor. No tree, no locks.
  • FileSystem — the service: resolution, node creation, lock ordering, and the operations (mkdir, write, rm, mv, cp, find, walk).
  • NodeVisitor — SizeVisitor, SearchVisitor, TreeVisitor, StatVisitor. The visitor drives the recursion.
  • SecureFileSystem — the Proxy, holding a User; Permission, NodeStatus, NodeStat, SizeReport — the value vocabulary.

Class diagram

Structure: the Composite tree and the service that navigates it.

classDiagram
    class Node {
        <<abstract>>
        +name: str
        +owner: str
        +parent: Directory
        +status: NodeStatus
        +created: float
        +modified: float
        -_lock: RLock
        +size() int*
        +accept(visitor)*
        +is_directory() bool*
        +path() str
        +locked() Iterator
        +stat() NodeStat
    }
    class File {
        -_chunks: List~str~
        -_handles: int
        +read() str
        +write(content, now) int
        +append(content, now) int
        +open() FileHandle
        +unlink() NodeStatus
    }
    class Directory {
        -_children: Dict~str,Node~
        +add(node) Node
        +get_or_add(node) Node
        +remove(name) Node
        +children() List~Node~
        +names() List~str~
        +is_empty() bool
    }
    class FileHandle {
        +file: File
        +read() str
        +close()
    }
    class FileSystem {
        +root: Directory
        +resolve(path, cwd) Node
        +mkdir(path, parents) Directory
        +write(path, content) int
        +ls(path) List~str~
        +rm(path, recursive) Node
        +mv(source, destination) Node
        +cp(source, destination) Node
        +walk(path) Iterator
    }
    class PathResolver {
        +normalize(path, cwd) str
        +split(path, cwd) List~str~
        +parent(path) str
        +is_ancestor(ancestor, descendant) bool
    }
    class NodeStat {
        +path: str
        +size: int
        +mode() str
    }
    class NodeStatus {
        <<enumeration>>
        ACTIVE
        UNLINKED
        RELEASED
    }
    class Permission {
        <<enumeration>>
        NONE
        EXECUTE
        WRITE
        READ
        ALL
    }
    Node <|-- File
    Node <|-- Directory
    Directory "1" o-- "many" Node : children
    File "1" o-- "many" FileHandle
    FileSystem "1" *-- "1" Directory : root
    FileSystem ..> PathResolver : resolves with
    Node ..> NodeStat : stat
    Node --> NodeStatus
    Node --> Permission

Behaviour: traversals that live outside the tree, and the permission proxy in front of it.

classDiagram
    class NodeVisitor {
        <<interface>>
        +visit_file(file: File)
        +visit_directory(directory: Directory)
    }
    class SizeVisitor {
        +files: int
        +directories: int
        +total_bytes: int
        +largest_file: str
        +report() SizeReport
    }
    class SearchVisitor {
        +matches: List~str~
        +by_name(name) SearchVisitor
        +by_extension(extension) SearchVisitor
        +by_min_size(minimum) SearchVisitor
    }
    class TreeVisitor {
        +render() str
    }
    class StatVisitor {
        +stats: List~NodeStat~
    }
    class SizeReport {
        +files: int
        +directories: int
        +total_bytes: int
        +largest_file: str
    }
    class Node
    class File
    class Directory
    class FileSystem {
        +accept(visitor, path)
        +usage(path) SizeReport
        +find(path, name, extension) List~str~
        +tree(path) str
    }
    class SecureFileSystem {
        +user: User
        +read(path) str
        +write(path, content) int
        +ls(path) List~str~
        +rm(path, recursive) Node
    }
    class User {
        +name: str
        +is_admin: bool
    }
    NodeVisitor <|.. SizeVisitor
    NodeVisitor <|.. SearchVisitor
    NodeVisitor <|.. TreeVisitor
    NodeVisitor <|.. StatVisitor
    Node ..> NodeVisitor : accept
    File --|> Node
    Directory --|> Node
    FileSystem ..> NodeVisitor : drives
    SizeVisitor ..> SizeReport : produces
    SecureFileSystem --> "1" FileSystem : delegates to
    SecureFileSystem --> "1" User

Design patterns applied

Pattern Where Why it earns its place
Composite Node → File / Directory size() on a directory is sum(child.size()) and it is the same call on a leaf. Every recursive operation stops being a type check and becomes a recursive call.
Visitor SizeVisitor, SearchVisitor, TreeVisitor, StatVisitor Search, du, tree and a listing API are four traversals that have nothing to do with what a file is. Adding a fifth touches no node class. The visitor drives the recursion, so pruning is a one-line change.
Iterator FileSystem.walk A generator yielding (path, node) depth-first and sorted. Callers can stream a huge tree without materialising it, and walk snapshots each directory so a concurrent delete cannot break the loop.
Proxy SecureFileSystem Identical surface, permission checks in front. The core stays free of if user.can(...), and "run this batch job as root" is one line at the call site.
Factory Method mkdir / _file_for_write creating nodes Node creation is centralised, so a symlink or a device node becomes a third Node subclass and one branch, not a rewrite.
Strategy (light) SearchVisitor(predicate) by_name, by_extension and by_min_size are three predicates, not three classes.
Dependency Injection Clock Timestamps are asserted exactly (modified == 1_700_000_030) instead of being fuzzed with tolerances.

Deliberately not used: Singleton for FileSystem. It is tempting — there is "one" file system — but tests build dozens, and mounting a second in-memory volume should be a second object, not a redesign. Also not used: the Command pattern for undoable operations. It is a real option (rm becomes a command that keeps the unlinked subtree), but it doubles the surface, and the UNLINKED status already gives you the piece that actually matters. Say you considered it, and say what it would cost.

Key flows

write("/srv/app/main.py", data) — resolve, create the parents, get-or-create the file, stamp it.

sequenceDiagram
    autonumber
    actor C as Caller
    participant FS as FileSystem
    participant PR as PathResolver
    participant D as Directory srv/app
    participant F as File main.py
    participant CL as Clock
    C->>FS: write(/srv/app/main.py, data)
    FS->>PR: split(path, cwd)
    PR-->>FS: [srv, app, main.py]
    FS->>FS: mkdir(/srv/app) walking one level at a time
    loop each missing component
        FS->>D: get_or_add(Directory) under the directory lock
    end
    FS->>D: get_or_add(File main.py)
    alt the name already exists
        D-->>FS: the existing node
    else created now
        D-->>FS: the new file, parent linked
    end
    FS->>CL: now()
    CL-->>FS: 1700000000.0
    FS->>F: write(data, now) under the file lock
    F-->>C: bytes written

Path resolution, which is where most candidates lose points.

flowchart TD
    p_in["Input path plus cwd"] --> p_abs{"Starts with a separator"}
    p_abs -->|"no"| p_join["Prefix the working directory"]
    p_abs -->|"yes"| p_split["Split on the separator"]
    p_join --> p_split
    p_split --> p_loop["For each component"]
    p_loop --> p_empty{"Empty or a single dot"}
    p_empty -->|"yes"| p_skip["Skip: collapses repeats and a trailing separator"]
    p_empty -->|"no"| p_up{"Is it the parent marker"}
    p_up -->|"yes"| p_pop["Pop one component, or stay at the root"]
    p_up -->|"no"| p_name["validate_name, then push"]
    p_skip --> p_done
    p_pop --> p_done
    p_name --> p_done["Join into one absolute path"]
    p_done --> p_walk["Walk the tree: one dict lookup per component"]
    p_walk --> p_check{"Component resolves"}
    p_check -->|"missing"| p_nf["PathNotFoundError"]
    p_check -->|"a file in the middle"| p_nd["NotADirectoryError"]
    p_check -->|"yes"| p_node["Node"]

A node's life. UNLINKED is the state that makes rm on an open log file behave the way operators expect.

stateDiagram-v2
    [*] --> ACTIVE : created and linked into a directory
    ACTIVE --> UNLINKED : rm while a handle is open
    ACTIVE --> RELEASED : rm with no open handles
    UNLINKED --> RELEASED : last handle closed
    RELEASED --> [*]

Implementation

Start with the vocabulary. NodeStatus is the enum the state diagram draws, and Permission is an IntFlag so READ | WRITE is one value rather than a set.

code/lld/in_memory_file_system/models.py — statuses and permissions
class NodeStatus(StrEnum):
    """POSIX unlink semantics in three words.

    Removing a file takes it out of the directory tree, but the bytes survive
    while a handle is still open -- which is why ``rm`` on a log a process is
    writing does not free the disk until the process restarts.
    """

    ACTIVE = "active"  # reachable from the root
    UNLINKED = "unlinked"  # removed from its parent, still held by an open handle
    RELEASED = "released"  # last handle closed, storage reclaimed


class Permission(IntFlag):
    """The classic three bits. ``IntFlag`` so ``READ | WRITE`` is one value."""

    NONE = 0
    EXECUTE = 1  # on a directory: may traverse into it
    WRITE = 2
    READ = 4
    READ_WRITE = READ | WRITE
    ALL = READ | WRITE | EXECUTE

    def allows(self, needed: Permission) -> bool:
        return (self & needed) == needed
code/lld/in_memory_file_system/models.py — errors
class PathNotFoundError(NotFoundError):
    """No node at that path."""


class PathExistsError(ConflictError):
    """A node already exists where one was to be created."""


class NotADirectoryError_(ValidationError):
    """A path component that must be a directory is a file."""


class IsADirectoryError_(ValidationError):
    """A directory was passed where a file was required (or rm without -r)."""


class InvalidPathError(ValidationError):
    """Empty path, empty component, or a name that is too long."""


class DirectoryNotEmptyError(ConflictError):
    """rm on a non-empty directory without the recursive flag."""


class RecursiveMoveError(ConflictError):
    """mv of a directory into its own subtree."""


class PermissionDeniedError(ConflictError):
    """The user lacks a required bit on the node or on a parent directory."""


class NodeReleasedError(InvalidStateError):
    """Operation on a handle whose file has already been released."""

Write the resolver next, and write it as pure string handling. Keeping it away from the tree is what lets you test nine edge cases in one parametrize and never think about them again.

code/lld/in_memory_file_system/paths.py
class PathResolver:
    """Pure string handling -- no tree, no locks, therefore trivially testable.

    Keeping resolution out of ``FileSystem`` is deliberate: the tricky cases are
    ``//`` runs, a trailing slash, ``.``, ``..`` past the root, and relative
    paths against a working directory. All of them are decided here, once.
    """

    @staticmethod
    def normalize(path: str, cwd: str = ROOT) -> str:
        """Absolute, separator-collapsed, dot-free. ``..`` at the root stays at the root."""
        if not path or not path.strip():
            raise InvalidPathError("path must be a non-empty string")
        raw = path if path.startswith(SEPARATOR) else f"{cwd.rstrip(SEPARATOR)}{SEPARATOR}{path}"
        parts: list[str] = []
        for part in raw.split(SEPARATOR):
            if part in ("", "."):
                continue  # collapses "//" and a trailing "/"
            if part == "..":
                if parts:
                    parts.pop()  # "/.." is "/", never an error
                continue
            parts.append(validate_name(part))
        return ROOT + SEPARATOR.join(parts)

    @staticmethod
    def split(path: str, cwd: str = ROOT) -> list[str]:
        normalized = PathResolver.normalize(path, cwd)
        return [] if normalized == ROOT else normalized.lstrip(SEPARATOR).split(SEPARATOR)

    @staticmethod
    def parent(path: str, cwd: str = ROOT) -> str:
        parts = PathResolver.split(path, cwd)
        return ROOT + SEPARATOR.join(parts[:-1])

    @staticmethod
    def basename(path: str, cwd: str = ROOT) -> str:
        parts = PathResolver.split(path, cwd)
        return parts[-1] if parts else ""

    @staticmethod
    def join(*parts: str) -> str:
        joined = SEPARATOR.join(part.strip(SEPARATOR) for part in parts if part.strip(SEPARATOR))
        return ROOT + joined

    @staticmethod
    def is_ancestor(ancestor: str, descendant: str) -> bool:
        """``/a`` is an ancestor of ``/a/b`` but not of ``/ab`` -- the check mv needs."""
        if ancestor == ROOT:
            return True
        return descendant == ancestor or descendant.startswith(ancestor + SEPARATOR)

Now the Composite. Node declares the three things every node answers, and it owns the lock — there is no lock anywhere above it.

code/lld/in_memory_file_system/nodes.py — the base
class Node(ABC):
    """Composite base: a file and a directory answer the same questions.

    Every node owns an ``RLock``. A directory's lock guards its children dict;
    a file's lock guards its content. Nothing guards the whole tree, so two
    threads working in different directories never meet.
    """

    def __init__(
        self,
        name: str,
        clock: Clock,
        owner: str = "root",
        owner_permissions: Permission = Permission.ALL,
        other_permissions: Permission = Permission.READ | Permission.EXECUTE,
    ) -> None:
        self.name = validate_name(name) if name else name  # only the root is nameless
        self.owner = owner
        self.owner_permissions = owner_permissions
        self.other_permissions = other_permissions
        self.parent: Directory | None = None
        self.status = NodeStatus.ACTIVE
        self.created = clock.now()
        self.modified = self.created
        self._lock = threading.RLock()

    @abstractmethod
    def size(self) -> int:
        """Composite: a file knows its bytes, a directory sums its children."""

    @abstractmethod
    def accept(self, visitor: NodeVisitor) -> None:
        """Visitor: double dispatch, so new traversals need no change here."""

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

    def path(self) -> str:
        parts: list[str] = []
        node: Node | None = self
        while node is not None and node.parent is not None:
            parts.append(node.name)
            node = node.parent
        return "/" + "/".join(reversed(parts))

    @contextmanager
    def locked(self) -> Iterator[None]:
        """Public handle on this node's lock, so services can order acquisitions."""
        with self._lock:
            yield

    def touch(self, now: float) -> None:
        with self._lock:
            self.modified = now

    def effective_permissions(self, user_name: str, is_admin: bool = False) -> Permission:
        if is_admin or user_name == self.owner:
            return self.owner_permissions
        return self.other_permissions

    def stat(self) -> NodeStat:
        with self._lock:
            return NodeStat(
                path=self.path(),
                is_directory=self.is_directory(),
                size=self.size(),
                owner=self.owner,
                status=self.status,
                created=self.created,
                modified=self.modified,
                owner_permissions=self.owner_permissions,
                other_permissions=self.other_permissions,
            )

    def __repr__(self) -> str:
        return f"{type(self).__name__}({self.path()!r})"

The leaf stores chunks rather than one string, so appending a log line is O(1). unlink and close_handle are the whole POSIX story in twelve lines.

code/lld/in_memory_file_system/nodes.py — files and handles
class File(Node):
    """A leaf. Content is a list of chunks so append is O(1), not O(size)."""

    def __init__(self, name: str, clock: Clock, owner: str = "root") -> None:
        super().__init__(name, clock, owner, Permission.READ_WRITE, Permission.READ)
        self._chunks: list[str] = []
        self._size = 0
        self._handles = 0

    def is_directory(self) -> bool:
        return False

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

    def read(self) -> str:
        with self._lock:
            self._require_readable()
            return "".join(self._chunks)

    def write(self, content: str, now: float) -> int:
        with self._lock:
            self._require_readable()
            self._chunks = [content]
            self._size = len(content)
            self.modified = now
            return self._size

    def append(self, content: str, now: float) -> int:
        with self._lock:
            self._require_readable()
            self._chunks.append(content)
            self._size += len(content)
            self.modified = now
            return self._size

    def accept(self, visitor: NodeVisitor) -> None:
        visitor.visit_file(self)

    def open(self) -> FileHandle:
        """An open handle keeps the bytes alive after ``rm`` -- POSIX unlink semantics."""
        with self._lock:
            self._require_readable()
            self._handles += 1
            return FileHandle(self)

    def close_handle(self) -> None:
        with self._lock:
            self._handles = max(0, self._handles - 1)
            if self._handles == 0 and self.status is NodeStatus.UNLINKED:
                self._release_locked()

    def unlink(self) -> NodeStatus:
        """Removed from the tree. Released now if nobody has it open."""
        with self._lock:
            self.status = NodeStatus.UNLINKED
            if self._handles == 0:
                self._release_locked()
            return self.status

    def open_handles(self) -> int:
        with self._lock:
            return self._handles

    def _release_locked(self) -> None:
        self._chunks = []
        self._size = 0
        self.status = NodeStatus.RELEASED

    def _require_readable(self) -> None:
        if self.status is NodeStatus.RELEASED:
            raise NodeReleasedError(f"{self.name} has been released")


class FileHandle:
    """Proof that the file outlives its directory entry while someone holds it."""

    def __init__(self, file: File) -> None:
        self.file = file
        self._closed = False

    def read(self) -> str:
        return self.file.read()

    def append(self, content: str, now: float) -> int:
        return self.file.append(content, now)

    def close(self) -> None:
        if not self._closed:
            self._closed = True
            self.file.close_handle()

    def __enter__(self) -> FileHandle:
        return self

    def __exit__(self, *exc: object) -> None:
        self.close()

The composite is a dict plus a lock. get_or_add is the method that makes mkdir -p correct under contention: the check and the insert happen inside one critical section.

code/lld/in_memory_file_system/nodes.py — directories
class Directory(Node):
    """A composite. Its lock guards the children dict and nothing else."""

    def __init__(self, name: str, clock: Clock, owner: str = "root") -> None:
        super().__init__(name, clock, owner)
        self._children: dict[str, Node] = {}

    def is_directory(self) -> bool:
        return True

    def size(self) -> int:
        with self._lock:
            children = list(self._children.values())
        return sum(child.size() for child in children)  # recursion outside our own lock

    def accept(self, visitor: NodeVisitor) -> None:
        visitor.visit_directory(self)

    def add(self, node: Node) -> Node:
        with self._lock:
            if node.name in self._children:
                raise PathExistsError(f"{node.name} already exists in {self.path() or '/'}")
            self._children[node.name] = node
            node.parent = self
            return node

    def get_or_add(self, node: Node) -> Node:
        """mkdir -p: idempotent under contention, because it decides under the lock."""
        with self._lock:
            existing = self._children.get(node.name)
            if existing is not None:
                return existing
            self._children[node.name] = node
            node.parent = self
            return node

    def remove(self, name: str) -> Node:
        with self._lock:
            node = self._children.pop(name, None)
            if node is None:
                raise PathNotFoundError(f"{name} not found in {self.path() or '/'}")
            node.parent = None
            return node

    def get(self, name: str) -> Node | None:
        with self._lock:
            return self._children.get(name)

    def children(self) -> list[Node]:
        with self._lock:
            return [self._children[name] for name in sorted(self._children)]

    def names(self) -> list[str]:
        with self._lock:
            return sorted(self._children)

    def is_empty(self) -> bool:
        with self._lock:
            return not self._children

    def unlink(self) -> NodeStatus:
        with self._lock:
            self.status = NodeStatus.RELEASED
            return self.status

The visitors are where the Visitor pattern justifies itself. Note that Directory.size() already exists from Composite — the visitors are for the operations you would not put on a node.

code/lld/in_memory_file_system/visitors.py — the interface
class NodeVisitor(Protocol):
    """Double dispatch: the node calls back the method for its own type."""

    def visit_file(self, file: File) -> None: ...
    def visit_directory(self, directory: Directory) -> None: ...
code/lld/in_memory_file_system/visitors.py — four traversals
class SizeVisitor:
    """One traversal, four answers -- the reason this is not a method on Node."""

    def __init__(self) -> None:
        self.files = 0
        self.directories = 0
        self.total_bytes = 0
        self.largest_file: str | None = None
        self._largest = -1

    def visit_file(self, file: File) -> None:
        size = file.size()
        self.files += 1
        self.total_bytes += size
        if size > self._largest:
            self._largest, self.largest_file = size, file.path()

    def visit_directory(self, directory: Directory) -> None:
        self.directories += 1
        for child in directory.children():  # the visitor drives the recursion
            child.accept(self)

    def report(self) -> SizeReport:
        return SizeReport(self.files, self.directories, self.total_bytes, self.largest_file)


class SearchVisitor:
    """find(1) as an object. The predicate is the only thing that varies."""

    def __init__(self, predicate: Callable[[Node], bool]) -> None:
        self._predicate = predicate
        self.matches: list[str] = []

    def visit_file(self, file: File) -> None:
        if self._predicate(file):
            self.matches.append(file.path())

    def visit_directory(self, directory: Directory) -> None:
        if self._predicate(directory):
            self.matches.append(directory.path())
        for child in directory.children():
            child.accept(self)

    @staticmethod
    def by_name(name: str) -> SearchVisitor:
        return SearchVisitor(lambda node: node.name == name)

    @staticmethod
    def by_extension(extension: str) -> SearchVisitor:
        suffix = extension if extension.startswith(".") else f".{extension}"
        return SearchVisitor(lambda node: not node.is_directory() and node.name.endswith(suffix))

    @staticmethod
    def by_min_size(minimum: int) -> SearchVisitor:
        return SearchVisitor(lambda node: not node.is_directory() and node.size() >= minimum)


class TreeVisitor:
    """Renders ``tree(1)``. Purely presentational, and therefore not on Node."""

    def __init__(self) -> None:
        self.lines: list[str] = []
        self._depth = 0

    def visit_file(self, file: File) -> None:
        self.lines.append(f"{'  ' * self._depth}{file.name} ({file.size()}B)")

    def visit_directory(self, directory: Directory) -> None:
        self.lines.append(f"{'  ' * self._depth}{directory.name or ''}/")
        self._depth += 1
        for child in directory.children():
            child.accept(self)
        self._depth -= 1

    def render(self) -> str:
        return "\n".join(self.lines)


class StatVisitor:
    """Collects a stat record per node -- the shape a listing API would return."""

    def __init__(self) -> None:
        self.stats: list[NodeStat] = []

    def visit_file(self, file: File) -> None:
        self.stats.append(file.stat())

    def visit_directory(self, directory: Directory) -> None:
        self.stats.append(directory.stat())
        for child in directory.children():
            child.accept(self)

Finally the service. Read mv first: the subtree check, the destination rules, and _two_locks sorting by absolute path are the three things an interviewer is looking for.

code/lld/in_memory_file_system/services.py — the file system
class FileSystem:
    """The service. It owns path resolution, node creation and the lock ordering.

    There is no global tree lock. Structural changes take the lock of the
    *directory* they mutate; the two operations that touch two directories --
    ``mv`` and ``cp`` -- take both, always sorted by absolute path, so two
    threads swapping files between the same pair cannot deadlock.
    """

    def __init__(self, clock: Clock | None = None, owner: str = "root") -> None:
        self._clock = clock or SystemClock()
        self.root = Directory("", self._clock, owner)
        self._owner = owner

    # --- resolution ----------------------------------------------------------------
    def resolve(self, path: str, cwd: str = ROOT) -> Node:
        node: Node = self.root
        for index, part in enumerate(PathResolver.split(path, cwd)):
            if not node.is_directory():
                raise NotADirectoryError_(f"{'/'.join(PathResolver.split(path, cwd)[:index])} is not a directory")
            child = node.get(part)  # type: ignore[union-attr]
            if child is None:
                raise PathNotFoundError(f"{PathResolver.normalize(path, cwd)} does not exist")
            node = child
        return node

    def exists(self, path: str, cwd: str = ROOT) -> bool:
        try:
            self.resolve(path, cwd)
        except (PathNotFoundError, NotADirectoryError_):
            return False
        return True

    def stat(self, path: str, cwd: str = ROOT) -> NodeStat:
        return self.resolve(path, cwd).stat()

    # --- directories ---------------------------------------------------------------
    def mkdir(self, path: str, parents: bool = True, cwd: str = ROOT) -> Directory:
        """``mkdir -p`` by default: idempotent, and safe when two threads race on it."""
        parts = PathResolver.split(path, cwd)
        if not parts:
            return self.root
        node: Directory = self.root
        for index, part in enumerate(parts):
            last = index == len(parts) - 1
            existing = node.get(part)
            if existing is not None:
                if not existing.is_directory():
                    raise NotADirectoryError_(f"{existing.path()} is a file")
                if last and not parents:
                    raise PathExistsError(f"{existing.path()} already exists")
                node = existing  # type: ignore[assignment]
                continue
            if not parents and not last:
                raise PathNotFoundError(f"{node.path() or ROOT} has no child {part}")
            node = node.get_or_add(Directory(part, self._clock, self._owner))  # type: ignore[assignment]
        return node

    def ls(self, path: str = ROOT, cwd: str = ROOT) -> list[str]:
        """LeetCode 588 semantics: a directory lists its sorted children, a file lists itself."""
        node = self.resolve(path, cwd)
        return node.names() if node.is_directory() else [node.name]  # type: ignore[union-attr]

    def walk(self, path: str = ROOT, cwd: str = ROOT) -> Iterator[tuple[str, Node]]:
        """Iterator: depth-first, name-sorted, and a snapshot at each level."""
        node = self.resolve(path, cwd)
        yield node.path() or ROOT, node
        if node.is_directory():
            for child in node.children():  # type: ignore[union-attr]
                yield from self.walk(child.path(), cwd)

    # --- files ----------------------------------------------------------------------
    def create(self, path: str, cwd: str = ROOT) -> File:
        parent, name = self._parent_for(path, cwd, create=True)
        return parent.add(File(name, self._clock, self._owner))  # type: ignore[return-value]

    def write(self, path: str, content: str, cwd: str = ROOT) -> int:
        """Resolve (creating parents), get-or-create the file, replace its content."""
        file = self._file_for_write(path, cwd)
        return file.write(content, self._clock.now())

    def append(self, path: str, content: str, cwd: str = ROOT) -> int:
        file = self._file_for_write(path, cwd)
        return file.append(content, self._clock.now())

    def read(self, path: str, cwd: str = ROOT) -> str:
        node = self.resolve(path, cwd)
        if node.is_directory():
            raise IsADirectoryError_(f"{node.path()} is a directory")
        return node.read()  # type: ignore[union-attr]

    def open(self, path: str, cwd: str = ROOT) -> FileHandle:
        node = self.resolve(path, cwd)
        if node.is_directory():
            raise IsADirectoryError_(f"{node.path()} is a directory")
        return node.open()  # type: ignore[union-attr]

    def _file_for_write(self, path: str, cwd: str) -> File:
        parent, name = self._parent_for(path, cwd, create=True)
        existing = parent.get_or_add(File(name, self._clock, self._owner))
        if existing.is_directory():
            raise IsADirectoryError_(f"{existing.path()} is a directory")
        parent.touch(self._clock.now())
        return existing  # type: ignore[return-value]

    # --- structure ------------------------------------------------------------------
    def rm(self, path: str, recursive: bool = False, cwd: str = ROOT) -> Node:
        target = PathResolver.normalize(path, cwd)
        if target == ROOT:
            raise InvalidPathError("cannot remove the root")
        node = self.resolve(target)
        if node.is_directory() and not node.is_empty() and not recursive:  # type: ignore[union-attr]
            raise DirectoryNotEmptyError(f"{target} is not empty; use recursive=True")
        parent = node.parent
        if parent is None:  # already detached by a concurrent rm
            raise PathNotFoundError(f"{target} is no longer linked")
        with parent.locked():
            parent.remove(node.name)
            parent.modified = self._clock.now()
        self._unlink_subtree(node)
        return node

    def mv(self, source: str, destination: str, cwd: str = ROOT) -> Node:
        """Rename or move. A directory may never be moved into its own subtree."""
        src = PathResolver.normalize(source, cwd)
        dst = PathResolver.normalize(destination, cwd)
        if src == ROOT:
            raise InvalidPathError("cannot move the root")
        node = self.resolve(src)
        if node.is_directory() and PathResolver.is_ancestor(src, dst):
            raise RecursiveMoveError(f"cannot move {src} into its own subtree ({dst})")

        target_parent, target_name = self._destination_for(node, dst)
        old_parent = node.parent
        if old_parent is None:
            raise PathNotFoundError(f"{src} is no longer linked")
        with self._two_locks(old_parent, target_parent):
            if target_parent.get(target_name) is not None:
                raise PathExistsError(f"{PathResolver.join(target_parent.path(), target_name)} already exists")
            old_parent.remove(node.name)
            node.name = target_name
            target_parent.add(node)
            now = self._clock.now()
            old_parent.modified = target_parent.modified = node.modified = now
        return node

    def cp(self, source: str, destination: str, cwd: str = ROOT) -> Node:
        """Deep copy. The clone is a new subtree with fresh timestamps."""
        node = self.resolve(source, cwd)
        dst = PathResolver.normalize(destination, cwd)
        target_parent, target_name = self._destination_for(node, dst)
        clone = self._clone(node, target_name)
        with target_parent.locked():
            target_parent.add(clone)
            target_parent.modified = self._clock.now()
        return clone

    # --- queries ---------------------------------------------------------------------
    def size(self, path: str = ROOT, cwd: str = ROOT) -> int:
        return self.resolve(path, cwd).size()

    def usage(self, path: str = ROOT, cwd: str = ROOT) -> SizeReport:
        visitor = SizeVisitor()
        self.accept(visitor, path, cwd)
        return visitor.report()

    def find(self, path: str = ROOT, name: str | None = None, extension: str | None = None, cwd: str = ROOT) -> list[str]:
        if name is not None:
            visitor = SearchVisitor.by_name(name)
        elif extension is not None:
            visitor = SearchVisitor.by_extension(extension)
        else:
            raise InvalidPathError("find needs a name or an extension")
        self.accept(visitor, path, cwd)
        return visitor.matches

    def tree(self, path: str = ROOT, cwd: str = ROOT) -> str:
        visitor = TreeVisitor()
        self.accept(visitor, path, cwd)
        return visitor.render()

    def accept(self, visitor: NodeVisitor, path: str = ROOT, cwd: str = ROOT) -> None:
        self.resolve(path, cwd).accept(visitor)

    def chmod(self, path: str, owner_permissions: Permission, other_permissions: Permission, cwd: str = ROOT) -> NodeStat:
        node = self.resolve(path, cwd)
        with node.locked():
            node.owner_permissions = owner_permissions
            node.other_permissions = other_permissions
            node.modified = self._clock.now()
        return node.stat()

    # --- internals --------------------------------------------------------------------
    def _parent_for(self, path: str, cwd: str, create: bool) -> tuple[Directory, str]:
        parts = PathResolver.split(path, cwd)
        if not parts:
            raise InvalidPathError("a file needs a name")
        parent_path = PathResolver.join(*parts[:-1]) if parts[:-1] else ROOT
        parent = self.mkdir(parent_path) if create else self.resolve(parent_path)
        if not parent.is_directory():
            raise NotADirectoryError_(f"{parent_path} is not a directory")
        return parent, parts[-1]  # type: ignore[return-value]

    def _destination_for(self, node: Node, dst: str) -> tuple[Directory, str]:
        """``mv a b/`` where b exists means "into b"; otherwise b is the new name."""
        if self.exists(dst):
            existing = self.resolve(dst)
            if existing.is_directory():
                return existing, node.name  # type: ignore[return-value]
            raise PathExistsError(f"{dst} already exists")
        parent, name = self._parent_for(dst, ROOT, create=False)
        return parent, name

    def _clone(self, node: Node, name: str) -> Node:
        if not node.is_directory():
            clone = File(name, self._clock, node.owner)
            clone.write(node.read(), self._clock.now())  # type: ignore[union-attr]
            return clone
        directory = Directory(name, self._clock, node.owner)
        for child in node.children():  # type: ignore[union-attr]
            directory.add(self._clone(child, child.name))
        return directory

    def _unlink_subtree(self, node: Node) -> None:
        if node.is_directory():
            for child in node.children():  # type: ignore[union-attr]
                self._unlink_subtree(child)
        node.unlink()  # type: ignore[union-attr]

    @contextmanager
    def _two_locks(self, first: Node, second: Node) -> Iterator[None]:
        """Always by absolute path: one global order means no lock cycle."""
        if first is second:
            with first.locked():
                yield
            return
        low, high = sorted((first, second), key=lambda node: node.path())
        with low.locked(), high.locked():
            yield

The proxy is short, which is the point — it adds one concern and delegates everything else. The one subtlety is _require_parent: it walks up to the nearest ancestor that exists, because mkdir creates every missing level, so checking only the immediate parent lets mkdir /private/deep/sub build a whole chain inside a directory the caller cannot write to without any check running at all.

code/lld/in_memory_file_system/services.py — the permission proxy
class SecureFileSystem:
    """Proxy: the same surface as ``FileSystem``, with a permission check first.

    Putting the checks in a proxy rather than inside every method keeps the core
    readable and makes "run this batch job as root" a one-line change of user.
    """

    def __init__(self, filesystem: FileSystem, user: User) -> None:
        self._fs = filesystem
        self.user = user

    def read(self, path: str) -> str:
        self._require(path, Permission.READ)
        return self._fs.read(path)

    def write(self, path: str, content: str) -> int:
        self._require_parent(path, Permission.WRITE)
        if self._fs.exists(path):
            self._require(path, Permission.WRITE)
        return self._fs.write(path, content)

    def ls(self, path: str = ROOT) -> list[str]:
        self._require(path, Permission.READ | Permission.EXECUTE)
        return self._fs.ls(path)

    def mkdir(self, path: str) -> Directory:
        self._require_parent(path, Permission.WRITE)
        return self._fs.mkdir(path)

    def rm(self, path: str, recursive: bool = False) -> Node:
        self._require_parent(path, Permission.WRITE)
        return self._fs.rm(path, recursive)

    def stat(self, path: str) -> NodeStat:
        self._require(path, Permission.READ)
        return self._fs.stat(path)

    def _require(self, path: str, needed: Permission) -> Node:
        node = self._fs.resolve(path)
        granted = node.effective_permissions(self.user.name, self.user.is_admin)
        if not granted.allows(needed):
            raise PermissionDeniedError(f"{self.user.name} lacks {needed.name} on {node.path() or ROOT}")
        return node

    def _require_parent(self, path: str, needed: Permission) -> None:
        """Check the nearest ancestor that *exists*, not just the immediate parent.

        Stopping at a missing parent is a hole, because ``mkdir`` creates every
        level: ``mkdir /private/deep/sub`` under a root-only ``/private`` would
        find no ``/private/deep`` to check, run no check at all, and create the
        chain anyway. The root always exists, so the walk terminates.
        """
        current = PathResolver.parent(path)
        while current != ROOT and not self._fs.exists(current):
            current = PathResolver.parent(current)
        self._require(current, needed)

Running python -m lld.in_memory_file_system.demo:

ls /srv/app -> ['README.md', 'logs', 'main.py']
read log    -> 'boot\nready\n'
path edge cases: ['README.md', 'logs', 'main.py'] == ['README.md', 'logs', 'main.py']
du /srv: 29B in 3 files, 3 dirs, largest /srv/app/main.py
find *.log  -> ['/srv/app/logs/app.log']
after mv: /srv -> ['README.md', 'app'], /srv/app -> ['logs', 'main.py']
rejected: cannot move /srv/app into its own subtree (/srv/app/logs/app)
rm with a handle open -> status=unlinked, still readable: 'boot\nready\n'
after close -> status=released
guest denied: guest lacks READ on /srv/app/main.py
root allowed: "print('hi')\n"
cp -r /srv/app /backup -> ['logs', 'main.py'], 12B
rm -r /srv -> status=released, released=True, root now ['backup']
backup/
  logs/
  main.py (12B)

Concurrency and edge cases

Which lock protects what. One per node, and no lock above them:

  1. Directory._lock guards that directory's children dict. Two threads creating files in different directories never contend. This is the granularity that matters: a global tree lock would serialise every operation in the system, and a lock per file alone would leave the dict unprotected.
  2. File._lock guards the chunk list, the size counter and the handle count. Three hundred threads appending to one log serialise here and every line survives.
  3. Two directories, one fixed order. mv and cp take both parents through _two_locks, which sorts them by absolute path. Two threads moving files in opposite directions between /a and /b therefore acquire in the same order and cannot form a cycle. Naming this ordering rule is the single highest-value sentence in the concurrency section.

The race get_or_add prevents. mkdir -p /shared/dir-0 from eight threads at once: a naive if not exists: add() has a window between the check and the insert, and the losers get PathExistsError for a path that should be idempotent. Deciding under the lock makes the loser return the winner's directory instead. The concurrency test runs 200 such calls across four directories and asserts exactly five directories exist afterwards.

mv into its own subtree. PathResolver.is_ancestor(src, dst) is checked before anything is locked. Without it, mv /a /a/b leaves /a referenced only by its own descendant — a cycle unreachable from the root, invisible to ls and a permanent leak. Note that the check compares components, not string prefixes: /a is an ancestor of /a/b but not of /ab.

Delete while iterating. Directory.children() returns a sorted snapshot taken under the lock, and Directory.size() releases its own lock before recursing. So a concurrent rm during a walk or a du yields a slightly stale view rather than a RuntimeError; the traversal never sees a half-mutated dict.

rm on an open file. The directory entry disappears immediately, the node moves to UNLINKED, and the bytes stay readable through the handle until the last close() moves it to RELEASED. This is why deleting a log file does not free space until the writing process restarts, and saying so signals operational experience.

Path edge cases handled: / normalises to /; a trailing slash and repeated separators collapse; . is dropped; .. pops one component and is a no-op at the root; relative paths resolve against a working directory; a component that is a file in the middle of a path raises NotADirectoryError; empty and whitespace-only paths are rejected; names are validated (no separators, no reserved words, at most 255 characters).

Cost model. Resolution is one dict lookup per component, so /a/b/c/d.txt costs about four main-memory references at ~100 ns each — call it 400 ns. A real file system doing one 4 KB SSD read per inode would spend ~16 µs per level, roughly 40 times more per component; that gap is the whole reason page caches exist. The ceiling is memory: at roughly 1 KB per small file including content, a million files is about 1 GB and fits comfortably on a 64–512 GB box, while a hundred million does not — which is where this becomes a storage design problem.

Common mistake

Wrapping every operation in one global lock and calling it thread-safe. It is safe and it is useless: ls on an unrelated directory now waits behind a large cp. The other half of the same mistake is going per-node without defining an acquisition order — the first two-directory mv under load deadlocks, and it will not reproduce on your laptop. Per-node locks plus "always sorted by absolute path" is the answer, and it is one contextmanager.

Extensibility and follow-ups

  • LeetCode 588 parity is already there: ls, mkdir, addContentToFile and readContentFromFile map to ls, mkdir, append and read, including "ls on a file returns the file name". A test walks the exact example sequence from the problem.
  • Quotas: a QuotaVisitor accumulating bytes per owner, plus a check in _file_for_write. The visitor already exists in spirit — SizeVisitor with a grouping key.
  • Symlinks: a third Node subclass holding a target path. Resolution follows it with a depth limit (POSIX uses 40) to break cycles, and is_ancestor must then be checked on the resolved path, which is a good thing to mention before it becomes a bug.
  • Versioning: File already keeps chunks; keep a list of (version, chunks) and have read take an optional version. Copy-on-write makes a snapshot O(1).
  • Sharing and ACLs: the Permission masks become an ACL list, and SecureFileSystem grows a group lookup. Nothing in the tree changes, which is the payoff for putting the checks in a proxy.
  • Undoable operations: give each mutation a Command with the unlinked subtree kept alive, and rm becomes a trash bin.
  • Going distributed is the hand-off: chunking, content-addressed blocks, metadata sharded separately from data, and sync conflicts — see Design Dropbox or Google Drive.

Interview tip

Draw the Composite in the first five minutes, then immediately say "traversals go in Visitors, not on Node" and give one example the interviewer did not ask for (du, tree, quota). Then name the lock ordering rule. Those two moves cover the two things this problem is actually testing, and both take ten seconds to say.

Tests

tests/test_in_memory_file_system.py has 30 cases (15 functions, two of them parameterised). The four worth walking through are the happy path, path normalisation, mv, and concurrency.

The happy path pins mkdir -p, append, sorted ls, recursive size, the injected clock and the LeetCode ls-on-a-file rule in six assertions:

code/lld/in_memory_file_system/tests/test_in_memory_file_system.py — happy path
def test_mkdir_write_read_and_ls(fs: FileSystem, clock: FakeClock) -> None:
    fs.mkdir("/srv/app/logs")
    fs.write("/srv/app/main.py", "print('hi')\n")
    clock.advance(30)
    fs.append("/srv/app/logs/app.log", "boot\n")
    fs.append("/srv/app/logs/app.log", "ready\n")

    assert fs.ls("/srv/app") == ["logs", "main.py"]  # sorted, always
    assert fs.read("/srv/app/logs/app.log") == "boot\nready\n"
    assert fs.size("/srv") == 12 + 11  # Composite sums the subtree
    assert fs.stat("/srv/app/logs/app.log").modified == 1_700_000_030
    assert fs.ls("/srv/app/main.py") == ["main.py"]  # LeetCode 588: a file lists itself

Path normalisation is a table, because that is what it is. Nine rows, one line each, and the is_ancestor test that keeps /ab from looking like a child of /a:

code/lld/in_memory_file_system/tests/test_in_memory_file_system.py — path edge cases
@pytest.mark.parametrize(
    ("raw", "cwd", "expected"),
    [
        ("/", "/", "/"),
        ("/a/b/", "/", "/a/b"),  # trailing slash
        ("//a///b", "/", "/a/b"),  # repeated separators
        ("/a/./b", "/", "/a/b"),  # "." components
        ("/a/b/..", "/", "/a"),  # parent
        ("/..", "/", "/"),  # ".." past the root is the root, not an error
        ("/a/../../b", "/", "/b"),
        ("b/c", "/a", "/a/b/c"),  # relative to a working directory
        ("../c", "/a/b", "/a/c"),
    ],
)
def test_path_normalisation_edge_cases(raw: str, cwd: str, expected: str) -> None:
    assert PathResolver.normalize(raw, cwd) == expected


def test_is_ancestor_does_not_confuse_a_prefix_with_a_parent() -> None:
    assert PathResolver.is_ancestor("/a", "/a/b") is True
    assert PathResolver.is_ancestor("/a", "/ab") is False
    assert PathResolver.is_ancestor("/a", "/a") is True

The mv test covers all four behaviours in one narrative — move up, move into an existing directory, refuse the subtree, refuse an existing name:

code/lld/in_memory_file_system/tests/test_in_memory_file_system.py — move
def test_mv_renames_moves_and_refuses_its_own_subtree(fs: FileSystem) -> None:
    fs.mkdir("/srv/app/logs")
    fs.write("/srv/app/README.md", "# app")

    fs.mv("/srv/app/README.md", "/srv/README.md")  # move up a level
    assert fs.ls("/srv") == ["README.md", "app"] and fs.ls("/srv/app") == ["logs"]

    fs.mv("/srv/README.md", "/srv/app")  # destination is a directory: move into it
    assert fs.ls("/srv/app") == ["README.md", "logs"]

    with pytest.raises(RecursiveMoveError):
        fs.mv("/srv/app", "/srv/app/logs/app")  # would detach the subtree from the root
    with pytest.raises(PathExistsError):
        fs.mv("/srv/app/logs", "/srv/app/README.md")

The concurrency test is the one to describe out loud: 200 tasks over eight threads, each doing mkdir -p on one of four shared directories and then writing its own file. The invariant is that exactly five directories exist and all 200 files landed.

code/lld/in_memory_file_system/tests/test_in_memory_file_system.py — concurrency
def test_concurrent_mkdir_and_write_never_lose_a_file(fs: FileSystem) -> None:
    def worker(i: int) -> None:
        fs.mkdir(f"/shared/dir-{i % 4}")
        fs.write(f"/shared/dir-{i % 4}/file-{i:03d}.txt", "x" * (i % 7))

    with ThreadPoolExecutor(max_workers=8) as pool:
        list(pool.map(worker, range(200)))

    assert fs.ls("/shared") == [f"dir-{i}" for i in range(4)]  # mkdir -p raced 200 times
    report = fs.usage("/shared")
    assert report.files == 200  # every writer got its own file
    assert report.directories == 5  # /shared plus four children, created exactly once
    assert report.total_bytes == sum(i % 7 for i in range(200))

The rest cover: seven invalid operations through parametrize; mkdir idempotency and its refusal to walk through a file; recursive rm releasing the whole subtree; the unlink-with-an-open-handle sequence; cp producing an independent deep copy; three visitors reporting and searching; walk yielding a sorted depth-first order; 300 concurrent appends to one file keeping every line; the permission proxy denying a guest and admitting the owner and an admin, and refusing a deep mkdir whose parent does not exist yet; and the LeetCode 588 example sequence verbatim. Run them with uv run pytest code/lld/in_memory_file_system -q.

45-minute pacing

Minutes What to do What to say or write
0–5 Clarify Absolute or relative paths? What does ls on a file do? What about .. at the root? Concurrency? Out of scope: persistence, symlinks, quotas.
5–10 Entities Nouns: Node, File, Directory, FileSystem, PathResolver, Visitor. Draw the Composite and say "Visitor for traversals" immediately.
10–17 Class diagram Tree on the left, visitors on the right, the proxy in front of the service. Mark the per-node lock.
17–33 Code PathResolver.normalize (all the edge cases) → Directory.get_or_add → FileSystem.mkdir → write → mv with the subtree check and _two_locks → SizeVisitor.
33–40 Concurrency Per-node locks, the ordering rule, the mkdir -p race, snapshots during traversal, and unlink-with-open-handle.
40–45 Extensions Symlinks with a depth limit, quotas as a visitor, ACLs in the proxy, versioning by chunk lists, and the hand-off to cloud file storage.