SyntaxPilot
Courses/Low-Level Design/Lesson 84
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Low-Level Design · Lesson 84 of 90

Design an in-memory file system

file system requirementsComposite pattern appliedFileDirectorypath parsingmkdir ls cdfile contentspermissionssize calculationsearch with Visitorabsolute and relative paths

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:

  1. mkdir ("make directory"): create a folder.
  2. ls ("list"): show what's inside a folder.
  3. cd ("change directory"): move the current folder.
  4. Create, write, append to and read (cat) files.
  5. A folder's size: the total size of everything inside it.
  6. Permissions: who may read or write.
  7. 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 /docs also shows /docs-old/plan.txt: a path in this map is just text, and "/docs-old/plan.txt".startsWith("/docs") is true. (Checking startsWith("/docs/") fixes this one symptom, but not the others.)
  • size of /docs: 33 counts the old plan too (7 + 8 + 18); the real answer is 15.
  • Is /music a 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 ls scans 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, with size() and print().
  • Leaf: an item with no children. Here, File.
  • Composite: an item that holds children of the common type. Here, Directory, whose children are Nodes (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 with new; 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, so root.add(new Directory("docs")) gives back a Directory you can keep adding to.
  • TreeMap keeps the children sorted by name, so ls and print come out in order.
  • StringBuilder is a text buffer you can change in place (append, clear), unlike a String, 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.pdf means 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 path notes/todo.txt means /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:

  1. Start at the root if the path begins with /, else at the cwd.
  2. Split the path on /.
  3. 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.
  4. 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 . shows cv.pdf and notes/.
  • cd notes/../notes goes 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/ravi throws NoSuchElementException: No such file or directory: /home/ravi. NoSuchElementException is 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 cat command, short for "concatenate").

Permissions: for each user, a set of what they may do: READ, WRITE, or both.

  • Permission is an enum (a Java type with a fixed list of values).
  • The set is an EnumSet: a Set made 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.
  • content and access are private: 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) and visitDirectory(Directory d).
  • Each node has one method, accept(Visitor v). A file calls v.visitFile(this). A directory calls v.visitDirectory(this), then accept(v) on every child, so the visitor walks the whole tree.
  • Calling accept and then the right visit method is called double dispatch: the right code runs based on both the visitor's type and the node's type, with no instanceof.
  • A new operation = a new visitor class. File and Directory never 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 and file(...) 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 / adds notes.txt (14) = 58.
  • find lists files in name order because each folder's children are in a TreeMap (2025/ sorts before plan.txt).
  • mv moved the whole 2025 folder (with tax.txt inside) to archive-2025, a rename and a move in one; rm then 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; cd into 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 keeps size() and the Visitor keeps find free 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

  1. Which pattern fits a file system, and why? Composite: files (leaves) and folders (composites) share one Node type, so size, print and search treat both the same way.
  2. 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.
  3. How do you store a folder's children? A map from name to node (TreeMap for sorted ls, HashMap for speed).
  4. Absolute vs relative paths? Absolute starts with / at the root; relative starts at the current working directory. . is this folder, .. the parent.
  5. 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.
  6. How do mkdir, ls, cd work? mkdir resolves the parent and adds a folder; ls lists a folder's children; cd sets the cwd to a resolved folder.
  7. How do you model permissions? Per node, a map from user to an EnumSet of READ/WRITE; the owner gets all; check before every read and write.
  8. How would you search for files? A Visitor that walks the tree with accept, collecting matches; or an index from name to nodes.
  9. Why a Visitor and not a find() method on each node? New operations become new classes without editing the node classes.
  10. 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-old inside /docs, counted the wrong size, and couldn't hold an empty folder.
  • The Composite pattern applied: Node is the common type, File the leaf, Directory the 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 EnumSet of 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.