Knowledge Guide
Home › Hands-On Builds › LLD Katas

Design an In-Memory File System

Build an In-Memory File System

"Design an in-memory file system" sounds like a warm-up: mkdir, addContentToFile, readContentFromFile, ls — four methods, done in ten minutes. It's the same shape as LeetCode's classic Design In-Memory File System problem, and most candidates reach for the same shortcut: a single Map<String, String> from full path to content. It passes every example the interviewer types out by hand. Then two questions land, and the map falls apart: "list everything directly under /usr" and "rename /usr/local to /opt/local — what does that cost you?" A map has no idea which paths are "under" which other paths — it can only find out by comparing every key against every other key. This kata makes you feel that failure first, then build the fix — a Composite tree of File/Directory nodes — in Java and Go, and prove both its correctness and its cost advantage with real numbers, not hand-waving.

The Trap

The obvious first model: one flat map, full path in, content out.

class NaiveFileSystem {
    Map<String, String> pathToContent = new HashMap<>();   // "/usr/local/bin/go" -> "..."
}

addContentToFile and readContentFromFile are trivial — a single get/put by the full path string, O(1). It even feels elegant: no tree to build, no path-walking code, just a hash map doing what hash maps do. Then implement ls("/usr"). The map has entries for /usr/local/bin/go, /usr/local/lib/libc.so, /usr/share/doc/readme.txt — and you need exactly ["local", "share"] back: the direct children only, not the whole subtree, not duplicates. There is no field anywhere that says "these two keys are siblings under the same parent" — the only way to find out is to walk every key in the map, string-compare it against the prefix "/usr/", and pick out the next path segment. A filesystem with 2 million files scattered across it means 2 million string comparisons to answer "what's in this one folder," no matter how small that folder is.

Now try the follow-up: rename /usr/local to /opt/local. Every single key that starts with /usr/local/ — could be one file, could be 200,000 — has to be found (another full scan) and rewritten with a new prefix. There is no "move a subtree" operation on a flat map; there is only "notice, after the fact, which keys happen to share a string prefix, and edit every one of them." The trap is treating "contains" as a string relationship instead of a structural one. Real hierarchy — this directory owns these children — has to be a pointer you can follow, not a substring you have to search for.

Scope it like a senior

Before writing a line of tree code, pin the contract down:

Answer: a tree of nodes rooted at /, where a directory's children are a first-class map living on that directory — not inferred from string prefixes — plus a per-directory lock so concurrent mkdir of the same path can't orphan anything.

Reason to the design

Simplest thing that could work is the flat map — the trap above. Why it fails, precisely: ls and moveTo both need to answer "what's structurally under this path," and a flat map stores no structure, only strings that happen to share prefixes. Answering a structural question by re-deriving it from scratch, over the ENTIRE dataset, every single call, is the bug — not a performance nitpick, a design smell.

The fix, iterated: make "X is a child of Y" an actual pointer instead of a shared string prefix. A Directory node holds a Map<String, Node> of its own direct children; a File node holds content and no children. Both are a Node. This is the Composite pattern: a File (leaf) and a Directory (composite, itself holding more Nodes) are handled through one shared shape, so path-resolution code — "walk to this path" — never needs to know or care which kind of node it's standing on until the one place that legitimately differs: ls, where a file answers "just me" and a directory answers "here are my direct children." Everything else — mkdir, addContentToFile, rm, moveTo — is the same walk regardless of what's at the far end.

Path resolution, concretely: split the path on /, drop empty segments (handles leading/trailing/doubled slashes for free), and walk from the root, following children.get(segment) one hop at a time. mkdir's "create every missing intermediate directory" is exactly this walk, except a missing segment gets a brand-new Directory instead of returning "not found."

Why ls becomes cheap: once "children of /usr" is a real map living on the /usr node, listing them is just reading that one map's keys — cost proportional to how many children this one directory has, never to how many files exist anywhere else in the tree.

Why rm/moveTo become cheap: the map entry is the parent-child relationship. Deleting a directory is one children.remove(name) on its parent — the whole subtree underneath goes with it (unreferenced, garbage-collected), because nothing else in the tree ever stored a full path string that would need to be found and edited. Moving a subtree is a detach-and-reattach of one pointer: remove the node from its old parent's children map, rename it, insert it into the new parent's children map. The size of the subtree being moved never enters the cost — that's the whole payoff of representing "contains" structurally instead of textually.

The concurrency wrinkle, iterated: the naive "walk the tree, and if a segment is missing, create it" is a classic check-then-act: get(name) returns null, so you build a new Directory and put it — but two threads racing on the exact same missing segment can BOTH see null, BOTH build their own Directory, and whichever put lands last wins the map slot. The other thread's Directory object still exists in memory — anything written into it (a file the losing thread added, believing it owned that folder) is now unreachable from the root, silently gone. The fix is making "get-or-create" a single atomic step, not two: Java's ConcurrentHashMap.computeIfAbsent guarantees only one Directory is ever created and installed per key even under a race; Go's equivalent is a mutex per directory node guarding its own children map.

Build it — milestones

Attempt-first: the contract is mkdir(path), addContentToFile(path, content) (creates-or-appends), readContentFromFile(path) -> String, ls(path) -> List<String> (sorted), plus rm(path) and moveTo(src, dest). Try each milestone before reading the reference implementation below.

Reference implementation — Java

One file, three pieces: the Composite tree (Node/FileNode/DirNode/FileSystem) that's the real answer; FlatFileSystem, the naive alternative from The Trap, kept alongside so the break-it section can measure it directly; and UnsafeFileSystem, a deliberately-unsynchronized twin of the tree kept only to reproduce the concurrency race. Save as FileSystem.java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;

/** Node is the Composite: File and Directory both extend it, so path
 *  resolution walks the tree without ever type-switching -- the ONE place
 *  that legitimately cares which subtype it has is ls(), because a file
 *  and a directory answer "what's here" differently. */
abstract class Node {
    String name;   // mutable -- moveTo() renames in place instead of copying
    Node(String name) { this.name = name; }
}

final class FileNode extends Node {
    final StringBuilder content = new StringBuilder();
    FileNode(String name) { super(name); }
}

final class DirNode extends Node {
    // ConcurrentHashMap + computeIfAbsent (see FileSystem.walkToParent) is
    // what makes concurrent mkdir of the SAME path safe -- see UnsafeFileSystem
    // below for what happens with plain get-then-put instead.
    final Map<String, Node> children = new ConcurrentHashMap<>();
    DirNode(String name) { super(name); }
}

/** The Composite tree file system: mkdir/addContentToFile/readContentFromFile/
 *  ls/rm/moveTo, all implemented as a walk down Node.children pointers. */
final class FileSystem {
    private final DirNode root = new DirNode("");

    private static List<String> split(String path) {
        List<String> parts = new ArrayList<>();
        for (String p : path.split("/")) if (!p.isEmpty()) parts.add(p);
        return parts;
    }

    /**
     * Walks to the DIRECTORY that should contain the LAST path segment.
     * computeIfAbsent is atomic PER KEY on a ConcurrentHashMap: concurrent
     * mkdir("/a/b/c") calls racing on the same missing segment all converge
     * on the SAME DirNode instance -- nobody's directory is silently
     * orphaned, which is exactly the bug UnsafeFileSystem has below.
     */
    private DirNode walkToParent(List<String> parts, boolean createIntermediate) {
        DirNode cur = root;
        for (int i = 0; i < parts.size() - 1; i++) {
            String seg = parts.get(i);
            Node child;
            if (createIntermediate) {
                child = cur.children.computeIfAbsent(seg, DirNode::new);
            } else {
                child = cur.children.get(seg);
                if (child == null) return null;
            }
            if (!(child instanceof DirNode)) {
                throw new IllegalStateException(seg + " exists and is a file, not a directory");
            }
            cur = (DirNode) child;
        }
        return cur;
    }

    private Node resolve(List<String> parts) {
        Node cur = root;
        for (String seg : parts) {
            if (!(cur instanceof DirNode)) return null;
            cur = ((DirNode) cur).children.get(seg);
            if (cur == null) return null;
        }
        return cur;
    }

    /** ls on a directory: O(children at THIS node) -- never a scan of the
     *  whole filesystem. ls on a file returns just its own name (POSIX ls
     *  semantics). */
    List<String> ls(String path) {
        Node n = resolve(split(path));
        if (n == null) throw new NoSuchElementException("no such path: " + path);
        if (n instanceof FileNode) return Arrays.asList(n.name);
        List<String> names = new ArrayList<>(((DirNode) n).children.keySet());
        Collections.sort(names);
        return names;
    }

    /** mkdir -p semantics: create every missing intermediate directory. */
    void mkdir(String path) {
        List<String> parts = split(path);
        if (parts.isEmpty()) return; // mkdir("/") is a no-op
        DirNode parent = walkToParent(parts, true);
        String last = parts.get(parts.size() - 1);
        Node created = parent.children.computeIfAbsent(last, DirNode::new);
        if (!(created instanceof DirNode)) throw new IllegalStateException(last + " exists as a file");
    }

    /** Creates the file (and any missing parent directories) if absent, then
     *  APPENDS content -- classic addContentToFile semantics. */
    void addContentToFile(String path, String content) {
        List<String> parts = split(path);
        if (parts.isEmpty()) throw new IllegalArgumentException("cannot write to root");
        DirNode parent = walkToParent(parts, true);
        String last = parts.get(parts.size() - 1);
        Node node = parent.children.computeIfAbsent(last, FileNode::new);
        if (!(node instanceof FileNode)) throw new IllegalStateException(last + " is a directory");
        FileNode file = (FileNode) node;
        synchronized (file) { file.content.append(content); }
    }

    String readContentFromFile(String path) {
        Node n = resolve(split(path));
        if (n == null) throw new NoSuchElementException("no such path: " + path);
        if (!(n instanceof FileNode)) throw new IllegalStateException(path + " is not a file");
        FileNode file = (FileNode) n;
        synchronized (file) { return file.content.toString(); }
    }

    /** rm: detach the node from its parent. O(1) -- the whole subtree (if a
     *  directory) becomes unreachable and is reclaimed by the GC in one map
     *  removal; nothing else in the tree stores full paths, so nothing else
     *  needs to change. */
    void rm(String path) {
        List<String> parts = split(path);
        if (parts.isEmpty()) throw new IllegalArgumentException("cannot rm root");
        DirNode parent = walkToParent(parts, false);
        if (parent == null) throw new NoSuchElementException("no such path: " + path);
        String last = parts.get(parts.size() - 1);
        if (parent.children.remove(last) == null) throw new NoSuchElementException("no such path: " + path);
    }

    /** moveTo: detach the node from its old parent, rename it in place, and
     *  re-attach under the new parent. O(1) regardless of subtree size --
     *  the WHOLE subtree moves as one pointer, because no path is stored
     *  anywhere else that would need rewriting. */
    void moveTo(String srcPath, String destPath) {
        List<String> srcParts = split(srcPath);
        if (srcParts.isEmpty()) throw new IllegalArgumentException("cannot move root");
        DirNode srcParent = walkToParent(srcParts, false);
        if (srcParent == null) throw new NoSuchElementException("no such path: " + srcPath);
        String srcName = srcParts.get(srcParts.size() - 1);
        Node moved = srcParent.children.remove(srcName);
        if (moved == null) throw new NoSuchElementException("no such path: " + srcPath);

        List<String> destParts = split(destPath);
        DirNode destParent = walkToParent(destParts, true);
        String destName = destParts.get(destParts.size() - 1);
        moved.name = destName;                      // O(1): rename in place
        destParent.children.put(destName, moved);    // O(1): re-parent -- the whole subtree rides along
    }
}

/**
 * The NAIVE alternative most candidates reach for first: one flat map from
 * full path string to file content, plus a set of directory paths. Point
 * lookups (readContentFromFile) are O(1) -- but ls() and moveTo() must SCAN
 * every entry in the entire filesystem, because "this path is a child of
 * that path" is not stored anywhere; it can only be recovered by
 * string-prefix-matching every key against every other key.
 * lastScanCount is instrumentation ONLY, to make that cost measurable.
 */
final class FlatFileSystem {
    private final Map<String, String> files = new HashMap<>(); // full path -> content (files only)
    private final Set<String> dirs = new HashSet<>();          // full path -> "this is a directory" marker
    int lastScanCount;

    FlatFileSystem() { dirs.add("/"); }

    void mkdir(String path) {
        StringBuilder cur = new StringBuilder();
        for (String seg : path.split("/")) {
            if (seg.isEmpty()) continue;
            cur.append("/").append(seg);
            dirs.add(cur.toString());
        }
    }

    void addContentToFile(String path, String content) {
        files.merge(path, content, String::concat);
    }

    String readContentFromFile(String path) {
        String c = files.get(path);
        if (c == null) throw new NoSuchElementException("no such file: " + path);
        return c;
    }

    /** Must scan EVERY key in BOTH maps to find direct children of `path` --
     *  there is no structural pointer from a directory to its children. */
    List<String> ls(String path) {
        if (files.containsKey(path)) { lastScanCount = 1; return Arrays.asList(lastSegment(path)); }
        String prefix = path.equals("/") ? "/" : path + "/";
        Set<String> names = new TreeSet<>();
        int scanned = 0;
        for (String p : files.keySet()) {
            scanned++;
            if (p.startsWith(prefix)) names.add(directChild(p, prefix));
        }
        for (String p : dirs) {
            scanned++;
            if (!p.equals(path) && p.startsWith(prefix)) names.add(directChild(p, prefix));
        }
        lastScanCount = scanned; // == size of BOTH maps combined -- O(n), not O(children)
        return new ArrayList<>(names);
    }

    /** No pointer exists from "the subtree" to "its entries" either -- every
     *  key in the ENTIRE filesystem must be examined to find which ones fall
     *  under srcPath, then rewritten with destPath as the new prefix. */
    void moveTo(String srcPath, String destPath) {
        String srcPrefix = srcPath + "/";
        List<String> matchedFiles = new ArrayList<>();
        List<String> matchedDirs = new ArrayList<>();
        int scanned = 0;
        for (String p : new ArrayList<>(files.keySet())) {
            scanned++;
            if (p.equals(srcPath) || p.startsWith(srcPrefix)) matchedFiles.add(p);
        }
        for (String p : new ArrayList<>(dirs)) {
            scanned++;
            if (p.equals(srcPath) || p.startsWith(srcPrefix)) matchedDirs.add(p);
        }
        lastScanCount = scanned; // == total entries, REGARDLESS of how big the moved subtree is
        for (String p : matchedFiles) files.put(destPath + p.substring(srcPath.length()), files.remove(p));
        for (String p : matchedDirs) { dirs.remove(p); dirs.add(destPath + p.substring(srcPath.length())); }
    }

    private static String lastSegment(String path) {
        int i = path.lastIndexOf('/');
        return path.substring(i + 1);
    }

    private static String directChild(String fullPath, String prefix) {
        String rest = fullPath.substring(prefix.length());
        int slash = rest.indexOf('/');
        return slash == -1 ? rest : rest.substring(0, slash);
    }
}

/**
 * UNSAFE TWIN of FileSystem -- reuses the exact same DirNode/FileNode
 * classes (and their ConcurrentHashMap-backed children), but does the
 * get-or-create as TWO separate steps (get, then put) instead of ONE atomic
 * computeIfAbsent. This proves a subtle point: making the MAP thread-safe is
 * not enough -- get-then-put is still a check-then-act race even when each
 * individual map operation is internally safe. Exists ONLY for the break-it
 * demo below -- never call from real code.
 */
final class UnsafeFileSystem {
    private final DirNode root = new DirNode("");

    DirNode mkdirUnsafe(String name) {
        Node child = root.children.get(name);              // CHECK -- no lock
        if (child == null) {
            try { Thread.sleep(1); } catch (InterruptedException ignored) { } // widen the window
            child = new DirNode(name);
            root.children.put(name, child);                 // ACT -- last writer wins; earlier winners' DirNode instances are orphaned
        }
        return (DirNode) child;
    }

    void addContentToFileUnsafe(DirNode dir, String name, String content) {
        Node existing = dir.children.get(name);
        FileNode file;
        if (existing == null) { file = new FileNode(name); dir.children.put(name, file); }
        else file = (FileNode) existing;
        synchronized (file) { file.content.append(content); }
    }

    List<String> ls(String name) {
        Node n = root.children.get(name);
        if (n == null) throw new NoSuchElementException("no such path: " + name);
        List<String> names = new ArrayList<>(((DirNode) n).children.keySet());
        Collections.sort(names);
        return names;
    }
}

Reference implementation — Go

Same shape, three files in one package. Node is an interface satisfied by *FileNode and *DirNode; a mutex per directory node guards its own children map (that's the concurrency fix, in place from the start rather than bolted on). Save as filesystem/filesystem.go:

// Package filesystem is the reference implementation for the "Design an
// In-Memory File System" LLD kata: a Composite tree of File/Directory nodes,
// path resolution by walking child pointers, and a per-directory lock that
// makes concurrent mkdir of the same path safe.
package filesystem

import (
	"errors"
	"sort"
	"strings"
	"sync"
)

// Node is the Composite: FileNode and DirNode both satisfy it, so path
// resolution never type-switches except at Ls(), the one place a file and a
// directory legitimately answer "what's here" differently.
type Node interface {
	Name() string
}

// FileNode is a leaf: one name, one piece of content, guarded by its own lock.
type FileNode struct {
	mu      sync.Mutex
	name    string
	content strings.Builder
}

func (f *FileNode) Name() string { return f.name }

// DirNode is a composite: a name plus a map of children, guarded by mu.
// mu is what makes get-or-create for THIS directory's children atomic --
// see walkToParent below, and UnsafeFileSystem for what happens without it.
type DirNode struct {
	mu       sync.Mutex
	name     string
	children map[string]Node
}

func (d *DirNode) Name() string { return d.name }

func newDir(name string) *DirNode { return &DirNode{name: name, children: make(map[string]Node)} }

// FileSystem is the Composite tree file system.
type FileSystem struct {
	root *DirNode
}

func NewFileSystem() *FileSystem { return &FileSystem{root: newDir("")} }

func splitPath(path string) []string {
	raw := strings.Split(path, "/")
	out := make([]string, 0, len(raw))
	for _, p := range raw {
		if p != "" {
			out = append(out, p)
		}
	}
	return out
}

// walkToParent walks to the directory that should contain the LAST path
// segment. Each level's get-or-create is one atomic "lock, check, create if
// absent, unlock" step under THAT directory's own lock -- concurrent Mkdir
// calls racing on the same missing segment always converge on the SAME
// DirNode, never a duplicate. See UnsafeFileSystem for the naive version
// that skips this lock.
func (fs *FileSystem) walkToParent(parts []string, createIntermediate bool) (*DirNode, error) {
	cur := fs.root
	for i := 0; i < len(parts)-1; i++ {
		seg := parts[i]
		cur.mu.Lock()
		child, ok := cur.children[seg]
		if !ok {
			if !createIntermediate {
				cur.mu.Unlock()
				return nil, errors.New("no such directory: " + seg)
			}
			child = newDir(seg)
			cur.children[seg] = child
		}
		cur.mu.Unlock()
		dir, isDir := child.(*DirNode)
		if !isDir {
			return nil, errors.New(seg + " exists and is a file, not a directory")
		}
		cur = dir
	}
	return cur, nil
}

func (fs *FileSystem) resolve(parts []string) (Node, error) {
	var cur Node = fs.root
	for _, seg := range parts {
		d, ok := cur.(*DirNode)
		if !ok {
			return nil, errors.New("no such path")
		}
		d.mu.Lock()
		child, ok := d.children[seg]
		d.mu.Unlock()
		if !ok {
			return nil, errors.New("no such path: " + seg)
		}
		cur = child
	}
	return cur, nil
}

// Ls on a directory is O(children at THIS node) -- never a scan of the whole
// filesystem. Ls on a file returns just its own name (POSIX ls semantics).
func (fs *FileSystem) Ls(path string) ([]string, error) {
	n, err := fs.resolve(splitPath(path))
	if err != nil {
		return nil, err
	}
	if f, ok := n.(*FileNode); ok {
		return []string{f.Name()}, nil
	}
	d := n.(*DirNode)
	d.mu.Lock()
	defer d.mu.Unlock()
	names := make([]string, 0, len(d.children))
	for name := range d.children {
		names = append(names, name)
	}
	sort.Strings(names)
	return names, nil
}

// Mkdir creates every missing intermediate directory (mkdir -p semantics).
// THREAD-SAFE: see walkToParent.
func (fs *FileSystem) Mkdir(path string) error {
	parts := splitPath(path)
	if len(parts) == 0 {
		return nil // mkdir("/") is a no-op
	}
	parent, err := fs.walkToParent(parts, true)
	if err != nil {
		return err
	}
	last := parts[len(parts)-1]
	parent.mu.Lock()
	defer parent.mu.Unlock()
	if existing, ok := parent.children[last]; ok {
		if _, isDir := existing.(*DirNode); !isDir {
			return errors.New(last + " exists as a file")
		}
		return nil
	}
	parent.children[last] = newDir(last)
	return nil
}

// AddContentToFile creates the file (and any missing parent directories) if
// absent, then APPENDS content -- classic addContentToFile semantics.
func (fs *FileSystem) AddContentToFile(path, content string) error {
	parts := splitPath(path)
	if len(parts) == 0 {
		return errors.New("cannot write to root")
	}
	parent, err := fs.walkToParent(parts, true)
	if err != nil {
		return err
	}
	last := parts[len(parts)-1]

	parent.mu.Lock()
	existing, ok := parent.children[last]
	var file *FileNode
	if !ok {
		file = &FileNode{name: last}
		parent.children[last] = file
	} else {
		f, isFile := existing.(*FileNode)
		if !isFile {
			parent.mu.Unlock()
			return errors.New(last + " is a directory")
		}
		file = f
	}
	parent.mu.Unlock()

	file.mu.Lock()
	file.content.WriteString(content)
	file.mu.Unlock()
	return nil
}

func (fs *FileSystem) ReadContentFromFile(path string) (string, error) {
	n, err := fs.resolve(splitPath(path))
	if err != nil {
		return "", err
	}
	f, ok := n.(*FileNode)
	if !ok {
		return "", errors.New(path + " is not a file")
	}
	f.mu.Lock()
	defer f.mu.Unlock()
	return f.content.String(), nil
}

// Rm detaches path from its parent. O(1): the whole subtree (if a directory)
// becomes unreferenced and is reclaimed by the GC in one map delete --
// nothing else in the tree stores full paths, so nothing else needs to change.
func (fs *FileSystem) Rm(path string) error {
	parts := splitPath(path)
	if len(parts) == 0 {
		return errors.New("cannot rm root")
	}
	parent, err := fs.walkToParent(parts, false)
	if err != nil {
		return err
	}
	last := parts[len(parts)-1]
	parent.mu.Lock()
	defer parent.mu.Unlock()
	if _, ok := parent.children[last]; !ok {
		return errors.New("no such path: " + path)
	}
	delete(parent.children, last)
	return nil
}

// MoveTo moves/renames a subtree in O(1): detach the node from its old
// parent, rename it, and re-attach under the new parent. The subtree under
// it moves as a single pointer -- no path is stored anywhere else to rewrite.
func (fs *FileSystem) MoveTo(srcPath, destPath string) error {
	srcParts := splitPath(srcPath)
	if len(srcParts) == 0 {
		return errors.New("cannot move root")
	}
	srcParent, err := fs.walkToParent(srcParts, false)
	if err != nil {
		return err
	}
	srcName := srcParts[len(srcParts)-1]

	srcParent.mu.Lock()
	moved, ok := srcParent.children[srcName]
	if ok {
		delete(srcParent.children, srcName)
	}
	srcParent.mu.Unlock()
	if !ok {
		return errors.New("no such path: " + srcPath)
	}

	destParts := splitPath(destPath)
	destParent, err := fs.walkToParent(destParts, true)
	if err != nil {
		return err
	}
	destName := destParts[len(destParts)-1]

	switch m := moved.(type) {
	case *FileNode:
		m.name = destName
	case *DirNode:
		m.name = destName
	}
	destParent.mu.Lock()
	destParent.children[destName] = moved
	destParent.mu.Unlock()
	return nil
}

The naive flat-map alternative, kept alongside for the break-it comparison. Save as filesystem/flat.go (same package):

package filesystem

import (
	"sort"
	"strings"
)

// FlatFileSystem is the NAIVE alternative most candidates reach for first:
// one flat map from full path string to file content, plus a set of
// directory paths. Point lookups (ReadContentFromFile) are O(1) -- but Ls
// and MoveTo must SCAN every entry in the entire filesystem, because "this
// path is a child of that path" is not stored anywhere; it can only be
// recovered by string-prefix-matching every key against every other key.
// LastScanCount is instrumentation ONLY, to make that cost measurable.
type FlatFileSystem struct {
	files         map[string]string // full path -> content (files only)
	dirs          map[string]bool   // full path -> "this is a directory" marker
	LastScanCount int
}

func NewFlatFileSystem() *FlatFileSystem {
	fs := &FlatFileSystem{files: map[string]string{}, dirs: map[string]bool{}}
	fs.dirs["/"] = true
	return fs
}

func (fs *FlatFileSystem) Mkdir(path string) {
	cur := ""
	for _, seg := range strings.Split(path, "/") {
		if seg == "" {
			continue
		}
		cur += "/" + seg
		fs.dirs[cur] = true
	}
}

func (fs *FlatFileSystem) AddContentToFile(path, content string) {
	fs.files[path] = fs.files[path] + content
}

func (fs *FlatFileSystem) ReadContentFromFile(path string) string {
	return fs.files[path]
}

// Ls must scan EVERY key in BOTH maps to find direct children of `path` --
// there is no structural pointer from a directory to its children.
func (fs *FlatFileSystem) Ls(path string) []string {
	if _, ok := fs.files[path]; ok {
		fs.LastScanCount = 1
		return []string{lastSegment(path)}
	}
	prefix := path + "/"
	if path == "/" {
		prefix = "/"
	}
	names := map[string]bool{}
	scanned := 0
	for p := range fs.files {
		scanned++
		if strings.HasPrefix(p, prefix) {
			names[directChild(p, prefix)] = true
		}
	}
	for p := range fs.dirs {
		scanned++
		if p != path && strings.HasPrefix(p, prefix) {
			names[directChild(p, prefix)] = true
		}
	}
	fs.LastScanCount = scanned // == size of BOTH maps combined -- O(n), not O(children)
	out := make([]string, 0, len(names))
	for n := range names {
		out = append(out, n)
	}
	sort.Strings(out)
	return out
}

// MoveTo: no pointer exists from "the subtree" to "its entries" either --
// every key in the ENTIRE filesystem must be examined to find which ones
// fall under srcPath, then rewritten with destPath as the new prefix.
func (fs *FlatFileSystem) MoveTo(srcPath, destPath string) {
	srcPrefix := srcPath + "/"
	var matchedFiles, matchedDirs []string
	scanned := 0
	for p := range fs.files {
		scanned++
		if p == srcPath || strings.HasPrefix(p, srcPrefix) {
			matchedFiles = append(matchedFiles, p)
		}
	}
	for p := range fs.dirs {
		scanned++
		if p == srcPath || strings.HasPrefix(p, srcPrefix) {
			matchedDirs = append(matchedDirs, p)
		}
	}
	fs.LastScanCount = scanned // == total entries, REGARDLESS of how big the moved subtree is
	for _, p := range matchedFiles {
		fs.files[destPath+p[len(srcPath):]] = fs.files[p]
		delete(fs.files, p)
	}
	for _, p := range matchedDirs {
		delete(fs.dirs, p)
		fs.dirs[destPath+p[len(srcPath):]] = true
	}
}

func lastSegment(path string) string {
	i := strings.LastIndex(path, "/")
	return path[i+1:]
}

func directChild(fullPath, prefix string) string {
	rest := fullPath[len(prefix):]
	if i := strings.Index(rest, "/"); i != -1 {
		return rest[:i]
	}
	return rest
}

The unsynchronized twin for the concurrency break-it. Save as filesystem/unsafe.go (same package):

package filesystem

import (
	"sort"
	"time"
)

// unsafeNode is a minimal directory node with NO lock at all -- not even a
// thread-safe map read/write. Exists ONLY for the break-it demo.
type unsafeNode struct {
	name     string
	children map[string]*unsafeNode
}

// UnsafeFileSystem reproduces the naive get-or-create most people write
// first: check whether the child exists, THEN create and insert it, with no
// synchronization between the check and the act. Go's map runtime detects
// concurrent mutation of the SAME map and kills the process outright --
// unlike Java's collections, which can silently corrupt or drop entries
// instead of crashing (see UnsafeFileSystem.mkdirUnsafe in the Java
// reference implementation for that contrast). Never use this in real code.
type UnsafeFileSystem struct {
	root *unsafeNode
}

func NewUnsafeFileSystem() *UnsafeFileSystem {
	return &UnsafeFileSystem{root: &unsafeNode{name: "", children: make(map[string]*unsafeNode)}}
}

// MkdirUnsafe creates (or returns the existing) child directory of root
// named `name` -- CHECK then ACT, no lock between them.
func (fs *UnsafeFileSystem) MkdirUnsafe(name string) *unsafeNode {
	child, ok := fs.root.children[name] // CHECK -- no lock
	if !ok {
		time.Sleep(time.Millisecond) // widen the window
		child = &unsafeNode{name: name, children: make(map[string]*unsafeNode)}
		fs.root.children[name] = child // ACT -- concurrent writers here crash the Go runtime
	}
	return child
}

func (fs *UnsafeFileSystem) AddMarkerUnsafe(dir *unsafeNode, marker string) {
	dir.children[marker] = &unsafeNode{name: marker, children: nil}
}

func (fs *UnsafeFileSystem) LsUnsafe(name string) []string {
	dir := fs.root.children[name]
	names := make([]string, 0, len(dir.children))
	for n := range dir.children {
		names = append(names, n)
	}
	sort.Strings(names)
	return names
}

Break it

This is the M1–M5 correctness suite plus both break-it demonstrations for Java. Save as FileSystemBreakIt.java, alongside FileSystem.java above:

import java.util.Arrays;
import java.util.List;

public final class FileSystemBreakIt {
    static int pass = 0, fail = 0;

    static void check(String name, boolean cond) {
        if (cond) { pass++; System.out.println("PASS: " + name); }
        else      { fail++; System.out.println("FAIL: " + name); }
    }

    public static void main(String[] args) throws InterruptedException {

        // --- M1: mkdir + addContentToFile + readContentFromFile + ls, on a fresh tree ---
        {
            FileSystem fs = new FileSystem();
            fs.mkdir("/a/b/c");                       // mkdir -p semantics: creates a, b, c
            check("M1: ls(/) shows the top-level dir created by mkdir -p", fs.ls("/").equals(Arrays.asList("a")));
            check("M1: ls(/a) shows b", fs.ls("/a").equals(Arrays.asList("b")));
            check("M1: ls(/a/b) shows c", fs.ls("/a/b").equals(Arrays.asList("c")));

            fs.addContentToFile("/a/b/c/file.txt", "hello");
            fs.addContentToFile("/a/b/c/file.txt", " world");   // addContentToFile APPENDS
            check("M1: addContentToFile appends across calls", fs.readContentFromFile("/a/b/c/file.txt").equals("hello world"));
            check("M1: ls(/a/b/c) now shows the file too, sorted", fs.ls("/a/b/c").equals(Arrays.asList("file.txt")));
            check("M1: ls on a FILE path returns just that file's own name", fs.ls("/a/b/c/file.txt").equals(Arrays.asList("file.txt")));
        }

        // --- M2: multiple siblings, ls returns them SORTED ---
        {
            FileSystem fs = new FileSystem();
            fs.mkdir("/docs");
            fs.addContentToFile("/docs/zebra.txt", "z");
            fs.addContentToFile("/docs/apple.txt", "a");
            fs.mkdir("/docs/mango");
            check("M2: ls returns files AND subdirectories, sorted together",
                    fs.ls("/docs").equals(Arrays.asList("apple.txt", "mango", "zebra.txt")));
        }

        // --- M3: rm detaches a whole subtree in one shot ---
        {
            FileSystem fs = new FileSystem();
            fs.mkdir("/a/b/c");
            fs.addContentToFile("/a/b/c/f.txt", "x");
            fs.addContentToFile("/a/b/g.txt", "y");
            fs.rm("/a/b/c");                            // removes c AND everything under it
            check("M3: rm(/a/b/c) removes the whole subtree", fs.ls("/a/b").equals(Arrays.asList("g.txt")));
            boolean threw = false;
            try { fs.readContentFromFile("/a/b/c/f.txt"); } catch (Exception e) { threw = true; }
            check("M3: content under the removed subtree is gone", threw);
        }

        // --- M4: moveTo relocates a whole subtree, content intact, in one call ---
        {
            FileSystem fs = new FileSystem();
            fs.mkdir("/project/src");
            fs.addContentToFile("/project/src/main.go", "package main");
            fs.addContentToFile("/project/src/util.go", "package main // util");
            fs.moveTo("/project/src", "/archive/src");
            check("M4: after moveTo, the OLD path is gone", fs.ls("/project").isEmpty());
            check("M4: the NEW path has both files, content intact",
                    fs.ls("/archive/src").equals(Arrays.asList("main.go", "util.go"))
                            && fs.readContentFromFile("/archive/src/main.go").equals("package main"));
        }

        // --- Break-it #1: FLAT map vs TREE -- cost of ls() and moveTo() ---
        {
            final int noiseFiles = 5000; // files scattered elsewhere in the filesystem
            FlatFileSystem flat = new FlatFileSystem();
            FileSystem tree = new FileSystem();

            flat.mkdir("/target");
            tree.mkdir("/target");
            flat.addContentToFile("/target/only.txt", "x");
            tree.addContentToFile("/target/only.txt", "x");

            for (int i = 0; i < noiseFiles; i++) {
                String p = "/noise" + i + "/f.txt";
                flat.mkdir("/noise" + i);
                flat.addContentToFile(p, "x");
                tree.mkdir("/noise" + i);
                tree.addContentToFile(p, "x");
            }

            List<String> flatLs = flat.ls("/target");
            List<String> treeLs = tree.ls("/target");
            check("break-it setup: flat and tree agree on ls(/target) contents",
                    flatLs.equals(treeLs) && flatLs.equals(Arrays.asList("only.txt")));

            System.out.println("ls(/target): FLAT scanned " + flat.lastScanCount + " entries (noiseFiles="
                    + noiseFiles + " elsewhere in the fs); TREE examined only " + treeLs.size() + " child(ren) of /target");
            check("break-it: FLAT map's ls() scans ~the WHOLE filesystem, not just /target's own children",
                    flat.lastScanCount > noiseFiles);
            check("fix: TREE's ls() only ever touches /target's OWN children -- 1 here, independent of noiseFiles",
                    treeLs.size() == 1);

            flat.moveTo("/target", "/moved");
            tree.moveTo("/target", "/moved");
            System.out.println("moveTo(/target, /moved): FLAT scanned " + flat.lastScanCount
                    + " entries to find & rewrite the ones under /target (== whole fs)");
            check("break-it: FLAT map's moveTo() rewrites/scans EVERY key in the filesystem, not just the moved subtree",
                    flat.lastScanCount > noiseFiles);
            check("fix: TREE's moveTo() is a constant-size detach+reattach -- the moved data survives intact",
                    tree.readContentFromFile("/moved/only.txt").equals("x"));
        }

        // --- Break-it #2: concurrent mkdir of the SAME path (the "make it thread-safe" milestone) ---
        {
            final int threads = 200;

            UnsafeFileSystem unsafe = new UnsafeFileSystem();
            Thread[] pool = new Thread[threads];
            for (int t = 0; t < threads; t++) {
                final int id = t;
                pool[t] = new Thread(() -> {
                    DirNode dir = unsafe.mkdirUnsafe("racedir");     // racing, unsynchronized get-or-create
                    unsafe.addContentToFileUnsafe(dir, "marker" + id, "x");
                });
            }
            for (Thread th : pool) th.start();
            for (Thread th : pool) th.join();
            int unsafeSeen = unsafe.ls("racedir").size();
            System.out.println("BREAK-IT (concurrent mkdir): " + unsafeSeen + " / " + threads
                    + " markers survived (want " + threads + ") -- the rest were written into an orphaned DirNode instance");
            check("break-it: UNSAFE concurrent mkdir loses marker files to orphaned directory instances",
                    unsafeSeen < threads);

            FileSystem safe = new FileSystem();
            Thread[] safePool = new Thread[threads];
            for (int t = 0; t < threads; t++) {
                final int id = t;
                safePool[t] = new Thread(() -> {
                    safe.mkdir("/racedir");
                    safe.addContentToFile("/racedir/marker" + id, "x");
                });
            }
            for (Thread th : safePool) th.start();
            for (Thread th : safePool) th.join();
            int safeSeen = safe.ls("/racedir").size();
            System.out.println("FIX (computeIfAbsent): " + safeSeen + " / " + threads + " markers survived (want " + threads + ")");
            check("fix: computeIfAbsent-based mkdir never orphans a directory under concurrent creation",
                    safeSeen == threads);
        }

        System.out.println();
        System.out.println(pass + " passed, " + fail + " failed");
        if (fail > 0) System.exit(1);
    }
}

Measured in this session (javac FileSystem.java FileSystemBreakIt.java && java FileSystemBreakIt): all 18/18 assertions pass. With noiseFiles = 5000, ls(/target) on the FLAT map scanned 10,003 entries (the whole filesystem) to answer a question about ONE directory with ONE child; the TREE examined exactly 1. moveTo(/target, /moved) on the FLAT map scanned the same 10,003 entries again to find and rewrite the handful that actually mattered. The concurrent-mkdir race is genuinely nondeterministic and reproduces on every run: repeated executions measured 75, 115, 125, and 168 of 200 marker files surviving under the UNSAFE twin (never all 200 — some are always written into a DirNode that lost the race for the "racedir" slot and became unreachable from the root); the safe, computeIfAbsent-based version landed on exactly 200/200 every single run.

For Go, this is the M1–M5 correctness suite plus the flat-vs-tree cost comparison and the SAFE concurrency test, all runnable with go test. Save as filesystem/filesystem_test.go:

package filesystem

import (
	"strconv"
	"sync"
	"testing"
)

func mustLs(t *testing.T, fs *FileSystem, path string) []string {
	t.Helper()
	names, err := fs.Ls(path)
	if err != nil {
		t.Fatalf("Ls(%s): %v", path, err)
	}
	return names
}

func eq(a, b []string) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

// --- M1: mkdir + addContentToFile + readContentFromFile + ls, on a fresh tree ---
func TestBasicMkdirAddReadLs(t *testing.T) {
	fs := NewFileSystem()
	if err := fs.Mkdir("/a/b/c"); err != nil {
		t.Fatalf("Mkdir: %v", err)
	}
	if got := mustLs(t, fs, "/"); !eq(got, []string{"a"}) {
		t.Fatalf("expected [a], got %v", got)
	}
	if got := mustLs(t, fs, "/a"); !eq(got, []string{"b"}) {
		t.Fatalf("expected [b], got %v", got)
	}
	if got := mustLs(t, fs, "/a/b"); !eq(got, []string{"c"}) {
		t.Fatalf("expected [c], got %v", got)
	}

	if err := fs.AddContentToFile("/a/b/c/file.txt", "hello"); err != nil {
		t.Fatalf("AddContentToFile: %v", err)
	}
	if err := fs.AddContentToFile("/a/b/c/file.txt", " world"); err != nil { // APPENDS
		t.Fatalf("AddContentToFile: %v", err)
	}
	content, err := fs.ReadContentFromFile("/a/b/c/file.txt")
	if err != nil || content != "hello world" {
		t.Fatalf("expected 'hello world', got %q err=%v", content, err)
	}
	if got := mustLs(t, fs, "/a/b/c"); !eq(got, []string{"file.txt"}) {
		t.Fatalf("expected [file.txt], got %v", got)
	}
	if got := mustLs(t, fs, "/a/b/c/file.txt"); !eq(got, []string{"file.txt"}) {
		t.Fatalf("Ls on a file should return just its own name, got %v", got)
	}
}

// --- M2: multiple siblings, Ls returns them SORTED ---
func TestLsReturnsSortedSiblings(t *testing.T) {
	fs := NewFileSystem()
	fs.Mkdir("/docs")
	fs.AddContentToFile("/docs/zebra.txt", "z")
	fs.AddContentToFile("/docs/apple.txt", "a")
	fs.Mkdir("/docs/mango")
	got := mustLs(t, fs, "/docs")
	if !eq(got, []string{"apple.txt", "mango", "zebra.txt"}) {
		t.Fatalf("expected sorted [apple.txt mango zebra.txt], got %v", got)
	}
}

// --- M3: Rm detaches a whole subtree in one shot ---
func TestRmRemovesWholeSubtree(t *testing.T) {
	fs := NewFileSystem()
	fs.Mkdir("/a/b/c")
	fs.AddContentToFile("/a/b/c/f.txt", "x")
	fs.AddContentToFile("/a/b/g.txt", "y")
	if err := fs.Rm("/a/b/c"); err != nil {
		t.Fatalf("Rm: %v", err)
	}
	if got := mustLs(t, fs, "/a/b"); !eq(got, []string{"g.txt"}) {
		t.Fatalf("expected [g.txt] after rm, got %v", got)
	}
	if _, err := fs.ReadContentFromFile("/a/b/c/f.txt"); err == nil {
		t.Fatalf("expected error reading content under a removed subtree")
	}
}

// --- M4: MoveTo relocates a whole subtree, content intact, in one call ---
func TestMoveToRelocatesSubtree(t *testing.T) {
	fs := NewFileSystem()
	fs.Mkdir("/project/src")
	fs.AddContentToFile("/project/src/main.go", "package main")
	fs.AddContentToFile("/project/src/util.go", "package main // util")
	if err := fs.MoveTo("/project/src", "/archive/src"); err != nil {
		t.Fatalf("MoveTo: %v", err)
	}
	if got := mustLs(t, fs, "/project"); len(got) != 0 {
		t.Fatalf("expected /project empty after move, got %v", got)
	}
	got := mustLs(t, fs, "/archive/src")
	if !eq(got, []string{"main.go", "util.go"}) {
		t.Fatalf("expected [main.go util.go], got %v", got)
	}
	content, _ := fs.ReadContentFromFile("/archive/src/main.go")
	if content != "package main" {
		t.Fatalf("expected content intact after move, got %q", content)
	}
}

// --- Break-it #1: FLAT map vs TREE -- cost of Ls() and MoveTo() ---
func TestFlatVsTreeLsAndMoveCost(t *testing.T) {
	const noiseFiles = 5000
	flat := NewFlatFileSystem()
	tree := NewFileSystem()

	flat.Mkdir("/target")
	tree.Mkdir("/target")
	flat.AddContentToFile("/target/only.txt", "x")
	tree.AddContentToFile("/target/only.txt", "x")

	for i := 0; i < noiseFiles; i++ {
		p := "/noise" + strconv.Itoa(i) + "/f.txt"
		flat.Mkdir("/noise" + strconv.Itoa(i))
		flat.AddContentToFile(p, "x")
		tree.Mkdir("/noise" + strconv.Itoa(i))
		tree.AddContentToFile(p, "x")
	}

	flatLs := flat.Ls("/target")
	treeLs := mustLs(t, tree, "/target")
	if !eq(flatLs, []string{"only.txt"}) || !eq(treeLs, []string{"only.txt"}) {
		t.Fatalf("expected both to agree on [only.txt], flat=%v tree=%v", flatLs, treeLs)
	}

	t.Logf("Ls(/target): FLAT scanned %d entries (noiseFiles=%d); TREE examined only %d child(ren)",
		flat.LastScanCount, noiseFiles, len(treeLs))
	if flat.LastScanCount <= noiseFiles {
		t.Fatalf("expected FLAT map's Ls to scan ~the whole filesystem (>%d), got %d", noiseFiles, flat.LastScanCount)
	}
	if len(treeLs) != 1 {
		t.Fatalf("expected TREE's Ls to touch only /target's own child, got %d", len(treeLs))
	}

	flat.MoveTo("/target", "/moved")
	if err := tree.MoveTo("/target", "/moved"); err != nil {
		t.Fatalf("MoveTo: %v", err)
	}
	t.Logf("MoveTo(/target, /moved): FLAT scanned %d entries (== whole fs)", flat.LastScanCount)
	if flat.LastScanCount <= noiseFiles {
		t.Fatalf("expected FLAT map's MoveTo to scan ~the whole filesystem (>%d), got %d", noiseFiles, flat.LastScanCount)
	}
	content, err := tree.ReadContentFromFile("/moved/only.txt")
	if err != nil || content != "x" {
		t.Fatalf("expected moved content intact, got %q err=%v", content, err)
	}
}

// TestConcurrentMkdirIsSafe hammers the LOCKED Mkdir path for the SAME
// nested directory from many goroutines. Run with `go test -race`: it must
// report zero races, in contrast to UnsafeFileSystem (exercised by the
// separate cmd/breakit_concurrentmkdir program on purpose, since it crashes
// the process).
func TestConcurrentMkdirIsSafe(t *testing.T) {
	const goroutines = 200
	fs := NewFileSystem()
	var wg sync.WaitGroup
	for i := 0; i < goroutines; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			fs.Mkdir("/racedir")
			fs.AddContentToFile("/racedir/marker"+strconv.Itoa(i), "x")
		}(i)
	}
	wg.Wait()
	names, err := fs.Ls("/racedir")
	if err != nil {
		t.Fatalf("Ls: %v", err)
	}
	if len(names) != goroutines {
		t.Fatalf("expected all %d markers to survive concurrent mkdir, got %d", goroutines, len(names))
	}
}

And the separate break-it binary that reproduces the concurrency race with Go's naive, lock-free twin — it has to be its own program, not a go test case, because the expected outcome is a crash. Save as cmd/breakit_concurrentmkdir/main.go, in a module that imports the filesystem package above:

// Command breakit_concurrentmkdir hammers UnsafeFileSystem.MkdirUnsafe (the
// naive check-then-act, no lock) with 200 goroutines all racing to create
// the SAME directory "racedir" off the root and then write their own marker
// file into whichever *unsafeNode they got back. Expect either:
//   - a crash: Go's map runtime detects the concurrent writes to the shared
//     root.children map and calls fatal() -- "fatal error: concurrent map
//     writes" -- not recoverable, which is why this is its own binary; or
//   - if you get unlucky and it doesn't crash this run, fewer than 200
//     markers survive, because some goroutines wrote their marker into an
//     *unsafeNode that lost the race and was never reachable from root.
//
//	go run ./cmd/breakit_concurrentmkdir          # usually crashes: fatal error: concurrent map writes
//	go run -race ./cmd/breakit_concurrentmkdir    # prints "WARNING: DATA RACE" first
package main

import (
	"fmt"
	"strconv"
	"sync"

	"filesystemkata/filesystem"
)

func main() {
	const goroutines = 200
	fs := filesystem.NewUnsafeFileSystem()

	var wg sync.WaitGroup
	for i := 0; i < goroutines; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			dir := fs.MkdirUnsafe("racedir") // racing, unsynchronized get-or-create
			fs.AddMarkerUnsafe(dir, "marker"+strconv.Itoa(i))
		}(i)
	}
	wg.Wait()

	// Reached only if the runtime didn't catch the race THIS run -- still
	// wrong, just not caught this time. That's the danger of an unguarded map.
	names := fs.LsUnsafe("racedir")
	fmt.Printf("no crash this run, but only %d / %d markers survived (want %d) -- the rest were written into an orphaned directory instance\n",
		len(names), goroutines, goroutines)
}

Measured in this session: go build ./... and go vet ./... are clean; go test ./... passes 6/6, and go test -race ./filesystem/... -count=3 passes with zero races across 3 repeated runs. go run ./cmd/breakit_concurrentmkdir crashed with fatal error: concurrent map writes on every one of 4 repeated runs; go run -race ./cmd/breakit_concurrentmkdir printed WARNING: DATA RACE, pinpointing the exact unsynchronized read (mapaccess1_faststr) and write (mapaccess2_faststr) inside MkdirUnsafe, before the same crash. The same missing lock produces two different failure signatures across languages, just like in the library kata: Java's ConcurrentHashMap stays internally consistent under the race — it just silently drops the losing thread's directory, a wrong-but-quiet answer — while Go's built-in map detects the concurrent write and kills the process outright, a loud non-answer. Neither is "safer"; both mean the same thing: this code needed one atomic get-or-create and instead had two separate steps.

Optimise — trade-offs

DecisionOption AOption BWhen A winsWhen B wins
Representing hierarchyFlat path→content map (The Trap)Composite tree (this kata) — note this is a trie keyed by path segment: a DirNode is a trie node whose edges are named by the next path component, not by one character. You don't need a separate "trie" implementation for this problem; the tree you build already is oneYou genuinely only ever do point reads/writes by full path and NEVER list a directory or move a subtree — vanishingly rare for anything called a "file system"Any workload that needs "what's in this folder" or "move this folder" to cost proportional to the folder, not the whole filesystem — which is the actual definition of a hierarchical file system
rm / moveTo costFlat map: scan+match every key against the target prefix, O(total entries in the fs)Tree: one map remove + one map insert on the parent(s), O(1) regardless of subtree sizeNever, for these two operations specifically — there's no scenario where re-deriving structure via string scan beats reading a pointerAlways — this is the entire reason the tree exists
Composite pattern itselfComposite (File/Directory share one Node shape)Type-checked / instanceof-scattered design (separate, unrelated File and Directory classes, client code branches on type everywhere)You need a NEW node type added often (symlink, mount point, device file) and want adding it to cost "implement one interface," not "hunt down every instanceof site in the codebase" — Composite's real winAlmost never for THIS problem; but be honest about Composite's own cost: a FileNode "pretends" to have no children, and operations that only make sense for one subtype (only directories have children; only files have content) still need a cast or a type check somewhere at the edges. Composite gives you uniform traversal, not fully uniform operations
Concurrency on directory creationTwo-step check-then-act (get, then create-and-put) — the naive version, whether backed by a plain map (Go: crashes) or even a thread-safe map (Java: silently drops the loser)One atomic get-or-create (Java: ConcurrentHashMap.computeIfAbsent; Go: a mutex around the whole "check, create if absent" step per directory)Never, once concurrent writers are possible — a thread-safe collection is not the same guarantee as an atomic compound operation on itAlways, whenever more than one thread can call mkdir on overlapping paths
Where a real filesystem differsA real OS filesystem separates the name (a directory entry / dentry) from the data + metadata (an inode): several directory entries can point at the SAME inode (hard links), content lives in fixed-size disk blocks referenced by the inode rather than one contiguous in-memory buffer, and permissions/ownership/timestamps live on the inode, not the tree position. This kata's FileNode conflates "the name at this tree position" with "the content" into one object — perfectly fine for interview scope, but it's exactly why hard links don't fall out for free (see Defend below): you'd need to add that inode-style indirection deliberately.

Defend under drilling

You can now defend

Re-authored/Deepened for this guide. Concept: the Composite Pattern. Reference implementations (Java + Go) compiled and tested in-session: javac clean, 18/18 assertions pass (including both break-it demonstrations — the flat map scanned 10,003 entries against the tree's 1 for both ls and moveTo, and the unsafe concurrent mkdir measured 75–168 of 200 markers surviving across repeated runs, never all 200, while the fixed version landed on 200/200 every run); go build + go vet + go test clean (6/6), go test -race clean across 3 repeated runs, and cmd/breakit_concurrentmkdir crashed with fatal error: concurrent map writes on every one of 4 runs, with go run -race additionally pinpointing the exact unsynchronized map access before each crash.

🤖 Don't fully get this? Learn it with Claude

Stuck on Design an In-Memory File System? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Design an In-Memory File System** (Hands-On Builds) and want to truly understand it. Explain Design an In-Memory File System from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Design an In-Memory File System** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Design an In-Memory File System** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Design an In-Memory File System** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Design a Movie Ticket Booking SystDesign the Snake Game →