In-Memory File System

Hierarchical Virtual File System

Design a file system that lives in memory: a tree of directories and files with mkdir, ls, write, read, rm and mv, correct path handling and clear errors.

Overview

An in-memory file system is a tree. Directories are the inner nodes, files are the leaves, and every path such as /home/ana/notes.txt is a walk from the root down that tree, one name at a time. The system offers the everyday commands: make a directory, list one, write to a file, read it back, remove things and move them.

The problem tests three things. First, whether you model files and directories so that code which walks the tree does not care which one it holds; that is the Composite pattern. Second, whether you parse paths carefully: extra slashes, ., .. and the root are where most bugs live. Third, whether you guard the operations that can break the tree, such as moving a directory inside itself, and say how you would make it safe for several threads.

A strong answer draws the tree, writes one walk helper that every command uses, lists the error cases before coding, and ends with a demo that exercises each of them.

Scoping the problem

Absolute paths only, or a current directory too? — A current directory adds per-session state — Absolute paths; . and .. inside them are resolved
Does write replace or append? — Changes the File API — Append; create the file if it is missing
Does mkdir create missing parents? — Like mkdir -p or not — Yes
What does ls on a file return? — A common edge case — A list with just the file name
Must ls be sorted? — Sorted dict or sort on read — Sorted by name
Remove and move, or only the four core commands? — rm and mv bring the hard cases — Both, with errors for bad moves
Many threads at once? — Decides the locking — Yes, operations must not corrupt the tree

Core entities

Each node keeps a pointer to its parent. The walk does not need it, but mv does: it climbs from the destination toward the root to check that a directory is not being moved inside itself.

Path handling

Every command starts by turning the path string into a list of names. Doing this in one pure function, split_path, means the tree code never sees a slash.

/ — [] — The root
/a/b/c — [a, b, c] — Split on slash
//a///b/ — [a, b] — Empty names from extra slashes are dropped
/a/./b — [a, b] — A single dot means this directory
/a/b/../c — [a, c] — Two dots drop the previous name
/.. — [] — Two dots at the root stay at the root, as POSIX allows
a/b — error — Only absolute paths are accepted

POSIX lets an implementation give a path that starts with exactly two slashes a special meaning; this design treats it like one slash, which is what most interviewers expect.

Errors are part of the design

Name the error cases before you code; the interviewer will ask about them one by one.

read, ls, du, rm — Path does not exist — NotFound
read, write — Path is a directory — IsADirectory
any walk — A file sits in the middle of the path, such as /notes.md/x — NotADirectory
mkdir — A file already has that name — AlreadyExists
rm — Directory is not empty and recursive is false — FsError
mv — Destination name is taken — AlreadyExists
mv — Destination is inside the source, such as /b into /b/c — InvalidMove

The last row mirrors POSIX rename, which refuses when the old path names an ancestor of the new one. Without the check, the moved directory would end up inside its own subtree: it is cut off from the root, and its children point back to it in a cycle.

Cost of each operation

With d the depth of the path, k the children of one directory, and n the nodes under a subtree:

walk, mkdir, rm — O(d) — A dict lookup per level
read, write — O(d) plus the text copied — Read joins every chunk once
ls on a directory — O(d + k log k) — Sorted on read; a sorted map would make it O(d + k)
mv — O(d) — The ancestor check climbs at most d levels
du, find — O(d + n) — Visits the whole subtree

What you will be able to do

Model files and directories with the Composite pattern and say what it buys you.
Write one path parser that handles extra slashes, dot, dot-dot and the root.
List the error cases of each command and raise a clear error for each.
Explain why moving a directory into itself must be refused and how to check it.
Make the tree safe for many threads and discuss finer-grained locking.

Functional requirements

mkdir(path) creates a directory and any missing parents
ls(path) returns the sorted names in a directory, or [name] when path is a file
write(path, text) creates the file (and missing parents) or appends to it
read(path) returns the whole content of a file
rm(path, recursive) removes a file or an empty directory; a full directory only when recursive is true
mv(src, dst) moves or renames a file or directory; refuses a taken name or a move into itself
du(path) returns the bytes stored under a path; find(path, name) returns every matching path
Paths are absolute; extra slashes, . and .. are resolved

Non-functional requirements

Resolving a path costs O(depth): one dict lookup per level
Every failure raises a named error; nothing fails silently or returns an empty value by mistake
Safe under many threads: every public method holds the tree lock
Path parsing is a pure function, separate from the tree
New node types (a symlink, for example) add a Node subclass without touching the walk of existing ones

Interview questions

Why use the Composite pattern here, and where does it stop helping?
How do you make it safe for many threads, and how would you reduce lock contention?
How would you add symbolic links?
How would you persist this file system or make it survive a crash?
Large files: what changes if a file can be gigabytes?