Design an in-memory filesystem

01A tree you can mutate safely

02Requirements sketch

03FileSystemEntry, File, Folder, FileSystem

from __future__ import annotations
from abc import ABC, abstractmethod
from typing import Optional

class FileSystemEntry(ABC):
    def __init__(self, name: str):
        self.name = name
        self.parent: Optional[Folder] = None

    def get_path(self) -> str:
        if self.parent is None:
            return "/"
        parts = []
        cur: Optional[FileSystemEntry] = self
        while cur is not None and cur.parent is not None:
            parts.append(cur.name)
            cur = cur.parent
        return "/" + "/".join(reversed(parts))

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

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

    def is_directory(self) -> bool:
        return False

class Folder(FileSystemEntry):
    def __init__(self, name: str):
        super().__init__(name)
        self.children: dict[str, FileSystemEntry] = {}

    def is_directory(self) -> bool:
        return True

    def add_child(self, entry: FileSystemEntry) -> None:
        self.children[entry.name] = entry
        entry.parent = self

    def remove_child(self, name: str) -> Optional[FileSystemEntry]:
        entry = self.children.pop(name, None)
        if entry:
            entry.parent = None
        return entry

class FileSystem:
    def __init__(self):
        self.root = Folder("")
        self.root.parent = None

import java.util.*;

abstract class FileSystemEntry {
    String name;
    Folder parent; // nullable

    FileSystemEntry(String name) { this.name = name; }

    String getPath() {
        if (parent == null) return "/";
        List<String> parts = new ArrayList<>();
        FileSystemEntry cur = this;
        while (cur != null && cur.parent != null) {
            parts.add(cur.name);
            cur = cur.parent;
        }
        Collections.reverse(parts);
        return "/" + String.join("/", parts);
    }

    abstract boolean isDirectory();
}

class File extends FileSystemEntry {
    String content;

    File(String name, String content) {
        super(name);
        this.content = content == null ? "" : content;
    }

    boolean isDirectory() { return false; }
}

class Folder extends FileSystemEntry {
    Map<String, FileSystemEntry> children = new HashMap<>();

    Folder(String name) { super(name); }

    boolean isDirectory() { return true; }

    void addChild(FileSystemEntry entry) {
        children.put(entry.name, entry);
        entry.parent = this;
    }

    FileSystemEntry removeChild(String name) {
        FileSystemEntry entry = children.remove(name);
        if (entry != null) entry.parent = null;
        return entry;
    }
}

class FileSystem {
    Folder root = new Folder("");

    FileSystem() { root.parent = null; }
}

04Path helpers and mutating APIs

def extract_name(path: str) -> str:
    parts = [p for p in path.split("/") if p]
    if not parts:
        raise ValueError("invalid path")
    return parts[-1]

def resolve_path(self, path: str) -> FileSystemEntry:
    if path == "/":
        return self.root
    cur: FileSystemEntry = self.root
    for part in [p for p in path.split("/") if p]:
        if not isinstance(cur, Folder) or part not in cur.children:
            raise FileNotFoundError(path)
        cur = cur.children[part]
    return cur

def resolve_parent(self, path: str) -> Folder:
    if path == "/":
        raise ValueError("root has no parent")
    parts = [p for p in path.split("/") if p]
    parent_path = "/" + "/".join(parts[:-1]) if len(parts) > 1 else "/"
    parent = self.resolve_path(parent_path)
    if not isinstance(parent, Folder):
        raise NotADirectoryError(parent_path)
    return parent

def create_file(self, path: str, content: str = "") -> File:
    if path == "/":
        raise ValueError("cannot create file at root")
    parent = self.resolve_parent(path)
    name = extract_name(path)
    if name in parent.children:
        raise FileExistsError(name)
    f = File(name, content)
    parent.add_child(f)
    return f

def move(self, src_path: str, dest_folder_path: str) -> None:
    if src_path == "/":
        raise ValueError("cannot move root")
    src_parent = self.resolve_parent(src_path)
    name = extract_name(src_path)
    entry = src_parent.children.get(name)
    if entry is None:
        raise FileNotFoundError(src_path)
    dest = self.resolve_path(dest_folder_path)
    if not isinstance(dest, Folder):
        raise NotADirectoryError(dest_folder_path)
    # Cycle detection: cannot move folder into itself or descendant
    if isinstance(entry, Folder):
        cur: Optional[FileSystemEntry] = dest
        while cur is not None:
            if cur is entry:
                raise ValueError("cycle")
            cur = cur.parent
    if name in dest.children:
        raise FileExistsError(name)
    src_parent.remove_child(name)
    dest.add_child(entry)

static String extractName(String path) {
    String[] parts = Arrays.stream(path.split("/")).filter(p -> !p.isEmpty()).toArray(String[]::new);
    if (parts.length == 0) throw new IllegalArgumentException("invalid path");
    return parts[parts.length - 1];
}

FileSystemEntry resolvePath(String path) {
    if ("/".equals(path)) return root;
    FileSystemEntry cur = root;
    for (String part : path.split("/")) {
        if (part.isEmpty()) continue;
        if (!(cur instanceof Folder) || !((Folder) cur).children.containsKey(part)) {
            throw new NoSuchFileException(path);
        }
        cur = ((Folder) cur).children.get(part);
    }
    return cur;
}

Folder resolveParent(String path) {
    if ("/".equals(path)) throw new IllegalArgumentException("root has no parent");
    String[] parts = Arrays.stream(path.split("/")).filter(p -> !p.isEmpty()).toArray(String[]::new);
    String parentPath = parts.length > 1 ? "/" + String.join("/", Arrays.copyOf(parts, parts.length - 1)) : "/";
    FileSystemEntry parent = resolvePath(parentPath);
    if (!(parent instanceof Folder)) throw new NotDirectoryException(parentPath);
    return (Folder) parent;
}

File createFile(String path, String content) {
    if ("/".equals(path)) throw new IllegalArgumentException("cannot create file at root");
    Folder parent = resolveParent(path);
    String name = extractName(path);
    if (parent.children.containsKey(name)) throw new FileAlreadyExistsException(name);
    File f = new File(name, content == null ? "" : content);
    parent.addChild(f);
    return f;
}

void move(String srcPath, String destFolderPath) {
    if ("/".equals(srcPath)) throw new IllegalArgumentException("cannot move root");
    Folder srcParent = resolveParent(srcPath);
    String name = extractName(srcPath);
    FileSystemEntry entry = srcParent.children.get(name);
    if (entry == null) throw new NoSuchFileException(srcPath);
    FileSystemEntry dest = resolvePath(destFolderPath);
    if (!(dest instanceof Folder)) throw new NotDirectoryException(destFolderPath);
    // Cycle detection: cannot move folder into itself or descendant
    if (entry instanceof Folder) {
        FileSystemEntry cur = dest;
        while (cur != null) {
            if (cur == entry) throw new IllegalArgumentException("cycle");
            cur = cur.parent;
        }
    }
    if (((Folder) dest).children.containsKey(name)) {
        throw new FileAlreadyExistsException(name);
    }
    srcParent.removeChild(name);
    ((Folder) dest).addChild(entry);
}

05Verification

1. createFolder('/docs'); createFile('/docs/a.txt', 'hi').
2. get/list return the file; rename to b.txt updates path.
3. move('/docs', '/docs/nested') → cycle error.
4. move('/docs/b.txt', '/archive') after creating /archive succeeds.
5. delete('/docs') removes the subtree (if you chose recursive delete).

• Happy: mkdir /docs; create /docs/a.txt; write; ls shows a.txt.
• Failure: create existing path → error; move directory into its descendant → cycle error.
• Concurrency: two mkdir /a/b and /a/c — parent dir lock serializes child map mutations.

06Extensibility: locks

• Coarse lock — one mutex on FileSystem for all mutations. Simple, correct, limited throughput.
• Fine-grained locks — per-folder locks; on move, lock ordering (e.g. sort parent paths alphabetically) to avoid deadlock between two moves.
• RW locks — concurrent readers on list/get; exclusive writers on create/delete/move.
• Search index — secondary map name→paths updated on create/rename/delete for fast find-by-name follow-ups.

07Common interview pitfalls

• Designing distributed GFS when prompt is in-memory single host.
• Path as string everywhere with no Entry tree (Directory/File).
• move() without cycle detection (moving dir under itself).
• delete non-empty directory without policy (reject vs recursive).
• No locks when concurrent mkdir/create on same parent.
• Symlinks complexity before basic CRUD works.

08Interview script (say this)

1. In-memory FS: File and Directory entries; path resolve helpers.
2. APIs: mkdir, create, write, read, ls, delete, move.
3. move must detect cycles; delete policy stated.
4. Trace: mkdir /a/b, create file, move /a under /a/b should fail.
5. Concurrency: lock per directory or single FS lock for v1.

09Extra verification traces

def move(self, src: str, dst: str):
    s, d_parent, name = self.resolve_move_args(src, dst)
    if isinstance(s, Directory) and self.is_ancestor(s, d_parent):
        raise RuntimeError("cycle")
    with d_parent.lock:
        d_parent.add(name, s)
    self.detach(src)

void move(String src, String dst) {
    // s, dParent, name = resolveMoveArgs(src, dst)
    FileSystemEntry s = /* resolve src */ null;
    Folder dParent = /* resolve dest parent */ null;
    String name = /* basename */ null;
    if (s instanceof Directory && isAncestor((Directory) s, dParent)) {
        throw new RuntimeException("cycle");
    }
    synchronized (dParent.lock) {
        dParent.add(name, s);
    }
    detach(src);
}

10Staff-level follow-ups

• Permissions? — Acl on Entry; resolve checks before mutate.
• Watchers? — Observer on Directory for create/delete events.
• Persistence? — Serialize tree snapshot; journal mutations.
• Symlinks? — Symlink entry type + resolve depth limit.

11Complete solution: locked FS mutations

from threading import Lock
from typing import Optional

class Node:
    def __init__(self, name: str, is_dir: bool):
        self.name = name
        self.is_dir = is_dir
        self.children: dict[str, "Node"] = {}
        self.content = ""

class FileSystem:
    def __init__(self):
        self.root = Node("", True)
        self._lock = Lock()

    def _resolve(self, path: str) -> Optional[Node]:
        if path == "/":
            return self.root
        cur = self.root
        for part in path.strip("/").split("/"):
            if not cur.is_dir or part not in cur.children:
                return None
            cur = cur.children[part]
        return cur

    def mkdir(self, path: str) -> bool:
        with self._lock:
            parts = path.strip("/").split("/")
            cur = self.root
            for p in parts[:-1]:
                if p not in cur.children or not cur.children[p].is_dir:
                    return False
                cur = cur.children[p]
            name = parts[-1]
            if name in cur.children:
                return False
            cur.children[name] = Node(name, True)
            return True

    def create_file(self, path: str, content: str = "") -> bool:
        with self._lock:
            parent_path, _, name = path.strip("/").rpartition("/")
            parent = self._resolve("/" + parent_path if parent_path else "/")
            if parent is None or not parent.is_dir or name in parent.children:
                return False
            node = Node(name, False)
            node.content = content
            parent.children[name] = node
            return True

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

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

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

class FileSystem {
    Node root = new Node("", true);
    private final ReentrantLock lock = new ReentrantLock();

    Node resolve(String path) {
        if ("/".equals(path)) return root;
        Node cur = root;
        String trimmed = path.replaceAll("^/+|/+
quot;, "");
        if (trimmed.isEmpty()) return root;
        for (String part : trimmed.split("/")) {
            if (!cur.isDir || !cur.children.containsKey(part)) return null;
            cur = cur.children.get(part);
        }
        return cur;
    }

    boolean mkdir(String path) {
        lock.lock();
        try {
            String trimmed = path.replaceAll("^/+|/+
quot;, "");
            String[] parts = trimmed.split("/");
            Node cur = root;
            for (int i = 0; i < parts.length - 1; i++) {
                String p = parts[i];
                if (!cur.children.containsKey(p) || !cur.children.get(p).isDir) return false;
                cur = cur.children.get(p);
            }
            String name = parts[parts.length - 1];
            if (cur.children.containsKey(name)) return false;
            cur.children.put(name, new Node(name, true));
            return true;
        } finally {
            lock.unlock();
        }
    }

    boolean createFile(String path, String content) {
        lock.lock();
        try {
            String trimmed = path.replaceAll("^/+|/+
quot;, "");
            int slash = trimmed.lastIndexOf('/');
            String parentPath = slash >= 0 ? trimmed.substring(0, slash) : "";
            String name = slash >= 0 ? trimmed.substring(slash + 1) : trimmed;
            Node parent = resolve(parentPath.isEmpty() ? "/" : "/" + parentPath);
            if (parent == null || !parent.isDir || parent.children.containsKey(name)) return false;
            Node node = new Node(name, false);
            node.content = content == null ? "" : content;
            parent.children.put(name, node);
            return true;
        } finally {
            lock.unlock();
        }
    }
}

12Concurrency cases

• Two mkdir same path — one wins; other False.
• move deadlock — if locking src and dst separately, order by path string.
• Readers — coarse lock or RW lock if list/read is hot.