51 — LLD: In-memory File System

Understanding the Problem

Implement an in-memory file system with mkdir, pwd, cd, ls (with wildcard), touch, write, and read. Path resolution follows Unix conventions — absolute if it starts with /, relative otherwise, with . and .. support.

What is the in-memory FS problem?

It is a tree plus a path-resolver. Each node is a directory or a file; directories have children, files have content. The tricky bits are relative-path walking, wildcard ls, and keeping the invariants clean when the same name could collide between files and directories.

---

Requirements

Clarifying Questions

You: Are file and directory names case-sensitive?

Interviewer: Yes.

Simple string keys in the children map.

You: What does ls do on a file vs a directory?

Interviewer: On a file, return just that file's name. On a directory, return its children.

Branch on isDir at the resolved node.

You: Wildcard — only * or full globs?

Interviewer: Just *. Anywhere in the pattern.

Compile to a regex once per call.

You: Is there a current working directory, or is every call absolute?

Interviewer: Maintain a cwd. cd and pwd manage it.

Internal state is a cwd path stack.

You: Permissions?

Interviewer: Out of scope.

Final Requirements

1. mkdir(path) — create directory (recursive, like mkdir -p).
2. pwd() — return absolute path of current dir.
3. cd(path) — change working directory; throws on file or missing path.
4. ls(pattern?) — list current directory entries, optionally filtered by a glob.
5. touch(path) — create empty file.
6. write(path, content) — overwrite file content.
7. read(path) -> string.

Out of scope: permissions, symlinks (as follow-up), quotas, concurrent writer safety beyond a single lock.

---

Core Entities and Relationships

Entity	Responsibility
Node	Represents either a directory or a file. Name, flag, children, content.
FileSystem	Root node, cwd stack, all operations.
PathResolver (helper)	Convert string path to a node stack, honouring . and ...

Why one Node for both kinds? Because Unix does the same, and it keeps the tree uniform. The isDir flag is cheap.

Why a stack for cwd? Because pwd must print every segment, and cd .. is a pop. A stack is the natural structure.

Design is iterative — build path resolution first, everything else is thin wrapper on top.

---

Class Design

Node

State: name, isDir, children: Map<name, Node>, content: string

FileSystem

State:

• root: Node("/", isDir=true)
• cwd: Node[] — path stack starting with root

Methods:

• resolve(path) -> Node[] — returns a stack ending at the target; throws on missing path
• pwd() — joins cwd minus root with /
• mkdir(path), cd(path), touch(path), write(path, content), read(path)
• ls(pattern = "*")

Design principles at play:

• Single Responsibility — Node stores, FileSystem navigates, PathResolver is an internal helper.
• Open/Closed — adding rm or mv does not change existing operations.
• Information Expert — path resolution lives on FileSystem because it knows about the cwd.

---

Implementation

Core Logic: resolve(path)

Bad approach: combine cwd and path into one string, then parse once.

• Bug-prone with ..s and /s in odd spots.

Good approach: start from root (if absolute) or cwd (if relative), walk each segment. . is a no-op, .. pops if above root, otherwise descend.

Great approach: same, but return the whole stack (not just the leaf) so pwd and cd share one function.

Verification

cwd = [root]
mkdir("/a/b/c")
  resolve-or-create walks a, b, c; each missing created as dir.
pwd()
  -> "/"

cd("/a/b")
  resolve returns [root, a, b]; cwd = that.
pwd()
  -> "/a/b"

touch("file.txt")
  dir = cwd leaf = b. b.children has no "file.txt". Add as file.
write("file.txt", "hello")
  resolve(file.txt) from cwd = [root, a, b, file.txt]. Set content.
read("/a/b/file.txt")
  -> "hello"

ls()
  cwd leaf = b. children keys = ["c", "file.txt"]. Sorted.

ls("*.txt")
  regex = ^.*\.txt$. Filters to ["file.txt"].

cd("..")
  pop cwd. cwd = [root, a].
pwd()
  -> "/a"

Thread Safety

• One ReentrantReadWriteLock on the filesystem. ls, read, pwd, resolve take the read lock. mkdir, cd (mutates cwd), touch, write take the write lock.
• For production, lock per subtree would scale, but a single lock is fine for an interview.
• cwd is intrinsically single-user — each user's filesystem instance has its own cwd. If you model multi-user, move cwd out of the filesystem.

Complete Code Implementation

Java

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

class Node {
    public final String name;
    public final boolean isDir;
    public final Map<String, Node> children = new TreeMap<>();
    public String content = "";

    public Node(String name, boolean isDir) { this.name = name; this.isDir = isDir; }
}

public class FileSystem {
    private final Node root = new Node("/", true);
    private final List<Node> cwd = new ArrayList<>(List.of(root));
    private final ReentrantReadWriteLock rw = new ReentrantReadWriteLock();

    private List<Node> resolve(String path) {
        String[] parts;
        List<Node> stack = new ArrayList<>();
        if (path.startsWith("/")) {
            stack.add(root);
            parts = Arrays.stream(path.split("/")).filter(s -> !s.isEmpty()).toArray(String[]::new);
        } else {
            stack.addAll(cwd);
            parts = Arrays.stream(path.split("/")).filter(s -> !s.isEmpty()).toArray(String[]::new);
        }
        for (String part : parts) {
            if (part.equals(".")) continue;
            if (part.equals("..")) { if (stack.size() > 1) stack.remove(stack.size() - 1); continue; }
            Node parent = stack.get(stack.size() - 1);
            Node next = parent.children.get(part);
            if (next == null) throw new RuntimeException("NO_SUCH_PATH:" + path);
            stack.add(next);
        }
        return stack;
    }

    public String pwd() {
        rw.readLock().lock();
        try {
            if (cwd.size() == 1) return "/";
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i < cwd.size(); i++) sb.append("/").append(cwd.get(i).name);
            return sb.toString();
        } finally { rw.readLock().unlock(); }
    }

    public void cd(String path) {
        rw.writeLock().lock();
        try {
            List<Node> stack = resolve(path);
            if (!stack.get(stack.size() - 1).isDir) throw new RuntimeException("NOT_A_DIR");
            cwd.clear(); cwd.addAll(stack);
        } finally { rw.writeLock().unlock(); }
    }

    public void mkdir(String path) {
        rw.writeLock().lock();
        try {
            String[] parts = Arrays.stream(path.split("/")).filter(s -> !s.isEmpty()).toArray(String[]::new);
            Node node = path.startsWith("/") ? root : cwd.get(cwd.size() - 1);
            for (String p : parts) {
                Node child = node.children.get(p);
                if (child == null) { child = new Node(p, true); node.children.put(p, child); }
                if (!child.isDir) throw new RuntimeException("NAME_TAKEN_BY_FILE");
                node = child;
            }
        } finally { rw.writeLock().unlock(); }
    }

    public void touch(String path) {
        rw.writeLock().lock();
        try {
            int idx = path.lastIndexOf('/');
            String dirPath = idx <= 0 ? (idx == 0 ? "/" : ".") : path.substring(0, idx);
            String name = path.substring(idx + 1);
            List<Node> stack = resolve(dirPath);
            Node dir = stack.get(stack.size() - 1);
            if (!dir.isDir) throw new RuntimeException("NOT_A_DIR");
            if (!dir.children.containsKey(name)) dir.children.put(name, new Node(name, false));
        } finally { rw.writeLock().unlock(); }
    }

    public void write(String path, String content) {
        rw.writeLock().lock();
        try {
            Node n = leafOrCreate(path);
            if (n.isDir) throw new RuntimeException("IS_DIR");
            n.content = content;
        } finally { rw.writeLock().unlock(); }
    }

    private Node leafOrCreate(String path) {
        int idx = path.lastIndexOf('/');
        String dirPath = idx <= 0 ? (idx == 0 ? "/" : ".") : path.substring(0, idx);
        String name = path.substring(idx + 1);
        List<Node> stack = resolve(dirPath);
        Node dir = stack.get(stack.size() - 1);
        if (!dir.isDir) throw new RuntimeException("NOT_A_DIR");
        Node n = dir.children.get(name);
        if (n == null) { n = new Node(name, false); dir.children.put(name, n); }
        return n;
    }

    public String read(String path) {
        rw.readLock().lock();
        try {
            List<Node> stack = resolve(path);
            Node n = stack.get(stack.size() - 1);
            if (n.isDir) throw new RuntimeException("IS_DIR");
            return n.content;
        } finally { rw.readLock().unlock(); }
    }

    public List<String> ls(String pattern) {
        rw.readLock().lock();
        try {
            Node dir = cwd.get(cwd.size() - 1);
            if (!dir.isDir) return List.of(dir.name);
            String regex = "^" + pattern.replace("*", ".*") + "$";
            return dir.children.keySet().stream().filter(n -> n.matches(regex)).sorted().toList();
        } finally { rw.readLock().unlock(); }
    }
}

C++

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

class Node {
public:
    std::string name;
    bool isDir;
    std::map<std::string, std::shared_ptr<Node>> children;
    std::string content;
    Node(std::string n, bool d) : name(std::move(n)), isDir(d) {}
};

class FileSystem {
public:
    FileSystem() : root(std::make_shared<Node>("/", true)) { cwd.push_back(root); }

    std::string pwd() {
        std::shared_lock<std::shared_mutex> g(mu);
        if (cwd.size() == 1) return "/";
        std::string out;
        for (size_t i = 1; i < cwd.size(); i++) { out += "/"; out += cwd[i]->name; }
        return out;
    }

    void cd(const std::string& path) {
        std::unique_lock<std::shared_mutex> g(mu);
        auto stack = resolve(path);
        if (!stack.back()->isDir) throw std::runtime_error("NOT_A_DIR");
        cwd = stack;
    }

    void mkdir(const std::string& path) {
        std::unique_lock<std::shared_mutex> g(mu);
        auto parts = split(path);
        auto node = path.starts_with("/") ? root : cwd.back();
        for (auto& p : parts) {
            auto it = node->children.find(p);
            if (it == node->children.end()) {
                auto child = std::make_shared<Node>(p, true);
                node->children[p] = child; node = child;
            } else {
                if (!it->second->isDir) throw std::runtime_error("NAME_TAKEN_BY_FILE");
                node = it->second;
            }
        }
    }

    void touch(const std::string& path) {
        std::unique_lock<std::shared_mutex> g(mu);
        auto [dirPath, name] = splitParent(path);
        auto stack = resolve(dirPath);
        auto dir = stack.back();
        if (!dir->isDir) throw std::runtime_error("NOT_A_DIR");
        if (!dir->children.count(name))
            dir->children[name] = std::make_shared<Node>(name, false);
    }

    void write(const std::string& path, const std::string& content) {
        std::unique_lock<std::shared_mutex> g(mu);
        auto n = leafOrCreate(path);
        if (n->isDir) throw std::runtime_error("IS_DIR");
        n->content = content;
    }

    std::string read(const std::string& path) {
        std::shared_lock<std::shared_mutex> g(mu);
        auto stack = resolve(path);
        auto n = stack.back();
        if (n->isDir) throw std::runtime_error("IS_DIR");
        return n->content;
    }

    std::vector<std::string> ls(const std::string& pattern = "*") {
        std::shared_lock<std::shared_mutex> g(mu);
        auto dir = cwd.back();
        if (!dir->isDir) return {dir->name};
        std::string regexStr;
        for (char c : pattern) if (c == '*') regexStr += ".*"; else regexStr += c;
        std::regex re("^" + regexStr + "$");
        std::vector<std::string> out;
        for (auto& [k, _] : dir->children) if (std::regex_match(k, re)) out.push_back(k);
        return out;
    }

private:
    std::shared_ptr<Node> root;
    std::vector<std::shared_ptr<Node>> cwd;
    std::shared_mutex mu;

    std::vector<std::string> split(const std::string& path) {
        std::vector<std::string> parts; std::string cur;
        for (char c : path) {
            if (c == '/') { if (!cur.empty()) parts.push_back(cur); cur.clear(); }
            else cur += c;
        }
        if (!cur.empty()) parts.push_back(cur);
        return parts;
    }

    std::pair<std::string, std::string> splitParent(const std::string& path) {
        auto idx = path.find_last_of('/');
        if (idx == std::string::npos) return {".", path};
        return {idx == 0 ? "/" : path.substr(0, idx), path.substr(idx + 1)};
    }

    std::vector<std::shared_ptr<Node>> resolve(const std::string& path) {
        std::vector<std::shared_ptr<Node>> stack;
        if (path.starts_with("/")) stack.push_back(root);
        else stack = cwd;
        for (auto& part : split(path)) {
            if (part == ".") continue;
            if (part == "..") { if (stack.size() > 1) stack.pop_back(); continue; }
            auto it = stack.back()->children.find(part);
            if (it == stack.back()->children.end()) throw std::runtime_error("NO_SUCH_PATH:" + path);
            stack.push_back(it->second);
        }
        return stack;
    }

    std::shared_ptr<Node> leafOrCreate(const std::string& path) {
        auto [dirPath, name] = splitParent(path);
        auto stack = resolve(dirPath);
        auto dir = stack.back();
        if (!dir->isDir) throw std::runtime_error("NOT_A_DIR");
        auto it = dir->children.find(name);
        if (it == dir->children.end()) {
            auto n = std::make_shared<Node>(name, false);
            dir->children[name] = n; return n;
        }
        return it->second;
    }
};

TypeScript

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

class FileSystem {
  private root = new Node("/", true);
  private cwd: Node[] = [this.root];

  private resolve(path: string): Node[] {
    const parts = path.startsWith("/")
      ? path.split("/").filter(Boolean)
      : [...this.cwd.slice(1).map((n) => n.name), ...path.split("/").filter(Boolean)];
    const stack: Node[] = [this.root];
    for (const part of parts) {
      if (part === ".") continue;
      if (part === "..") { if (stack.length > 1) stack.pop(); continue; }
      const parent = stack[stack.length - 1];
      const next = parent.children.get(part);
      if (!next) throw new Error(`NO_SUCH_PATH:${path}`);
      stack.push(next);
    }
    return stack;
  }

  pwd(): string {
    return "/" + this.cwd.slice(1).map((n) => n.name).join("/");
  }

  cd(path: string): void {
    const stack = this.resolve(path);
    if (!stack[stack.length - 1].isDir) throw new Error("NOT_A_DIR");
    this.cwd = stack;
  }

  mkdir(path: string): void {
    const parts = path.split("/").filter(Boolean);
    let node = path.startsWith("/") ? this.root : this.cwd[this.cwd.length - 1];
    for (const p of parts) {
      if (!node.children.has(p)) node.children.set(p, new Node(p, true));
      node = node.children.get(p)!;
      if (!node.isDir) throw new Error("NAME_TAKEN_BY_FILE");
    }
  }

  touch(path: string): void {
    const idx = path.lastIndexOf("/");
    const dirPath = idx === 0 ? "/" : idx < 0 ? "." : path.substring(0, idx);
    const fileName = path.substring(idx + 1);
    const dir = this.resolve(dirPath).pop()!;
    if (!dir.children.has(fileName)) dir.children.set(fileName, new Node(fileName, false));
  }

  write(path: string, content: string): void {
    const node = this.resolve(path).pop()!;
    if (node.isDir) throw new Error("IS_DIR");
    node.content = content;
  }

  read(path: string): string {
    const node = this.resolve(path).pop()!;
    if (node.isDir) throw new Error("IS_DIR");
    return node.content;
  }

  ls(pattern = "*"): string[] {
    const dir = this.cwd[this.cwd.length - 1];
    const regex = new RegExp("^" + pattern.replace(/\*/g, ".*") + "$");
    return [...dir.children.keys()].filter((n) => regex.test(n)).sort();
  }
}

---

Extensibility

1. "Permissions"

Add owner, mode to Node. Check mode bits on each operation via a PermissionChecker interface. Keeps the check pluggable.

2. "Symlinks"

Add linkTo?: Node on Node. In resolve, if the node is a symlink, dereference (with a cycle-detection counter). The tree now has a cycle-check budget.

3. "Persistence and recovery"

Add a write-ahead log: each mkdir, touch, write appends a record. On boot, replay records to rebuild the tree. Snapshots every N records compact the log.

---

What is Expected at Each Level

Level	Expectations
Mid	Flat Map<path, content> lookup, no path traversal.
Senior / SMTS	Proper tree, relative path resolution with ./.., wildcard ls, single-lock thread safety.
Staff	Journalling, snapshotting, copy-on-write, mount points, quotas.