Design an In-Memory File System

Problem Statement

Design an in-memory Unix-like file system (similar to an in-memory virtual file system). The file system should support representing files and directories recursively, navigating using absolute and relative paths, listing directory contents, creating directories, writing/reading file data, and deleting nodes.

Asked In Companies

Google Microsoft Apple

---

Functional Requirements

• Represent directory tree structures cleanly using uniform abstractions (Composite Pattern).
• Support creating files: createFile(path, content).
• Support creating folders: mkdir(path), creating intermediate paths if necessary.
• Read file data: cat(path).
• List folder contents: ls(path), sorting children alphabetically.
• Delete nodes: rm(path).
• Resolve target nodes using absolute paths (starting with /) and relative paths containing .. (parent directory traversal).

---

Objects Required

• Node (Abstract base class representing items in the file system)
• FileNode (Leaf node representing physical files storing strings)
• DirectoryNode (Composite node containing mapped lists of children)
• FileSystem (Main coordinator controlling directory trees and resolving paths)

---

Node Base Class

We apply the **Composite Design Pattern** to model directories and files uniformly. The Node class provides shared metadata and holds parent links to support relative path backtracking.

public abstract class Node {
    protected String name;
    protected DirectoryNode parent;
    protected final boolean isDir;

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

    public String getName() { return name; }
    public DirectoryNode getParent() { return parent; }
    public boolean isDir() { return isDir; }

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

The constructor sets basic identifier properties. The getAbsolutePath() method traverses upward using parent links to recursively compile the absolute location path of the node.

---

FileNode & DirectoryNode Classes

Here, we implement our leaf and composite variants. A FileNode contains file data, while a DirectoryNode tracks child nodes.

public class FileNode extends Node {
    private String content;

    public FileNode(String name, DirectoryNode parent, String content) {
        super(name, parent, false);
        this.content = content;
    }

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

The constructor calls the base class and registers initial text contents. Getter and setter methods expose or update file data.

import java.util.HashMap;
import java.util.Map;

public class DirectoryNode extends Node {
    private final Map<String, Node> children;

    public DirectoryNode(String name, DirectoryNode parent) {
        super(name, parent, true);
        this.children = new HashMap<>();
    }

    public Map<String, Node> getChildren() {
        return children;
    }

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

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

The DirectoryNode maintains an internal hash map of child nodes keyed by name. addChild() and removeChild() handle updates to the child list.

---

FileSystem Class

The FileSystem class coordinates structural modifications and path resolution. It handles token tracking and maps traversal flows.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class FileSystem {
    private final DirectoryNode root;
    private DirectoryNode cwd;

    public FileSystem() {
        this.root = new DirectoryNode("", null);
        this.cwd = root;
    }

    public DirectoryNode getCwd() {
        return cwd;
    }

    public void changeDirectory(String path) {
        Node node = resolveNode(path);
        if (node == null) {
            throw new RuntimeException("Directory not found: " + path);
        }
        if (!node.isDir()) {
            throw new RuntimeException("Not a directory: " + path);
        }
        this.cwd = (DirectoryNode) node;
    }

    public Node resolveNode(String path) {
        if (path.isEmpty()) return cwd;
        
        DirectoryNode current = path.startsWith("/") ? root : cwd;
        String[] parts = path.split("/");

        for (String part : parts) {
            if (part.isEmpty() || part.equals(".")) continue;

            if (part.equals("..")) {
                if (current.getParent() != null) {
                    current = current.getParent();
                }
                continue;
            }

            Node child = current.getChildren().get(part);
            if (child == null) return null;

            if (child.isDir()) {
                current = (DirectoryNode) child;
            } else {
                // Return immediately if matching file leaf is resolved before parsing finishes
                return child;
            }
        }
        return current;
    }

    public void mkdir(String path) {
        DirectoryNode current = path.startsWith("/") ? root : cwd;
        String[] parts = path.split("/");

        for (String part : parts) {
            if (part.isEmpty() || part.equals(".") || part.equals("..")) continue;

            Node child = current.getChildren().get(part);
            if (child == null) {
                DirectoryNode newDir = new DirectoryNode(part, current);
                current.addChild(newDir);
                current = newDir;
            } else if (child.isDir()) {
                current = (DirectoryNode) child;
            } else {
                throw new RuntimeException("Conflict: A file named '" + part + "' already exists.");
            }
        }
    }

    public void createFile(String path, String content) {
        int lastSlashIdx = path.lastIndexOf('/');
        String dirPath = lastSlashIdx <= 0 ? "" : path.substring(0, lastSlashIdx);
        String fileName = lastSlashIdx == -1 ? path : path.substring(lastSlashIdx + 1);

        if (!dirPath.isEmpty()) {
            mkdir(dirPath);
        }

        Node dirNode = resolveNode(dirPath.isEmpty() ? "." : dirPath);
        if (dirNode == null || !dirNode.isDir()) {
            throw new RuntimeException("Invalid directory path: " + dirPath);
        }

        DirectoryNode parentDir = (DirectoryNode) dirNode;
        FileNode file = new FileNode(fileName, parentDir, content);
        parentDir.addChild(file);
    }

    public List<String> ls(String path) {
        Node node = resolveNode(path);
        if (node == null) {
            throw new RuntimeException("Path not found: " + path);
        }

        List<String> results = new ArrayList<>();
        if (node.isDir()) {
            DirectoryNode dir = (DirectoryNode) node;
            results.addAll(dir.getChildren().keySet());
            Collections.sort(results);
        } else {
            results.add(node.getName());
        }
        return results;
    }

    public String cat(String path) {
        Node node = resolveNode(path);
        if (node == null || node.isDir()) {
            throw new RuntimeException("Invalid file path: " + path);
        }
        return ((FileNode) node).getContent();
    }

    public void rm(String path) {
        Node node = resolveNode(path);
        if (node == null) {
            throw new RuntimeException("Path not found: " + path);
        }
        if (node == root) {
            throw new RuntimeException("Cannot delete root directory.");
        }

        DirectoryNode parent = node.getParent();
        parent.removeChild(node.getName());
    }
}

Here is an explanation of the core operations in the FileSystem class:

• The constructor sets the system root directory and points the current working directory (cwd) to it.
• resolveNode() traverses path arrays recursively. It switches context to root if paths start with a slash, skips duplicate dots, backtracks to parents on double-dot markers, and returns null if a path is invalid.
• mkdir() creates folders along the specified path sequentially, skipping existing directories.
• createFile() extracts target directories, compiles parent paths dynamically, and binds a new FileNode inside its parent directory.
• ls() lists child names in alphabetical order, while cat() returns file contents.
• rm() fetches parent links and unregisters child nodes. It blocks actions trying to delete the root directory.

---

Main Driver Class

This class tests our in-memory file system. It creates directories, writes files, displays catalog indexes, navigates using absolute/relative paths, and handles node deletions.

import java.util.List;

public class Main {
    public static void main(String[] args) {
        FileSystem fs = new FileSystem();

        System.out.println("--- Creating Directories ---");
        fs.mkdir("/usr/local/bin");
        fs.mkdir("documents/work"); // relative path
        
        System.out.println("Current Directory contents: " + fs.ls("."));
        System.out.println("Contents of /usr/local: " + fs.ls("/usr/local"));

        System.out.println("\n--- Creating Files ---");
        fs.createFile("/usr/local/bin/script.sh", "echo 'Hello World'");
        fs.createFile("documents/work/report.txt", "Project status is Green.");

        System.out.println("Reading /usr/local/bin/script.sh: " + fs.cat("/usr/local/bin/script.sh"));
        System.out.println("Reading documents/work/report.txt: " + fs.cat("documents/work/report.txt"));

        System.out.println("\n--- Navigating Directories (cd) ---");
        fs.changeDirectory("documents");
        System.out.println("Changed directory. Current Path: " + fs.getCwd().getAbsolutePath());
        System.out.println("Contents of current directory: " + fs.ls("."));

        System.out.println("\n--- Navigating Backwards (cd ../usr) ---");
        fs.changeDirectory("../usr");
        System.out.println("Changed directory. Current Path: " + fs.getCwd().getAbsolutePath());

        System.out.println("\n--- Deleting File (rm) ---");
        fs.rm("/usr/local/bin/script.sh");
        System.out.println("Deleted script.sh. Contents of /usr/local/bin: " + fs.ls("/usr/local/bin"));
    }
}

The main() driver initializes the file system, registers directories, writes file data, navigates using dot markers, and validates directory structure updates.

---

Class Diagram

---

Also See

• Most Commonly Asked Low Level Design Interview Questions
• Top 10 Low Level Design Interview Questions