Cruxly

Cruxly › Low-level design › LLD Exercises

In-Memory File System

a file and a directory are the same interface, and that single decision buys everything else

Open the interactive lesson

Prompt: design an in-memory file system supporting mkdir(path), create(path, content), read(path), write(path, content), delete(path), and ls(path) (listing a directory's immediate children). Paths are POSIX-style (/a/b/c).

45 minutes. The interesting part is not path parsing. It's that a file and a directory are the same abstraction with different capabilities, and treating them as unrelated classes is what makes every operation need a type check.

Applying the five moves: nouns are FileSystemEntry (the shared abstraction), File, Directory — and move 2's "kill most of them" is really move 2's opposite here: the insight is unifying File and Directory under one interface rather than listing them as separate types. The invariant is "every path resolves to at most one entry, and a directory's children are always entries of the same shared type" — this is what lets ls and delete stay uniform instead of branching on type. The interface seam is FileSystemEntry itself, and it's the entire exercise, not an add-on — the prompt's hint is that both files and directories need delete, and only a shared interface avoids a type check at every call site. Concurrency: an in-memory file system accessed by one process is often single-threaded by assumption — say that explicitly, and name path-level locking (not a single global lock) as the answer if the follow-up adds concurrent access.

Scope, and the interface that makes the tree uniform

In scope: the six operations above, path resolution, an in-memory tree (no real disk I/O — say this explicitly). Out of scope (say it): permissions/ownership, symbolic links, concurrent access from multiple processes (address as a follow-up, not in the base design).

The composite decision, stated before any class: a directory contains entries, and an entry is either a file or another directory — this is the Composite pattern, arrived at because the problem has a recursive structure (a directory inside a directory inside a directory) and every operation (ls, delete, path resolution) needs to treat a file and a directory uniformly at every level except the one place they actually differ, which is whether they hold content or children.

public interface FileSystemEntry {
    String name();
    boolean isDirectory();
}

public class FileEntry implements FileSystemEntry {
    private final String name;
    private StringBuilder content = new StringBuilder();
    FileEntry(String name) { this.name = name; }
    public String name() { return name; }
    public boolean isDirectory() { return false; }
    String read() { return content.toString(); }
    void write(String data) { content = new StringBuilder(data); }
}

public class DirectoryEntry implements FileSystemEntry {
    private final String name;
    private final Map<String, FileSystemEntry> children = new LinkedHashMap<>();  // insertion order for ls
    DirectoryEntry(String name) { this.name = name; }
    public String name() { return name; }
    public boolean isDirectory() { return true; }
    Map<String, FileSystemEntry> children() { return children; }
}

LinkedHashMap, not HashMap, for a directory's children — ls on a real file system returns entries in a stable, usually creation-order sequence, and a plain hash map's iteration order is an implementation detail that can silently change. This is a small choice that signals whether the candidate has thought about what ls actually needs to guarantee, not just that it needs to return a list.

Path resolution — the actual recursive exercise

Path resolution is where the exercise actually lives, because every operation above (create, read, write, delete, ls) reduces to "resolve a path to an entry, then do something small to it." Getting this one method right correctly is most of the design.

public class InMemoryFileSystem {
    private final DirectoryEntry root = new DirectoryEntry("/");

    /** Resolves a path to its entry, or null if any component doesn't exist. */
    private FileSystemEntry resolve(String path) {
        if (path.equals("/")) return root;
        FileSystemEntry current = root;
        for (String part : path.split("/")) {
            if (part.isEmpty()) continue;                     // handles leading "/" and "//" artifacts
            if (!current.isDirectory()) return null;           // walked into a file expecting a directory
            current = ((DirectoryEntry) current).children().get(part);
            if (current == null) return null;
        }
        return current;
    }

    /** Resolves the PARENT of a path and returns it with the final segment's name —
     *  every mutating operation (mkdir, create, delete) needs the parent, not the target. */
    private DirectoryEntry resolveParent(String path) {
        int lastSlash = path.lastIndexOf('/');
        String parentPath = lastSlash <= 0 ? "/" : path.substring(0, lastSlash);
        FileSystemEntry parent = resolve(parentPath);
        if (parent == null || !parent.isDirectory()) {
            throw new IllegalArgumentException("Parent directory does not exist: " + parentPath);
        }
        return (DirectoryEntry) parent;
    }

    public void mkdir(String path) {
        String name = path.substring(path.lastIndexOf('/') + 1);
        DirectoryEntry parent = resolveParent(path);
        if (parent.children().containsKey(name)) {
            throw new IllegalArgumentException("Already exists: " + path);
        }
        parent.children().put(name, new DirectoryEntry(name));
    }

    public List<String> ls(String path) {
        FileSystemEntry entry = resolve(path);
        if (entry == null) throw new IllegalArgumentException("No such path: " + path);
        if (!entry.isDirectory()) return List.of(entry.name());   // ls on a file returns just that file
        return new ArrayList<>(((DirectoryEntry) entry).children().keySet());
    }
    // create, read, write, delete: same resolveParent-then-act shape, omitted for space
}

The single cast to DirectoryEntry after checking isDirectory() is the one place the interface's uniformity temporarily breaks, and that is by design, not a leak — everywhere else in the codebase, code operates on FileSystemEntry without knowing or caring which concrete type it holds. Confining the type check to exactly the boundary where the two types genuinely differ (a directory has children, a file has content) is what "Composite done right" looks like, versus a design that scatters instanceof checks through every method.

Delete, and the recursion that actually corners you

Deleting a file is one map removal. Deleting a non-empty directory is the exercise, because it forces an explicit decision the prompt didn't state: does delete on a non-empty directory fail, or does it recurse and delete everything inside?

public void delete(String path) {
    DirectoryEntry parent = resolveParent(path);
    String name = path.substring(path.lastIndexOf('/') + 1);
    parent.children().remove(name);
}
public void delete(String path, boolean recursive) {
    DirectoryEntry parent = resolveParent(path);
    String name = path.substring(path.lastIndexOf('/') + 1);
    FileSystemEntry target = parent.children().get(name);
    if (target == null) throw new IllegalArgumentException("No such path: " + path);

    if (target.isDirectory() && !((DirectoryEntry) target).children().isEmpty() && !recursive) {
        throw new IllegalStateException("Directory not empty: " + path);   // POSIX rmdir's actual behaviour
    }
    parent.children().remove(name);
}

Requiring the caller to pass recursive explicitly, and throwing rather than silently doing the more destructive thing, mirrors real POSIX semantics (rmdir refuses a non-empty directory; rm -r is a distinct, opt-in operation) — and naming that this mirrors real tool behaviour, rather than inventing arbitrary semantics, is what shows the candidate has used a file system, not just modelled one abstractly.

Recursive delete itself is a straightforward tree walk once the interface is uniform — deleteRecursive(entry) on a DirectoryEntry recurses into every child and calls itself, and on a FileEntry does nothing extra, exactly the shape Composite is supposed to make trivial. If this recursion feels complicated to write, that is a signal the interface boundary from the previous section was drawn in the wrong place.

Follow-ups they will ask

"Add file size and a du (disk usage) command." FileEntry.size() returns its content length directly; DirectoryEntry.size() sums its children's sizes recursively — this is the same Composite shape as delete, and if the interface already forces every entry to answer "how big am I," the follow-up is one method added to an interface that already anticipated variation, not a redesign.

"Support concurrent access — two threads creating files in the same directory." Each DirectoryEntry's children map needs its own lock (or a concurrent map), not one global file-system lock — two threads creating files in different directories should never contend, the same per-node-not-per-tree locking principle as the movie-booking exercise's per-showtime lock elsewhere in this track. The harder case: one thread deleting a directory while another creates a file inside it — resolving this requires deciding whether resolveParent itself needs to hold a lock across the resolve-then-mutate sequence, the classic check-then-act shape again, one level up in a tree instead of one key in a map.

"Add symbolic links." A symlink is a third FileSystemEntry implementation that stores a target path instead of content or children, and resolve() needs an explicit decision about whether to follow it transparently or return it as-is — and if it follows links, it needs cycle detection (a link pointing at an ancestor of itself), which is the one place this "clean tree" model stops being a tree at all and the design has to say so honestly rather than pretending symlinks are free.

How to say it in the interview

"A file system is a tree where every node is addressable by path, and the one decision that shapes everything else is making File and Directory both implement one FileSystemEntry interface, so ls and delete and path resolution never need to ask what kind of thing they are looking at."

Checklist

Practice this interactively
Share this lessonWhatsAppLinkedInX

Related lessons