On this page

Design File System (OOP)

The file system design problem is a classic LLD exercise that tests your understanding of the Composite pattern, tree traversal, and clean interface design. Files and directories form a tree structure where directories can contain both files and other directories. The Composite pattern lets you treat individual files and directory hierarchies through a uniform interface.

The prompt usually arrives as "design an in-memory file system" or "implement mkdir, ls and mv". It looks easy, because everyone has used a shell. The difficulty is in the details a shell hides: what .. means at the root, what mv a b does when b is a directory and when it isn't, why mv /home /home/user must fail, which permission bit cd needs, and how to make a directory's size cheap to read. Interviewers use this problem to check three things: whether you reach for the Composite pattern without being told, whether you treat path parsing as real logic with edge cases, and whether your mutations are safe when a check fails halfway through.

This page follows the LLD interview framework. The first half is the original compact design, kept as it was, with corrections marked inline. The second half is a complete, runnable version in Java, Python and TypeScript that fixes those problems and adds permissions per user, cd with relative paths, safe mv, concurrency, three "the interviewer adds X" extensions and the tests that pin the behaviour down.

Requirements

Clarifying questions

Spend the first few minutes narrowing the problem. These are the questions that change the design, with the answers we assume on this page:

QuestionWhy it mattersAssumed answer
In-memory only, or backed by a disk?Disk means inodes, blocks and a cache: a different problemIn-memory, single process
Do we need users and permissions?Adds an owner, a group and mode bits to every node, plus a check on every step of a pathYes: Unix-style rwx for owner, group and others, and a root user that bypasses checks
Relative paths and a current directory?Needs a session object holding cwd, and ./.. handlingYes
Which commands?Sets the public APImkdir [-p], ls, cd, write/append, read, rm [-r], mv, du, chmod, chown
Symbolic or hard links?Turns the tree into a graph, so resolution needs loop detectionNot at first, discussed as a follow-up
Concurrent callers?Decides the locking storyYes, several threads may call the same instance
Is file content text or bytes?Size is bytes, so text needs encodingBytes, written as UTF-8 text in the API
What happens on error?Exceptions vs result codesOne exception type carrying a POSIX-like code (ENOENT, EEXIST, ENOTDIR, EISDIR, EACCES, EPERM, EINVAL, ENOTEMPTY)

Functional Requirements

#RequirementDetails
FR-1Create files and directoriesCreate at any path in the tree
FR-2Delete files and directoriesRecursive delete for directories
FR-3Move/renameMove a file/directory to a new path
FR-4List contentsList immediate children or recursive tree
FR-5Path resolutionNavigate paths like /home/user/docs/file.txt
FR-6File contentRead and write file contents
FR-7SearchFind by name, extension, size, or modified date
FR-8PermissionsRead, write, execute permissions per entry
FR-9Size calculationFile size directly; directory size = sum of children

The complete implementation later on this page adds three requirements that the table above leaves implicit:

#RequirementDetails
FR-10SessionsEach caller has a user, a group and a current directory, and cd changes it
FR-11mkdir -pCreate every missing directory on the path, and succeed if the directory already exists
FR-12Safe mvmv both renames and moves; it refuses to move a directory into its own subtree and never loses the source when it fails

Non-functional requirements

In LLD "non-functional" is about the code, not about latency budgets:

  • Atomic operations. Each command either fully happens or leaves the tree exactly as it was. A failed mv must not detach the source.
  • Correct under concurrency. Two threads moving the same file: exactly one succeeds. A thousand concurrent creates in one directory: no lost entries.
  • Extensible. Quotas, links, search filters and undo should plug in without rewriting the resolver.
  • Testable. Every error path returns a specific code, so tests can assert on EEXIST vs ENOTDIR instead of a generic failure.
  • Predictable cost. Resolving a path is in its depth, independent of how many files exist.

Out of scope

Persistence, block allocation, file descriptors and open-file tables, timestamps beyond what the original code keeps, and links. We name them so the interviewer knows we saw them, and come back to links and persistence in the follow-ups.

Core entities and relationships

EntityKindHoldsRelationship
NodeAbstract componentname, owner, group, mode bits, parentThe common type of everything in the tree
FileLeafbytesHas exactly one parent directory
DirectoryCompositemap of name to child NodeOwns its children; a child belongs to exactly one directory
FileSystemService / facadethe root directory and the lockParses paths, checks permissions, runs commands
SessionValue-ish contextuser, group, current directoryOne per caller; passed to every command
FsErrorErrora code and the pathThrown by every failed command

Three modelling decisions are worth saying aloud:

  1. The name lives on the node, and the directory indexes children by name. That makes lookup per path component. The cost is that a rename has to update both the node and the parent's map, which is why rename and move are the same operation (mv).
  2. Each node keeps a parent pointer. Without it you can't compute path(), follow .., or check whether a destination lies inside the source. The cost is a second reference to keep consistent, so only attach and detach touch it.
  3. The root is the only node without a parent, and its name is empty. Every other path is built by joining names with / and putting one / in front. Giving the root the name "/" instead is the source of the double-slash bug corrected below.

A Session isn't part of the tree. It's the caller's context, the equivalent of a process's user id and working directory. Keeping it outside FileSystem lets many users share one tree, each with their own cwd.

Composite Pattern

The key design insight is the Composite pattern. Both File and Directory implement a common FileSystemEntry interface. A Directory contains a list of FileSystemEntry objects — which can be files or other directories. This recursive composition creates the tree structure.

classDiagram
    class FileSystemEntry {
        <<interface>>
        +name: string
        +parent: Directory
        +getSize(): number
        +getPath(): string
        +isDirectory(): boolean
        +getPermissions(): Permissions
    }

    class File {
        -content: string
        -size: number
        -extension: string
        +read(): string
        +write(content): void
        +getSize(): number
    }

    class Directory {
        -children: Map~string, FileSystemEntry~
        +add(entry): void
        +remove(name): void
        +get(name): FileSystemEntry
        +list(): FileSystemEntry[]
        +getSize(): number
    }

    FileSystemEntry <|-- File
    FileSystemEntry <|-- Directory
    Directory o-- FileSystemEntry : contains

Why Composite and not something flatter? Because nearly every operation is recursive in the same way: size, search, delete, copy, print. With a shared Node type, Directory.size() is one line that sums child.size() without knowing which children are files. The caller asking for du /home doesn't branch on type either. The pattern page covers the general form: Composite.

Class diagram of the complete implementation

The runnable version later on this page keeps the same shape but renames the component to Node, moves the permission bits onto each node as a single Unix mode integer, and adds the Session and FsError types:

classDiagram
    class Node {
        <<abstract>>
        +name: String
        +owner: String
        +group: String
        +mode: int
        +parent: Directory
        +size() long
        +isDir() bool
        +path() String
    }
    class File {
        +data: bytes
        +size() long
    }
    class Directory {
        +children: Map~String, Node~
        +size() long
        +attach(node)
        +detach(name) Node
    }
    class Session {
        +user: String
        +group: String
        +cwd: String
    }
    class FileSystem {
        -root: Directory
        -lock: ReadWriteLock
        +mkdir(s, path, parents)
        +writeFile(s, path, text, append)
        +readFile(s, path) String
        +ls(s, path) List
        +du(s, path) long
        +rm(s, path, recursive)
        +mv(s, src, dst) String
        +chmod(s, path, mode)
        +chown(s, path, owner, group)
        +cd(s, path)
        #walk(s, path, create) Node
        #parentAndName(s, path) Target
        #need(s, node, bits, path)
        #beforeGrow(dir, delta, moving)
    }
    class FsError {
        +code: String
    }
    Node <|-- File
    Node <|-- Directory
    Directory o-- "*" Node : children
    FileSystem --> "1" Directory : root
    FileSystem ..> Session : uses
    FileSystem ..> FsError : throws

walk and parentAndName are the only two ways into the tree. Every command uses one of them, which is why path edge cases are fixed in one place and every command inherits the fix.

Flow: resolving a path

sequenceDiagram
    participant C as Caller
    participant FS as FileSystem
    participant D as Current directory
    C->>FS: ls(alice, "./docs//../a.md")
    FS->>FS: relative path, so start from walk(cwd)
    loop each component split on slash
        FS->>D: is it a Directory? need X
        alt empty or dot
            FS->>FS: stay where we are
        else dot dot
            FS->>FS: move to parent, the root stays the root
        else a name
            FS->>D: children.get(name)
            D-->>FS: child, or ENOENT
        end
    end
    FS->>FS: trailing slash on a file gives ENOTDIR
    FS-->>C: the resolved node

Flow: mv validates everything before it mutates anything

sequenceDiagram
    participant C as Caller
    participant FS as FileSystem
    participant SP as Source parent
    participant DP as Destination parent
    C->>FS: mv(s, "a/x", "b")
    FS->>FS: take the write lock
    FS->>FS: parentAndName("a/x") gives SP and "x"
    FS->>FS: walk("b") finds a Directory, so DP is b and the name stays "x"
    FS->>FS: same parent and same name? return, nothing to do
    FS->>FS: climb from DP to the root, fail with EINVAL if we meet the node
    FS->>DP: children.get("x")
    DP-->>FS: existing entry, or none
    FS->>FS: need W and X on SP and DP, call the beforeGrow hook
    FS->>SP: detach("x")
    FS->>DP: attach(node)
    FS->>FS: release the write lock
    FS-->>C: "/b/x"

The decision logic inside mv is the part candidates most often get wrong, so it's worth drawing on its own:

flowchart TD
    A["mv src dst"] --> B{"src exists?"}
    B -->|"no"| E1["ENOENT"]
    B -->|"yes"| C{"dst is an existing directory?"}
    C -->|"yes"| D1["target = dst + basename of src"]
    C -->|"no"| D2["target = parent of dst + basename of dst"]
    D1 --> F{"target is src itself?"}
    D2 --> F
    F -->|"yes"| N["no-op, return path"]
    F -->|"no"| G{"target parent inside src?"}
    G -->|"yes"| E2["EINVAL"]
    G -->|"no"| H{"name already taken?"}
    H -->|"no"| M["check permissions, detach, attach"]
    H -->|"file over file"| M
    H -->|"a directory involved"| E3["EEXIST"]

Lifecycle of a node

A node has a short lifecycle, but drawing it shows the invariant that matters: a node is reachable from the root only while it's attached, and mv is a detach followed by an attach under one lock, so no other thread ever sees it detached.

stateDiagram-v2
    [*] --> Detached : constructed
    Detached --> Attached : parent.attach
    Attached --> Attached : mv, new parent or new name
    Attached --> Detached : parent.detach by rm
    Detached --> [*] : unreachable, garbage collected

Path resolution in depth

Path resolution is where an "easy" file system turns into a real one. The complete implementation resolves one component at a time, starting at the root for absolute paths and at the session's cwd for relative ones:

InputcwdResultRule
/anythe rootEmpty components are skipped, so nothing is left to walk
//home///aliceany/home/aliceRepeated slashes collapse, as POSIX allows
docs/a.md/home/alice/home/alice/docs/a.mdRelative paths start at cwd
./docs/./a.md/home/alice/home/alice/docs/a.md. stays in place
docs/../readme/home/alice/home/alice/readme.. goes to the parent
/.. or /../..anythe root.. at the root stays at the root
a.md//home/aliceENOTDIRA trailing slash demands a directory
a.md/x/home/aliceENOTDIRYou can't descend into a file
missing/xanyENOENTA missing middle component
empty stringanyENOENTPOSIX treats "" as no such file

Two decisions here deserve a sentence each in the interview.

Physical, not lexical, ... A lexical resolver first rewrites a/../b to b as a string, then walks it. A physical resolver walks a, then goes to its parent. Without links the two agree on the destination, but they disagree on errors: if a is a file, POSIX says a/../b is ENOTDIR, and only the physical walk notices. The physical walk also checks search permission on a. It's the same amount of code, so pick the correct one. Once symbolic links arrive, the difference stops being academic, because link/.. is the parent of the link's target.

Splitting a path into parent and name. Commands that create or remove (mkdir, write, rm, the rename form of mv) don't want the node at the path. They want its parent directory plus the last name. parentAndName strips trailing slashes, splits at the last /, rejects a final component of "", . or .. with EINVAL (you can't rm / or mkdir ..), and walks the parent. Getting this wrong is how rm ./ ends up deleting the current directory from under the caller.

Permissions model

Each node carries an owner, a group and a 9-bit mode such as 0o755. A caller falls into exactly one class: owner if their user matches, else group if their group matches, else others. Only that class's three bits count, so a file with mode 0o077 is unreadable by its own owner even though everyone else can read it. That's real Unix behaviour and a nice detail to mention.

OperationBits required
Cross a directory while resolving a pathx on that directory
ls a directoryr on it
ls a filenothing beyond reaching it
Read a filer on the file
Write or append to an existing filew on the file
Create a file or directory, rm an entryw and x on the parent directory
mvw and x on both the source parent and the destination parent
chmodbe the owner, or root (EPERM otherwise)
chownbe root

Two consequences surprise people. Deleting a file needs no permission on the file itself, only on the directory that lists it, because deleting is an edit to the directory. And a directory with r but not x lets you list names but not open anything inside it. The complete implementation enforces both, because need is called with the right bits at each step instead of a single "can this user touch this path" check at the top.

Size aggregation

du asks for the size of a subtree. There are two designs, and the choice is a classic trade-off:

Recursive (Directory.size() sums children)Cached (each directory stores its total)
Read a directory's size for descendants
Write k bytes to a file: add k to every ancestor
Move a subtree: subtract on the old path, add on the new
RiskSlow du on huge treesCounters drift if any mutation forgets to update them

The core uses the recursive version because it can't be wrong: there's no second copy of the truth. The cached version is the right answer once the interviewer adds quotas or asks for a fast du, and the extension section shows where the update has to go. The rule for the cached version is that size changes propagate only through attach, detach and the one place that changes file bytes, so a mutation can't skip them.

Implementation

About the code in this section

This is the original compact implementation, kept for reference. It shows the Composite structure clearly but has a few bugs, each marked with a correction below. The complete runnable implementation further down fixes them and adds sessions, per-user permissions and safe mv.

Types and Permissions

TypeScript:

enum Permission {
  READ = 1 << 0,    // 1
  WRITE = 1 << 1,   // 2
  EXECUTE = 1 << 2, // 4
}

interface Permissions {
  owner: number;  // bitmask of Permission
  group: number;
  others: number;
}

const DEFAULT_FILE_PERMISSIONS: Permissions = {
  owner: Permission.READ | Permission.WRITE,  // 6 (rw-)
  group: Permission.READ,                     // 4 (r--)
  others: Permission.READ,                    // 4 (r--)
};

const DEFAULT_DIR_PERMISSIONS: Permissions = {
  owner: Permission.READ | Permission.WRITE | Permission.EXECUTE,  // 7 (rwx)
  group: Permission.READ | Permission.EXECUTE,                     // 5 (r-x)
  others: Permission.READ | Permission.EXECUTE,                    // 5 (r-x)
};

Python:

from enum import IntFlag
from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from datetime import datetime
from typing import Callable
import fnmatch

class Permission(IntFlag):
    READ = 1 << 0     # 1
    WRITE = 1 << 1    # 2
    EXECUTE = 1 << 2  # 4

@dataclass
class Permissions:
    owner: int = Permission.READ | Permission.WRITE           # 6
    group: int = Permission.READ                              # 4
    others: int = Permission.READ                             # 4

DEFAULT_FILE_PERMS = Permissions(
    owner=Permission.READ | Permission.WRITE,
    group=Permission.READ,
    others=Permission.READ
)

DEFAULT_DIR_PERMS = Permissions(
    owner=Permission.READ | Permission.WRITE | Permission.EXECUTE,
    group=Permission.READ | Permission.EXECUTE,
    others=Permission.READ | Permission.EXECUTE
)

FileSystemEntry (Base)

TypeScript:

abstract class FileSystemEntry {
  public parent: Directory | null = null;
  public createdAt: Date = new Date();
  public modifiedAt: Date = new Date();
  protected permissions: Permissions;

  constructor(
    public name: string,
    permissions?: Permissions
  ) {
    this.permissions = permissions ?? { ...DEFAULT_FILE_PERMISSIONS };
  }

  abstract getSize(): number;
  abstract isDirectory(): boolean;

  getPath(): string {
    const parts: string[] = [];
    let current: FileSystemEntry | null = this;

    while (current !== null) {
      parts.unshift(current.name);
      current = current.parent;
    }

    const path = parts.join("/");
    return path.startsWith("/") ? path : "/" + path;
  }

  getPermissions(): Permissions {
    return { ...this.permissions };
  }

  setPermissions(perms: Permissions): void {
    this.permissions = { ...perms };
    this.modifiedAt = new Date();
  }

  hasPermission(perm: Permission, role: "owner" | "group" | "others" = "owner"): boolean {
    return (this.permissions[role] & perm) !== 0;
  }

  getExtension(): string {
    const lastDot = this.name.lastIndexOf(".");
    return lastDot > 0 ? this.name.substring(lastDot + 1) : "";
  }
}

Python:

class FileSystemEntry(ABC):
    def __init__(self, name: str, permissions: Permissions | None = None):
        self.name = name
        self.parent: 'Directory | None' = None
        self.created_at = datetime.now()
        self.modified_at = datetime.now()
        self._permissions = permissions or Permissions()

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

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

    def get_path(self) -> str:
        parts: list[str] = []
        current: FileSystemEntry | None = self

        while current is not None:
            parts.append(current.name)
            current = current.parent

        parts.reverse()
        path = "/".join(parts)
        return path if path.startswith("/") else "/" + path

    def get_permissions(self) -> Permissions:
        return Permissions(
            self._permissions.owner,
            self._permissions.group,
            self._permissions.others
        )

    def set_permissions(self, perms: Permissions) -> None:
        self._permissions = perms
        self.modified_at = datetime.now()

    def has_permission(self, perm: Permission,
                       role: str = "owner") -> bool:
        return bool(getattr(self._permissions, role) & perm)

    def get_extension(self) -> str:
        last_dot = self.name.rfind(".")
        return self.name[last_dot + 1:] if last_dot > 0 else ""

Correction (2026-11-10): `getPath()` returns a double slash

The root directory is created as Directory("/"), so the walk up collects ["/", "home", "user"], and joining with / gives //home/user. That already starts with /, so it's returned as is. Running the Python version confirms it: get_path() on /home/user/a.txt returns //home/user/a.txt. The fix is to stop before adding the root's name: loop while current.parent is not null, then prepend a single /. The complete implementation does this and gives the root an empty name.

Correction (2026-11-10): permission checks always use the owner bits

hasPermission defaults role to "owner", and no caller ever passes another role, so the group and others bits are stored but never consulted, and there's no notion of who is asking. A real check needs the caller's identity: pick owner, group or others by comparing the caller to the node's owner and group, then test that class's bits. The complete implementation passes a Session to every command for exactly this reason.

File Class

TypeScript:

class File extends FileSystemEntry {
  private content: string = "";

  constructor(name: string, content = "", permissions?: Permissions) {
    super(name, permissions ?? { ...DEFAULT_FILE_PERMISSIONS });
    this.content = content;
  }

  isDirectory(): boolean {
    return false;
  }

  getSize(): number {
    return new TextEncoder().encode(this.content).length;
  }

  read(): string {
    if (!this.hasPermission(Permission.READ)) {
      throw new Error(`Permission denied: cannot read ${this.name}`);
    }
    return this.content;
  }

  write(content: string): void {
    if (!this.hasPermission(Permission.WRITE)) {
      throw new Error(`Permission denied: cannot write to ${this.name}`);
    }
    this.content = content;
    this.modifiedAt = new Date();
  }

  append(content: string): void {
    if (!this.hasPermission(Permission.WRITE)) {
      throw new Error(`Permission denied: cannot write to ${this.name}`);
    }
    this.content += content;
    this.modifiedAt = new Date();
  }
}

Python:

class File(FileSystemEntry):
    def __init__(self, name: str, content: str = "",
                 permissions: Permissions | None = None):
        super().__init__(name, permissions or DEFAULT_FILE_PERMS)
        self._content = content

    def is_directory(self) -> bool:
        return False

    def get_size(self) -> int:
        return len(self._content.encode("utf-8"))

    def read(self) -> str:
        if not self.has_permission(Permission.READ):
            raise PermissionError(f"Cannot read {self.name}")
        return self._content

    def write(self, content: str) -> None:
        if not self.has_permission(Permission.WRITE):
            raise PermissionError(f"Cannot write to {self.name}")
        self._content = content
        self.modified_at = datetime.now()

    def append(self, content: str) -> None:
        if not self.has_permission(Permission.WRITE):
            raise PermissionError(f"Cannot write to {self.name}")
        self._content += content
        self.modified_at = datetime.now()

Directory Class

TypeScript:

class Directory extends FileSystemEntry {
  private children: Map<string, FileSystemEntry> = new Map();

  constructor(name: string, permissions?: Permissions) {
    super(name, permissions ?? { ...DEFAULT_DIR_PERMISSIONS });
  }

  isDirectory(): boolean {
    return true;
  }

  getSize(): number {
    let total = 0;
    for (const [, child] of this.children) {
      total += child.getSize();
    }
    return total;
  }

  add(entry: FileSystemEntry): void {
    if (!this.hasPermission(Permission.WRITE)) {
      throw new Error(`Permission denied: cannot write to ${this.name}`);
    }
    if (this.children.has(entry.name)) {
      throw new Error(`Entry '${entry.name}' already exists in ${this.getPath()}`);
    }
    entry.parent = this;
    this.children.set(entry.name, entry);
    this.modifiedAt = new Date();
  }

  remove(name: string): FileSystemEntry | null {
    if (!this.hasPermission(Permission.WRITE)) {
      throw new Error(`Permission denied: cannot modify ${this.name}`);
    }
    const entry = this.children.get(name);
    if (!entry) return null;

    entry.parent = null;
    this.children.delete(name);
    this.modifiedAt = new Date();
    return entry;
  }

  get(name: string): FileSystemEntry | null {
    return this.children.get(name) ?? null;
  }

  list(): FileSystemEntry[] {
    if (!this.hasPermission(Permission.READ)) {
      throw new Error(`Permission denied: cannot list ${this.name}`);
    }
    return [...this.children.values()];
  }

  listNames(): string[] {
    return [...this.children.keys()].sort();
  }

  has(name: string): boolean {
    return this.children.has(name);
  }

  get childCount(): number {
    return this.children.size;
  }
}

Python:

class Directory(FileSystemEntry):
    def __init__(self, name: str, permissions: Permissions | None = None):
        super().__init__(name, permissions or DEFAULT_DIR_PERMS)
        self._children: dict[str, FileSystemEntry] = {}

    def is_directory(self) -> bool:
        return True

    def get_size(self) -> int:
        return sum(child.get_size() for child in self._children.values())

    def add(self, entry: FileSystemEntry) -> None:
        if not self.has_permission(Permission.WRITE):
            raise PermissionError(f"Cannot write to {self.name}")
        if entry.name in self._children:
            raise FileExistsError(f"'{entry.name}' already exists in {self.get_path()}")
        entry.parent = self
        self._children[entry.name] = entry
        self.modified_at = datetime.now()

    def remove(self, name: str) -> FileSystemEntry | None:
        if not self.has_permission(Permission.WRITE):
            raise PermissionError(f"Cannot modify {self.name}")
        entry = self._children.pop(name, None)
        if entry:
            entry.parent = None
            self.modified_at = datetime.now()
        return entry

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

    def list_entries(self) -> list[FileSystemEntry]:
        if not self.has_permission(Permission.READ):
            raise PermissionError(f"Cannot list {self.name}")
        return list(self._children.values())

    def list_names(self) -> list[str]:
        return sorted(self._children.keys())

    def has(self, name: str) -> bool:
        return name in self._children

    @property
    def child_count(self) -> int:
        return len(self._children)

TypeScript:

class FileSystem {
  private root: Directory;

  constructor() {
    this.root = new Directory("/");
  }

  resolve(path: string): FileSystemEntry | null {
    if (path === "/") return this.root;

    const parts = path.split("/").filter((p) => p.length > 0);
    let current: FileSystemEntry = this.root;

    for (const part of parts) {
      if (!current.isDirectory()) return null;
      const dir = current as Directory;
      const next = dir.get(part);
      if (!next) return null;
      current = next;
    }

    return current;
  }

  createFile(path: string, content = ""): File {
    const parts = path.split("/").filter((p) => p.length > 0);
    const fileName = parts.pop()!;
    const parentPath = "/" + parts.join("/");

    const parent = this.ensureDirectory(parentPath);
    const file = new File(fileName, content);
    parent.add(file);
    return file;
  }

  createDirectory(path: string): Directory {
    return this.ensureDirectory(path);
  }

  private ensureDirectory(path: string): Directory {
    if (path === "/" || path === "") return this.root;

    const parts = path.split("/").filter((p) => p.length > 0);
    let current: Directory = this.root;

    for (const part of parts) {
      let next = current.get(part);
      if (!next) {
        const newDir = new Directory(part);
        current.add(newDir);
        next = newDir;
      }
      if (!next.isDirectory()) {
        throw new Error(`${part} is not a directory`);
      }
      current = next as Directory;
    }

    return current;
  }

  delete(path: string): boolean {
    const entry = this.resolve(path);
    if (!entry || entry === this.root) return false;

    const parent = entry.parent;
    if (!parent) return false;

    parent.remove(entry.name);
    return true;
  }

  move(sourcePath: string, destPath: string): boolean {
    const source = this.resolve(sourcePath);
    if (!source || source === this.root) return false;

    const destParent = this.resolve(destPath);
    if (!destParent || !destParent.isDirectory()) return false;

    const parent = source.parent;
    if (!parent) return false;

    parent.remove(source.name);
    (destParent as Directory).add(source);
    return true;
  }

  // Search functionality
  find(
    startPath: string,
    predicate: (entry: FileSystemEntry) => boolean
  ): FileSystemEntry[] {
    const start = this.resolve(startPath);
    if (!start) return [];

    const results: FileSystemEntry[] = [];
    this.findRecursive(start, predicate, results);
    return results;
  }

  private findRecursive(
    entry: FileSystemEntry,
    predicate: (entry: FileSystemEntry) => boolean,
    results: FileSystemEntry[]
  ): void {
    if (predicate(entry)) {
      results.push(entry);
    }

    if (entry.isDirectory()) {
      for (const child of (entry as Directory).list()) {
        this.findRecursive(child, predicate, results);
      }
    }
  }

  // Convenience search methods
  findByName(startPath: string, pattern: string): FileSystemEntry[] {
    return this.find(startPath, (e) => {
      // Simple glob matching: * matches any sequence
      const regex = new RegExp(
        "^" + pattern.replace(/\*/g, ".*").replace(/\?/g, ".") + "$"
      );
      return regex.test(e.name);
    });
  }

  findByExtension(startPath: string, ext: string): FileSystemEntry[] {
    return this.find(startPath, (e) => e.getExtension() === ext);
  }

  findBySize(
    startPath: string,
    minSize: number,
    maxSize: number = Infinity
  ): FileSystemEntry[] {
    return this.find(
      startPath,
      (e) => !e.isDirectory() && e.getSize() >= minSize && e.getSize() <= maxSize
    );
  }

  // Tree visualization
  printTree(path = "/", indent = ""): string {
    const entry = this.resolve(path);
    if (!entry) return "";

    let output = indent + entry.name + (entry.isDirectory() ? "/" : "") + "\n";

    if (entry.isDirectory()) {
      const children = (entry as Directory).list();
      children.sort((a, b) => a.name.localeCompare(b.name));

      for (let i = 0; i < children.length; i++) {
        const isLast = i === children.length - 1;
        const prefix = indent + (isLast ? "  " : "| ");
        const connector = isLast ? "└─ " : "├─ ";
        output += indent + connector;
        output += children[i].name;
        output += children[i].isDirectory() ? "/\n" : ` (${children[i].getSize()}B)\n`;

        if (children[i].isDirectory()) {
          const childPath = children[i].getPath();
          const subTree = this.printTree(childPath, prefix);
          // Only print sub-children
          const lines = subTree.split("\n").slice(1);
          output += lines.join("\n");
        }
      }
    }

    return output;
  }
}

Python:

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

    def resolve(self, path: str) -> FileSystemEntry | None:
        if path == "/":
            return self.root

        parts = [p for p in path.split("/") if p]
        current: FileSystemEntry = self.root

        for part in parts:
            if not current.is_directory():
                return None
            nxt = current.get(part)
            if not nxt:
                return None
            current = nxt

        return current

    def create_file(self, path: str, content: str = "") -> File:
        parts = [p for p in path.split("/") if p]
        file_name = parts.pop()
        parent_path = "/" + "/".join(parts)

        parent = self._ensure_directory(parent_path)
        f = File(file_name, content)
        parent.add(f)
        return f

    def create_directory(self, path: str) -> Directory:
        return self._ensure_directory(path)

    def _ensure_directory(self, path: str) -> Directory:
        if path in ("/", ""):
            return self.root

        parts = [p for p in path.split("/") if p]
        current = self.root

        for part in parts:
            nxt = current.get(part)
            if not nxt:
                new_dir = Directory(part)
                current.add(new_dir)
                nxt = new_dir
            if not nxt.is_directory():
                raise NotADirectoryError(f"{part} is not a directory")
            current = nxt

        return current

    def delete(self, path: str) -> bool:
        entry = self.resolve(path)
        if not entry or entry is self.root:
            return False
        parent = entry.parent
        if not parent:
            return False
        parent.remove(entry.name)
        return True

    def move(self, source_path: str, dest_path: str) -> bool:
        source = self.resolve(source_path)
        if not source or source is self.root:
            return False
        dest_parent = self.resolve(dest_path)
        if not dest_parent or not dest_parent.is_directory():
            return False
        parent = source.parent
        if not parent:
            return False
        parent.remove(source.name)
        dest_parent.add(source)
        return True

    def find(self, start_path: str,
             predicate: Callable[[FileSystemEntry], bool]) -> list[FileSystemEntry]:
        start = self.resolve(start_path)
        if not start:
            return []
        results: list[FileSystemEntry] = []
        self._find_recursive(start, predicate, results)
        return results

    def _find_recursive(self, entry: FileSystemEntry,
                        predicate: Callable[[FileSystemEntry], bool],
                        results: list[FileSystemEntry]) -> None:
        if predicate(entry):
            results.append(entry)
        if entry.is_directory():
            for child in entry.list_entries():
                self._find_recursive(child, predicate, results)

    def find_by_name(self, start_path: str, pattern: str) -> list[FileSystemEntry]:
        return self.find(start_path, lambda e: fnmatch.fnmatch(e.name, pattern))

    def find_by_extension(self, start_path: str, ext: str) -> list[FileSystemEntry]:
        return self.find(start_path, lambda e: e.get_extension() == ext)

    def find_by_size(self, start_path: str,
                     min_size: int, max_size: int = float('inf')) -> list[FileSystemEntry]:
        return self.find(
            start_path,
            lambda e: not e.is_directory() and min_size <= e.get_size() <= max_size
        )

Correction (2026-11-10): `move()` can lose the entry or detach a subtree

move() removes the source from its parent before adding it to the destination. If the destination already has an entry with that name, add() throws after the source has been detached, and the entry is gone. A run of the Python version confirms that after the FileExistsError, the source path no longer resolves. move() also never checks whether the destination is inside the source: move("/home", "/home/b") detaches /home, attaches it under its own child, and leaves a cycle that nothing can reach from the root. Again confirmed by running it: /home stops resolving. The fix is to validate everything first (exists, not the root, destination not inside the source, no name collision, permissions) and only then detach and attach. The complete implementation's mv does that and also supports renaming.

Correction (2026-11-10): the TypeScript glob doesn't escape regex characters

findByName turns the glob into a regex by replacing * and ? but leaves every other character as is, so the . in a.txt matches any character (aXtxt matches) and a name containing ( or + builds a broken regex. Escape everything except * and ? first, for example pattern.replace(/[.+^${}()|[\]\\]/g, "\\$&"), and build the regex once outside the predicate instead of once per entry. The Python version is fine because fnmatch does the escaping.

Usage Example

TypeScript:

const fs = new FileSystem();

// Create directory structure
fs.createDirectory("/home/user/docs");
fs.createDirectory("/home/user/photos");
fs.createDirectory("/var/log");

// Create files
fs.createFile("/home/user/docs/resume.pdf", "PDF content here...");
fs.createFile("/home/user/docs/notes.txt", "Some notes");
fs.createFile("/home/user/photos/vacation.jpg", "JPEG binary data");
fs.createFile("/var/log/app.log", "2024-01-01 INFO: Started");

// Search
const txtFiles = fs.findByExtension("/home", "txt");
console.log(txtFiles.map((f) => f.getPath()));
// ["/home/user/docs/notes.txt"]

const largeFiles = fs.findBySize("/", 10);
console.log(largeFiles.map((f) => `${f.getPath()} (${f.getSize()}B)`));

// Directory size (recursive)
const homeDir = fs.resolve("/home/user") as Directory;
console.log(`Home size: ${homeDir.getSize()} bytes`);

Tree Visualization

/
├─ home/
│  └─ user/
│     ├─ docs/
│     │  ├─ notes.txt (10B)
│     │  └─ resume.pdf (19B)
│     └─ photos/
│        └─ vacation.jpg (16B)
└─ var/
   └─ log/
      └─ app.log (27B)

Correction (2026-11-10): `app.log` is 24 bytes, and the glyphs differ

The usage example writes "2024-01-01 INFO: Started", which is 24 bytes in UTF-8, not 27. The other three sizes are right. Also, the printTree method above draws continuation lines with "| " rather than "│ ", so its real output uses a plain pipe; the tree shown is the intended rendering, not its literal output.

Complete runnable implementation

Each tab below is one self-contained file that compiles and runs as is: javac FileSystemDemo.java && java -ea FileSystemDemo, python filesystem.py, or tsx filesystem.ts (it also passes tsc --strict). The main/demo function at the bottom of each is the test suite: it asserts every edge case discussed on this page and prints a line when they all pass. The Java and Python versions also run two concurrency checks with real threads.

Compared with the compact version above, this one:

  • passes a Session (user, group, cwd) to every command, so permissions depend on who is asking and relative paths work;
  • resolves paths physically, one component at a time, handling "", ., .., repeated and trailing slashes;
  • checks x on every directory it crosses and the right bits for each command;
  • validates mv completely before mutating, supports rename, and refuses to move a directory into itself;
  • reports failures with a POSIX-like code instead of null, false or a generic error;
  • guards the tree with a read-write lock (Java) or a mutex (Python);
  • exposes one protected hook, beforeGrow, that the quota extension overrides.
import java.nio.charset.StandardCharsets;
import java.util.*;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.function.Supplier;

class FsError extends RuntimeException {
    final String code;
    FsError(String code, String path) { super(code + ": " + path); this.code = code; }
}

/** Component in the Composite: everything a File and a Directory share. */
abstract class Node {
    String name, owner, group;
    int mode;
    Directory parent;

    Node(String name, String owner, String group, int mode) {
        this.name = name; this.owner = owner; this.group = group; this.mode = mode;
    }

    abstract long size();
    boolean isDir() { return false; }

    String path() {
        Deque<String> parts = new ArrayDeque<>();
        for (Node n = this; n.parent != null; n = n.parent) parts.addFirst(n.name);
        return "/" + String.join("/", parts);
    }
}

/** Leaf. */
class File extends Node {
    byte[] data = new byte[0];
    File(String name, String owner, String group) { super(name, owner, group, 0644); }
    long size() { return data.length; }
}

/** Composite. TreeMap keeps ls output sorted for free. */
class Directory extends Node {
    final TreeMap<String, Node> children = new TreeMap<>();
    Directory(String name, String owner, String group) { super(name, owner, group, 0755); }
    @Override boolean isDir() { return true; }

    long size() {
        long total = 0;
        for (Node c : children.values()) total += c.size();
        return total;
    }

    void attach(Node n) { n.parent = this; children.put(n.name, n); }
    Node detach(String name) { Node n = children.remove(name); n.parent = null; return n; }
}

final class Session {
    final String user, group;
    String cwd;
    Session(String user, String group, String cwd) { this.user = user; this.group = group; this.cwd = cwd; }
}

record Target(Directory parent, String name) {}

class FileSystem {
    static final int R = 4, W = 2, X = 1;
    final Directory root = new Directory("", "root", "root");
    private final ReentrantReadWriteLock rw = new ReentrantReadWriteLock();

    /** Extension hook, a no-op in the core. */
    protected void beforeGrow(Directory dir, long delta, Node moving) {}

    <T> T read(Supplier<T> op) {
        rw.readLock().lock();
        try { return op.get(); } finally { rw.readLock().unlock(); }
    }

    <T> T write(Supplier<T> op) {
        rw.writeLock().lock();
        try { return op.get(); } finally { rw.writeLock().unlock(); }
    }

    void need(Session s, Node n, int bits, String path) {
        if (s.user.equals("root")) return;
        int granted = s.user.equals(n.owner) ? (n.mode >> 6) & 7
                : s.group.equals(n.group) ? (n.mode >> 3) & 7
                : n.mode & 7;
        if ((granted & bits) != bits) throw new FsError("EACCES", path);
    }

    Node walk(Session s, String path, boolean create) {
        if (path.isEmpty()) throw new FsError("ENOENT", path);
        Node node = path.startsWith("/") ? root : walk(s, s.cwd, false);
        for (String part : path.split("/")) {
            if (part.isEmpty()) continue;                       // leading, trailing or doubled slash
            if (!(node instanceof Directory dir)) throw new FsError("ENOTDIR", path);
            need(s, dir, X, path);                              // search permission on every directory crossed
            if (part.equals(".")) continue;
            if (part.equals("..")) { node = dir.parent == null ? dir : dir.parent; continue; }
            Node next = dir.children.get(part);
            if (next == null) {
                if (!create) throw new FsError("ENOENT", path);
                need(s, dir, W, path);
                next = new Directory(part, s.user, s.group);
                dir.attach(next);
            }
            node = next;
        }
        if (path.endsWith("/") && !node.isDir()) throw new FsError("ENOTDIR", path);
        return node;
    }

    Target parentAndName(Session s, String path) {
        String p = path.replaceAll("/+$", "");
        int cut = p.lastIndexOf('/');
        String name = p.substring(cut + 1);
        if (name.isEmpty() || name.equals(".") || name.equals("..")) throw new FsError("EINVAL", path);
        String parentPath = cut < 0 ? "." : (cut == 0 ? "/" : p.substring(0, cut));
        Node parent = walk(s, parentPath, false);
        if (!(parent instanceof Directory dir)) throw new FsError("ENOTDIR", path);
        need(s, dir, X, path);
        return new Target(dir, name);
    }

    void mkdir(Session s, String path, boolean parents) {
        write(() -> {
            if (parents) {
                if (!walk(s, path, true).isDir()) throw new FsError("EEXIST", path);
                return null;
            }
            Target t = parentAndName(s, path);
            if (t.parent().children.containsKey(t.name())) throw new FsError("EEXIST", path);
            need(s, t.parent(), W, path);
            t.parent().attach(new Directory(t.name(), s.user, s.group));
            return null;
        });
    }

    void writeFile(Session s, String path, String text, boolean append) {
        write(() -> {
            if (path.endsWith("/")) throw new FsError("EISDIR", path);
            Target t = parentAndName(s, path);
            Node existing = t.parent().children.get(t.name());
            if (existing instanceof Directory) throw new FsError("EISDIR", path);
            File f = (File) existing;
            boolean created = f == null;
            if (created) {
                need(s, t.parent(), W, path);
                f = new File(t.name(), s.user, s.group);
            } else {
                need(s, f, W, path);
            }
            byte[] bytes = text.getBytes(StandardCharsets.UTF_8);
            byte[] next = bytes;
            if (append) {
                next = Arrays.copyOf(f.data, f.data.length + bytes.length);
                System.arraycopy(bytes, 0, next, f.data.length, bytes.length);
            }
            if (next.length > f.data.length) beforeGrow(t.parent(), next.length - f.data.length, null);
            if (created) t.parent().attach(f);
            f.data = next;
            return null;
        });
    }

    String readFile(Session s, String path) {
        return read(() -> {
            if (!(walk(s, path, false) instanceof File f)) throw new FsError("EISDIR", path);
            need(s, f, R, path);
            return new String(f.data, StandardCharsets.UTF_8);
        });
    }

    List<String> ls(Session s, String path) {
        return read(() -> {
            Node n = walk(s, path, false);
            if (!(n instanceof Directory dir)) return List.of(n.name);   // ls on a file prints the file
            need(s, dir, R, path);
            List<String> out = new ArrayList<>();
            dir.children.forEach((name, c) -> out.add(c.isDir() ? name + "/" : name));
            return out;
        });
    }

    long du(Session s, String path) {
        return read(() -> {
            Node n = walk(s, path, false);
            if (n.isDir()) need(s, n, R, path);
            return n.size();   // Composite: one call, the tree does the recursion
        });
    }

    void rm(Session s, String path, boolean recursive) {
        write(() -> {
            Target t = parentAndName(s, path);
            Node n = t.parent().children.get(t.name());
            if (n == null) throw new FsError("ENOENT", path);
            if (n instanceof Directory d && !d.children.isEmpty() && !recursive) throw new FsError("ENOTEMPTY", path);
            // Simplification: rm -r checks only the top parent, real rm needs W+X on every subdirectory
            need(s, t.parent(), W | X, path);
            t.parent().detach(t.name());
            return null;
        });
    }

    /** rename(2)-style move. Returns the final absolute path. */
    String mv(Session s, String src, String dst) {
        return write(() -> {
            Target from = parentAndName(s, src);
            Directory sp = from.parent();
            Node node = sp.children.get(from.name());
            if (node == null) throw new FsError("ENOENT", src);
            Node target = null;
            try { target = walk(s, dst, false); } catch (FsError e) { if (!e.code.equals("ENOENT")) throw e; }
            Directory dp;
            String dname;
            if (target instanceof Directory d) { dp = d; dname = node.name; }   // mv x dir -> dir/x
            else { Target to = parentAndName(s, dst); dp = to.parent(); dname = to.name(); }
            if (dp == sp && dname.equals(from.name())) return node.path();   // onto itself: no-op
            for (Node a = dp; a != null; a = a.parent)                       // never into its own subtree
                if (a == node) throw new FsError("EINVAL", dst);
            Node existing = dp.children.get(dname);
            if (existing != null && (existing.isDir() || node.isDir())) throw new FsError("EEXIST", dst);
            need(s, sp, W | X, src);
            need(s, dp, W | X, dst);
            if (dp != sp) beforeGrow(dp, node.size(), node);
            // every check passed: only now mutate, so a failure never loses the node
            if (existing != null) dp.detach(dname);
            sp.detach(from.name());
            node.name = dname;
            dp.attach(node);
            return node.path();
        });
    }

    void chmod(Session s, String path, int mode) {
        write(() -> {
            Node n = walk(s, path, false);
            if (!s.user.equals("root") && !s.user.equals(n.owner)) throw new FsError("EPERM", path);
            n.mode = mode;
            return null;
        });
    }

    void chown(Session s, String path, String owner, String group) {
        write(() -> {
            Node n = walk(s, path, false);
            if (!s.user.equals("root")) throw new FsError("EPERM", path);
            n.owner = owner; n.group = group;
            return null;
        });
    }

    String realpath(Session s, String path) { return read(() -> walk(s, path, false).path()); }

    void cd(Session s, String path) {
        read(() -> {
            Node n = walk(s, path, false);
            if (!n.isDir()) throw new FsError("ENOTDIR", path);
            s.cwd = n.path();
            return null;
        });
    }
}

public class FileSystemDemo {
    static void expect(String code, Runnable r) {
        try { r.run(); } catch (FsError e) {
            if (!e.code.equals(code)) throw new AssertionError("expected " + code + ", got " + e.code);
            return;
        }
        throw new AssertionError("expected " + code + ", nothing thrown");
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) throws Exception {
        FileSystem fs = new FileSystem();
        Session root = new Session("root", "root", "/");
        fs.mkdir(root, "/home/alice", true);
        fs.chown(root, "/home/alice", "alice", "dev");
        Session alice = new Session("alice", "dev", "/home/alice");
        Session bob = new Session("bob", "ops", "/");

        // mkdir -p, relative paths, ".", "..", "//" and trailing slashes
        fs.mkdir(alice, "projects/archon/docs/", true);
        fs.mkdir(alice, "projects/archon", true);
        expect("EEXIST", () -> fs.mkdir(alice, "projects", false));
        fs.writeFile(alice, "projects/archon/docs/a.md", "hello", false);
        fs.writeFile(alice, "./projects//archon/docs/../readme.txt", "hi!", false);
        check(fs.ls(alice, "projects/archon").equals(List.of("docs/", "readme.txt")), "ls");
        check(fs.ls(alice, "/home/alice/projects/archon/readme.txt").equals(List.of("readme.txt")), "ls file");
        expect("ENOTDIR", () -> fs.ls(alice, "projects/archon/readme.txt/"));
        expect("ENOTDIR", () -> fs.mkdir(alice, "projects/archon/readme.txt/x", true));
        expect("ENOENT", () -> fs.ls(alice, "nope"));
        fs.writeFile(alice, "projects/archon/readme.txt", "!!", true);

        // size aggregation through the Composite
        check(fs.du(alice, "/home/alice") == 10, "du");
        check(fs.readFile(alice, "projects/archon/readme.txt").equals("hi!!!"), "append");

        // cd and ".." at the root
        fs.cd(alice, "projects/archon/docs/..");
        check(alice.cwd.equals("/home/alice/projects/archon"), "cd ..");
        fs.cd(alice, "/../..");
        check(alice.cwd.equals("/"), "cd above root");
        fs.cd(alice, "/home/alice");

        // mv edge cases
        check(fs.mv(alice, "projects/archon/readme.txt", "projects/archon/README").equals("/home/alice/projects/archon/README"), "rename");
        check(fs.mv(alice, "projects/archon/README", "projects").equals("/home/alice/projects/README"), "into dir");
        check(fs.mv(alice, "projects/README", "projects/README").equals("/home/alice/projects/README"), "onto itself");
        expect("EINVAL", () -> fs.mv(alice, "projects", "projects/archon/docs"));
        expect("EINVAL", () -> fs.mv(alice, "projects", "projects"));
        fs.writeFile(alice, "projects/other.txt", "x", false);
        fs.mv(alice, "projects/other.txt", "projects/README");
        check(fs.ls(alice, "projects").equals(List.of("README", "archon/")), "replace file");
        fs.mkdir(alice, "archon", false);
        expect("EEXIST", () -> fs.mv(alice, "archon", "projects/README"));
        expect("EINVAL", () -> fs.rm(alice, "/", true));

        // permissions
        expect("EACCES", () -> fs.writeFile(bob, "/home/alice/evil", "x", false));
        check(fs.ls(bob, "/home/alice").equals(List.of("archon/", "projects/")), "bob can list 755");
        fs.chmod(alice, "/home/alice", 0700);
        expect("EACCES", () -> fs.ls(bob, "/home/alice"));
        expect("EACCES", () -> fs.readFile(bob, "/home/alice/projects/README"));
        expect("EPERM", () -> fs.chmod(bob, "/home/alice", 0777));

        // rm
        expect("ENOTEMPTY", () -> fs.rm(alice, "projects", false));
        fs.rm(alice, "projects", true);
        check(fs.ls(alice, ".").equals(List.of("archon/")), "rm -r");

        // concurrency: two movers race for one file, exactly one wins
        fs.mkdir(root, "/race", false);
        fs.writeFile(root, "/race/x", "data", false);
        List<String> results = Collections.synchronizedList(new ArrayList<>());
        List<Thread> threads = new ArrayList<>();
        for (String d : List.of("/race/a", "/race/b")) {
            threads.add(Thread.ofPlatform().start(() -> {
                try { fs.mv(root, "/race/x", d); results.add("ok"); }
                catch (FsError e) { results.add(e.code); }
            }));
        }
        for (Thread t : threads) t.join();
        check(new TreeSet<>(results).equals(new TreeSet<>(List.of("ENOENT", "ok"))), "race " + results);
        check(fs.ls(root, "/race").size() == 1, "one file left");

        // concurrency: many writers into one directory, no lost entries
        fs.mkdir(root, "/load", false);
        threads.clear();
        for (int i = 0; i < 8; i++) {
            int id = i;
            threads.add(Thread.ofPlatform().start(() -> {
                for (int j = 0; j < 100; j++) fs.writeFile(root, "/load/f" + id + "-" + j, "ab", false);
            }));
        }
        for (Thread t : threads) t.join();
        check(fs.ls(root, "/load").size() == 800, "800 files");
        check(fs.du(root, "/load") == 1600, "1600 bytes");
        System.out.println("java: all file system checks passed");
    }
}
"""In-memory file system: Composite tree, POSIX-style path resolution,
owner/group/other permission bits, size aggregation, ls/mkdir/mv/rm."""
from __future__ import annotations

import threading
from dataclasses import dataclass

R, W, X = 4, 2, 1


class FsError(Exception):
    def __init__(self, code: str, path: str):
        super().__init__(f"{code}: {path}")
        self.code = code


class Node:
    """Component in the Composite: everything a File and a Directory share."""

    def __init__(self, name: str, owner: str, group: str, mode: int):
        self.name, self.owner, self.group, self.mode = name, owner, group, mode
        self.parent: Directory | None = None

    def size(self) -> int:
        raise NotImplementedError

    def is_dir(self) -> bool:
        return False

    def path(self) -> str:
        parts: list[str] = []
        node: Node = self
        while node.parent is not None:  # the root is the only node without a parent
            parts.append(node.name)
            node = node.parent
        return "/" + "/".join(reversed(parts))


class File(Node):  # Leaf
    def __init__(self, name: str, owner: str, group: str):
        super().__init__(name, owner, group, 0o644)
        self.data = b""

    def size(self) -> int:
        return len(self.data)


class Directory(Node):  # Composite
    def __init__(self, name: str, owner: str, group: str):
        super().__init__(name, owner, group, 0o755)
        self.children: dict[str, Node] = {}

    def is_dir(self) -> bool:
        return True

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

    def attach(self, node: Node) -> None:
        node.parent = self
        self.children[node.name] = node

    def detach(self, name: str) -> Node:
        node = self.children.pop(name)
        node.parent = None
        return node


@dataclass
class Session:
    user: str
    group: str
    cwd: str = "/"


class FileSystem:
    def __init__(self) -> None:
        self.root = Directory("", "root", "root")
        # Simplification: one lock for the whole tree; Python's stdlib has no RW lock
        self._lock = threading.Lock()

    # ---- extension hook (no-op in the core) ----
    def _before_grow(self, directory: Directory, delta: int, moving: Node | None) -> None:
        pass

    # ---- permissions ----
    def _need(self, s: Session, node: Node, bits: int, path: str) -> None:
        if s.user == "root":
            return
        if s.user == node.owner:
            granted = (node.mode >> 6) & 7
        elif s.group == node.group:
            granted = (node.mode >> 3) & 7
        else:
            granted = node.mode & 7
        if granted & bits != bits:
            raise FsError("EACCES", path)

    # ---- path resolution ----
    def _walk(self, s: Session, path: str, create: bool = False) -> Node:
        if not path:
            raise FsError("ENOENT", path)
        node: Node = self.root if path.startswith("/") else self._walk(s, s.cwd)
        for part in path.split("/"):
            if part == "":  # leading, trailing or doubled slash
                continue
            if not isinstance(node, Directory):
                raise FsError("ENOTDIR", path)
            self._need(s, node, X, path)  # search permission on every directory crossed
            if part == ".":
                continue
            if part == "..":
                node = node.parent or node  # ".." at the root stays at the root
                continue
            nxt = node.children.get(part)
            if nxt is None:
                if not create:
                    raise FsError("ENOENT", path)
                self._need(s, node, W, path)
                nxt = Directory(part, s.user, s.group)
                node.attach(nxt)
            node = nxt
        if path.endswith("/") and not node.is_dir():
            raise FsError("ENOTDIR", path)
        return node

    def _parent_and_name(self, s: Session, path: str) -> tuple[Directory, str]:
        p = path.rstrip("/")
        cut = p.rfind("/")
        name = p[cut + 1:]
        if name in ("", ".", ".."):
            raise FsError("EINVAL", path)
        parent_path = "." if cut < 0 else (p[:cut] or "/")
        parent = self._walk(s, parent_path)
        if not isinstance(parent, Directory):
            raise FsError("ENOTDIR", path)
        self._need(s, parent, X, path)
        return parent, name

    # ---- commands ----
    def mkdir(self, s: Session, path: str, parents: bool = False) -> None:
        with self._lock:
            if parents:
                if not self._walk(s, path, create=True).is_dir():
                    raise FsError("EEXIST", path)
                return
            parent, name = self._parent_and_name(s, path)
            if name in parent.children:
                raise FsError("EEXIST", path)
            self._need(s, parent, W, path)
            parent.attach(Directory(name, s.user, s.group))

    def write_file(self, s: Session, path: str, text: str, append: bool = False) -> None:
        with self._lock:
            if path.endswith("/"):
                raise FsError("EISDIR", path)
            parent, name = self._parent_and_name(s, path)
            node = parent.children.get(name)
            if isinstance(node, Directory):
                raise FsError("EISDIR", path)
            created = node is None
            if node is None:
                self._need(s, parent, W, path)
                node = File(name, s.user, s.group)
            else:
                self._need(s, node, W, path)
            assert isinstance(node, File)
            data = text.encode("utf-8")
            new_data = node.data + data if append else data
            if len(new_data) > len(node.data):
                self._before_grow(parent, len(new_data) - len(node.data), None)
            if created:
                parent.attach(node)
            node.data = new_data

    def read_file(self, s: Session, path: str) -> str:
        with self._lock:
            node = self._walk(s, path)
            if not isinstance(node, File):
                raise FsError("EISDIR", path)
            self._need(s, node, R, path)
            return node.data.decode("utf-8")

    def ls(self, s: Session, path: str = ".") -> list[str]:
        with self._lock:
            node = self._walk(s, path)
            if not isinstance(node, Directory):
                return [node.name]  # ls on a file prints the file
            self._need(s, node, R, path)
            return sorted(n + "/" if c.is_dir() else n for n, c in node.children.items())

    def du(self, s: Session, path: str = ".") -> int:
        with self._lock:
            node = self._walk(s, path)
            if node.is_dir():
                self._need(s, node, R, path)
            return node.size()  # Composite: one call, the tree does the recursion

    def rm(self, s: Session, path: str, recursive: bool = False) -> None:
        with self._lock:
            parent, name = self._parent_and_name(s, path)
            node = parent.children.get(name)
            if node is None:
                raise FsError("ENOENT", path)
            if isinstance(node, Directory) and node.children and not recursive:
                raise FsError("ENOTEMPTY", path)
            # Simplification: rm -r checks only the top parent, real rm needs W+X on every subdirectory
            self._need(s, parent, W | X, path)
            parent.detach(name)

    def mv(self, s: Session, src: str, dst: str) -> str:
        """rename(2)-style move. Returns the final absolute path."""
        with self._lock:
            sp, sname = self._parent_and_name(s, src)
            node = sp.children.get(sname)
            if node is None:
                raise FsError("ENOENT", src)
            try:
                target: Node | None = self._walk(s, dst)
            except FsError as e:
                if e.code != "ENOENT":
                    raise
                target = None
            if isinstance(target, Directory):  # mv x existing_dir -> existing_dir/x
                dp, dname = target, node.name
            else:  # mv x new_name (rename), or onto an existing file
                dp, dname = self._parent_and_name(s, dst)
            if dp is sp and dname == sname:
                return node.path()  # moving onto itself is a no-op
            anc: Directory | None = dp
            while anc is not None:  # never move a directory into its own subtree
                if anc is node:
                    raise FsError("EINVAL", dst)
                anc = anc.parent
            existing = dp.children.get(dname)
            if existing is not None and (existing.is_dir() or node.is_dir()):
                raise FsError("EEXIST", dst)
            self._need(s, sp, W | X, src)
            self._need(s, dp, W | X, dst)
            if dp is not sp:
                self._before_grow(dp, node.size(), node)
            # every check passed: only now mutate, so a failure never loses the node
            if existing is not None:
                dp.detach(dname)
            sp.detach(sname)
            node.name = dname
            dp.attach(node)
            return node.path()

    def chmod(self, s: Session, path: str, mode: int) -> None:
        with self._lock:
            node = self._walk(s, path)
            if s.user not in ("root", node.owner):
                raise FsError("EPERM", path)
            node.mode = mode

    def chown(self, s: Session, path: str, owner: str, group: str) -> None:
        with self._lock:
            node = self._walk(s, path)
            if s.user != "root":
                raise FsError("EPERM", path)
            node.owner, node.group = owner, group

    def realpath(self, s: Session, path: str) -> str:
        with self._lock:
            return self._walk(s, path).path()

    def cd(self, s: Session, path: str) -> None:
        with self._lock:
            node = self._walk(s, path)
            if not node.is_dir():
                raise FsError("ENOTDIR", path)
            s.cwd = node.path()


def expect(code: str, fn) -> None:
    try:
        fn()
    except FsError as e:
        assert e.code == code, f"expected {code}, got {e.code}"
        return
    raise AssertionError(f"expected {code}, nothing raised")


def main() -> None:
    fs = FileSystem()
    root = Session("root", "root")
    fs.mkdir(root, "/home/alice", parents=True)
    fs.chown(root, "/home/alice", "alice", "dev")
    alice = Session("alice", "dev", "/home/alice")
    bob = Session("bob", "ops", "/")

    # mkdir -p, relative paths, ".", "..", "//" and trailing slashes
    fs.mkdir(alice, "projects/archon/docs/", parents=True)
    fs.mkdir(alice, "projects/archon", parents=True)  # -p is idempotent
    expect("EEXIST", lambda: fs.mkdir(alice, "projects"))
    fs.write_file(alice, "projects/archon/docs/a.md", "hello")
    fs.write_file(alice, "./projects//archon/docs/../readme.txt", "hi!")
    assert fs.ls(alice, "projects/archon") == ["docs/", "readme.txt"]
    assert fs.ls(alice, "/home/alice/projects/archon/readme.txt") == ["readme.txt"]
    expect("ENOTDIR", lambda: fs.ls(alice, "projects/archon/readme.txt/"))
    expect("ENOTDIR", lambda: fs.mkdir(alice, "projects/archon/readme.txt/x", parents=True))
    expect("ENOENT", lambda: fs.ls(alice, "nope"))
    fs.write_file(alice, "projects/archon/readme.txt", "!!", append=True)

    # size aggregation through the Composite
    assert fs.du(alice, "/home/alice") == 5 + 5
    assert fs.read_file(alice, "projects/archon/readme.txt") == "hi!!!"

    # cd and ".." at the root
    fs.cd(alice, "projects/archon/docs/..")
    assert alice.cwd == "/home/alice/projects/archon"
    fs.cd(alice, "/../..")
    assert alice.cwd == "/"
    fs.cd(alice, "/home/alice")

    # mv: rename, into a directory, onto a file, onto itself, into own subtree, collisions
    assert fs.mv(alice, "projects/archon/readme.txt", "projects/archon/README") == "/home/alice/projects/archon/README"
    assert fs.mv(alice, "projects/archon/README", "projects") == "/home/alice/projects/README"
    assert fs.mv(alice, "projects/README", "projects/README") == "/home/alice/projects/README"
    expect("EINVAL", lambda: fs.mv(alice, "projects", "projects/archon/docs"))
    expect("EINVAL", lambda: fs.mv(alice, "projects", "projects"))
    fs.write_file(alice, "projects/other.txt", "x")
    fs.mv(alice, "projects/other.txt", "projects/README")  # file replaces file
    assert fs.ls(alice, "projects") == ["README", "archon/"]
    fs.mkdir(alice, "archon")
    expect("EEXIST", lambda: fs.mv(alice, "archon", "projects/README"))
    expect("EINVAL", lambda: fs.rm(alice, "/"))

    # permissions: bob is not the owner and not in group dev
    expect("EACCES", lambda: fs.write_file(bob, "/home/alice/evil", "x"))
    assert fs.ls(bob, "/home/alice") == ["archon/", "projects/"]
    fs.chmod(alice, "/home/alice", 0o700)
    expect("EACCES", lambda: fs.ls(bob, "/home/alice"))
    expect("EACCES", lambda: fs.read_file(bob, "/home/alice/projects/README"))
    expect("EPERM", lambda: fs.chmod(bob, "/home/alice", 0o777))

    # rm
    expect("ENOTEMPTY", lambda: fs.rm(alice, "projects"))
    fs.rm(alice, "projects", recursive=True)
    assert fs.ls(alice) == ["archon/"]

    # concurrency: two movers race for one file, exactly one wins
    fs.mkdir(root, "/race")
    fs.write_file(root, "/race/x", "data")
    results: list[str] = []

    def mover(dst: str) -> None:
        try:
            fs.mv(root, "/race/x", dst)
            results.append("ok")
        except FsError as e:
            results.append(e.code)

    threads = [threading.Thread(target=mover, args=(d,)) for d in ("/race/a", "/race/b")]
    for t in threads:
        t.start()
    for t in threads:
        t.join()
    assert sorted(results) == ["ENOENT", "ok"], results
    assert len(fs.ls(root, "/race")) == 1

    # concurrency: many writers into one directory, no lost entries
    fs.mkdir(root, "/load")

    def writer(i: int) -> None:
        for j in range(100):
            fs.write_file(root, f"/load/f{i}-{j}", "ab")

    threads = [threading.Thread(target=writer, args=(i,)) for i in range(8)]
    for t in threads:
        t.start()
    for t in threads:
        t.join()
    assert len(fs.ls(root, "/load")) == 800
    assert fs.du(root, "/load") == 1600
    print("python: all file system checks passed")


if __name__ == "__main__":
    main()
// In-memory file system: Composite tree, POSIX-style path resolution,
// owner/group/other permission bits, size aggregation, ls/mkdir/mv/rm.
export const R = 4, W = 2, X = 1;

export class FsError extends Error {
  constructor(public readonly code: string, path: string) {
    super(`${code}: ${path}`);
  }
}

/** Component in the Composite: everything a File and a Directory share. */
export abstract class Node {
  parent: Directory | null = null;
  constructor(public name: string, public owner: string, public group: string, public mode: number) {}
  abstract size(): number;
  isDir(): this is Directory {
    return false;
  }
  path(): string {
    const parts: string[] = [];
    for (let n: Node = this; n.parent !== null; n = n.parent) parts.unshift(n.name);
    return "/" + parts.join("/");
  }
}

/** Leaf. */
export class File extends Node {
  data = new Uint8Array(0);
  constructor(name: string, owner: string, group: string) {
    super(name, owner, group, 0o644);
  }
  size(): number {
    return this.data.length;
  }
}

/** Composite. */
export class Directory extends Node {
  readonly children = new Map<string, Node>();
  constructor(name: string, owner: string, group: string) {
    super(name, owner, group, 0o755);
  }
  override isDir(): this is Directory {
    return true;
  }
  size(): number {
    let total = 0;
    for (const c of this.children.values()) total += c.size();
    return total;
  }
  attach(n: Node): void {
    n.parent = this;
    this.children.set(n.name, n);
  }
  detach(name: string): Node {
    const n = this.children.get(name)!;
    this.children.delete(name);
    n.parent = null;
    return n;
  }
}

export class Session {
  constructor(public readonly user: string, public readonly group: string, public cwd = "/") {}
}

const encoder = new TextEncoder();
const decoder = new TextDecoder();

// JavaScript runs one call at a time on the event loop and none of these
// methods await, so each operation is atomic without a lock.
export class FileSystem {
  readonly root = new Directory("", "root", "root");

  /** Extension hook, a no-op in the core. */
  protected beforeGrow(_dir: Directory, _delta: number, _moving: Node | null): void {}

  protected need(s: Session, n: Node, bits: number, path: string): void {
    if (s.user === "root") return;
    const granted = s.user === n.owner ? (n.mode >> 6) & 7 : s.group === n.group ? (n.mode >> 3) & 7 : n.mode & 7;
    if ((granted & bits) !== bits) throw new FsError("EACCES", path);
  }

  protected walk(s: Session, path: string, create = false): Node {
    if (path === "") throw new FsError("ENOENT", path);
    let node: Node = path.startsWith("/") ? this.root : this.walk(s, s.cwd);
    for (const part of path.split("/")) {
      if (part === "") continue; // leading, trailing or doubled slash
      if (!(node instanceof Directory)) throw new FsError("ENOTDIR", path);
      this.need(s, node, X, path); // search permission on every directory crossed
      if (part === ".") continue;
      if (part === "..") {
        node = node.parent ?? node; // ".." at the root stays at the root
        continue;
      }
      let next = node.children.get(part);
      if (next === undefined) {
        if (!create) throw new FsError("ENOENT", path);
        this.need(s, node, W, path);
        next = new Directory(part, s.user, s.group);
        node.attach(next);
      }
      node = next;
    }
    if (path.endsWith("/") && !node.isDir()) throw new FsError("ENOTDIR", path);
    return node;
  }

  protected parentAndName(s: Session, path: string): [Directory, string] {
    const p = path.replace(/\/+$/, "");
    const cut = p.lastIndexOf("/");
    const name = p.slice(cut + 1);
    if (name === "" || name === "." || name === "..") throw new FsError("EINVAL", path);
    const parentPath = cut < 0 ? "." : p.slice(0, cut) || "/";
    const parent = this.walk(s, parentPath);
    if (!(parent instanceof Directory)) throw new FsError("ENOTDIR", path);
    this.need(s, parent, X, path);
    return [parent, name];
  }

  mkdir(s: Session, path: string, parents = false): void {
    if (parents) {
      if (!this.walk(s, path, true).isDir()) throw new FsError("EEXIST", path);
      return;
    }
    const [parent, name] = this.parentAndName(s, path);
    if (parent.children.has(name)) throw new FsError("EEXIST", path);
    this.need(s, parent, W, path);
    parent.attach(new Directory(name, s.user, s.group));
  }

  writeFile(s: Session, path: string, text: string, append = false): void {
    if (path.endsWith("/")) throw new FsError("EISDIR", path);
    const [parent, name] = this.parentAndName(s, path);
    const existing = parent.children.get(name);
    if (existing instanceof Directory) throw new FsError("EISDIR", path);
    let f = existing as File | undefined;
    const created = f === undefined;
    if (f === undefined) {
      this.need(s, parent, W, path);
      f = new File(name, s.user, s.group);
    } else {
      this.need(s, f, W, path);
    }
    const bytes = encoder.encode(text);
    let next = bytes;
    if (append) {
      next = new Uint8Array(f.data.length + bytes.length);
      next.set(f.data);
      next.set(bytes, f.data.length);
    }
    if (next.length > f.data.length) this.beforeGrow(parent, next.length - f.data.length, null);
    if (created) parent.attach(f);
    f.data = next;
  }

  readFile(s: Session, path: string): string {
    const n = this.walk(s, path);
    if (!(n instanceof File)) throw new FsError("EISDIR", path);
    this.need(s, n, R, path);
    return decoder.decode(n.data);
  }

  ls(s: Session, path = "."): string[] {
    const n = this.walk(s, path);
    if (!(n instanceof Directory)) return [n.name]; // ls on a file prints the file
    this.need(s, n, R, path);
    return [...n.children.entries()]
      .map(([name, c]) => (c.isDir() ? name + "/" : name))
      .sort();
  }

  du(s: Session, path = "."): number {
    const n = this.walk(s, path);
    if (n.isDir()) this.need(s, n, R, path);
    return n.size(); // Composite: one call, the tree does the recursion
  }

  rm(s: Session, path: string, recursive = false): void {
    const [parent, name] = this.parentAndName(s, path);
    const n = parent.children.get(name);
    if (n === undefined) throw new FsError("ENOENT", path);
    if (n instanceof Directory && n.children.size > 0 && !recursive) throw new FsError("ENOTEMPTY", path);
    // Simplification: rm -r checks only the top parent, real rm needs W+X on every subdirectory
    this.need(s, parent, W | X, path);
    parent.detach(name);
  }

  /** rename(2)-style move. Returns the final absolute path. */
  mv(s: Session, src: string, dst: string): string {
    const [sp, sname] = this.parentAndName(s, src);
    const node = sp.children.get(sname);
    if (node === undefined) throw new FsError("ENOENT", src);
    let target: Node | null = null;
    try {
      target = this.walk(s, dst);
    } catch (e) {
      if (!(e instanceof FsError) || e.code !== "ENOENT") throw e;
    }
    const [dp, dname]: [Directory, string] =
      target instanceof Directory ? [target, node.name] : this.parentAndName(s, dst);
    if (dp === sp && dname === sname) return node.path(); // onto itself: no-op
    for (let a: Node | null = dp; a !== null; a = a.parent) {
      if (a === node) throw new FsError("EINVAL", dst); // never into its own subtree
    }
    const existing = dp.children.get(dname);
    if (existing !== undefined && (existing.isDir() || node.isDir())) throw new FsError("EEXIST", dst);
    this.need(s, sp, W | X, src);
    this.need(s, dp, W | X, dst);
    if (dp !== sp) this.beforeGrow(dp, node.size(), node);
    // every check passed: only now mutate, so a failure never loses the node
    if (existing !== undefined) dp.detach(dname);
    sp.detach(sname);
    node.name = dname;
    dp.attach(node);
    return node.path();
  }

  chmod(s: Session, path: string, mode: number): void {
    const n = this.walk(s, path);
    if (s.user !== "root" && s.user !== n.owner) throw new FsError("EPERM", path);
    n.mode = mode;
  }

  chown(s: Session, path: string, owner: string, group: string): void {
    const n = this.walk(s, path);
    if (s.user !== "root") throw new FsError("EPERM", path);
    n.owner = owner;
    n.group = group;
  }

  realpath(s: Session, path: string): string {
    return this.walk(s, path).path();
  }

  cd(s: Session, path: string): void {
    const n = this.walk(s, path);
    if (!n.isDir()) throw new FsError("ENOTDIR", path);
    s.cwd = n.path();
  }
}

export function check(ok: boolean, what: string): void {
  if (!ok) throw new Error("check failed: " + what);
}

export function expect(code: string, fn: () => unknown): void {
  try {
    fn();
  } catch (e) {
    if (e instanceof FsError && e.code === code) return;
    throw new Error(`expected ${code}, got ${String(e)}`);
  }
  throw new Error(`expected ${code}, nothing thrown`);
}

function demo(): void {
  const fs = new FileSystem();
  const root = new Session("root", "root");
  fs.mkdir(root, "/home/alice", true);
  fs.chown(root, "/home/alice", "alice", "dev");
  const alice = new Session("alice", "dev", "/home/alice");
  const bob = new Session("bob", "ops");
  const same = (a: string[], b: string[]) => JSON.stringify(a) === JSON.stringify(b);

  // mkdir -p, relative paths, ".", "..", "//" and trailing slashes
  fs.mkdir(alice, "projects/archon/docs/", true);
  fs.mkdir(alice, "projects/archon", true);
  expect("EEXIST", () => fs.mkdir(alice, "projects"));
  fs.writeFile(alice, "projects/archon/docs/a.md", "hello");
  fs.writeFile(alice, "./projects//archon/docs/../readme.txt", "hi!");
  check(same(fs.ls(alice, "projects/archon"), ["docs/", "readme.txt"]), "ls");
  check(same(fs.ls(alice, "/home/alice/projects/archon/readme.txt"), ["readme.txt"]), "ls file");
  expect("ENOTDIR", () => fs.ls(alice, "projects/archon/readme.txt/"));
  expect("ENOTDIR", () => fs.mkdir(alice, "projects/archon/readme.txt/x", true));
  expect("ENOENT", () => fs.ls(alice, "nope"));
  fs.writeFile(alice, "projects/archon/readme.txt", "!!", true);

  // size aggregation through the Composite
  check(fs.du(alice, "/home/alice") === 10, "du");
  check(fs.readFile(alice, "projects/archon/readme.txt") === "hi!!!", "append");

  // cd and ".." at the root
  fs.cd(alice, "projects/archon/docs/..");
  check(alice.cwd === "/home/alice/projects/archon", "cd ..");
  fs.cd(alice, "/../..");
  check(alice.cwd === "/", "cd above root");
  fs.cd(alice, "/home/alice");

  // mv edge cases
  check(fs.mv(alice, "projects/archon/readme.txt", "projects/archon/README") === "/home/alice/projects/archon/README", "rename");
  check(fs.mv(alice, "projects/archon/README", "projects") === "/home/alice/projects/README", "into dir");
  check(fs.mv(alice, "projects/README", "projects/README") === "/home/alice/projects/README", "onto itself");
  expect("EINVAL", () => fs.mv(alice, "projects", "projects/archon/docs"));
  expect("EINVAL", () => fs.mv(alice, "projects", "projects"));
  fs.writeFile(alice, "projects/other.txt", "x");
  fs.mv(alice, "projects/other.txt", "projects/README");
  check(same(fs.ls(alice, "projects"), ["README", "archon/"]), "replace file");
  fs.mkdir(alice, "archon");
  expect("EEXIST", () => fs.mv(alice, "archon", "projects/README"));
  expect("EINVAL", () => fs.rm(alice, "/"));

  // permissions
  expect("EACCES", () => fs.writeFile(bob, "/home/alice/evil", "x"));
  check(same(fs.ls(bob, "/home/alice"), ["archon/", "projects/"]), "bob can list 755");
  fs.chmod(alice, "/home/alice", 0o700);
  expect("EACCES", () => fs.ls(bob, "/home/alice"));
  expect("EACCES", () => fs.readFile(bob, "/home/alice/projects/README"));
  expect("EPERM", () => fs.chmod(bob, "/home/alice", 0o777));

  // rm
  expect("ENOTEMPTY", () => fs.rm(alice, "projects"));
  fs.rm(alice, "projects", true);
  check(same(fs.ls(alice), ["archon/"]), "rm -r");
  console.log("typescript: all file system checks passed");
}

demo();

Reading the code

A few lines carry most of the design:

  • walk is the only resolver. mkdir -p is walk(path, create=true), which creates each missing directory as it goes and checks w on the parent before each creation. That removes the usual duplicate "resolve" and "ensure" loops, so ., .. and slash handling can't drift apart between them. cd is walk plus a directory check, and realpath is walk(...).path().
  • parentAndName refuses "", . and .. as a final name. That one check makes rm /, rm ., mkdir .. and mv / x all fail with EINVAL, with no special cases in the commands.
  • mv is a sequence of checks, then four lines of mutation. The checks are: source exists, work out the target parent and name, stop if it's the same place, climb from the destination to the root looking for the source, reject a collision that involves a directory, check permissions, run the quota hook. Only then does it detach and attach. Any exception before that point leaves the tree untouched, which is what the Command pattern undo extension relies on too.
  • Moving onto an existing file replaces it, like rename(2). Moving onto an existing directory moves into it. Moving a directory onto a file, or anything onto a non-empty name involving a directory, is EEXIST. GNU mv will also replace an empty directory with a directory. We chose the simpler, stricter rule and say so.
  • ls on a file returns just that file's name, as ls does, and ls on a directory needs r on it. Directories get a trailing / in the listing so tests can tell them apart.
  • du is one call to node.size(). The caller doesn't know or care whether the node is a file or a directory. That's the Composite paying for itself.
  • write creates the file object first and attaches it last. If the quota hook throws, a half-created empty file isn't left behind.
PatternWhere UsedWhy
CompositeFile and Directory share FileSystemEntry interfaceUniform treatment of files and directories
IteratorDirectory.list() and search methodsTraverse tree without exposing internals
StrategySearch predicates (find by name, size, extension)Flexible search criteria without modifying FileSystem
Template MethodgetPath(), getSize() in base vs subclassesCommon path logic, specialized size calculation

Correction (2026-11-10): that last row isn't Template Method

Template Method means a base-class method that fixes the steps of an algorithm and calls abstract "hook" steps that subclasses fill in. getPath() is ordinary inherited behaviour (it calls nothing abstract), and getSize() is plain polymorphism, which is part of Composite itself. Calling it Template Method in an interview invites a follow-up you don't want. If you need a real one here, the quota hook in the complete implementation is close: mv and writeFile fix the sequence and call an overridable beforeGrow step. See Template Method.

Patterns: why each one, and what we rejected

Composite (pattern page) is the core decision. Files and directories share Node, so size(), path() and traversal work on any node, and the service never asks "is this a file or a directory?" just to compute something.

  • Rejected: one Entry class with an isDir flag and both a content and a children field. It's fewer classes, but every method starts with if (isDir), a file carries an unused map, and nothing stops code from adding children to a file. With Composite that's a type error.
  • Rejected: a flat Map<String, Entry> keyed by full path. Lookup is for an exact path, and some interviewers will suggest it. But ls becomes a prefix scan over every key, and mv /a /b has to rewrite the key of every descendant, which is for a subtree of nodes. Deleting a directory has the same problem. The tree makes mv . Mention the flat map as a valid index on top of the tree if exact-path lookups dominate.
  • Rejected: "transparent" Composite with add/remove declared on Node so files throw at runtime. GoF discusses both forms. We use the "safe" form, with child management only on Directory, because a compile-time error beats a runtime one, and the service downcasts in exactly one place (walk).

Facade. FileSystem is the single entry point that hides resolution, permission checks and locking behind shell-like verbs. Callers never touch children directly. Rejected: exposing Directory.add publicly and letting callers build trees themselves, which spreads permission checks and invariants across every caller.

Strategy, as plain functions. The search predicates (findByName, findBySize) and the find extension take a predicate function. That's Strategy without the ceremony of an interface per criterion. Rejected: a SearchCriteria class hierarchy. With lambdas available in all three languages, it adds files and no behaviour. If criteria need to be combined, saved or printed, the Specification pattern is the next step up.

Iterator. Traversal (find, printTree) walks children without exposing the map. In Python the extension's _iter is a generator, which is the most direct form of the pattern.

Command (pattern page) appears only in the undo extension. Each mv becomes an object with execute and undo, and a history holds two stacks.

Hook (a tiny Template Method). beforeGrow is a protected no-op that the core calls at the only two places where bytes are added under a directory. The quota extension overrides it. Rejected: an Observer list of listeners. With one consumer, a list is speculative, and an observer that can veto a write (by throwing) isn't really an observer.

What we deliberately didn't use: Singleton for FileSystem (tests need fresh instances and two trees should be able to coexist), and Visitor for operations over the tree (it pays off when there are many node types and many operations; here there are two node types and size() is one line).

Complexity Analysis

OperationTimeSpace
Resolve path where = path depth
Create file/dir
Delete to find + to remove
List directory where = children count
Get directory size where = total descendants recursion
Search (find) where = all entries below start recursion

The complete implementation adds a few operations worth listing:

OperationTimeNotes
mvResolve both paths, then climb from the destination to the root for the subtree check
mkdir -pOne walk, creating as it goes
lsSorting children; in Java, where the TreeMap is already sorted
path()Walk parent pointers up to the root
du (recursive) with cached sizes, at per write

Concurrency

The question to answer first is what's shared. Here it's the whole tree: every children map, every parent pointer, every file's bytes and every mode. Sessions are not shared: each caller owns one, which is why cd can mutate its session's cwd while holding only a read lock.

What can go wrong without a lock

  • Lost entries. Two threads create different files in the same directory. Both read the map, both insert, and with an unsynchronized HashMap one insert can be lost or the map can be corrupted during a resize.
  • Double move. Two threads mv /race/x to different places. Both see the file, both detach it, and the second detach fails halfway or the file ends up attached in two directories.
  • Cycle by race. Thread A runs mv /a /b/inner while thread B runs mv /b /a/inner. Each subtree check passes against the tree as it was, and the two moves together create a cycle that's unreachable from the root. This one is the reason to think hard before choosing fine-grained locks.
  • Torn reads. du sums sizes while a mv detaches a subtree from one place and attaches it in another, so the total counts the subtree twice or not at all.

The choice: one read-write lock around the tree

The Java version wraps every command in a ReentrantReadWriteLock. Reads (ls, readFile, du, realpath, cd) share the read lock, and mutations (mkdir, writeFile, rm, mv, chmod, chown) take the write lock. Each command is therefore atomic and sees a consistent tree, so all four races above disappear. The tests check two of them directly: two threads race to move one file and exactly one gets ENOENT, and 8 threads create 800 files in one directory and all 800 are there.

The Python version uses a single threading.Lock because the standard library has no read-write lock. Reads serialize too, which is fine for an interview and for CPython's GIL anyway. The TypeScript version has no lock: none of its methods await, so each one runs to completion on the event loop before any other call starts. The moment a method awaits (for example, reading content from disk), that guarantee is gone and you'd need an async mutex around the critical section.

Why not per-node locks?

It's the natural follow-up: "a global lock serializes everything, can you do better?" You can, with care:

  1. Lock coupling for reads. Resolve a path hand over hand: lock the child, then release the parent. Readers in different subtrees never contend.
  2. Locks for a mutation. mkdir, write and rm touch one directory's map, so they lock just the parent directory in write mode, after resolving the path.
  3. mv is the hard case. It changes two directories, and the subtree check depends on the ancestor chain of the destination staying put. The classic approach, used by Linux's VFS for cross-directory renames, is a single rename lock per file system, taken before locking the two parents. The rename lock serializes moves against each other (which kills the cycle race), and the two parent locks are taken in a fixed order (ancestor first, otherwise by a stable id) to avoid deadlock.

Say that the global lock is the right first answer: it's obviously correct, and in-memory operations take microseconds, so contention only matters at very high thread counts. Then describe the finer scheme as the upgrade if profiling shows the lock is hot. See thread-safe class design for the general trade-off between coarse and fine locks.

The interviewer adds X

Three extensions come up often. Each is shown as code that sits on top of the complete implementation without editing its commands, which is the point to make: the core was designed with one seam (beforeGrow) and a public, composable API.

Extension A: directory quotas

"Each user's home directory can hold at most N bytes."

A quota is a limit attached to a directory. Every write and every move into a directory has to check the limit of every ancestor that has one, because a write to /home/alice/a/f grows /home/alice too. The core already calls beforeGrow(dir, delta, moving) before any growth. The extension overrides it. The one subtle case is a move inside the same quota tree: moving /home/alice/a/g to /home/alice/b doesn't change the total of /home/alice, so a node that is already inside a quota directory is skipped for that directory.

class QuotaFileSystem extends FileSystem {
    private final Map<Directory, Long> quotas = new HashMap<>();   // identity keys: Node has no equals()

    void setQuota(Session s, String path, long limit) {
        write(() -> {
            if (!(walk(s, path, false) instanceof Directory d)) throw new FsError("ENOTDIR", path);
            if (!s.user.equals("root")) throw new FsError("EPERM", path);
            quotas.put(d, limit);
            return null;
        });
    }

    @Override protected void beforeGrow(Directory dir, long delta, Node moving) {
        for (Directory a = dir; a != null; a = a.parent) {
            Long limit = quotas.get(a);
            // a node moved within the same quota tree is already counted there
            if (limit != null && !inside(moving, a) && a.size() + delta > limit)
                throw new FsError("EDQUOT", a.path());
        }
        // Simplification: a.size() walks the subtree on every write, cache sizes per directory if writes are hot
    }

    private static boolean inside(Node n, Directory d) {
        for (; n != null; n = n.parent) if (n == d) return true;
        return false;
    }
}
class QuotaFileSystem(FileSystem):
    def __init__(self) -> None:
        super().__init__()
        self.quotas: dict[Directory, int] = {}

    def set_quota(self, s: Session, path: str, limit: int) -> None:
        with self._lock:
            d = self._walk(s, path)
            if not isinstance(d, Directory):
                raise FsError("ENOTDIR", path)
            if s.user != "root":
                raise FsError("EPERM", path)
            self.quotas[d] = limit

    def _before_grow(self, directory: Directory, delta: int, moving: Node | None) -> None:
        a: Directory | None = directory
        while a is not None:
            limit = self.quotas.get(a)
            # a node moved within the same quota tree is already counted there
            if limit is not None and not _inside(moving, a) and a.size() + delta > limit:
                raise FsError("EDQUOT", a.path())
            a = a.parent
        # Simplification: a.size() walks the subtree on every write, cache sizes per directory if writes are hot


def _inside(node: Node | None, d: Directory) -> bool:
    while node is not None:
        if node is d:
            return True
        node = node.parent
    return False
class QuotaFileSystem extends FileSystem {
  private readonly quotas = new Map<Directory, number>();

  setQuota(s: Session, path: string, limit: number): void {
    const d = this.walk(s, path);
    if (!(d instanceof Directory)) throw new FsError("ENOTDIR", path);
    if (s.user !== "root") throw new FsError("EPERM", path);
    this.quotas.set(d, limit);
  }

  protected override beforeGrow(dir: Directory, delta: number, moving: Node | null): void {
    for (let a: Directory | null = dir; a !== null; a = a.parent) {
      const limit = this.quotas.get(a);
      // a node moved within the same quota tree is already counted there
      if (limit !== undefined && !inside(moving, a) && a.size() + delta > limit) {
        throw new FsError("EDQUOT", a.path());
      }
    }
    // Simplification: a.size() walks the subtree on every write, cache sizes per directory if writes are hot
  }
}

function inside(n: Node | null, d: Directory): boolean {
  for (; n !== null; n = n.parent) if (n === d) return true;
  return false;
}

Because mv and writeFile call the hook after all their other checks and before any mutation, a write that exceeds the quota leaves no trace: the test moves a 5-byte file into a home directory with 0 bytes to spare, gets EDQUOT, and checks that the file is still in /tmp. When writes get hot, switch to cached sizes: store size on each Directory and add the delta to every ancestor inside attach, detach and the byte assignment in writeFile. The quota check then becomes instead of .

Extension B: undo and redo for mv

"Users make mistakes. Add undo for moves."

This is the Command pattern. Each move becomes an object that remembers enough to reverse itself: the absolute path it came from and the absolute path where it landed (which mv returns, because moving into a directory changes the final name). A history keeps a done stack and an undone stack, and any new command clears the redo stack.

interface Command { void execute(); void undo(); }

class MoveCommand implements Command {
    private final FileSystem fs; private final Session s; private final String src, dst;
    private String origin, landed;
    MoveCommand(FileSystem fs, Session s, String src, String dst) { this.fs = fs; this.s = s; this.src = src; this.dst = dst; }
    public void execute() { origin = fs.realpath(s, src); landed = fs.mv(s, src, dst); }
    public void undo() { fs.mv(s, landed, origin); }
}

class History {
    private final Deque<Command> done = new ArrayDeque<>(), undone = new ArrayDeque<>();
    void run(Command c) { c.execute(); done.push(c); undone.clear(); }   // new action clears redo
    void undo() { Command c = done.pop(); c.undo(); undone.push(c); }
    void redo() { Command c = undone.pop(); c.execute(); done.push(c); }
}
class MoveCommand:
    def __init__(self, fs: FileSystem, s: Session, src: str, dst: str):
        self.fs, self.s, self.src, self.dst = fs, s, src, dst
        self.origin = ""
        self.landed = ""

    def execute(self) -> None:
        self.origin = self.fs.realpath(self.s, self.src)
        self.landed = self.fs.mv(self.s, self.src, self.dst)

    def undo(self) -> None:
        self.fs.mv(self.s, self.landed, self.origin)


class History:
    def __init__(self) -> None:
        self._done: list[MoveCommand] = []
        self._undone: list[MoveCommand] = []

    def run(self, cmd: MoveCommand) -> None:
        cmd.execute()
        self._done.append(cmd)
        self._undone.clear()  # a new action invalidates the redo stack

    def undo(self) -> None:
        cmd = self._done.pop()
        cmd.undo()
        self._undone.append(cmd)

    def redo(self) -> None:
        cmd = self._undone.pop()
        cmd.execute()
        self._done.append(cmd)
interface Command {
  execute(): void;
  undo(): void;
}

class MoveCommand implements Command {
  private origin = "";
  private landed = "";
  constructor(private fs: FileSystem, private s: Session, private src: string, private dst: string) {}
  execute(): void {
    this.origin = this.fs.realpath(this.s, this.src);
    this.landed = this.fs.mv(this.s, this.src, this.dst);
  }
  undo(): void {
    this.fs.mv(this.s, this.landed, this.origin);
  }
}

class History {
  private done: Command[] = [];
  private undone: Command[] = [];
  run(c: Command): void {
    c.execute();
    this.done.push(c);
    this.undone = []; // a new action invalidates the redo stack
  }
  undo(): void {
    const c = this.done.pop()!;
    c.undo();
    this.undone.push(c);
  }
  redo(): void {
    const c = this.undone.pop()!;
    c.execute();
    this.done.push(c);
  }
}

Two limits are worth stating rather than hiding. First, undo replays a move in reverse, so it fails if something now occupies the original path. That's a correct, visible failure (EEXIST) rather than silent corruption. Second, a move that replaced a file can't be undone this way, because the replaced file is gone. To support that, the command would keep the detached node and reattach it on undo, which needs a package-private restore(parent, node) on the file system. Undoing rm works the same way: keep the detached subtree in the command (a trash can), and reattach it on undo.

Extension C: find with composable filters

"Find every .py file over 5 bytes under /src, and skip folders I can't read."

The predicate approach from the original find scales well once the predicates compose. Small factory functions build predicates, and combines them (Java's Predicate.and, or a three-line both helper elsewhere), and the traversal skips unreadable directories the way find(1) does instead of failing the whole search.

class SearchableFileSystem extends FileSystem {
    List<String> find(Session s, String path, Predicate<Node> pred) {
        return read(() -> {
            List<String> out = new ArrayList<>();
            collect(s, walk(s, path, false), pred, out);
            Collections.sort(out);
            return out;
        });
    }

    private void collect(Session s, Node n, Predicate<Node> pred, List<String> out) {
        if (pred.test(n)) out.add(n.path());
        if (!(n instanceof Directory d)) return;
        try { need(s, d, R, d.path()); } catch (FsError e) { return; }   // like find(1): skip unreadable dirs
        for (Node c : d.children.values()) collect(s, c, pred, out);
    }

    static Predicate<Node> nameEnds(String suffix) { return n -> n.name.endsWith(suffix); }
    static Predicate<Node> largerThan(long size) { return n -> n instanceof File && n.size() > size; }
}
Pred = Callable[[Node], bool]


def name_ends(suffix: str) -> Pred:
    return lambda n: n.name.endswith(suffix)


def larger_than(size: int) -> Pred:
    return lambda n: isinstance(n, File) and n.size() > size


def both(a: Pred, b: Pred) -> Pred:
    return lambda n: a(n) and b(n)


class SearchableFileSystem(FileSystem):
    def find(self, s: Session, path: str, pred: Pred) -> list[str]:
        with self._lock:
            start = self._walk(s, path)
            return sorted(n.path() for n in self._iter(s, start) if pred(n))

    def _iter(self, s: Session, node: Node) -> Iterator[Node]:
        yield node
        if isinstance(node, Directory):
            try:
                self._need(s, node, R, node.path())
            except FsError:
                return  # like find(1): skip unreadable directories instead of failing
            for child in list(node.children.values()):
                yield from self._iter(s, child)
type Pred = (n: Node) => boolean;
const nameEnds = (suffix: string): Pred => (n) => n.name.endsWith(suffix);
const largerThan = (size: number): Pred => (n) => n instanceof File && n.size() > size;
const both = (a: Pred, b: Pred): Pred => (n) => a(n) && b(n);

class SearchableFileSystem extends FileSystem {
  find(s: Session, path: string, pred: Pred): string[] {
    const out: string[] = [];
    const visit = (n: Node): void => {
      if (pred(n)) out.push(n.path());
      if (!(n instanceof Directory)) return;
      try {
        this.need(s, n, R, n.path());
      } catch {
        return; // like find(1): skip unreadable directories
      }
      for (const c of n.children.values()) visit(c);
    };
    visit(this.walk(s, path));
    return out.sort();
  }
}

The extension files import the core (from filesystem import * style in Python, import { ... } from "./filesystem.ts" in TypeScript, the same default package in Java) and add their own asserts. All three were run against the core above.

Testing

The main/demo function in each language is a compact test suite. In a real codebase you'd split it into one test per behaviour, but the cases are the same. Group them by the thing that can break:

AreaCases asserted
Path resolutionrelative to cwd; ./, //, .. in the middle; .. at the root stays at the root; trailing slash on a file is ENOTDIR; missing component is ENOENT; descending into a file is ENOTDIR
mkdir-p creates the whole chain; -p on an existing directory succeeds; plain mkdir on an existing name is EEXIST; -p through a file is ENOTDIR
Files and sizecreate, overwrite, append; du of a directory equals the sum of its files (5 + 5 = 10 bytes)
mvrename in place; move into an existing directory keeps the name and returns the new path; moving onto itself is a no-op; moving a directory into its own subtree, or onto itself, is EINVAL; file over file replaces it; directory over file is EEXIST
rmnon-empty directory without -r is ENOTEMPTY; -r removes it; rm / is EINVAL
Permissionsanother user can't create in a 0755 directory they don't own (EACCES); they can list it; after chmod 0700 they can neither list it nor read a file inside it (search permission); a non-owner chmod is EPERM
Concurrency (Java, Python)two threads move the same file to different places, exactly one succeeds and the other gets ENOENT, one file remains; 8 threads create 100 files each in one directory, all 800 exist and du is 1,600
Extensionsquota rejects an over-limit write and an over-limit move without changing anything, and allows a move inside the same quota tree; undo, undo, redo restore the exact listing; find combines filters and skips an unreadable directory for a non-owner

A few testing habits matter more than the exact list:

  • Assert on the error code, not just "it threw". expect("ENOTDIR", ...) catches a regression where a trailing-slash bug turns into ENOENT, which a generic assertThrows would miss.
  • After every failing mutation, assert the tree is unchanged. That's the test that would have caught the original move() losing its source.
  • Make concurrency tests deterministic in their outcome, not their schedule. "Exactly one of two movers wins" is true for every interleaving, so the test never flakes. Run it in a loop a few hundred times in CI to give races a chance to show up.
  • Test through the public API. None of the tests touch children directly, so the internal representation (a TreeMap, a dict, a Map) can change without rewriting them.

Common Interview Mistakes

  1. Forgetting the parent reference — needed for getPath() and move operations
  2. Not handling edge cases — root deletion, moving to non-directory, circular references
  3. Ignoring permissions — real file systems enforce permissions at every level
  4. Name collisions — must check for duplicate names when adding entries

Common mistakes in more detail

The four above are the classics. These are the ones that separate a passable answer from a strong one:

  1. Mutating before validating. Detaching the source and then discovering a name collision is the single most common mv bug, and it was in this page's original code. Write every command as "all checks, then mutation", and say so aloud.
  2. No subtree check on mv. mv /a /a/b must fail. The check is three lines (climb from the destination parent to the root and look for the source), and forgetting it creates an unreachable cycle, which in a real system is leaked storage.
  3. Two path parsers. A resolve for reads and a separate ensureDirectory for mkdir -p will drift apart: one handles .., the other doesn't. Have one walker with a create flag.
  4. Splitting on / and filtering empties, then stopping. That handles // but not ., .. or trailing slashes, and it silently accepts file/... Spend two minutes listing path edge cases before coding; the interviewer is waiting for it.
  5. Root named "/". It looks natural and produces //home the moment you join names. Give the root an empty name, or special-case it in path().
  6. Permissions checked once, on the final node. Unix checks x on every directory in the path and w on the parent for create and delete. Checking w on the file you're deleting is wrong in both directions.
  7. ls that returns objects the caller can mutate. Returning the live children collection lets a caller add entries without permission checks. Return names or a copy.
  8. Recursing size() on every write for a quota without saying so. It's fine as a first version, but name the cost and the cached alternative before the interviewer does.
  9. Using isDirectory() checks everywhere instead of polymorphism. If getSize() is if (isDir) sum children else length, the Composite has been reinvented badly. Let each class answer for itself.
  10. Making FileSystem a Singleton. It makes tests share state, and nothing in the problem needs exactly one tree.

Extensions to Discuss

  • Symbolic links (Proxy pattern — link points to another entry)
  • File versioning (Memento pattern — save and restore states)
  • Observers for file changes (watch for modifications, like fs.watch())
  • Quota management (max size per directory or user)
  • Concurrent access (read/write locks per entry)

Interview follow-ups

How would you add symbolic links?

Add a third leaf, Symlink, that stores a target path string, not a node reference, because the target may not exist yet or may be replaced later. Resolution changes in one place: when walk reaches a symlink in the middle of a path, or at the end when the command follows links, it resolves the target (relative to the link's parent directory) and continues with the remaining components. Count hops and fail with ELOOP after a limit (Linux uses 40) to stop a -> b -> a. .. after a link goes to the parent of the target, which is why the physical walk matters. Commands like rm and mv act on the link itself, not its target, so parentAndName doesn't follow the final component. Structurally a symlink is close to a Proxy: it stands in for another node.

And hard links?

A hard link is a second name for the same file object. That breaks the tree's "one parent" rule, so the name has to move off the node and into the directory entry: Directory.children maps name to node, and the node no longer stores name or a single parent. The node gets a link count, and rm deletes the data only when the count reaches zero. path() stops being well defined, because a file can have several paths. Directories usually can't be hard-linked, which is precisely what keeps the directory structure a tree and makes .. unambiguous.

Why not store every node in a hash map keyed by its full path?

Exact lookups become , but ls becomes a scan for keys with a prefix, and mv or rm -r of a directory must rewrite or delete every descendant's key, which is . Permission checks still need each ancestor, which you'd look up one by one anyway. The tree gives for everything. If profiling showed exact lookups dominated, you'd keep the tree as the source of truth and add a path cache invalidated on mv and rm.

How would you make `du` O(1)?

Store a size on each directory. Every change of bytes under it (writing a file, attaching, detaching) adds the delta to the parent and walks up to the root. Writes become . The danger is drift: one forgotten update and the counters are wrong forever. Keep the updates inside attach, detach and one setData method, and add a debug assertion that compares the cached size with a recursive recount in tests.

How would you persist this to disk?

Separate names from data, the way real file systems do. Each file and directory becomes an inode with an id, metadata (owner, mode, size, times) and a list of block numbers. A directory's data is a list of (name, inode id) entries. A free-block bitmap tracks space, and a write-ahead journal makes multi-step updates such as mv crash-safe, because rename touches two directories and a crash in between would otherwise leave the file in both or neither. In an LLD interview, put persistence behind an interface (a repository for inodes) and keep the in-memory tree as the model.

How do you handle very large files?

Don't keep one contiguous byte array. Store content as fixed-size chunks (say 4 KB) in a list or a map from chunk index to bytes. Reads and writes at an offset touch only the affected chunks, appends add chunks, and sparse files leave missing chunks unallocated. Size becomes a stored field rather than the array length.

What changes if two users can be in several groups?

Session holds a set of groups, and the permission check uses the group bits if the node's group is in that set. The owner rule doesn't change: an owner always gets only the owner bits, even if a group would allow more. For richer rules (per-user grants), add an access-control list on each node and check it before the mode bits.

Why does `cd` need only the read lock, even though it changes state?

It changes the session, not the tree. Each caller owns its session, so there's no sharing to protect. What cd needs is a consistent view of the tree while it resolves the path, and the read lock gives that.

What happens to a session whose current directory is deleted?

Its cwd string still names the removed path, so the next relative operation fails with ENOENT when walk resolves the cwd. That's what Unix does too (getcwd fails in a deleted directory). An alternative is to store the cwd as a node reference. Then a moved directory stays the working directory, which matches Unix even more closely, but a deleted one is a detached node, and you'd need to check for that.

How would you watch for changes, like `inotify` or `fs.watch`?

Observer. A watcher registers on a directory, and attach, detach and writes publish events (created, deleted, modified, moved) to the watchers of the affected directory and, for recursive watches, its ancestors. Deliver events after the write lock is released, or on a queue, so a slow watcher can't block the file system. See Observer.

How would you add file versioning?

Keep the previous contents each time a file is overwritten: a list of (version, bytes, timestamp) on the file, capped by count or total size. Restoring a version is a write of the old bytes. This is Memento: the file hands out opaque snapshots and restores from them, and nothing outside can edit a snapshot.

Name ordering and case sensitivity?

Keep children in a sorted map if ls must be sorted and listing is frequent, or sort on demand if creation dominates. Case-insensitive systems (the macOS and Windows defaults) look names up by a folded key but display the original spelling, so the map key and the stored name differ. Decide that at the start; retrofitting it changes every lookup.

Further Reading