32 — LLD: In-memory File System

Frequently Asked at Uber — Reported repeatedly in recent L5A R3 (Coding-Depth) rounds.

Understanding the Problem

An in-memory file system mimics a POSIX-like tree of directories and files, but keeps everything in RAM. This is LeetCode 588 at heart, with an almost-guaranteed follow-up about wildcard matching. The design rewards a clean Composite tree and an explicit separation between node identity and traversal logic.

What is an In-memory File System?

A hierarchical namespace where every path resolves to either a directory (containing children) or a file (containing content). Operations mimic shell commands: ls, mkdir, append-to-file, read-file.

Requirements

Clarifying Questions

You: Is it case-sensitive, like Linux, or case-insensitive like Windows?

Interviewer: Case-sensitive.

Affects how you key children — plain strings, no normalization.

You: Can a file and a directory share the same name at the same level?

Interviewer: No. A node is either a file or a directory.

Lets you use a single Map<String, Node> for children and fail fast on collisions.

You: Does addContentToFile overwrite or append?

Interviewer: Append. Create the file if missing; otherwise append.

Clarifies the semantics. No "overwrite" mode in the core.

You: Concurrent readers and writers?

Interviewer: Start single-threaded. We will discuss concurrency.

Budget coarse locking first; promote to per-directory locks only if the interviewer pushes.

You: Max file size? Should reads stream?

Interviewer: In-memory strings are fine. Ignore streaming.

Final Requirements

ls(path) — if path is a file, return [filename]; if a directory, return sorted children names; empty if missing.
mkdir(path) — create intermediate directories as needed.
addContentToFile(path, content) — create file if missing, else append.
readContentFromFile(path) — return full content.
Case-sensitive. Exclusive name collision (file XOR directory at each name).

Out of scope: Permissions, symlinks, timestamps, streaming reads, crash recovery.

Deferred tradeoff: A global read-write lock is simpler and correct; per-directory hand-over-hand locking is a complexity multiplier and we will not pay it unless the workload proves contended.

Core Entities and Relationships

Two kinds of nodes — a file has content, a directory has children. Both share a name. That is textbook Composite pattern: a common abstract base with two concrete subtypes, and the directory holds a collection of its base type.

Entity	Responsibility
`Node`	Abstract base — name, type marker.
`Directory extends Node`	Sorted map of children names → nodes.
`File extends Node`	String content (appendable).
`FileSystem`	Owns the root. Path parsing, traversal, CRUD.

Why a TreeMap for children instead of HashMap? ls needs sorted output. Sorting once at insertion time beats re-sorting on every ls call.

Why an abstract Node base? So Directory.children can hold either subtype uniformly — and traversal code says "is this a file? if yes, stop; else descend" without casting at every level.

Design is iterative. If we later support hard links, we will introduce a separate Inode concept — multiple names pointing to the same file content.

Class Design

Node (abstract)

name: string — immutable.
isFile(): boolean — polymorphic.

File

content: StringBuilder — efficient append.

FileSystem

root: Directory — anchor for all paths.
lock: ReadWriteLock — for the concurrent variant.

Methods:

ls, mkdir, addContentToFile, readContentFromFile.
private resolve(path) -> Node | null — shared traversal helper.
private split(path) -> List<String> — path tokenizer.

JavaC++TypeScript

java

public abstract class Node {
    protected final String name;
    protected Node(String name) { this.name = name; }
    public abstract boolean isFile();
    public String getName() { return name; }
}

public class Directory extends Node {
    final TreeMap<String, Node> children = new TreeMap<>();
    public Directory(String name) { super(name); }
    public boolean isFile() { return false; }
}

public class File extends Node {
    final StringBuilder content = new StringBuilder();
    public File(String name) { super(name); }
    public boolean isFile() { return true; }
}

public class FileSystem {
    private final Directory root = new Directory("");
    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    public List<String> ls(String path) { /* ... */ }
    public void mkdir(String path) { /* ... */ }
    public void addContentToFile(String path, String content) { /* ... */ }
    public String readContentFromFile(String path) { /* ... */ }
}

cpp

struct Node {
    std::string name;
    bool isFile;
    std::string content;              // valid when isFile
    std::map<std::string, std::shared_ptr<Node>> children;
    explicit Node(std::string n, bool f) : name(std::move(n)), isFile(f) {}
};

class FileSystem {
    std::shared_ptr<Node> root = std::make_shared<Node>("", false);
    std::shared_mutex mtx;
public:
    std::vector<std::string> ls(const std::string& path);
    void mkdir(const std::string& path);
    void addContent(const std::string& path, const std::string& content);
    std::string readContent(const std::string& path);
};

typescript

class FSNode {
  constructor(public name: string, public isFile: boolean) {}
  content = "";
  children: Map<string, FSNode> = new Map();
}

export class FileSystem {
  private root = new FSNode("", false);

  ls(path: string): string[] { /* ... */ }
  mkdir(path: string): void { /* ... */ }
  addContentToFile(path: string, content: string): void { /* ... */ }
  readContentFromFile(path: string): string { /* ... */ }
}

Design principles at play:

Composite: Directory and File share the Node base. Traversal code is uniform.
Single Responsibility: Node subtypes store data; FileSystem owns traversal and invariants.
Law of Demeter (mostly): Callers never touch children directly; they go through ls, mkdir, etc.

Implementation

Core Logic: Path Splitting

/a/b/c → ["a", "b", "c"]. / → []. Trailing slashes tolerated. Empty segments dropped.

Core Logic: mkdir

Split the path into segments.
Starting from root, descend. For each segment:
- If child exists and is a directory, descend.
- If child exists and is a file, throw (collision).
- If child missing, create a new Directory and descend.

Core Logic: addContentToFile

Split the path. Last segment is the filename; preceding segments are directories.
Ensure all parent directories exist (create as needed, like mkdir -p).
At the parent, look up the filename:
- Missing → create File, insert.
- Exists as File → append to existing.
- Exists as Directory → throw.

Core Logic: ls

Resolve the path.
If null (not found) → return empty list.
If file → return [name].
If directory → return sorted children names (TreeMap already sorted).

Implementations

JavaC++TypeScript

java

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

public void mkdir(String path) {
    lock.writeLock().lock();
    try {
        Directory cur = root;
        for (String part : split(path)) {
            Node next = cur.children.get(part);
            if (next == null) {
                Directory d = new Directory(part);
                cur.children.put(part, d);
                cur = d;
            } else if (next.isFile()) {
                throw new IllegalStateException("path collides with file: " + part);
            } else {
                cur = (Directory) next;
            }
        }
    } finally {
        lock.writeLock().unlock();
    }
}

public List<String> ls(String path) {
    lock.readLock().lock();
    try {
        Node node = resolve(path);
        if (node == null) return List.of();
        if (node.isFile()) return List.of(node.getName());
        Directory d = (Directory) node;
        return new ArrayList<>(d.children.keySet());  // TreeMap already sorted
    } finally {
        lock.readLock().unlock();
    }
}

public void addContentToFile(String path, String content) {
    lock.writeLock().lock();
    try {
        List<String> parts = split(path);
        if (parts.isEmpty()) throw new IllegalArgumentException();
        Directory cur = root;
        for (int i = 0; i < parts.size() - 1; i++) {
            Node n = cur.children.get(parts.get(i));
            if (n == null) {
                Directory d = new Directory(parts.get(i));
                cur.children.put(parts.get(i), d);
                cur = d;
            } else if (n.isFile()) {
                throw new IllegalStateException();
            } else {
                cur = (Directory) n;
            }
        }
        String fname = parts.get(parts.size() - 1);
        Node existing = cur.children.get(fname);
        File f;
        if (existing == null) {
            f = new File(fname);
            cur.children.put(fname, f);
        } else if (existing.isFile()) {
            f = (File) existing;
        } else {
            throw new IllegalStateException("path is a directory");
        }
        f.content.append(content);
    } finally {
        lock.writeLock().unlock();
    }
}

public String readContentFromFile(String path) {
    lock.readLock().lock();
    try {
        Node n = resolve(path);
        if (n == null || !n.isFile()) throw new NoSuchElementException();
        return ((File) n).content.toString();
    } finally {
        lock.readLock().unlock();
    }
}

private Node resolve(String path) {
    Node cur = root;
    for (String p : split(path)) {
        if (!(cur instanceof Directory d)) return null;
        cur = d.children.get(p);
        if (cur == null) return null;
    }
    return cur;
}

cpp

std::vector<std::string> split(const std::string& path) {
    std::vector<std::string> out;
    size_t i = 0;
    while (i < path.size()) {
        while (i < path.size() && path[i] == '/') ++i;
        size_t j = i;
        while (j < path.size() && path[j] != '/') ++j;
        if (j > i) out.emplace_back(path.substr(i, j - i));
        i = j;
    }
    return out;
}

void FileSystem::mkdir(const std::string& path) {
    std::unique_lock lk(mtx);
    auto cur = root;
    for (auto& part : split(path)) {
        auto it = cur->children.find(part);
        if (it == cur->children.end()) {
            auto d = std::make_shared<Node>(part, false);
            cur->children[part] = d;
            cur = d;
        } else if (it->second->isFile) {
            throw std::runtime_error("path collides with file");
        } else {
            cur = it->second;
        }
    }
}

typescript

private split(path: string): string[] {
  return path.split("/").filter(p => p.length > 0);
}

mkdir(path: string): void {
  let cur = this.root;
  for (const part of this.split(path)) {
    if (!cur.children.has(part)) {
      cur.children.set(part, new FSNode(part, false));
    }
    const next = cur.children.get(part)!;
    if (next.isFile) throw new Error("path collides with file");
    cur = next;
  }
}

ls(path: string): string[] {
  const node = this.resolve(path);
  if (!node) return [];
  if (node.isFile) return [node.name];
  return [...node.children.keys()].sort();
}

addContentToFile(path: string, content: string): void {
  const parts = this.split(path);
  if (parts.length === 0) throw new Error("bad path");
  let cur = this.root;
  for (let i = 0; i < parts.length - 1; i++) {
    if (!cur.children.has(parts[i])) {
      cur.children.set(parts[i], new FSNode(parts[i], false));
    }
    const next = cur.children.get(parts[i])!;
    if (next.isFile) throw new Error("collision");
    cur = next;
  }
  const fname = parts[parts.length - 1];
  let f = cur.children.get(fname);
  if (!f) { f = new FSNode(fname, true); cur.children.set(fname, f); }
  else if (!f.isFile) throw new Error("is directory");
  f.content += content;
}

readContentFromFile(path: string): string {
  const n = this.resolve(path);
  if (!n || !n.isFile) throw new Error("not a file");
  return n.content;
}

private resolve(path: string): FSNode | null {
  let cur = this.root;
  for (const part of this.split(path)) {
    if (cur.isFile) return null;
    const next = cur.children.get(part);
    if (!next) return null;
    cur = next;
  }
  return cur;
}

Thread Safety

A ReadWriteLock over the whole tree is simple and correct. Many concurrent readers (ls, readContentFromFile) run in parallel; any writer (mkdir, addContentToFile) excludes everyone.

For higher concurrency, per-directory locks with hand-over-hand traversal are possible — but the deadlock surface is non-trivial and real workloads rarely justify it. Only pursue if the interviewer asks or contention is proven.

Never hold the lock while doing I/O or calling listener code. Here every operation is in-memory, so a coarse RWLock is fine.

Verification

mkdir("/a/b"), addContentToFile("/a/b/c.txt", "hello"), addContentToFile("/a/b/c.txt", " world"), ls("/a/b"), readContentFromFile("/a/b/c.txt").

Step	Tree	Returns
mkdir	`/a/b` exists	-
addContent 1	`/a/b/c.txt` = "hello"	-
addContent 2	`/a/b/c.txt` = "hello world"	-
ls("/a/b")	-	`["c.txt"]`
read	-	`"hello world"`

Edge case: ls("/a/b/c.txt") returns ["c.txt"] — file path case. ls("/does/not/exist") returns [].

Complete Code Implementation

JavaC++TypeScript

java

import java.util.*;
import java.util.concurrent.locks.*;

public abstract class Node {
    protected final String name;
    protected Node(String name) { this.name = name; }
    public abstract boolean isFile();
    public String getName() { return name; }
}

public class Directory extends Node {
    final TreeMap<String, Node> children = new TreeMap<>();
    public Directory(String name) { super(name); }
    public boolean isFile() { return false; }
}

public class File extends Node {
    final StringBuilder content = new StringBuilder();
    public File(String name) { super(name); }
    public boolean isFile() { return true; }
}

public class FileSystem {
    private final Directory root = new Directory("");
    private final ReadWriteLock lock = new ReentrantReadWriteLock();

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

    private Node resolve(String path) {
        Node cur = root;
        for (String p : split(path)) {
            if (!(cur instanceof Directory d)) return null;
            cur = d.children.get(p);
            if (cur == null) return null;
        }
        return cur;
    }

    public void mkdir(String path) {
        lock.writeLock().lock();
        try {
            Directory cur = root;
            for (String part : split(path)) {
                Node next = cur.children.get(part);
                if (next == null) {
                    Directory d = new Directory(part);
                    cur.children.put(part, d);
                    cur = d;
                } else if (next.isFile()) {
                    throw new IllegalStateException();
                } else cur = (Directory) next;
            }
        } finally { lock.writeLock().unlock(); }
    }

    public List<String> ls(String path) {
        lock.readLock().lock();
        try {
            Node node = resolve(path);
            if (node == null) return List.of();
            if (node.isFile()) return List.of(node.getName());
            return new ArrayList<>(((Directory) node).children.keySet());
        } finally { lock.readLock().unlock(); }
    }

    public void addContentToFile(String path, String content) {
        lock.writeLock().lock();
        try {
            List<String> parts = split(path);
            if (parts.isEmpty()) throw new IllegalArgumentException();
            Directory cur = root;
            for (int i = 0; i < parts.size() - 1; i++) {
                Node n = cur.children.get(parts.get(i));
                if (n == null) {
                    Directory d = new Directory(parts.get(i));
                    cur.children.put(parts.get(i), d);
                    cur = d;
                } else if (n.isFile()) throw new IllegalStateException();
                else cur = (Directory) n;
            }
            String fname = parts.get(parts.size() - 1);
            Node existing = cur.children.get(fname);
            File f;
            if (existing == null) {
                f = new File(fname);
                cur.children.put(fname, f);
            } else if (existing.isFile()) f = (File) existing;
            else throw new IllegalStateException();
            f.content.append(content);
        } finally { lock.writeLock().unlock(); }
    }

    public String readContentFromFile(String path) {
        lock.readLock().lock();
        try {
            Node n = resolve(path);
            if (n == null || !n.isFile()) throw new NoSuchElementException();
            return ((File) n).content.toString();
        } finally { lock.readLock().unlock(); }
    }
}

cpp

#include <map>
#include <memory>
#include <mutex>
#include <shared_mutex>
#include <string>
#include <vector>

struct Node {
    std::string name;
    bool isFile;
    std::string content;
    std::map<std::string, std::shared_ptr<Node>> children;
    explicit Node(std::string n, bool f) : name(std::move(n)), isFile(f) {}
};

class FileSystem {
    std::shared_ptr<Node> root = std::make_shared<Node>("", false);
    std::shared_mutex mtx;

    std::vector<std::string> split(const std::string& p) {
        std::vector<std::string> out;
        size_t i = 0;
        while (i < p.size()) {
            while (i < p.size() && p[i] == '/') ++i;
            size_t j = i;
            while (j < p.size() && p[j] != '/') ++j;
            if (j > i) out.emplace_back(p.substr(i, j - i));
            i = j;
        }
        return out;
    }
public:
    std::vector<std::string> ls(const std::string& path) {
        std::shared_lock lk(mtx);
        auto cur = root;
        for (auto& p : split(path)) {
            auto it = cur->children.find(p);
            if (it == cur->children.end()) return {};
            cur = it->second;
        }
        if (cur->isFile) return { cur->name };
        std::vector<std::string> out;
        for (auto& kv : cur->children) out.push_back(kv.first);
        return out;
    }

    void mkdir(const std::string& path) {
        std::unique_lock lk(mtx);
        auto cur = root;
        for (auto& part : split(path)) {
            auto it = cur->children.find(part);
            if (it == cur->children.end()) {
                auto d = std::make_shared<Node>(part, false);
                cur->children[part] = d;
                cur = d;
            } else if (it->second->isFile) throw std::runtime_error("collision");
            else cur = it->second;
        }
    }
};

typescript

class FSNode {
  constructor(public name: string, public isFile: boolean) {}
  content = "";
  children: Map<string, FSNode> = new Map();
}

export class FileSystem {
  private root = new FSNode("", false);

  private split(p: string): string[] { return p.split("/").filter(s => s.length > 0); }

  private resolve(path: string): FSNode | null {
    let cur = this.root;
    for (const part of this.split(path)) {
      if (cur.isFile) return null;
      const next = cur.children.get(part);
      if (!next) return null;
      cur = next;
    }
    return cur;
  }

  ls(path: string): string[] {
    const n = this.resolve(path);
    if (!n) return [];
    if (n.isFile) return [n.name];
    return [...n.children.keys()].sort();
  }

  mkdir(path: string): void {
    let cur = this.root;
    for (const part of this.split(path)) {
      if (!cur.children.has(part)) cur.children.set(part, new FSNode(part, false));
      const next = cur.children.get(part)!;
      if (next.isFile) throw new Error("collision");
      cur = next;
    }
  }

  addContentToFile(path: string, content: string): void {
    const parts = this.split(path);
    if (parts.length === 0) throw new Error("bad path");
    let cur = this.root;
    for (let i = 0; i < parts.length - 1; i++) {
      if (!cur.children.has(parts[i])) cur.children.set(parts[i], new FSNode(parts[i], false));
      const next = cur.children.get(parts[i])!;
      if (next.isFile) throw new Error("collision");
      cur = next;
    }
    const fname = parts[parts.length - 1];
    let f = cur.children.get(fname);
    if (!f) { f = new FSNode(fname, true); cur.children.set(fname, f); }
    else if (!f.isFile) throw new Error("is directory");
    f.content += content;
  }

  readContentFromFile(path: string): string {
    const n = this.resolve(path);
    if (!n || !n.isFile) throw new Error("not a file");
    return n.content;
  }
}

Extensibility

1. "Support `ls` with wildcards, e.g. `ls("/a/*/file.txt")`?"

Parse the path into segments. For each segment:

If it is a literal → descend to that child.
If it contains * or ? → expand matching children and recurse on each.

The traversal becomes a BFS that collects all matching leaf paths. Compile each wildcard segment to a regex once per call.

java

private void expand(Node node, List<String> segments, int i, List<String> acc, String path) {
    if (i == segments.size()) { acc.add(path); return; }
    if (!(node instanceof Directory d)) return;
    String seg = segments.get(i);
    Pattern p = compileGlob(seg);
    for (var e : d.children.entrySet()) {
        if (p.matcher(e.getKey()).matches()) {
            expand(e.getValue(), segments, i + 1, acc, path + "/" + e.getKey());
        }
    }
}

Tradeoff: Wildcards can fan out exponentially. Cap the results or stream them to the caller.

2. "Rename or move a path (`mv src dst`)?"

Resolve both parents, remove from source's children, insert into destination's under the new name — all inside the write lock. Must be transactional: if the destination insert fails (collision), restore the source. Pre-check both sides before mutating.

3. "Permissions — who can read/write what?"

Add owner, mode (rwxrwxrwx) to Node. Every method takes a User principal and checks permission bits on each directory in the path. Introduce a PermissionService to centralize the check.

Tradeoff: Cross-cutting concern. Cleanest as an aspect/decorator rather than polluting every method, but that costs one layer of indirection.

What is Expected at Each Level

Level	Expectations
Junior (L4)	Flat `HashMap<String, File>` keyed by full path. Misses the tree structure — interviewer will hint.
Mid (L5)	Composite tree with `Directory`/`File`, recursive traversal, correct collision handling. Mentions RWLock when asked.
Senior (L5A)	Clean `Node` abstraction, RWLock by default, solves the wildcard follow-up in ~10 minutes using BFS + regex per segment. Proactively mentions the per-directory lock trade-off.
Staff (L6)	Inode/dentry separation, hard and soft links, journaling for crash safety, mount points, and how this evolves into a distributed FS.

32 — LLD: In-memory File System ​

Understanding the Problem ​

Requirements ​

Clarifying Questions ​

Final Requirements ​

Core Entities and Relationships ​

Class Design ​

Node (abstract) ​

Directory ​

File ​

FileSystem ​

Implementation ​

Core Logic: Path Splitting ​

Core Logic: mkdir ​

Core Logic: addContentToFile ​

Core Logic: ls ​

Implementations ​

Thread Safety ​

Verification ​

Complete Code Implementation ​

Extensibility ​

1. "Support ls with wildcards, e.g. ls("/a/*/file.txt")?" ​

2. "Rename or move a path (mv src dst)?" ​

3. "Permissions — who can read/write what?" ​

What is Expected at Each Level ​

32 — LLD: In-memory File System

Understanding the Problem

Requirements

Clarifying Questions

Final Requirements

Core Entities and Relationships

Class Design

Node (abstract)

Directory

File

FileSystem

Implementation

Core Logic: Path Splitting

Core Logic: mkdir

Core Logic: addContentToFile

Core Logic: ls

Implementations

Thread Safety

Verification

Complete Code Implementation

Extensibility

1. "Support `ls` with wildcards, e.g. `ls("/a/*/file.txt")`?"

2. "Rename or move a path (`mv src dst`)?"

3. "Permissions — who can read/write what?"

What is Expected at Each Level