These are the notes for Low-Level Design (LLD) episode 84: designing an in-memory file system, files and folders kept in a program's memory, with commands like mkdir, ls and cd. We cover the file system requirements, the Composite pattern applied to File and Directory, size calculation, path parsing with absolute and relative paths, the commands mkdir, ls and cd, file contents, permissions, and search with a Visitor.
How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly. People, files and sizes are made up. This is a teaching model, not how any real operating system stores files on disk.
1. The problem: the office almirah
An office almirah is a tall steel cupboard with labelled shelves ("Accounts"). Inside a shelf are box files ("2025"), and a box file can hold more box files. Inside, finally, are the papers, each with its contents ("tax.txt"). Some shelves are locked ("ask Asha for the key"), and sometimes the boss says "find me every tax paper, wherever it is". A computer's file system is this almirah.
| Real life | In the design |
|---|---|
| A shelf or a box file | A Directory (folder) |
| A box file inside a shelf | A directory inside a directory: a tree |
| A paper with writing on it | A File with contents |
| "Accounts → 2025 → tax.txt" | A path: /accounts/2025/tax.txt |
| "The shelf you're standing at" | The current working directory (cwd) |
| "Ask Asha for the key" | Permissions |
| "Find every tax paper" | Search (with a Visitor) |
| "How full is this shelf?" | Size calculation |
2. Requirements and the two kinds of things
File system requirements, kept small enough for a machine-coding round:
mkdir("make directory"): create a folder.ls("list"): show what's inside a folder.cd("change directory"): move the current folder.- Create, write, append to and read (
cat) files. - A folder's size: the total size of everything inside it.
- Permissions: who may read or write.
- Search: find files by name, anywhere in the tree.
Two kinds of things:
- A File has contents: the text
Q4 plan. Its size here is the number of characters. - A Directory (another word for folder) holds files and other directories.
- A path is a thing's address:
/docs/plan.txt. Each/goes one folder deeper; the very first/is the root, the top folder of the whole tree.
3. Attempt 1: a flat map of paths
Our first attempt has no real folders: a TreeMap from the full path to the contents.
import java.util.*;
public class Main { public static void main(String[] args) {
Map<String, String> files = new TreeMap<>(); // attempt: full path -> contents, no real folders
files.put("/docs/plan.txt", "Q4 plan");
files.put("/docs/todo.txt", "buy milk");
files.put("/docs-old/plan.txt", "old plan from 2019");
files.put("/photos/goa.jpg", "jpg bytes");
files.put("/music", ""); // an empty folder? only a fake empty file
System.out.println("ls /docs:");
int size = 0;
for (var e : files.entrySet())
if (e.getKey().startsWith("/docs")) { // "everything that starts with /docs"
System.out.println(" " + e.getKey()); size += e.getValue().length(); }
System.out.println("size of /docs: " + size + " characters");
System.out.println("is /music a folder? " + files.get("/music").isEmpty() + " ...or an empty file?");
} }
Real output:
ls /docs:
/docs-old/plan.txt
/docs/plan.txt
/docs/todo.txt
size of /docs: 33 characters
is /music a folder? true ...or an empty file?
Why it failed
ls /docsalso shows/docs-old/plan.txt: a path in this map is just text, and"/docs-old/plan.txt".startsWith("/docs")is true. (CheckingstartsWith("/docs/")fixes this one symptom, but not the others.)size of /docs: 33counts the old plan too (7 + 8 + 18); the real answer is 15.- Is
/musica folder or an empty file? The map can't tell: there are no folder objects at all, so an empty folder can't exist. - Every
lsscans every file in the system, and renaming a folder means rewriting every key under it.
4. The Composite pattern applied
The fix is to store it the way the almirah is built: as a tree. Each directory holds its children, looked up by name.
The Composite pattern (episode 32) is how you build a tree where single items and groups are treated the same way:
- Component: the common type both share. Here, the abstract class
Node, withsize()andprint(). - Leaf: an item with no children. Here,
File. - Composite: an item that holds children of the common type. Here,
Directory, whose children areNodes (files or folders).
Now code can ask any node its size without knowing which kind it is:
- a File's size is the length of its contents;
- a Directory's size asks each child and adds up the answers.
No if, no instanceof (Java's "is this object of that type?" check). That is the size calculation, and it works at any depth.
import java.util.*;
abstract class Node { // Composite: the type files AND folders share
final String name; Directory parent;
Node(String n) { name = n; }
abstract int size();
abstract void print(String indent);
String path() { return parent == null ? "" : parent.path() + "/" + name; } }
class File extends Node { // a leaf: holds contents, no children
final StringBuilder content = new StringBuilder();
File(String n, String c) { super(n); content.append(c); }
int size() { return content.length(); }
void print(String indent) { System.out.println(indent + name + " (" + size() + ")"); } }
class Directory extends Node { // a composite: holds Nodes, files or folders
final Map<String, Node> children = new TreeMap<>(); // sorted by name
Directory(String n) { super(n); }
<T extends Node> T add(T child) { child.parent = this; children.put(child.name, child); return child; }
int size() { int s = 0; for (Node c : children.values()) s += c.size(); return s; } // no instanceof
void print(String indent) {
System.out.println(indent + (parent == null ? "/" : name + "/") + " (" + size() + ")");
for (Node c : children.values()) c.print(indent + " "); } }
public class Main { public static void main(String[] args) {
Directory root = new Directory("");
Directory docs = root.add(new Directory("docs"));
docs.add(new File("plan.txt", "Q4 plan")); docs.add(new File("todo.txt", "buy milk"));
root.add(new Directory("docs-old")).add(new File("plan.txt", "old plan from 2019"));
root.add(new Directory("music")); // a real, empty folder
root.print("");
System.out.println(docs.path() + " is " + docs.size() + " characters");
} }
Real output:
/ (33)
docs/ (15)
plan.txt (7)
todo.txt (8)
docs-old/ (18)
plan.txt (18)
music/ (0)
/docs is 15 characters
- A real tree:
docs/is 15 (7 + 8),docs-old/is its own folder (18),music/is a real empty folder (size 0), and the root/is 33: every file counted once. abstract class Node: an abstract class can't be created withnew; it exists to be extended.abstract int size();is a method every subclass must write.<T extends Node> T add(T child)is a generic method: it returns the same type you passed in, soroot.add(new Directory("docs"))gives back aDirectoryyou can keep adding to.TreeMapkeeps the children sorted by name, solsandprintcome out in order.StringBuilderis a text buffer you can change in place (append, clear), unlike aString, which can't change.path()walks up the parents: the root has no parent and an empty name.
5. Path parsing: absolute and relative paths
- An absolute path starts at the root: it begins with
/./home/asha/cv.pdfmeans the same thing wherever you are. - A relative path starts at the current working directory (cwd), the folder you
cd'd into. In/home/asha, the pathnotes/todo.txtmeans/home/asha/notes/todo.txt. .means "this folder";..means "the parent folder", one level up. At the root,..stays at the root.
Path parsing turns the text into a node:
- Start at the root if the path begins with
/, else at the cwd. - Split the path on
/. - Walk one part at a time: skip empty parts (from
//or a leading/) and.; for..go to the parent; otherwise step into the child with that name. - If a part isn't there: "No such file or directory". If you try to step into a file: "Not a directory".
The commands on top of it:
mkdir path: resolve the parent part (everything before the last/), check it is a directory, add a new folder with the last part as its name.touch path: the same, for an empty file (the name of the Unix command that creates an empty file).cd path: resolve it; it must be a directory; it becomes the cwd.ls path: resolve it and list the children's names, with/after folders.
To keep this program inside one screen, Node here is a single class with an isDir flag; sections 4 and the mini project use the proper File / Directory classes.
import java.util.*;
class Node { final String name; final Node parent; final boolean isDir; // a folder or a file
final Map<String, Node> kids = new TreeMap<>(); // children by name
Node(String n, Node p, boolean d) { name = n; parent = p; isDir = d; }
String path() { return parent == null ? "/" : (parent.parent == null ? "" : parent.path()) + "/" + name; }
Node dir() { if (!isDir) throw new IllegalStateException("Not a directory: " + path()); return this; } }
class FileSystem { final Node root = new Node("", null, true); Node cwd = root; // cwd: current folder
Node resolve(String path) { // path parsing
Node at = path.startsWith("/") ? root : cwd; // absolute or relative
for (String part : path.split("/")) {
if (part.isEmpty() || part.equals(".")) continue; // "." = this folder
if (part.equals("..")) { if (at.parent != null) at = at.parent; continue; } // ".." = up
at = at.dir().kids.get(part);
if (at == null) throw new NoSuchElementException("No such file or directory: " + path); }
return at; }
void create(String path, boolean isDir) { // mkdir (folder) or touch (file)
int i = path.lastIndexOf('/'); String n = path.substring(i + 1);
Node p = resolve(i < 0 ? "." : i == 0 ? "/" : path.substring(0, i)).dir();
p.kids.put(n, new Node(n, p, isDir)); }
void cd(String path) { cwd = resolve(path).dir(); }
List<String> ls(String path) {
return resolve(path).dir().kids.values().stream().map(k -> k.name + (k.isDir ? "/" : "")).toList(); } }
public class Main { public static void main(String[] args) {
FileSystem fs = new FileSystem(); fs.create("/home", true); fs.create("/home/asha", true);
fs.cd("/home/asha"); fs.create("notes", true); fs.create("notes/todo.txt", false);
fs.create("cv.pdf", false); System.out.println(fs.cwd.path() + " ls: " + fs.ls("."));
fs.cd("notes/../notes"); System.out.println(fs.cwd.path() + " ls: " + fs.ls(""));
fs.cd("../../../.."); System.out.println(fs.cwd.path() + " ls: " + fs.ls(".")); // stops at /
fs.cd("/home/ravi"); } }
Real output:
/home/asha ls: [cv.pdf, notes/]
/home/asha/notes ls: [todo.txt]
/ ls: [home/]
Exception in thread "main" java.util.NoSuchElementException: No such file or directory: /home/ravi
at FileSystem.resolve(Main.java:14)
at FileSystem.cd(Main.java:20)
at Main.main(Main.java:29)
- In asha's folder,
ls .showscv.pdfandnotes/. cd notes/../notesgoes into notes, up, and into notes again: /home/asha/notes.ls ""(an empty path) means the cwd.cd ../../../..goes up four times from/home/asha/notes, and stops at/.cd /home/ravithrowsNoSuchElementException: No such file or directory: /home/ravi.NoSuchElementExceptionis Java's exception for "the thing you asked for isn't there".path.split("/")on"/home/asha"gives["", "home", "asha"]: the empty first part is why we skip empty parts.
6. File contents and permissions
On a shared office drive with no rules, anybody can open Asha's plan and overwrite it. And a file needs real file contents:
- write replaces the contents;
- append adds to the end;
- cat reads them out (named after the Unix
catcommand, short for "concatenate").
Permissions: for each user, a set of what they may do: READ, WRITE, or both.
Permissionis an enum (a Java type with a fixed list of values).- The set is an
EnumSet: aSetmade specially for enum values; very small and fast.EnumSet.allOf(Permission.class)= both;EnumSet.noneOf(...)= none. - The owner, the user who created the file, gets both, and only the owner can share (grant) permissions.
- Every read and every write checks first, and refuses with "Permission denied", using
SecurityException, Java's built-in exception for a security problem.
Real systems (Linux, for example) use a compact version of the same idea: read, write and execute bits for the owner, the owner's group, and everyone else.
import java.util.*;
enum Permission { READ, WRITE }
class File {
final String name, owner; private final StringBuilder content = new StringBuilder();
private final Map<String, Set<Permission>> access = new HashMap<>(); // user -> what they may do
File(String n, String o) { name = n; owner = o; access.put(o, EnumSet.allOf(Permission.class)); }
private void check(String user, Permission p) {
if (!access.getOrDefault(user, Set.of()).contains(p))
throw new SecurityException("Permission denied: " + user + " cannot " + p + " " + name); }
void write(String user, String text) { // replace the contents
check(user, Permission.WRITE); content.setLength(0); content.append(text); }
void append(String user, String text) { check(user, Permission.WRITE); content.append(text); }
String cat(String user) { check(user, Permission.READ); return content.toString(); }
void grant(String by, String user, Permission p) {
if (!by.equals(owner)) throw new SecurityException("only " + owner + " can share " + name);
access.computeIfAbsent(user, u -> EnumSet.noneOf(Permission.class)).add(p); } }
public class Main { public static void main(String[] args) {
File plan = new File("plan.txt", "asha");
plan.write("asha", "Q4 plan."); plan.append("asha", " Hire 2 people.");
System.out.println("asha: cat plan.txt -> " + plan.cat("asha"));
try { plan.cat("ravi"); } catch (SecurityException e) { System.out.println("ravi: " + e.getMessage()); }
plan.grant("asha", "ravi", Permission.READ); // share it, read only
System.out.println("ravi: cat plan.txt -> " + plan.cat("ravi"));
plan.write("ravi", "Hire 20 people.");
} }
Real output:
asha: cat plan.txt -> Q4 plan. Hire 2 people.
ravi: Permission denied: ravi cannot READ plan.txt
ravi: cat plan.txt -> Q4 plan. Hire 2 people.
Exception in thread "main" java.lang.SecurityException: Permission denied: ravi cannot WRITE plan.txt
at File.check(Main.java:9)
at File.write(Main.java:11)
at Main.main(Main.java:24)
- Asha writes, appends, and reads:
Q4 plan. Hire 2 people. - Before sharing, Ravi gets
Permission denied: ravi cannot READ plan.txt(caught and printed). - After
grant("asha", "ravi", READ), Ravi can read it. - Ravi's write throws
SecurityException: Permission denied: ravi cannot WRITE plan.txt. The plan is safe. contentandaccessareprivate: the only way in is through methods that check. That is encapsulation doing security work.access.computeIfAbsent(user, u -> EnumSet.noneOf(Permission.class))gets the user's set, creating an empty one the first time.
7. Search with a Visitor
The boss wants every .txt file. Then a count of all files. Then a backup. If each becomes a new method in both File and Directory, every new feature edits both classes again.
The Visitor pattern (episode 43) moves each operation into its own class:
- A visitor has one method per kind of node:
visitFile(File f)andvisitDirectory(Directory d). - Each node has one method,
accept(Visitor v). A file callsv.visitFile(this). A directory callsv.visitDirectory(this), thenaccept(v)on every child, so the visitor walks the whole tree. - Calling
acceptand then the rightvisitmethod is called double dispatch: the right code runs based on both the visitor's type and the node's type, with noinstanceof. - A new operation = a new visitor class.
FileandDirectorynever change again.
import java.util.*;
interface Visitor { void visitFile(File f); void visitDirectory(Directory d); } // one method per node type
abstract class Node { final String path; Node(String p) { path = p; }
abstract void accept(Visitor v); }
class File extends Node { final int size; File(String p, int s) { super(p); size = s; }
void accept(Visitor v) { v.visitFile(this); } }
class Directory extends Node { final List<Node> children = new ArrayList<>(); Directory(String p) { super(p); }
Directory dir(String n) { Directory d = new Directory(path + "/" + n); children.add(d); return d; }
Directory file(String n, int s) { children.add(new File(path + "/" + n, s)); return this; }
void accept(Visitor v) { v.visitDirectory(this); for (Node c : children) c.accept(v); } } // walk it
class FindByExtension implements Visitor { // search: *.txt
final String ext; final List<String> found = new ArrayList<>(); FindByExtension(String e) { ext = e; }
public void visitFile(File f) { if (f.path.endsWith(ext)) found.add(f.path); }
public void visitDirectory(Directory d) {} }
class CountVisitor implements Visitor { // a new operation, no edits above
int files, dirs, bytes;
public void visitFile(File f) { files++; bytes += f.size; }
public void visitDirectory(Directory d) { dirs++; } }
public class Main { public static void main(String[] args) {
Directory root = new Directory("");
root.dir("docs").file("plan.txt", 7).file("logo.png", 2048).dir("2025").file("tax.txt", 30);
root.dir("music").file("song.mp3", 4096); root.file("readme.txt", 12);
FindByExtension txt = new FindByExtension(".txt"); root.accept(txt);
System.out.println("find *.txt: " + txt.found);
CountVisitor c = new CountVisitor(); root.accept(c);
System.out.println(c.files + " files, " + c.dirs + " folders (with /), " + c.bytes + " bytes");
} }
Real output:
find *.txt: [/docs/plan.txt, /docs/2025/tax.txt, /readme.txt]
5 files, 4 folders (with /), 6193 bytes
- Find
*.txt:/docs/plan.txt,/docs/2025/tax.txt(deep inside a sub-folder) and/readme.txt. The logo and the song are skipped. - Count: 5 files, 4 folders (the root,
docs,2025,music), 6193 bytes (7 + 2048 + 30 + 4096 + 12). dir(...)returns the new sub-folder andfile(...)returns the same folder, so a tree can be built in one chained line.- The trade-off: adding a new operation is easy (a new visitor), but adding a new kind of node (say, a
Link) means adding a method to every visitor.
8. The class diagram
Node (abstract: name, parent, size(), accept(visitor)) ◁── File · Directory
File (a leaf): contents, size = length · owner + permissions READ / WRITE per user
Directory (a composite): children = TreeMap<name, Node> · size = sum of children's sizes
FileSystem: root "/" · cwd (current folder) · resolve(path) · mkdir · touch · ls · cd
resolve: starts with "/" → absolute (from root), else relative (from cwd) · "." stay · ".." up
Errors: "No such file or directory" · "Not a directory" · "Permission denied"
Visitor: visitFile · visitDirectory ◁── FindByExtension (search) · CountVisitor (stats)
9. Interview follow-ups
| Question | Answer |
|---|---|
mkdir -p a/b/c? |
Walk the path; create each missing folder on the way instead of throwing. The mini project does this. |
mv and rename? |
Cheap in a tree: remove the node from its old parent's map, change its name, add it to the new parent. In the flat map you'd rewrite every path below it. |
rm -r? |
Remove the node from its parent; its whole subtree goes with it (the garbage collector frees it). Refuse to remove /. |
| Moving a folder into itself? | Refuse it: walk up from the target's parent; if you meet the folder you're moving, it's a loop. |
| Symbolic links? | A node that stores a path and is followed during resolve; keep a limit (say 40 hops) so a link loop can't spin forever. |
| Many users at once? | A read-write lock per folder (ReentrantReadWriteLock): many readers at once, or one writer. |
| Large files? | Store contents in fixed-size blocks instead of one big string, so appending and reading part of a file are cheap. |
| Is folder size slow for a huge tree? | Cache each folder's size and update the cached sizes up the parent chain on every write. |
| Find by name quickly? | Keep an index from name to nodes, updated on create, move and delete; the Visitor is the simple version. |
10. Common mistakes
| Mistake | What you see (real) | Fix |
|---|---|---|
| A flat map of path strings | ls /docs lists /docs-old/plan.txt; size of /docs: 33 |
A tree of nodes |
| No folder objects | is /music a folder? true ...or an empty file? |
Directory as a real node |
instanceof checks everywhere |
size, print, search code repeated per type | Composite: Node with size() |
| Relative path parsed from the root | No such file or directory |
No leading /: start at the cwd |
| Stepping into a file | wrong results or crashes | Not a directory: ... |
| No permission check | anyone can overwrite the plan | Permission denied: ravi cannot WRITE plan.txt |
find(), count(), backup() in every node class |
both classes edited for every feature | A Visitor per operation |
Mini project: a small file system shell
One program that puts it together: proper File and Directory classes (Composite), permissions on every node, path parsing, mkdir -p, touch, write, append, cat, ls, cd, pwd, mv, rm -r, du (disk usage: a folder's size) and find with a Visitor, run first as Asha and then as Ravi.
import java.util.*;
enum Permission { READ, WRITE }
interface Visitor { void visitFile(File f); void visitDirectory(Directory d); }
abstract class Node { // Composite: the common type
String name; Directory parent;
final String owner;
final Map<String, Set<Permission>> access = new HashMap<>();
Node(String name, String owner) {
this.name = name; this.owner = owner;
access.put(owner, EnumSet.allOf(Permission.class));
}
abstract int size();
abstract void accept(Visitor v);
String path() {
if (parent == null) return "/";
return (parent.parent == null ? "" : parent.path()) + "/" + name;
}
void check(String user, Permission p) {
if (!access.getOrDefault(user, Set.of()).contains(p))
throw new SecurityException("Permission denied: " + user + " cannot " + p + " " + path());
}
}
class File extends Node { // leaf
private final StringBuilder content = new StringBuilder();
File(String name, String owner) { super(name, owner); }
int size() { return content.length(); }
void accept(Visitor v) { v.visitFile(this); }
void write(String user, String text) { check(user, Permission.WRITE); content.setLength(0); content.append(text); }
void append(String user, String text) { check(user, Permission.WRITE); content.append(text); }
String read(String user) { check(user, Permission.READ); return content.toString(); }
}
class Directory extends Node { // composite
final Map<String, Node> children = new TreeMap<>();
Directory(String name, String owner) { super(name, owner); }
int size() { int s = 0; for (Node c : children.values()) s += c.size(); return s; }
void accept(Visitor v) { v.visitDirectory(this); for (Node c : children.values()) c.accept(v); }
void add(Node n) { n.parent = this; children.put(n.name, n); }
}
class FindByName implements Visitor { // search with a Visitor: *.txt
final String suffix; final List<String> found = new ArrayList<>();
FindByName(String suffix) { this.suffix = suffix; }
public void visitFile(File f) { if (f.name.endsWith(suffix)) found.add(f.path()); }
public void visitDirectory(Directory d) { }
}
class FileSystem {
final Directory root = new Directory("", "root");
Directory cwd = root;
String user = "asha";
FileSystem() { root.access.put("asha", EnumSet.allOf(Permission.class)); root.access.put("ravi", EnumSet.of(Permission.READ)); }
private Node resolve(String path) {
Node at = path.startsWith("/") ? root : cwd;
for (String part : path.split("/")) {
if (part.isEmpty() || part.equals(".")) continue;
if (part.equals("..")) { if (at.parent != null) at = at.parent; continue; }
if (!(at instanceof Directory d)) throw new IllegalStateException("Not a directory: " + at.path());
at = d.children.get(part);
if (at == null) throw new NoSuchElementException("No such file or directory: " + path);
}
return at;
}
private Directory dir(String path) {
if (resolve(path) instanceof Directory d) return d;
throw new IllegalStateException("Not a directory: " + path);
}
private String parentOf(String path) { int i = path.lastIndexOf('/'); return i < 0 ? "." : i == 0 ? "/" : path.substring(0, i); }
private String nameOf(String path) { return path.substring(path.lastIndexOf('/') + 1); }
void mkdirP(String path) { // mkdir -p: create every missing folder
Directory at = path.startsWith("/") ? root : cwd;
for (String part : path.split("/")) {
if (part.isEmpty() || part.equals(".")) continue;
if (part.equals("..")) { if (at.parent != null) at = at.parent; continue; }
Node next = at.children.get(part);
if (next == null) { at.check(user, Permission.WRITE); Directory d = new Directory(part, user); at.add(d); next = d; }
if (!(next instanceof Directory d)) throw new IllegalStateException("Not a directory: " + next.path());
at = d;
}
}
File touch(String path) {
Directory p = dir(parentOf(path));
Node existing = p.children.get(nameOf(path));
if (existing instanceof File f) return f;
p.check(user, Permission.WRITE);
File f = new File(nameOf(path), user); p.add(f); return f;
}
void write(String path, String text) { touch(path).write(user, text); }
void append(String path, String text) { touch(path).append(user, text); }
String cat(String path) {
if (resolve(path) instanceof File f) return f.read(user);
throw new IllegalStateException("Is a directory: " + path);
}
List<String> ls(String path) {
return dir(path).children.values().stream().map(n -> n.name + (n instanceof Directory ? "/" : "")).toList();
}
void cd(String path) { cwd = dir(path); }
String pwd() { return cwd.path(); }
void mv(String from, String to) { // move or rename: change the parent and the name
Node n = resolve(from);
Directory target = dir(parentOf(to));
n.parent.check(user, Permission.WRITE); target.check(user, Permission.WRITE);
n.parent.children.remove(n.name);
n.name = nameOf(to);
target.add(n);
}
void rm(String path) { // rm -r: the whole subtree goes
Node n = resolve(path);
if (n == root) throw new IllegalStateException("refusing to remove /");
n.parent.check(user, Permission.WRITE);
n.parent.children.remove(n.name);
}
int du(String path) { return resolve(path).size(); }
List<String> find(String path, String suffix) { FindByName v = new FindByName(suffix); resolve(path).accept(v); return v.found; }
}
public class Main {
public static void main(String[] args) {
FileSystem fs = new FileSystem();
fs.mkdirP("/home/asha/docs/2025");
fs.cd("/home/asha");
fs.write("docs/plan.txt", "Q4 plan.");
fs.append("docs/plan.txt", " Hire 2 people.");
fs.write("docs/2025/tax.txt", "Tax filed on 31 July.");
fs.write("notes.txt", "Call the bank.");
System.out.println("pwd: " + fs.pwd() + ", ls: " + fs.ls("."));
System.out.println("cat docs/plan.txt: " + fs.cat("docs/plan.txt"));
System.out.println("du docs: " + fs.du("docs") + ", du /: " + fs.du("/"));
System.out.println("find *.txt: " + fs.find("/", ".txt"));
fs.mv("docs/2025", "archive-2025");
System.out.println("after mv, ls: " + fs.ls(".") + ", tax is at " + fs.find("/", "tax.txt"));
fs.rm("archive-2025");
System.out.println("after rm, ls: " + fs.ls("."));
fs.cd("docs/../..");
System.out.println("pwd: " + fs.pwd());
fs.user = "ravi";
System.out.println("ravi: ls /home/asha -> " + fs.ls("/home/asha"));
for (Runnable r : List.<Runnable>of(() -> fs.cat("/home/asha/docs/plan.txt"),
() -> fs.write("/home/asha/hack.txt", "hi"),
() -> fs.cd("/home/asha/notes.txt"),
() -> fs.cat("/home/ravi/cv.pdf"))) {
try { r.run(); } catch (RuntimeException e) { System.out.println("ravi: " + e.getClass().getSimpleName() + ": " + e.getMessage()); }
}
}
}
Real output:
pwd: /home/asha, ls: [docs/, notes.txt]
cat docs/plan.txt: Q4 plan. Hire 2 people.
du docs: 44, du /: 58
find *.txt: [/home/asha/docs/2025/tax.txt, /home/asha/docs/plan.txt, /home/asha/notes.txt]
after mv, ls: [archive-2025/, docs/, notes.txt], tax is at [/home/asha/archive-2025/tax.txt]
after rm, ls: [docs/, notes.txt]
pwd: /home
ravi: ls /home/asha -> [docs/, notes.txt]
ravi: SecurityException: Permission denied: ravi cannot READ /home/asha/docs/plan.txt
ravi: SecurityException: Permission denied: ravi cannot WRITE /home/asha
ravi: IllegalStateException: Not a directory: /home/asha/notes.txt
ravi: NoSuchElementException: No such file or directory: /home/ravi/cv.pdf
Notes on the design:
mkdirP("/home/asha/docs/2025")creates all four folders in one call.du docs= 23 (plan) + 21 (tax) = 44;du /addsnotes.txt(14) = 58.findlists files in name order because each folder's children are in aTreeMap(2025/sorts beforeplan.txt).mvmoved the whole2025folder (withtax.txtinside) toarchive-2025, a rename and a move in one;rmthen removed it with everything inside.- As Ravi: he can
ls(this model checks permissions on file contents and on changes, not on listing), but reading Asha's plan and writing into her folder are denied;cdinto a file is Not a directory; a missing path is No such file or directory. if (resolve(path) instanceof Directory d)is pattern matching for instanceof: check the type and get a typed variable in one step. The shell needs it once, to tell a folder from a file; the Composite keepssize()and the Visitor keepsfindfree of it.
Practice
1. You are in /home/asha/notes. Write the absolute path for each: todo.txt, ../cv.pdf, ./../../ravi, /tmp/../home.
Answer
/home/asha/notes/todo.txt, /home/asha/cv.pdf, /home/ravi, /home.
2. Add a pwd command to the program in section 5.
Answer
String pwd() { return cwd.path(); }. The path is already built by walking up the parents.
3. Write a BigFiles visitor that collects the paths of files larger than 1,000 bytes.
Answer
class BigFiles implements Visitor {
final List<String> found = new ArrayList<>();
public void visitFile(File f) { if (f.size > 1_000) found.add(f.path); }
public void visitDirectory(Directory d) {}
}
On the tree of section 7 it finds /docs/logo.png (2048) and /music/song.mp3 (4096). File and Directory don't change.
4. Why is the flat map's "rename /docs to /work" slow, and the tree's fast?
Answer
In the flat map every file's key contains the folder name, so every key under /docs must be removed and re-added: work grows with the number of files inside. In the tree, the folder is one node: change its name in one map entry, and every path below changes automatically, because paths are built from the parents.
5. In section 6, how would you add an EXECUTE permission and a "group" of users?
Answer
Add EXECUTE to the enum. For groups, keep a Map<String, Set<String>> groups (group → users) and a second map from group name to permissions; check passes if the user's own set or any of their groups' sets contains the permission.
6. Give the size of each folder: /a holds x.txt (5) and /a/b; /a/b holds y.txt (7) and the empty folder /a/b/c.
Answer
/a/b/c = 0, /a/b = 7 + 0 = 7, /a = 5 + 7 = 12, and the root = 12.
Quick quiz
cwd = /home/asha/notes. You run cd ../../ravi/./photos. Where are you? (a) /home/asha/ravi/photos (b) /home/ravi/photos (c) /ravi/photos (d) /home/asha/notes/ravi/photos
Answer
(b) /home/ravi/photos. No leading /, so start at /home/asha/notes. .. → /home/asha, .. → /home, ravi → /home/ravi, . stays, photos → /home/ravi/photos.
Interview questions
- Which pattern fits a file system, and why? Composite: files (leaves) and folders (composites) share one
Nodetype, so size, print and search treat both the same way. - How do you compute a folder's size? Recursively: a file returns its length, a folder returns the sum of its children's sizes; cache it for big trees.
- How do you store a folder's children? A map from name to node (
TreeMapfor sortedls,HashMapfor speed). - Absolute vs relative paths? Absolute starts with
/at the root; relative starts at the current working directory..is this folder,..the parent. - How do you parse a path? Split on
/, start at root or cwd, walk parts: skip empty and., go up for.., step into children; throw for missing parts and for stepping into a file. - How do
mkdir,ls,cdwork? mkdir resolves the parent and adds a folder; ls lists a folder's children; cd sets the cwd to a resolved folder. - How do you model permissions? Per node, a map from user to an
EnumSetof READ/WRITE; the owner gets all; check before every read and write. - How would you search for files? A Visitor that walks the tree with
accept, collecting matches; or an index from name to nodes. - Why a Visitor and not a
find()method on each node? New operations become new classes without editing the node classes. - What about concurrency? A read-write lock per folder, or one lock for the whole tree in a simple version.
Glossary
| Term | Meaning, with an example |
|---|---|
| File system | The way files and folders are organised and found: the office almirah |
| In-memory file system | A file system kept only in the program's memory (gone when it stops) |
| File system requirements | mkdir, ls, cd, write/read files, sizes, permissions, search |
| File | A node with contents: plan.txt holding Q4 plan |
| Directory / folder | A node that holds files and other folders: docs/ |
| Root | The top folder of the whole tree, written / |
| Tree | A structure where each item has one parent and any number of children |
| Path | A node's address: /docs/plan.txt |
| Absolute path | Starts with /, from the root: /home/asha/cv.pdf |
| Relative path | Starts at the current folder: notes/todo.txt |
| Current working directory (cwd) | The folder you are "in" right now; set with cd |
. |
This folder |
.. |
The parent folder, one level up; at the root it stays at the root |
| Path parsing | Turning a path's text into a node by walking it part by part |
| mkdir | "Make directory": create a folder |
| mkdir -p | Create a folder and every missing parent folder on the way |
| ls | "List": show a folder's children |
| cd | "Change directory": move the cwd |
| pwd | "Print working directory": show the cwd's path |
| touch | Create an empty file |
| cat | Print a file's contents |
| mv / rm -r / du | Move or rename / remove a folder and everything in it / disk usage (a folder's size) |
| File contents | The data inside a file; here text in a StringBuilder |
| Write / append | Replace the contents / add to the end |
| Size calculation | A file's size is its length; a folder's is the sum of its children's |
| Composite pattern | Treat single items and groups through one common type (episode 32) |
| Component | The common type in a Composite: Node |
| Leaf | A node with no children: File |
| Composite | A node that holds children of the common type: Directory |
| Abstract class | A class you can't create directly; subclasses fill in its abstract methods |
| instanceof | Java's "is this object of that type?" check |
| Pattern matching for instanceof | if (n instanceof Directory d): check and get a typed variable at once |
| Generic method | A method with a type parameter: <T extends Node> T add(T child) |
| StringBuilder | A text buffer you can change in place |
| TreeMap | A map that keeps keys sorted: children listed by name |
| Permissions | What each user may do with a node: READ, WRITE |
| Owner | The user who created a node; gets all permissions and can share |
| enum | A Java type with a fixed list of values: enum Permission { READ, WRITE } |
| EnumSet | A small, fast Set for enum values: EnumSet.allOf(Permission.class) |
| SecurityException | Java's built-in exception for a security problem: Permission denied |
| NoSuchElementException | Java's exception for "that isn't there": No such file or directory |
| IllegalStateException | Java's exception for "can't do that here": Not a directory |
| Encapsulation | Keeping data private so the only way in is through checked methods |
| Visitor pattern | Each operation is its own class with one method per node type (episode 43) |
| Visitor | An object with visitFile and visitDirectory |
| accept | The node method that hands itself to a visitor and, for folders, to its children |
| Double dispatch | The code that runs depends on both the visitor's type and the node's type |
| Search with Visitor | A visitor that collects matching files: FindByExtension(".txt") |
| Symbolic link | A node that points to another path |
| Read-write lock | Many readers at once, or one writer |
Summary
- The file system requirements give two kinds of things: File (contents) and Directory (children).
- A flat map of paths listed
/docs-oldinside/docs, counted the wrong size, and couldn't hold an empty folder. - The Composite pattern applied:
Nodeis the common type,Filethe leaf,Directorythe composite; size calculation is one polymorphic call. - Path parsing handles absolute and relative paths,
.and.., and gives clear errors; mkdir, ls and cd sit on top of it with a current folder. - File contents are written, appended and read, and permissions (an
EnumSetof READ/WRITE per user, set by the owner) are checked on every access. - Search with a Visitor finds files at any depth, and new operations are new visitor classes.
- Next episode: a chess game, part 1: the board, squares, the piece hierarchy and how each piece moves.