⏱️ 17 min read

Designing a File System

Difficulty: Intermediate Patterns: Composite, Template Method, Iterator Asked at: Uber, Amazon, Google, Microsoft, Flipkart

Functional Requirements

mkdir — create a directory at a given path, creating intermediate directories if needed (like mkdir -p)
ls — list contents of a directory, sorted alphabetically
touch — create a file at a given path
rm — remove a file or empty directory
pwd / resolve — resolve an absolute path to the corresponding node in the tree

Non-Functional Requirements

Extensibility — adding new node types (symlinks, devices) should be minimal code change
Thread-safety — concurrent mkdir/ls calls shouldn’t corrupt the tree
O(d) path resolution — where d is depth of the path (same as real file systems)

Core Entities

Entity	Description
`FileSystemNode`	Abstract base — name, parent reference, path computation
`Directory`	A node that can contain children (other nodes)
`File`	A leaf node with optional content
`FileSystem`	The API layer — owns the root directory, exposes mkdir/ls/touch/rm

Class Diagram

classDiagram
    class FileSystemNode {
        <<abstract>>
        #String name
        #Directory parent
        +getName() String
        +getPath() String
        +isDirectory() boolean*
    }

    class File {
        -String content
        +isDirectory() boolean
        +getContent() String
        +setContent(String)
    }

    class Directory {
        -TreeMap~String FileSystemNode~ children
        +addChild(FileSystemNode)
        +getChild(String) FileSystemNode
        +hasChild(String) boolean
        +removeChild(String)
        +listChildren() List~String~
        +isDirectory() boolean
    }

    class FileSystem {
        -Directory root
        -ReentrantReadWriteLock lock
        +mkdir(String path)
        +ls(String path) List~String~
        +touch(String path)
        +rm(String path)
        +find(String path String pattern) List~String~
        -resolve(String path) FileSystemNode
    }

    FileSystemNode <|-- File
    FileSystemNode <|-- Directory
    Directory o-- FileSystemNode : children
    FileSystem --> Directory : root

Design Patterns

Pattern	Where	Why
Composite	`FileSystemNode` → `Directory` (composite) / `File` (leaf)	A directory IS-A node that CONTAINS nodes. Uniform treatment of files and directories. This is the textbook use case for Composite.
Template Method	`getPath()` in base class calls `parent.getPath()` recursively	Path computation is the same algorithm for every node type — only `isDirectory()` varies.
Iterator (extension)	`find()` does DFS over the composite tree	Traversal logic is decoupled from node structure.

Data Structures

Component	Structure	Why
Children of a directory	`TreeMap<String, FileSystemNode>`	O(log n) insert, automatically sorted keys → `ls` returns alphabetical order for free
Path resolution	Split path by `/`, walk tree	O(d) where d = depth, matches real FS behavior
Root reference	Single `Directory` object	Entry point for all operations

How It All Fits Together

mkdir(“/home/user/documents”):

Split path into ["home", "user", "documents"]
Start at root. Check if home exists — if not, create Directory(“home”, root), add as child
Move into home. Check if user exists — if not, create and add
Move into user. Check if documents exists — if not, create and add
Each step: O(log n) lookup in TreeMap. Total: O(d × log n) where d=3, n=children per level

ls(“/home/user”):

Resolve path → get the user Directory node
Call listChildren() → returns TreeMap keys (already sorted)
Return ["documents"]

Key design decision: mkdir is idempotent — calling it on an existing directory is a no-op. But calling it where a file exists at that path is an error.

Complete Code

FileSystemNode.java

The abstract base class. Every node knows its name and parent. getPath() walks up the tree recursively — no need to store full paths (which would break on renames). isDirectory() is the single abstract method that subclasses implement.

package filesystem.model;

public abstract class FileSystemNode {
    protected String name;
    protected Directory parent;

    public FileSystemNode(String name, Directory parent) {
        this.name = name;
        this.parent = parent;
    }

    public String getName() {
        return name;
    }

    public Directory getParent() {
        return parent;
    }

    public String getPath() {
        if (parent == null) return "/"; // root
        String parentPath = parent.getPath();
        return parentPath.equals("/") ? "/" + name : parentPath + "/" + name;
    }

    public abstract boolean isDirectory();
}

from abc import ABC, abstractmethod


class FileSystemNode(ABC):
    def __init__(self, name: str, parent: "Directory | None"):
        self.name = name
        self.parent = parent

    def get_path(self) -> str:
        if self.parent is None:
            return "/"
        parent_path = self.parent.get_path()
        return f"{parent_path}{self.name}" if parent_path == "/" else f"{parent_path}/{self.name}"

    @abstractmethod
    def is_directory(self) -> bool:
        pass

#pragma once
#include <string>

class Directory; // forward declaration

class FileSystemNode {
protected:
    std::string name;
    Directory* parent;

public:
    FileSystemNode(const std::string& name, Directory* parent)
        : name(name), parent(parent) {}

    virtual ~FileSystemNode() = default;

    const std::string& getName() const { return name; }
    Directory* getParent() const { return parent; }
    std::string getPath() const;

    virtual bool isDirectory() const = 0;
};

class FileSystemNode {
    constructor(name, parent) {
        if (new.target === FileSystemNode) {
            throw new Error('FileSystemNode is abstract');
        }
        this.name = name;
        this.parent = parent;
    }

    getPath() {
        if (!this.parent) return '/';
        const parentPath = this.parent.getPath();
        return parentPath === '/' ? '/' + this.name : parentPath + '/' + this.name;
    }

    isDirectory() {
        throw new Error('Must implement isDirectory()');
    }
}

File.java

A leaf node. It holds optional content (for cat/write operations if extended later). It cannot have children — calling isDirectory() returns false, so path traversal stops here.

package filesystem.model;

public class File extends FileSystemNode {
    private String content;

    public File(String name, Directory parent) {
        super(name, parent);
        this.content = "";
    }

    @Override
    public boolean isDirectory() {
        return false;
    }

    public String getContent() {
        return content;
    }

    public void setContent(String content) {
        this.content = content;
    }
}

from filesystem.model.node import FileSystemNode


class File(FileSystemNode):
    def __init__(self, name: str, parent):
        super().__init__(name, parent)
        self.content = ""

    def is_directory(self) -> bool:
        return False

    def get_content(self) -> str:
        return self.content

    def set_content(self, content: str):
        self.content = content

#pragma once
#include "FileSystemNode.hpp"
#include <string>

class File : public FileSystemNode {
    std::string content;

public:
    File(const std::string& name, Directory* parent)
        : FileSystemNode(name, parent), content("") {}

    bool isDirectory() const override { return false; }

    const std::string& getContent() const { return content; }
    void setContent(const std::string& c) { content = c; }
};

class File extends FileSystemNode {
    constructor(name, parent) {
        super(name, parent);
        this.content = '';
    }

    isDirectory() {
        return false;
    }

    getContent() {
        return this.content;
    }

    setContent(content) {
        this.content = content;
    }
}

Directory.java

The composite node. Uses a TreeMap (Java) / sorted dict (Python) / std::map (C++) so children are always in alphabetical order — this makes ls trivial. The addChild, getChild, removeChild methods are the composite’s child-management interface.

package filesystem.model;

import java.util.*;

public class Directory extends FileSystemNode {
    private final TreeMap<String, FileSystemNode> children;

    public Directory(String name, Directory parent) {
        super(name, parent);
        this.children = new TreeMap<>();
    }

    @Override
    public boolean isDirectory() {
        return true;
    }

    public void addChild(FileSystemNode node) {
        children.put(node.getName(), node);
    }

    public FileSystemNode getChild(String name) {
        return children.get(name);
    }

    public boolean hasChild(String name) {
        return children.containsKey(name);
    }

    public void removeChild(String name) {
        children.remove(name);
    }

    public List<String> listChildren() {
        return new ArrayList<>(children.keySet());
    }

    public boolean isEmpty() {
        return children.isEmpty();
    }

    public Collection<FileSystemNode> getChildren() {
        return children.values();
    }
}

from sortedcontainers import SortedDict
from filesystem.model.node import FileSystemNode


class Directory(FileSystemNode):
    def __init__(self, name: str, parent):
        super().__init__(name, parent)
        self.children: SortedDict = SortedDict()

    def is_directory(self) -> bool:
        return True

    def add_child(self, node: FileSystemNode):
        self.children[node.name] = node

    def get_child(self, name: str):
        return self.children.get(name)

    def has_child(self, name: str) -> bool:
        return name in self.children

    def remove_child(self, name: str):
        del self.children[name]

    def list_children(self) -> list[str]:
        return list(self.children.keys())

    def is_empty(self) -> bool:
        return len(self.children) == 0

#pragma once
#include "FileSystemNode.hpp"
#include <map>
#include <string>
#include <vector>
#include <memory>

class Directory : public FileSystemNode {
    std::map<std::string, std::unique_ptr<FileSystemNode>> children;

public:
    Directory(const std::string& name, Directory* parent)
        : FileSystemNode(name, parent) {}

    bool isDirectory() const override { return true; }

    void addChild(std::unique_ptr<FileSystemNode> node) {
        children[node->getName()] = std::move(node);
    }

    FileSystemNode* getChild(const std::string& name) const {
        auto it = children.find(name);
        return it != children.end() ? it->second.get() : nullptr;
    }

    bool hasChild(const std::string& name) const {
        return children.count(name) > 0;
    }

    void removeChild(const std::string& name) {
        children.erase(name);
    }

    std::vector<std::string> listChildren() const {
        std::vector<std::string> result;
        for (const auto& [name, _] : children) {
            result.push_back(name);
        }
        return result;
    }

    bool isEmpty() const { return children.empty(); }
};

class Directory extends FileSystemNode {
    constructor(name, parent) {
        super(name, parent);
        this.children = new Map(); // JS Map preserves insertion order; we sort on ls
    }

    isDirectory() {
        return true;
    }

    addChild(node) {
        this.children.set(node.name, node);
    }

    getChild(name) {
        return this.children.get(name) || null;
    }

    hasChild(name) {
        return this.children.has(name);
    }

    removeChild(name) {
        this.children.delete(name);
    }

    listChildren() {
        return [...this.children.keys()].sort();
    }

    isEmpty() {
        return this.children.size === 0;
    }
}

FileSystem.java

The main API. This is what the interviewer interacts with. It owns the root directory, handles path parsing, and delegates to node methods. Note the ReentrantReadWriteLock — reads (ls) can be concurrent, writes (mkdir/touch/rm) are exclusive.

package filesystem;

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

public class FileSystem {
    private final Directory root;
    private final ReadWriteLock lock;

    public FileSystem() {
        this.root = new Directory("/", null);
        this.lock = new ReentrantReadWriteLock();
    }

    // ─── Path resolution ───
    private FileSystemNode resolve(String path) {
        if (path.equals("/")) return root;
        String[] parts = path.split("/");
        FileSystemNode current = root;
        for (int i = 1; i < parts.length; i++) {
            if (parts[i].isEmpty()) continue;
            if (!current.isDirectory()) return null;
            current = ((Directory) current).getChild(parts[i]);
            if (current == null) return null;
        }
        return current;
    }

    // ─── mkdir -p ───
    public void mkdir(String path) {
        lock.writeLock().lock();
        try {
            if (path.equals("/")) return;
            String[] parts = path.split("/");
            Directory current = root;
            for (int i = 1; i < parts.length; i++) {
                if (parts[i].isEmpty()) continue;
                if (!current.hasChild(parts[i])) {
                    current.addChild(new Directory(parts[i], current));
                } else {
                    FileSystemNode existing = current.getChild(parts[i]);
                    if (!existing.isDirectory()) {
                        throw new IllegalArgumentException(
                            parts[i] + " exists and is not a directory");
                    }
                }
                current = (Directory) current.getChild(parts[i]);
            }
        } finally {
            lock.writeLock().unlock();
        }
    }

    // ─── ls ───
    public List<String> ls(String path) {
        lock.readLock().lock();
        try {
            FileSystemNode node = resolve(path);
            if (node == null) {
                throw new IllegalArgumentException("Path not found: " + path);
            }
            if (!node.isDirectory()) {
                return Collections.singletonList(node.getName());
            }
            return ((Directory) node).listChildren();
        } finally {
            lock.readLock().unlock();
        }
    }

    // ─── touch ───
    public void touch(String path) {
        lock.writeLock().lock();
        try {
            int lastSlash = path.lastIndexOf('/');
            String parentPath = lastSlash == 0 ? "/" : path.substring(0, lastSlash);
            String fileName = path.substring(lastSlash + 1);

            FileSystemNode parentNode = resolve(parentPath);
            if (parentNode == null || !parentNode.isDirectory()) {
                throw new IllegalArgumentException("Parent directory not found: " + parentPath);
            }
            Directory parent = (Directory) parentNode;
            if (!parent.hasChild(fileName)) {
                parent.addChild(new File(fileName, parent));
            }
        } finally {
            lock.writeLock().unlock();
        }
    }

    // ─── rm ───
    public void rm(String path) {
        lock.writeLock().lock();
        try {
            if (path.equals("/")) {
                throw new IllegalArgumentException("Cannot remove root directory");
            }
            FileSystemNode node = resolve(path);
            if (node == null) {
                throw new IllegalArgumentException("Path not found: " + path);
            }
            if (node.isDirectory() && !((Directory) node).isEmpty()) {
                throw new IllegalArgumentException("Directory not empty: " + path);
            }
            node.getParent().removeChild(node.getName());
        } finally {
            lock.writeLock().unlock();
        }
    }

    // ─── find (bonus: recursive search) ───
    public List<String> find(String path, String pattern) {
        lock.readLock().lock();
        try {
            FileSystemNode node = resolve(path);
            if (node == null || !node.isDirectory()) return Collections.emptyList();
            List<String> results = new ArrayList<>();
            findHelper((Directory) node, pattern, results);
            return results;
        } finally {
            lock.readLock().unlock();
        }
    }

    private void findHelper(Directory dir, String pattern, List<String> results) {
        for (FileSystemNode child : dir.getChildren()) {
            if (child.getName().contains(pattern)) {
                results.add(child.getPath());
            }
            if (child.isDirectory()) {
                findHelper((Directory) child, pattern, results);
            }
        }
    }
}

import threading
from filesystem.model.directory import Directory
from filesystem.model.file import File


class FileSystem:
    def __init__(self):
        self.root = Directory("/", None)
        self._lock = threading.RWLock() if hasattr(threading, 'RWLock') else threading.Lock()

    def _resolve(self, path: str):
        if path == "/":
            return self.root
        parts = path.strip("/").split("/")
        current = self.root
        for part in parts:
            if not part:
                continue
            if not current.is_directory():
                return None
            current = current.get_child(part)
            if current is None:
                return None
        return current

    def mkdir(self, path: str):
        if path == "/":
            return
        parts = path.strip("/").split("/")
        current = self.root
        for part in parts:
            if not part:
                continue
            if not current.has_child(part):
                current.add_child(Directory(part, current))
            else:
                existing = current.get_child(part)
                if not existing.is_directory():
                    raise ValueError(f"{part} exists and is not a directory")
            current = current.get_child(part)

    def ls(self, path: str) -> list[str]:
        node = self._resolve(path)
        if node is None:
            raise ValueError(f"Path not found: {path}")
        if not node.is_directory():
            return [node.name]
        return node.list_children()

    def touch(self, path: str):
        last_slash = path.rfind("/")
        parent_path = "/" if last_slash == 0 else path[:last_slash]
        file_name = path[last_slash + 1:]
        parent = self._resolve(parent_path)
        if parent is None or not parent.is_directory():
            raise ValueError(f"Parent directory not found: {parent_path}")
        if not parent.has_child(file_name):
            parent.add_child(File(file_name, parent))

    def rm(self, path: str):
        if path == "/":
            raise ValueError("Cannot remove root directory")
        node = self._resolve(path)
        if node is None:
            raise ValueError(f"Path not found: {path}")
        if node.is_directory() and not node.is_empty():
            raise ValueError(f"Directory not empty: {path}")
        node.parent.remove_child(node.name)

    def find(self, path: str, pattern: str) -> list[str]:
        node = self._resolve(path)
        if node is None or not node.is_directory():
            return []
        results = []
        self._find_helper(node, pattern, results)
        return results

    def _find_helper(self, directory, pattern: str, results: list):
        for child in directory.children.values():
            if pattern in child.name:
                results.append(child.get_path())
            if child.is_directory():
                self._find_helper(child, pattern, results)

#pragma once
#include "model/Directory.hpp"
#include "model/File.hpp"
#include <string>
#include <vector>
#include <sstream>
#include <shared_mutex>
#include <stdexcept>

class FileSystem {
    std::unique_ptr<Directory> root;
    mutable std::shared_mutex mtx;

    FileSystemNode* resolve(const std::string& path) const {
        if (path == "/") return root.get();
        std::istringstream ss(path);
        std::string part;
        FileSystemNode* current = root.get();
        std::getline(ss, part, '/'); // skip leading empty
        while (std::getline(ss, part, '/')) {
            if (part.empty()) continue;
            if (!current->isDirectory()) return nullptr;
            current = static_cast<Directory*>(current)->getChild(part);
            if (!current) return nullptr;
        }
        return current;
    }

public:
    FileSystem() : root(std::make_unique<Directory>("/", nullptr)) {}

    void mkdir(const std::string& path) {
        std::unique_lock lock(mtx);
        if (path == "/") return;
        std::istringstream ss(path);
        std::string part;
        Directory* current = root.get();
        std::getline(ss, part, '/');
        while (std::getline(ss, part, '/')) {
            if (part.empty()) continue;
            if (!current->hasChild(part)) {
                current->addChild(std::make_unique<Directory>(part, current));
            } else if (!current->getChild(part)->isDirectory()) {
                throw std::runtime_error(part + " exists and is not a directory");
            }
            current = static_cast<Directory*>(current->getChild(part));
        }
    }

    std::vector<std::string> ls(const std::string& path) const {
        std::shared_lock lock(mtx);
        auto* node = resolve(path);
        if (!node) throw std::runtime_error("Path not found: " + path);
        if (!node->isDirectory()) return {node->getName()};
        return static_cast<const Directory*>(node)->listChildren();
    }

    void touch(const std::string& path) {
        std::unique_lock lock(mtx);
        auto lastSlash = path.rfind('/');
        std::string parentPath = lastSlash == 0 ? "/" : path.substr(0, lastSlash);
        std::string fileName = path.substr(lastSlash + 1);
        auto* parent = resolve(parentPath);
        if (!parent || !parent->isDirectory())
            throw std::runtime_error("Parent not found");
        auto* dir = static_cast<Directory*>(parent);
        if (!dir->hasChild(fileName))
            dir->addChild(std::make_unique<File>(fileName, dir));
    }

    void rm(const std::string& path) {
        std::unique_lock lock(mtx);
        if (path == "/") throw std::runtime_error("Cannot remove root");
        auto* node = resolve(path);
        if (!node) throw std::runtime_error("Path not found");
        if (node->isDirectory() && !static_cast<Directory*>(node)->isEmpty())
            throw std::runtime_error("Directory not empty");
        static_cast<Directory*>(node->getParent())->removeChild(node->getName());
    }
};

class FileSystem {
    constructor() {
        this.root = new Directory('/', null);
    }

    _resolve(path) {
        if (path === '/') return this.root;
        const parts = path.split('/').filter(p => p.length > 0);
        let current = this.root;
        for (const part of parts) {
            if (!current.isDirectory()) return null;
            current = current.getChild(part);
            if (!current) return null;
        }
        return current;
    }

    mkdir(path) {
        if (path === '/') return;
        const parts = path.split('/').filter(p => p.length > 0);
        let current = this.root;
        for (const part of parts) {
            if (!current.hasChild(part)) {
                current.addChild(new Directory(part, current));
            } else {
                const existing = current.getChild(part);
                if (!existing.isDirectory()) {
                    throw new Error(`${part} exists and is not a directory`);
                }
            }
            current = current.getChild(part);
        }
    }

    ls(path) {
        const node = this._resolve(path);
        if (!node) throw new Error(`Path not found: ${path}`);
        if (!node.isDirectory()) return [node.name];
        return node.listChildren();
    }

    touch(path) {
        const lastSlash = path.lastIndexOf('/');
        const parentPath = lastSlash === 0 ? '/' : path.substring(0, lastSlash);
        const fileName = path.substring(lastSlash + 1);
        const parent = this._resolve(parentPath);
        if (!parent || !parent.isDirectory()) {
            throw new Error(`Parent directory not found: ${parentPath}`);
        }
        if (!parent.hasChild(fileName)) {
            parent.addChild(new File(fileName, parent));
        }
    }

    rm(path) {
        if (path === '/') throw new Error('Cannot remove root directory');
        const node = this._resolve(path);
        if (!node) throw new Error(`Path not found: ${path}`);
        if (node.isDirectory() && !node.isEmpty()) {
            throw new Error(`Directory not empty: ${path}`);
        }
        node.parent.removeChild(node.name);
    }

    find(path, pattern) {
        const node = this._resolve(path);
        if (!node || !node.isDirectory()) return [];
        const results = [];
        this._findHelper(node, pattern, results);
        return results;
    }

    _findHelper(dir, pattern, results) {
        for (const [name, child] of dir.children) {
            if (name.includes(pattern)) results.push(child.getPath());
            if (child.isDirectory()) this._findHelper(child, pattern, results);
        }
    }
}

// ─── Demo ───
const fs = new FileSystem();
fs.mkdir('/home/user/documents');
fs.mkdir('/home/user/downloads');
fs.mkdir('/etc/config');
fs.touch('/home/user/documents/resume.txt');
fs.touch('/home/user/documents/notes.txt');

console.log('ls /:', fs.ls('/'));
console.log('ls /home/user:', fs.ls('/home/user'));
console.log('ls /home/user/documents:', fs.ls('/home/user/documents'));
console.log('find .txt:', fs.find('/', '.txt'));
fs.rm('/home/user/documents/notes.txt');
console.log('after rm:', fs.ls('/home/user/documents'));

Extensibility Analysis

What if the interviewer asks “How would you add…?”

Extension	How	Code Impact
Symlinks	New `SymLink extends FileSystemNode` with a `target: FileSystemNode` reference. `resolve()` follows symlinks transparently.	Add one class + modify `resolve()` with cycle detection
Permissions (chmod)	Add `permissions` field to `FileSystemNode`. Check in `resolve()` before returning.	One field + guard in resolve
File content / cat	Already supported — `File.setContent()` / `getContent()`	Zero changes
cd / relative paths	Add `currentDir` field to `FileSystem`. Resolve relative paths by prepending `currentDir.getPath()`.	Small addition to `resolve()`
rm -rf (recursive delete)	Add `rmRecursive()` that does DFS post-order deletion.	One new method
mv / rename	Remove from old parent, add to new parent, update `parent` reference.	One new method
Disk quota	Add `size` to File, aggregate up the tree. `addChild()` checks quota.	Observer pattern on size changes

Interview Tips

Start with the class diagram — draw FileSystemNode, Directory, File on the whiteboard first. Say “Composite pattern” explicitly.
Implement mkdir + ls first — these are the core ask. Get them working before adding touch/rm.
Use TreeMap — interviewers love when you justify sorted output without a separate sort step.
Mention thread-safety — even if you don’t fully implement it, say “I’d use a ReadWriteLock here” and the interviewer knows you’re thinking about concurrency.
Offer extensions proactively — after coding mkdir/ls, say “Want me to add rm and find, or discuss symlinks?”

Scale this design past a single process and these are the concepts it runs into:

Object Storage → — a real blob store has no directories at all; it flattens this tree into a flat key namespace with prefixes
Database Indexing → — O(d) path resolution and sorted directory listings are the same prefix-scan problem a B-tree index solves
Consistency Models → — concurrent mkdir and rm on the same path need a defined ordering, not just a lock
Merkle Trees → — hashing each node up the tree is how real systems detect which subtrees changed without walking everything

Designing a File System

Functional Requirements

Non-Functional Requirements

Core Entities

Class Diagram

Design Patterns

Data Structures

How It All Fits Together

Complete Code

FileSystemNode.java

File.java

Directory.java

FileSystem.java

Extensibility Analysis

Interview Tips

Discussion

Install SystemCraft

Designing a File System

Functional Requirements

Non-Functional Requirements

Core Entities

Class Diagram

Design Patterns

Data Structures

How It All Fits Together

Complete Code

FileSystemNode.java

File.java

Directory.java

FileSystem.java

Extensibility Analysis

Interview Tips

Related Concepts

Discussion

Shape what we build next

Install SystemCraft

Unlock AI Features