Problem 76 · Object & System Design

In-Memory File System

HardClassic DSA & systems

01Problem

Implement ls(path), mkdir(path), add_content_to_file(path, content), and read_content_from_file(path). ls on a file returns [filename]; on a directory returns sorted children. mkdir and add_content create missing parents.

02Key insight

Model it as a trie keyed by path segments, where each node is either a directory (children map) or a file (content buffer). All operations become a walk over split path components.

03Solution

solution.pypython58 lines

from __future__ import annotations


class _Inode:
    __slots__ = ("children", "content", "is_dir")

    def __init__(self, is_dir: bool) -> None:
        self.children: dict[str, _Inode] = {}
        self.content: list[str] = []  # list of chunks avoids O(n^2) appends
        self.is_dir = is_dir  # explicit: an empty directory is still a directory


class FileSystem:
    def __init__(self) -> None:
        self.root = _Inode(is_dir=True)

    @staticmethod
    def _parts(path: str) -> list[str]:
        return [p for p in path.split("/") if p]

    def _walk(self, path: str, create: bool = False) -> _Inode:
        node = self.root
        for part in self._parts(path):
            if not node.is_dir:
                raise NotADirectoryError(path)
            if part not in node.children:
                if not create:
                    raise FileNotFoundError(path)
                node.children[part] = _Inode(is_dir=True)
            node = node.children[part]
        return node

    def ls(self, path: str) -> list[str]:
        node = self._walk(path)
        if not node.is_dir:
            return [self._parts(path)[-1]]
        return sorted(node.children)

    def mkdir(self, path: str) -> None:
        node = self._walk(path, create=True)
        if not node.is_dir:
            raise FileExistsError(path)

    def add_content_to_file(self, path: str, content: str) -> None:
        *dirs, name = self._parts(path) or [""]
        parent = self._walk("/".join(dirs), create=True)
        if not parent.is_dir:
            raise NotADirectoryError(path)
        node = parent.children.setdefault(name, _Inode(is_dir=False)) if name else parent
        if node.is_dir:
            raise IsADirectoryError(path)
        node.content.append(content)

    def read_content_from_file(self, path: str) -> str:
        node = self._walk(path)
        if node.is_dir:
            raise IsADirectoryError(path)
        return "".join(node.content)

Try it first.

TimeO(depth) per op (+ k log k for ls sort)

SpaceO(nodes + content)

tests.py · 4 passing

tests.pypython18 lines

fs = FileSystem()
assert fs.ls("/") == []
fs.mkdir("/a/b/c")
fs.add_content_to_file("/a/b/c/d", "hello")
fs.add_content_to_file("/a/b/c/d", " world")
assert fs.ls("/") == ["a"] and fs.ls("/a/b/c") == ["d"] and fs.ls("/a/b/c/d") == ["d"]
assert fs.read_content_from_file("/a/b/c/d") == "hello world"
try:
    fs.ls("/missing"); assert False
except FileNotFoundError:
    pass
fs.mkdir("/empty")
for bad in ("/empty", "/"):
    try:
        fs.add_content_to_file(bad, "x"); assert False
    except IsADirectoryError:
        pass
assert fs.ls("/empty") == [] and fs.ls("/") == ["a", "empty"]

04Staff-level follow-up

Concurrent writers? Per-inode locks taken in path order (hand-over-hand) to avoid deadlock; real systems add a separate inode table so rename/hard links are O(1) pointer moves.