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:
| Question | Why it matters | Assumed answer |
|---|---|---|
| In-memory only, or backed by a disk? | Disk means inodes, blocks and a cache: a different problem | In-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 path | Yes: 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 ./.. handling | Yes |
| Which commands? | Sets the public API | mkdir [-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 detection | Not at first, discussed as a follow-up |
| Concurrent callers? | Decides the locking story | Yes, several threads may call the same instance |
| Is file content text or bytes? | Size is bytes, so text needs encoding | Bytes, written as UTF-8 text in the API |
| What happens on error? | Exceptions vs result codes | One exception type carrying a POSIX-like code (ENOENT, EEXIST, ENOTDIR, EISDIR, EACCES, EPERM, EINVAL, ENOTEMPTY) |
Functional Requirements
| # | Requirement | Details |
|---|---|---|
| FR-1 | Create files and directories | Create at any path in the tree |
| FR-2 | Delete files and directories | Recursive delete for directories |
| FR-3 | Move/rename | Move a file/directory to a new path |
| FR-4 | List contents | List immediate children or recursive tree |
| FR-5 | Path resolution | Navigate paths like /home/user/docs/file.txt |
| FR-6 | File content | Read and write file contents |
| FR-7 | Search | Find by name, extension, size, or modified date |
| FR-8 | Permissions | Read, write, execute permissions per entry |
| FR-9 | Size calculation | File size directly; directory size = sum of children |
The complete implementation later on this page adds three requirements that the table above leaves implicit:
| # | Requirement | Details |
|---|---|---|
| FR-10 | Sessions | Each caller has a user, a group and a current directory, and cd changes it |
| FR-11 | mkdir -p | Create every missing directory on the path, and succeed if the directory already exists |
| FR-12 | Safe mv | mv 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
mvmust 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
EEXISTvsENOTDIRinstead 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
| Entity | Kind | Holds | Relationship |
|---|---|---|---|
Node | Abstract component | name, owner, group, mode bits, parent | The common type of everything in the tree |
File | Leaf | bytes | Has exactly one parent directory |
Directory | Composite | map of name to child Node | Owns its children; a child belongs to exactly one directory |
FileSystem | Service / facade | the root directory and the lock | Parses paths, checks permissions, runs commands |
Session | Value-ish context | user, group, current directory | One per caller; passed to every command |
FsError | Error | a code and the path | Thrown by every failed command |
Three modelling decisions are worth saying aloud:
- 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). - 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 onlyattachanddetachtouch it. - 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:
| Input | cwd | Result | Rule |
|---|---|---|---|
/ | any | the root | Empty components are skipped, so nothing is left to walk |
//home///alice | any | /home/alice | Repeated slashes collapse, as POSIX allows |
docs/a.md | /home/alice | /home/alice/docs/a.md | Relative 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 /../.. | any | the root | .. at the root stays at the root |
a.md/ | /home/alice | ENOTDIR | A trailing slash demands a directory |
a.md/x | /home/alice | ENOTDIR | You can't descend into a file |
missing/x | any | ENOENT | A missing middle component |
| empty string | any | ENOENT | POSIX 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.
| Operation | Bits required |
|---|---|
| Cross a directory while resolving a path | x on that directory |
ls a directory | r on it |
ls a file | nothing beyond reaching it |
| Read a file | r on the file |
| Write or append to an existing file | w on the file |
Create a file or directory, rm an entry | w and x on the parent directory |
mv | w and x on both the source parent and the destination parent |
chmod | be the owner, or root (EPERM otherwise) |
chown | be 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 | |
| Risk | Slow du on huge trees | Counters 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)
File System (Path Resolution + Search)
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
xon every directory it crosses and the right bits for each command; - validates
mvcompletely before mutating, supports rename, and refuses to move a directory into itself; - reports failures with a POSIX-like code instead of
null,falseor 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:
walkis the only resolver.mkdir -piswalk(path, create=true), which creates each missing directory as it goes and checkswon the parent before each creation. That removes the usual duplicate "resolve" and "ensure" loops, so.,..and slash handling can't drift apart between them.cdiswalkplus a directory check, andrealpathiswalk(...).path().parentAndNamerefuses"",.and..as a final name. That one check makesrm /,rm .,mkdir ..andmv / xall fail withEINVAL, with no special cases in the commands.mvis 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, isEEXIST. GNUmvwill also replace an empty directory with a directory. We chose the simpler, stricter rule and say so. lson a file returns just that file's name, aslsdoes, andlson a directory needsron it. Directories get a trailing/in the listing so tests can tell them apart.duis one call tonode.size(). The caller doesn't know or care whether the node is a file or a directory. That's the Composite paying for itself.writecreates the file object first and attaches it last. If the quota hook throws, a half-created empty file isn't left behind.
| Pattern | Where Used | Why |
|---|---|---|
| Composite | File and Directory share FileSystemEntry interface | Uniform treatment of files and directories |
| Iterator | Directory.list() and search methods | Traverse tree without exposing internals |
| Strategy | Search predicates (find by name, size, extension) | Flexible search criteria without modifying FileSystem |
| Template Method | getPath(), getSize() in base vs subclasses | Common 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
Entryclass with anisDirflag and both acontentand achildrenfield. It's fewer classes, but every method starts withif (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. Butlsbecomes a prefix scan over every key, andmv /a /bhas to rewrite the key of every descendant, which is for a subtree of nodes. Deleting a directory has the same problem. The tree makesmv. Mention the flat map as a valid index on top of the tree if exact-path lookups dominate. - Rejected: "transparent" Composite with
add/removedeclared onNodeso files throw at runtime. GoF discusses both forms. We use the "safe" form, with child management only onDirectory, 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
| Operation | Time | Space |
|---|---|---|
| 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:
| Operation | Time | Notes |
|---|---|---|
mv | Resolve both paths, then climb from the destination to the root for the subtree check | |
mkdir -p | One walk, creating as it goes | |
ls | Sorting 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
HashMapone insert can be lost or the map can be corrupted during a resize. - Double move. Two threads
mv /race/xto different places. Both see the file, both detach it, and the seconddetachfails halfway or the file ends up attached in two directories. - Cycle by race. Thread A runs
mv /a /b/innerwhile thread B runsmv /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.
dusums sizes while amvdetaches 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:
- Lock coupling for reads. Resolve a path hand over hand: lock the child, then release the parent. Readers in different subtrees never contend.
- Locks for a mutation.
mkdir, write andrmtouch one directory's map, so they lock just the parent directory in write mode, after resolving the path. mvis 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
.pyfile 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:
| Area | Cases asserted |
|---|---|
| Path resolution | relative 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 size | create, overwrite, append; du of a directory equals the sum of its files (5 + 5 = 10 bytes) |
mv | rename 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 |
rm | non-empty directory without -r is ENOTEMPTY; -r removes it; rm / is EINVAL |
| Permissions | another 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 |
| Extensions | quota 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 intoENOENT, which a genericassertThrowswould 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
childrendirectly, so the internal representation (aTreeMap, a dict, aMap) can change without rewriting them.
Common Interview Mistakes
- Forgetting the parent reference — needed for getPath() and move operations
- Not handling edge cases — root deletion, moving to non-directory, circular references
- Ignoring permissions — real file systems enforce permissions at every level
- 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:
- Mutating before validating. Detaching the source and then discovering a name collision is the single most common
mvbug, and it was in this page's original code. Write every command as "all checks, then mutation", and say so aloud. - No subtree check on
mv.mv /a /a/bmust 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. - Two path parsers. A
resolvefor reads and a separateensureDirectoryformkdir -pwill drift apart: one handles.., the other doesn't. Have one walker with acreateflag. - Splitting on
/and filtering empties, then stopping. That handles//but not.,..or trailing slashes, and it silently acceptsfile/... Spend two minutes listing path edge cases before coding; the interviewer is waiting for it. - Root named
"/". It looks natural and produces//homethe moment you join names. Give the root an empty name, or special-case it inpath(). - Permissions checked once, on the final node. Unix checks
xon every directory in the path andwon the parent for create and delete. Checkingwon the file you're deleting is wrong in both directions. lsthat returns objects the caller can mutate. Returning the livechildrencollection lets a caller add entries without permission checks. Return names or a copy.- 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. - Using
isDirectory()checks everywhere instead of polymorphism. IfgetSize()isif (isDir) sum children else length, the Composite has been reinvented badly. Let each class answer for itself. - Making
FileSystema 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
- LLD Interviews Overview — SOLID principles and design patterns
- Trees — tree traversal algorithms used in recursive search
- Design Tic-Tac-Toe — another structured OOP design
- Composite pattern — the pattern this design is built on
- Command pattern — the basis of the undo extension
- Thread-Safe Class Design — coarse vs fine-grained locking
- The LLD Interview Framework — the 45-minute plan this page follows
- Design an In-Memory Key-Value Store — another in-memory data structure with concurrency and extensions
- Design Chess — Command for undo/redo in a game