Courses › Low-Level Design › Problem Walkthroughs

Design an In-Memory File System

The Composite pattern, path resolution, move/remove edge cases and composable search.

"Design an in-memory file system" checks three things: whether you can model a tree of directories and files with the Composite pattern, whether you parse paths carefully, and whether the operations stay clean as the follow-ups pile up (move, size, search, permissions). The same model also underlies the *Unix find* and *cloud file storage* questions.

Requirements

mkdir(path) creates directories, including missing parents (like mkdir -p).
write(path, content) creates or overwrites a file, and append adds to it. read(path) returns the content.
ls(path) lists a directory's entries in sorted order. For a file, it returns just the file's name.
rm(path), mv(src, dst), and size(path) (recursive for directories).
Errors: a missing path, a file where a directory was expected, removing a non-empty directory without the recursive flag.

Composite pattern

Files and directories share an interface (name, size(), parent), but only directories have children. Client code can treat both the same way, for example to compute a size recursively.

Node (abstract)   name, parent, created_at; size(), path()
  File            content
  Directory       children: dict[name, Node]
FileSystem        root; mkdir, write, read, ls, rm, mv, size, find

Storing children in a dict keyed by name gives O(1) lookup for each path component, so resolving a path costs O(depth).

Implementation

class FSError(Exception):
    pass


class Node:
    def __init__(self, name, parent=None):
        self.name, self.parent = name, parent

    def path(self):
        parts, node = [], self
        while node.parent:
            parts.append(node.name)
            node = node.parent
        return "/" + "/".join(reversed(parts))


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

    def size(self):
        return len(self.content)


class Directory(Node):
    def __init__(self, name, parent=None):
        super().__init__(name, parent)
        self.children = {}

    def size(self):
        return sum(child.size() for child in self.children.values())


class FileSystem:
    def __init__(self):
        self.root = Directory("")

    @staticmethod
    def _parts(path):
        if not path.startswith("/"):
            raise FSError("paths must be absolute")
        parts = []
        for p in path.split("/"):
            if p in ("", "."):
                continue
            if p == "..":
                if parts:
                    parts.pop()
            else:
                parts.append(p)
        return parts

    def _resolve(self, path):
        node = self.root
        for name in self._parts(path):
            if not isinstance(node, Directory) or name not in node.children:
                raise FSError(f"no such file or directory: {path}")
            node = node.children[name]
        return node

    def _parent_and_name(self, path, create_dirs=False):
        parts = self._parts(path)
        if not parts:
            raise FSError("cannot operate on root")
        node = self.root
        for name in parts[:-1]:
            child = node.children.get(name)
            if child is None and create_dirs:
                child = node.children[name] = Directory(name, node)
            if not isinstance(child, Directory):
                raise FSError(f"not a directory: {name}")
            node = child
        return node, parts[-1]

    def mkdir(self, path):
        node = self.root
        for name in self._parts(path):
            child = node.children.get(name)
            if child is None:
                child = node.children[name] = Directory(name, node)
            elif not isinstance(child, Directory):
                raise FSError(f"file exists: {name}")
            node = child

    def write(self, path, content, append=False):
        parent, name = self._parent_and_name(path, create_dirs=True)
        node = parent.children.get(name)
        if isinstance(node, Directory):
            raise FSError("is a directory")
        if node is None:
            parent.children[name] = File(name, parent, content)
        else:
            node.content = node.content + content if append else content

    def read(self, path):
        node = self._resolve(path)
        if not isinstance(node, File):
            raise FSError("is a directory")
        return node.content

    def ls(self, path="/"):
        node = self._resolve(path)
        if isinstance(node, File):
            return [node.name]
        return sorted(node.children)

    def rm(self, path, recursive=False):
        parent, name = self._parent_and_name(path)
        node = parent.children.get(name)
        if node is None:
            raise FSError("no such file or directory")
        if isinstance(node, Directory) and node.children and not recursive:
            raise FSError("directory not empty")
        del parent.children[name]

    def mv(self, src, dst):
        node = self._resolve(src)
        if node is self.root:
            raise FSError("cannot move root")
        new_parent, new_name = self._parent_and_name(dst)
        p = new_parent
        while p:                                   # moving a directory into itself
            if p is node:
                raise FSError("cannot move a directory into itself")
            p = p.parent
        if new_name in new_parent.children:
            raise FSError("destination exists")
        del node.parent.children[node.name]
        node.name, node.parent = new_name, new_parent
        new_parent.children[new_name] = node

    def size(self, path):
        return self._resolve(path).size()

fs = FileSystem()
fs.write("/a/b/notes.txt", "hello")
fs.mkdir("/a/c")
assert fs.ls("/a") == ["b", "c"]
fs.mv("/a/b/notes.txt", "/a/c/todo.txt")
assert fs.read("/a/c/../c/todo.txt") == "hello"
assert fs.size("/a") == 5

[!INTERVIEW] Name the edge cases you handle .. above the root, trailing slashes, writing to a path where a directory exists, moving a directory into its own subtree, and removing the root. Listing them, even before you implement them all, shows the carefulness this question is checking for.

Search: the `find` follow-up

"Find all files over 5 MB with the extension .log" is a DFS over the tree with a filter. Make the filters composable with the Specification pattern:

class Filter:
    def matches(self, node): raise NotImplementedError
    def __and__(self, other): return AndFilter(self, other)
    def __or__(self, other): return OrFilter(self, other)

class AndFilter(Filter):
    def __init__(self, a, b): self.a, self.b = a, b
    def matches(self, node): return self.a.matches(node) and self.b.matches(node)

class OrFilter(Filter):
    def __init__(self, a, b): self.a, self.b = a, b
    def matches(self, node): return self.a.matches(node) or self.b.matches(node)

class ExtensionFilter(Filter):
    def __init__(self, ext): self.ext = ext
    def matches(self, node): return isinstance(node, File) and node.name.endswith(self.ext)

class MinSizeFilter(Filter):
    def __init__(self, n): self.n = n
    def matches(self, node): return isinstance(node, File) and node.size() >= self.n

def find(root, flt):
    stack, out = [root], []
    while stack:
        node = stack.pop()
        if flt.matches(node):
            out.append(node.path())
        if isinstance(node, Directory):
            stack.extend(node.children.values())
    return out

New criteria (owner, modified-after, name regex) are new Filter classes, and the search code doesn't change.

Follow-ups

Fast size queries: cache each directory's size and update it up the parent chain on every write, append, remove or move. That's O(depth) per update instead of walking the whole subtree per query.
Permissions and owners: add fields to Node, and check them inside _resolve (execute permission on each directory) and in each operation.
Thread safety: a single read-write lock is the simple answer. Lock per directory is finer, but mv then needs both parents locked in a consistent order.
Symlinks: a third node type that holds a target path. _resolve follows it, with a hop limit to stop loops.
Large files: store content as a list of chunks or blocks instead of one string.