In-Memory File System

A directory tree in memory - mkdir, touch, ls, cat - where a directory and a file answer to the same interface for everything except "what's actually inside you." This is Composite, played completely straight.

Requirements

Functional

• Create a file with content at a given path, creating any missing parent directories.
• Create a directory at a given path.
• List the immediate children of a directory.
• Read a file's content by path; read a directory's total size as the sum of everything under it.
• Delete a file or a directory (and everything inside it).

Non-functional

• Path resolution (/a/b/c) should walk the tree node by node, not string-match against a flat table of every path ever created.
• Computing a directory's size must not require a separate "keep this in sync" step scattered across every mutation - it should fall out of composing the sizes of its children.

Design

FileSystemNode is the interface both File and Directory implement; anything that walks the tree (size, listing, deletion) calls the same methods on whichever kind of node it's holding and never checks "is this a file or a directory" itself. Directory holds a map of child name to FileSystemNode, so a subdirectory is stored exactly like a file - just a child that happens to have children of its own.

1. 1The caller gives a full path - the filesystem walks it, the caller never touches a node directly.
2. 2Each missing segment along the path becomes a new Directory, created on demand.
3. 3The final directory in the path gets the new File added as a named child.
4. 4Asking a directory for its size and asking a file for its size use the exact same method name.
5. 5A directory sums the size() of every child without knowing whether that child is a file or another directory.

Path resolution is a fold over path segments: start at the root, and for each segment ask the current directory for that named child, moving one level deeper each time - there's no separate index of "every path that exists."

Class diagram

implements

File and Directory both implement FileSystemNode; a Directory composes other FileSystemNodes, so size() and delete() recurse without ever checking node type.

Code

import java.util.*;

 

interface FileSystemNode {

String name();

long size();

}

 

class File implements FileSystemNode {

private final String name;

private byte[] content;

 

File(String name, byte[] content) {

this.name = name;

this.content = content;

}

 

public String name() { return name; }

public long size() { return content.length; }

byte[] read() { return content; }

void write(byte[] data) { this.content = data; }

}

 

class Directory implements FileSystemNode {

private final String name;

private final Map<String, FileSystemNode> children = new LinkedHashMap<>();

 

Directory(String name) {

this.name = name;

}

 

public String name() { return name; }

 

public long size() {

long total = 0;

for (FileSystemNode child : children.values()) total += child.size();

return total;

}

 

void addChild(FileSystemNode node) {

children.put(node.name(), node);

}

 

void removeChild(String name) {

children.remove(name);

}

 

FileSystemNode getChild(String name) {

return children.get(name);

}

 

List<String> list() {

return new ArrayList<>(children.keySet());

}

}

 

class FileSystem {

private final Directory root = new Directory("/");

 

private Directory resolveParent(String path, boolean createMissing) {

String[] segments = path.split("/");

Directory current = root;

for (int i = 1; i < segments.length - 1; i++) {

FileSystemNode next = current.getChild(segments[i]);

if (next == null) {

if (!createMissing) throw new NoSuchElementException("No such directory: " + segments[i]);

Directory created = new Directory(segments[i]);

current.addChild(created);

next = created;

}

current = (Directory) next;

}

return current;

}

 

void createFile(String path, byte[] data) {

String[] segments = path.split("/");

String fileName = segments[segments.length - 1];

Directory parent = resolveParent(path, true);

parent.addChild(new File(fileName, data));

}

 

void createDirectory(String path) {

String[] segments = path.split("/");

String dirName = segments[segments.length - 1];

Directory parent = resolveParent(path, true);

parent.addChild(new Directory(dirName));

}

 

byte[] read(String path) {

String[] segments = path.split("/");

String fileName = segments[segments.length - 1];

Directory parent = resolveParent(path, false);

File file = (File) parent.getChild(fileName);

return file.read();

}

 

void delete(String path) {

String[] segments = path.split("/");

String name = segments[segments.length - 1];

Directory parent = resolveParent(path, false);

parent.removeChild(name);

}

}

Design decisions

• FileSystemNode is the Composite interface - File is a leaf, Directory composes more nodes. size() on a file returns its content length; size() on a directory sums its children's size() calls, whatever those children are. Neither implementation needs to know the other exists, which is the entire point of Composite: the recursive structure lives in the interface's contract, not in a type-switching helper function.
• Directory stores children in a name-keyed map, not a list scanned by name on every lookup. Path resolution touches one map lookup per segment instead of a linear scan per level, which matters once a directory has more than a handful of entries.
• Path resolution walks the tree, it never consults a separate path-to-node table. A flat table would need updating on every create, move, and delete and could drift from the tree it's supposed to describe; walking the tree from the root means there is exactly one source of truth for what exists.
• What's missing for a real system: creating missing parent directories on touch is handled here as an eager mkdir -p; a real filesystem would also need move/rename (relinking a node under a new parent without recreating it, to keep it cheap regardless of subtree size) and permission checks per node, both of which are out of scope for the composite structure itself.

Common follow-ups

• How would you support mv? Add a move(path, newParentPath) on FileSystem that resolves both the source's current parent and the destination directory, then calls removeChild on the old parent and addChild on the new one with the same FileSystemNode reference. Nothing about the node itself changes, which is exactly why Composite makes this cheap - a subtree with a million files moves in one map operation, not a million copies.
• How would you cache size() instead of recomputing it every call? Give Directory a cachedSize field that every mutating method (addChild, removeChild) invalidates on itself and walks up to invalidate on every ancestor. The tradeoff is real: reads get O(1) again, but every write now touches every directory from the mutation point to the root, so it only pays off if reads vastly outnumber writes.
• How do you avoid stack overflow deleting a directory with a million-deep nesting? size() and delete() as written recurse per level, so a pathological depth blows the call stack before it blows anything else. Rewrite the recursive walk as an explicit stack-based DFS (push children onto a Deque instead of a real call) and the same Composite structure handles arbitrary depth without touching File's or Directory's public interface.
• Symlinks - how do they fit the Composite model? A Symlink would be a third FileSystemNode implementation whose size() and traversal delegate to whatever node its target path resolves to, rather than storing content itself. The interesting failure mode to name in an interview: a symlink pointing into its own subtree makes size() recurse forever, so resolution needs a visited-set guard the other two node types never needed.

Check yourself

Question 1 of 4

Why does `Directory.size()` never check whether a child is a File or another Directory?