mkdir -p, ls, cat, echo >>, mv and du, built from two classes that share one interface. The tree is the easy part; the marks are in path resolution, a move that must not swallow its own parent, and a quota that is checked before a single byte changes.
"Design a file system" is a favourite machine-coding prompt because it tests one pattern properly, Composite, and then a long tail of details that real tools get right and candidates usually don't. What does mkdir do when the parent doesn't exist? What does mv a.txt docs mean when docs is a directory, and when it isn't? What stops mv /home /home/asha/old? Every one of these has an answer in the behaviour of a Unix shell, and the interviewer expects you to know it, or to state your choice out loud.
This lesson builds the tree, the path resolver and the operations, with a byte quota and one lock, and uses Python's own FileNotFoundError, IsADirectoryError and friends so the errors read the way an operating system's would.
How the round runs#
"Implement an in-memory file system. Support mkdir, ls, reading and writing files, appending, moving and deleting. Paths are absolute and may contain . and ... We want a storage quota. Several threads will use it at once. 90 minutes, working code."
- 0–10 min — clarify: absolute or relative paths,
mkdir -p, whatlson a file returns,mvsemantics, quota, text or bytes - 10–20 min — the composite:
Node,File,Directory, andsize()as the recursive operation - 20–40 min — path resolution: normalising
.and.., walking the tree, the parent-and-name helper - 40–65 min — the operations, each with the error a shell would give
- 65–80 min — the quota, the lock, and a demo with concurrent appends
- 80–90 min — follow-ups: permissions, symlinks,
find, finer-grained locking
Requirements and clarifying questions#
| You ask | They answer | What it changes |
|---|---|---|
| Relative paths and a current directory? | Absolute only; a cd is a follow-up. |
Every path starts with / |
mkdir /a/b/c when /a doesn't exist? |
Fail, unless asked for -p. |
mkdir(path, parents=False); -p is idempotent |
ls on a file? |
Return just its name, like a shell. | ls handles both node types |
mv onto an existing directory? |
Move inside it. Onto an existing file: your choice. | We refuse to overwrite (like mv -n) and say so |
| Text or bytes? | Text in, but the quota counts bytes. | Store bytearray; encode as UTF-8 |
| Quota? | One quota for the whole file system. | A used counter checked before every write |
| Concurrency? | Many threads, same tree. | One lock around every operation; discuss finer locks |
The classes#
%% title: In-memory file system: the classes
classDiagram
class Node {
<<abstract>>
+name str
+parent Directory
+size() int
+path() str
}
class File {
+data bytearray
+size() int
}
class Directory {
+children dict
+size() int
}
class FileSystem {
+root Directory
+quota int
+used int
+mkdir(path, parents)
+ls(path) list
+write(path, text, append) int
+read(path) str
+mv(src, dst) str
+rm(path, recursive) int
+du(path) int
}
Node <|-- File
Node <|-- Directory
Directory "1" o-- "many" Node
FileSystem --> DirectoryDirectory holds Nodes, which may be files or directories: that recursive "has many of my own base type" arrow is what makes it a composite. Each node keeps a pointer to its parent, which gives you path() for free and makes the "can't move a directory inside itself" check a walk up the tree. FileSystem is the facade: it owns the root, the quota and the lock, and it's the only thing callers touch.
The interfaces#
# memfs.py, part 1: the composite: a file and a directory are both nodes
from __future__ import annotations
import threading
from abc import ABC, abstractmethod
class Node(ABC):
def __init__(self, name: str, parent: Directory | None) -> None:
self.name, self.parent = name, parent
@abstractmethod
def size(self) -> int: ...
def path(self) -> str:
parts, node = [], self
while node.parent is not None:
parts.append(node.name)
node = node.parent
return "/" + "/".join(reversed(parts))
class File(Node):
def __init__(self, name: str, parent: Directory) -> None:
super().__init__(name, parent)
self.data = bytearray()
def size(self) -> int:
return len(self.data)
class Directory(Node):
def __init__(self, name: str, parent: Directory | None) -> None:
super().__init__(name, parent)
self.children: dict[str, Node] = {}
def size(self) -> int: # the composite at work: a directory's size is its children's
return sum(c.size() for c in self.children.values())
class QuotaExceeded(OSError): ...size() on a directory is computed, not stored. That keeps every write O(1) and makes du O(subtree). If du were hot, you would cache sizes on directories and update every ancestor on each write: a classic trade-off to mention, not to build.
Path resolution#
Every operation starts the same way: turn a string into a node. It's two steps, and keeping them apart is what makes the errors right.
Normalise the string into a list of names: split on /, drop empty parts and ., and let .. pop the previous name (at the root, .. stays at the root, as in a shell). This is purely textual, which is correct here because there are no symbolic links; with symlinks, .. must be resolved during the walk instead.
Walk the list from the root. Each step can fail in two distinct ways, and the error should say which:
| Path | What's wrong | Error |
|---|---|---|
/home/nobody/x |
a name along the way doesn't exist | FileNotFoundError: /home/nobody |
/home/asha/readme.md/x |
a name along the way is a file | NotADirectoryError: /home/asha/readme.md |
read("/home/asha") |
the target is a directory | IsADirectoryError |
mkdir("/home") without -p |
the target exists | FileExistsError |
Most operations need "the parent directory and the last name" rather than the node itself: you can't walk to a file you're about to create. _parent_of(path) returns exactly that, and refuses the root, which has no parent and can't be written, moved or deleted.
The patterns, and why#
| Pattern | Where | Why it earns its place |
|---|---|---|
| Composite | Node ← File, Directory |
size(), path(), and future find or copy work on any node, at any depth, without type checks. |
| Facade | FileSystem |
Callers speak in paths; the tree, the quota and the lock are internal. |
| One shape for every operation | normalise → walk → check → mutate | Each method has the same steps, so each raises the same errors in the same order. |
| Iterator / Visitor (follow-up) | walk() over the tree |
find, du --max-depth and a backup job all become visitors of the same traversal. |
Concurrency and edge cases#
One re-entrant lock guards the whole tree, and every public method takes it. That sounds coarse, but think about what a finer scheme needs. mv changes two directories, the source's parent and the destination's, so per-directory locks must always be taken in one global order (say, by path) or two crossing moves deadlock. A walk down the tree would need hand-over-hand locking, and du would need a consistent snapshot of a whole subtree. For an in-memory structure where every operation takes microseconds, one lock is the right first answer; a readers–writer lock is the obvious next step, since ls, read and du don't mutate.
The quota check sits inside the same lock as the write, before any byte changes: compute the new total, refuse if it's over, and only then touch the file. Checking outside the lock would let two writers each see room for 6,000 bytes and together write 12,000.
mkdir -pon an existing directory: succeeds and does nothing; plainmkdirraisesFileExistsError- A file where a directory should be:
mkdir -p /a/bwhen/ais a file raises, it doesn't replace the file ..above the root: stays at the rootmv /home /home/asha/old/home: refused; walking up from the destination's parent reaches/homeitself- Overwriting vs appending under quota: an overwrite frees the old bytes first, so rewriting a file with a same-size version always fits
rmon a non-empty directory: refused withoutrecursive=True; with it, the quota gets the whole subtree back
The code#
The file system: path resolution first, then the operations, each normalise → walk → check → mutate:
# part 2: the file system: path resolution and the operations
class FileSystem:
def __init__(self, quota_bytes: int) -> None:
self.root = Directory("", None)
self.quota, self.used = quota_bytes, 0
self._lock = threading.RLock() # one lock for the tree: a move touches two directories
@staticmethod
def _parts(path: str) -> list[str]:
if not path.startswith("/"):
raise ValueError(f"absolute paths only: {path!r}")
out: list[str] = []
for p in path.split("/"):
if p == "..":
if out:
out.pop() # '..' at the root stays at the root
elif p not in ("", "."):
out.append(p)
return out
def _walk(self, parts: list[str]) -> Node:
node: Node = self.root
for i, p in enumerate(parts):
if not isinstance(node, Directory):
raise NotADirectoryError("/" + "/".join(parts[:i]))
if p not in node.children:
raise FileNotFoundError("/" + "/".join(parts[: i + 1]))
node = node.children[p]
return node
def _parent_of(self, path: str) -> tuple[Directory, str]:
parts = self._parts(path)
if not parts:
raise ValueError("not allowed on /")
parent = self._walk(parts[:-1])
if not isinstance(parent, Directory):
raise NotADirectoryError(parent.path())
return parent, parts[-1]
def mkdir(self, path: str, parents: bool = False) -> None:
with self._lock:
node: Directory = self.root
parts = self._parts(path)
for i, p in enumerate(parts):
child = node.children.get(p)
if child is None:
if not parents and i < len(parts) - 1:
raise FileNotFoundError("/" + "/".join(parts[: i + 1])) # plain mkdir needs the parent
child = node.children[p] = Directory(p, node)
elif not isinstance(child, Directory):
raise FileExistsError(child.path()) # a file is in the way
elif i == len(parts) - 1 and not parents:
raise FileExistsError(child.path()) # mkdir -p is idempotent; mkdir is not
node = child
def ls(self, path: str) -> list[str]:
with self._lock:
node = self._walk(self._parts(path))
if isinstance(node, File):
return [node.name]
return sorted(n + "/" if isinstance(c, Directory) else n for n, c in node.children.items())
def write(self, path: str, text: str, append: bool = False) -> int:
data = text.encode()
with self._lock:
parent, name = self._parent_of(path)
node = parent.children.get(name)
if isinstance(node, Directory):
raise IsADirectoryError(node.path())
old = node.size() if node and not append else 0
if self.used - old + len(data) > self.quota: # check before a single byte changes
raise QuotaExceeded(f"{path}: needs {len(data) - old} bytes, {self.quota - self.used} left")
if node is None:
node = parent.children[name] = File(name, parent)
if append:
node.data += data
else:
node.data[:] = data
self.used += len(data) - old
return node.size()
def read(self, path: str) -> str:
with self._lock:
node = self._walk(self._parts(path))
if isinstance(node, Directory):
raise IsADirectoryError(path)
return node.data.decode()
def mv(self, src: str, dst: str) -> str:
with self._lock:
sparent, sname = self._parent_of(src)
node = self._walk(self._parts(src))
try:
target = self._walk(self._parts(dst))
except FileNotFoundError:
target = None
if isinstance(target, Directory): # mv a.txt /docs -> /docs/a.txt
dparent, dname = target, sname
else:
dparent, dname = self._parent_of(dst)
if dname in dparent.children:
raise FileExistsError(dparent.children[dname].path()) # we chose no-clobber, like mv -n
ancestor: Directory | None = dparent
while ancestor is not None: # mv /a /a/b/c would detach /a from the tree
if ancestor is node:
raise ValueError(f"can't move {src} inside itself")
ancestor = ancestor.parent
del sparent.children[sname]
node.name, node.parent = dname, dparent
dparent.children[dname] = node
return node.path()
def rm(self, path: str, recursive: bool = False) -> int:
with self._lock:
parent, name = self._parent_of(path)
node = self._walk(self._parts(path))
if isinstance(node, Directory) and node.children and not recursive:
raise OSError(f"{path}: directory not empty")
freed = node.size()
del parent.children[name]
self.used -= freed
return freed
def du(self, path: str) -> int:
with self._lock:
return self._walk(self._parts(path)).size()A home directory, two moves, four refusals, eight writers, and the quota:
# part 3: a small project tree, a move, a quota, and eight writers on one log
if __name__ == "__main__":
fs = FileSystem(quota_bytes=10_000)
fs.mkdir("/home/asha/notes", parents=True)
fs.mkdir("/home/asha/notes", parents=True) # mkdir -p twice: fine
try:
fs.mkdir("/srv/app/logs")
except FileNotFoundError as e:
print("mkdir without -p:", e)
fs.write("/home/asha/notes/todo.txt", "fix the bug\n")
fs.write("/home/asha/notes/todo.txt", "write tests\n", append=True)
fs.write("/home/asha/readme.md", "# asha\n")
print(fs.ls("/home/asha"), "|", fs.ls("/home/asha/./notes/../readme.md"))
print(repr(fs.read("/home/asha/notes/../notes/todo.txt")))
print("moved to", fs.mv("/home/asha/notes", "/home/asha/archive"))
fs.mkdir("/home/asha/old")
print("moved to", fs.mv("/home/asha/archive/todo.txt", "/home/asha/old"))
for bad in [("/home", "/home/asha/old/home"), ("/home/asha/readme.md", "/home/asha/old/todo.txt")]:
try:
fs.mv(*bad)
except (ValueError, FileExistsError) as e:
print("rejected:", type(e).__name__, e)
for bad in [lambda: fs.read("/home/asha/old"), lambda: fs.write("/home/asha/readme.md/x", "hi")]:
try:
bad()
except (IsADirectoryError, NotADirectoryError) as e:
print("rejected:", type(e).__name__, e)
fs.mkdir("/srv/app/logs", parents=True)
def writer(w: int) -> None:
for i in range(100):
fs.write("/srv/app/logs/app.log", f"w{w}{i:02d}\n", append=True) # 5 bytes a line
ts = [threading.Thread(target=writer, args=(w,)) for w in range(8)]
for t in ts:
t.start()
for t in ts:
t.join()
print("app.log:", len(fs.read("/srv/app/logs/app.log").splitlines()), "lines,", fs.du("/srv/app/logs/app.log"), "bytes")
print("used", fs.used, "of", fs.quota, "| du /home:", fs.du("/home"), "| du /:", fs.du("/"))
try:
fs.write("/srv/app/dump.bin", "x" * 6000)
except QuotaExceeded as e:
print("rejected:", e)
print("freed", fs.rm("/srv", recursive=True), "| used", fs.used, "| /", fs.ls("/"))mkdir without -p: /srv
['notes/', 'readme.md'] | ['readme.md']
'fix the bug\nwrite tests\n'
moved to /home/asha/archive
moved to /home/asha/old/todo.txt
rejected: ValueError can't move /home inside itself
rejected: FileExistsError /home/asha/old/todo.txt
rejected: IsADirectoryError /home/asha/old
rejected: NotADirectoryError /home/asha/readme.md
app.log: 800 lines, 4000 bytes
used 4031 of 10000 | du /home: 31 | du /: 4031
rejected: /srv/app/dump.bin: needs 6000 bytes, 5969 left
freed 4000 | used 31 | / ['home/']mkdir -p twice is fine; plain mkdir reports the first missing directory. The two .. paths resolve as a shell would. Renaming notes to archive moves the whole subtree in one pointer change, and moving todo.txt onto the existing old directory puts it inside. Moving /home into its own descendant, overwriting a file, reading a directory and writing under a file are each refused with the error a shell would give. Eight threads append 100 five-byte lines each: 800 lines, 4,000 bytes. The quota then refuses a 6,000-byte write when 5,969 bytes are left, and rm -r /srv hands back exactly 4,000.
Extending it: the follow-ups#
- "Add permissions." Give each node an owner and read/write bits; pass a
userinto every operation, and check the bits on each directory walked (execute) and on the target (read or write). Put the checks in one_authorize(node, user, mode)helper so no operation forgets them. - "Add
cdand relative paths." ASessionobject holding a current directory; relative paths are joined to its path before normalising. Keep the session outsideFileSystem, since each user has their own. - "Implement
find /home -name '*.md'." A generator that walks a subtree depth-first and yields matching paths. Take the lock once, collect the results, release, then return them. - "Symbolic links." A third node type holding a target path. Resolution must now follow links during the walk (and count hops to stop loops), and
..can no longer be resolved by text alone. - "Large files." Store content in fixed-size blocks instead of one
bytearray, so appends don't copy and a quota can be enforced in blocks, as real file systems do.
Common mistakes#
isinstancechecks in every operation instead of a shared node interface- String surgery on paths in each method instead of one normaliser and one walker
mkdirthat silently creates parents, ormkdir -pthat fails on an existing directory- A move with no cycle check, which detaches a directory from the tree
- Quota checked after writing, or outside the lock
- Per-directory locks taken in whatever order a request names them, so two crossing moves deadlock
In-memory file system
Q1/3 Where does the Composite pattern pay off most in this design?
Answer & explanation
Answer: B
du is node.size(): files return their length, directories ask their children. No type checks, any depth, and a new node type only implements the interface.
Q2/3 What should mv("/home", "/home/asha/old/home") do?
Answer & explanation
Answer: C
Moving a directory into its own subtree would cut it off from the root. Walking up from the destination's parent and meeting the source is the check.
Q3/3 Two threads each write a 6,000-byte file with 10,000 bytes free. Why must the quota check be inside the lock?
Answer & explanation
Answer: B
Check-then-write is a race. With the check and the write in one critical section, the second writer sees only 4,000 bytes left and is refused.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.