Machine coding · not HLD
In-memory file system
You start with a HashMap from full path to bytes. mkdir /a/b and write /a/b/c.txt look easy. Then they ask ls /a, and you scan every key for a prefix. Then they create a file named /a, and /a/b is suddenly illegal. That is why this round wants a tree, not a path map.
An in-memory file system is a tree: a node is either a file (bytes) or a directory of child nodes, and path resolution walks that tree. If File and Directory duplicate path logic as unrelated classes, you will write find() twice. Blocks, replication, and metadata services belong on the related System Design note: File storage . If you mention , you wandered off.
The four commands
mkdir /a/b
Walk from root and create each missing DirectoryNode along the path.
write /a/b/c.txt
Parents must be directories; the FileNode leaf holds cloned bytes.
ls /a
Return the named children of that DirectoryNode, not a prefix scan.
Reject file-in-the-middle
A name is a file or a directory, not both at once.
What actually happens when you skip the tree
The HashMap story above is the usual first sketch, and it fails for two reasons that show up in every follow-up. ls of a directory becomes a prefix scan over every stored path. A file named /a then blocks /a/b, because the map has no place to say "this name is a directory that can still have children." Model the tree.
is the pattern because Node is the shared contract: File is a leaf with bytes, Directory is a composite with named children, and mkdir, ls, write, and read all walk from a root. See Composite. A is a sequence of names, not the storage model. Resolve starts at root and rejects a file in the middle of a path.
Ownership is composition: a directory owns its children, so deleting a directory deletes the subtree. A is the controller. Do not put bytes on Directory. ls can use Iterator on children. Size of a directory is a recursive query, Composite's classic extra. A size cache is optional and easy to get wrong; compute it first. , blocks, and permission bits are not this interview.
Simple rule of thumb
Once you have seen why the path map fails, the scope decision is small: what belongs in the first forty-five minutes, and what you should decline.
1. Model a tree. A HashMap of full paths cannot ls a directory cleanly or stop a file named /a from blocking /a/b (see the story above).
2. Keep paths absolute. Empty segment, trailing slash, and ".." are product choices. Relative paths need a ; skip cwd unless they ask. Absolute-only is the honest first scope.
3. Stay in machine coding. , path resolution, and a small API are the product. Designing an OS file system is a different round.
How to explain this in an interview
Say you will build a of FileNode leaves and DirectoryNode children, walk it with a value, and put mkdir, ls, write, read, and delete on a . Then decline and come back to mkdir.
From problem to mechanism
Here is the same HashMap failure, slowed down so you can see which object owns each job.
Problem. Callers need mkdir, write, read, and ls on paths such as /a/b/c.txt. A name cannot be a file and a directory at once.
Naive system. Store a String path as the only model. ls becomes a prefix scan. There is no walk that can reject a file in the middle.
Break it. write /a, then mkdir /a/b. The second command should fail because /a is a file. The map cannot say that cleanly, and a later delete can leave an orphan FileNode reachable by an old path string.
Mechanism. : Node is the component, FileNode is the leaf, DirectoryNode holds named children. A splits and validates. walks from root. Clone bytes on read and write so callers cannot mutate internals (encapsulation, same as not leaking an LRU Node). Directory size is a recursive sum of file byte lengths; compute it before you cache, because a cache goes stale on every write.
Node
Shared contract: a name, and whether this node is a directory.
FileNode
Holds bytes; read and write clone so callers cannot mutate storage.
DirectoryNode
Named children with add, get, and ls. No content bytes. LinkedHashMap keeps ls order.
Path
Value object that splits and validates. Resolve rules live in one place.
FileSystem
Facade for mkdir, ls, write, read, and delete. Always walks from root.
Java API sketch
The types above become this sketch. FileNode clones on the boundary; DirectoryNode uses LinkedHashMap so ls order is stable.
interface Node {
String name();
boolean isDirectory();
}
abstract class AbstractNode implements Node {
private final String name;
protected AbstractNode(String name) { this.name = Objects.requireNonNull(name); }
public final String name() { return name; }
}
class FileNode extends AbstractNode {
private byte[] content = new byte[0];
FileNode(String name) { super(name); }
public boolean isDirectory() { return false; }
void write(byte[] bytes) { content = bytes.clone(); }
byte[] read() { return content.clone(); }
}
class DirectoryNode extends AbstractNode {
private final Map<String, Node> children = new LinkedHashMap<>();
DirectoryNode(String name) { super(name); }
public boolean isDirectory() { return true; }
void add(Node child) { children.put(child.name(), child); }
Optional<Node> get(String name) { return Optional.ofNullable(children.get(name)); }
Collection<Node> children() { return Collections.unmodifiableCollection(children.values()); }
}
class Path {
static List<String> parts(String raw) { /* split, reject empty, reject .. if out of scope */ }
}
class FileSystem {
private final DirectoryNode root = new DirectoryNode("");
void mkdir(String path) { /* walk, create dirs */ }
void write(String path, byte[] content) { /* parent must be dir */ }
byte[] read(String path);
List<String> ls(String path);
}Tests that prove the seams
Tests never touch java.io.File. The tree is the product.
@Test
void mkdirWriteLs() {
FileSystem fs = new FileSystem();
fs.mkdir("/a/b");
fs.write("/a/b/c.txt", "hello".getBytes());
assertEquals(List.of("b"), fs.ls("/a"));
assertEquals("hello", new String(fs.read("/a/b/c.txt")));
}Walk /a/b/c.txt by hand
The mechanism names a walk from root. This is that walk after mkdir /a/b and write /a/b/c.txt hello, which is the tree the diagram shows.
Read the diagram definition
flowchart TB
R["/ (DirectoryNode)"]
A["a (DirectoryNode)"]
B["b (DirectoryNode)"]
C["c.txt (FileNode)"]
R --> A
A --> B
B --> Cmkdir /a/b starts at root. Part "a" is missing, so create DirectoryNode a under root. Part "b" is missing, create b under a. write /a/b/c.txt hello: walk a, walk b (must be directories), create FileNode c.txt, write bytes. ls /a returns [b]. ls /a/b returns [c.txt].
FileNode.write clones the array so external arrays cannot corrupt file contents. Callers must not retain a mutable alias into the tree. read() clones too. Deleting a directory must define whether non-empty deletes are allowed; composition means the children go away.
First tests
mkdir /a/b, ls /a → [b], write /a/b/c.txt, read equals hello, ls /a/b → [c.txt].
Reject tests
write /a then mkdir /a/b. Second command fails. Name /a is a file.
Invalid cases, concurrency, and what still breaks
The walk above assumes every parent is a directory. These cases are how the design says no, how two threads collide, and which follow-ups stay in scope.
Invalid cases
- write /a when /a is a directory: a name is a file or a directory, not both.
- mkdir /a/b when /a is a file: a file in the middle makes resolve fail.
- ls a missing path: pick a domain error or empty; do not NPE.
- String path as the only model: cannot ls or protect prefix collisions.
- Designing an OS file system: Composite, path resolution, and a small API are the product.
Concurrency
Two mkdir on the same path: serialize on or on the parent directory. Children maps are not thread-safe by default. A single lock on the facade is an honest first answer for machine coding.
What the follow-up changes
- mkdir -p creates missing intermediates; still a walk, still .
- Directory size is a recursive query first; cache later only if they insist.
- Distributed storage: open the System Design note; keep off this page.
Still fails when…
- A size cache goes stale on every write, which is why you compute first.
- Delete leaves an orphan FileNode reachable by an old path string.
- Callers keep a mutable byte[] alias if write or read skips clone.
Trade-offs
- One lock on the facade is honest; the other option is the parent directory.
- Absolute-only is the first scope; waits until they ask.
- ls order from LinkedHashMap is enough for this machine-coding round.
Wrap-up
You have the tree, the walk, and the rejections. Use the forty-five-minute plan below, then the related notes.
Forty-five minutes
- 0–8Sketch Node, FileNode, and DirectoryNode so the shared tree contract exists.
- 8–20Implement mkdir /a/b and ls /a by walking from the root.
- 20–32write and read c.txt; reject a file sitting in the middle of a path.
- 32–40Delete a directory so the whole subtree disappears with it.
- 40–45Name out loud, then decline and blocks.
Read next
Iterator on directory children is a polite extra. The required idea is Composite plus a Path value that walks from root. Mention the file-storage HLD when they ask blocks and replication, then come back to mkdir.
Key takeaway
Creating /a as a file blocks creating /a/b; that rejection is why you modeled a tree. Directories are composites, files hold cloned bytes, and size is recursive. Inode and distributed-storage interviews are a different round.