Simplified filesystem with paths and traversal: Frontier Interview's solution

Question: Simplified filesystem with paths and traversal

Companies: Anthropic

Difficulty: Medium

Problem statement

Implement a small filesystem with path lookup and directory traversal, extended in the final level with model-related behavior. The harness is strict, so edge cases around paths matter.

Level 1: mkdir(path) (creates parents), write(path, content), read(path), ls(path).
Level 2: rm(path) (recursive, never /), mv(src, dst).
Level 3: find(path, suffix="") and du(path).
Level 4: checkpoints named step-<n>.ckpt: latest_checkpoint(dir) and prune_checkpoints(dir, keep).

class FileSystem:
    def mkdir(self, path): ...
    def write(self, path, content): ...
    def read(self, path): ...
    def ls(self, path): ...

    def rm(self, path): ...
    def mv(self, src, dst): ...

    def find(self, path, suffix=""): ...
    def du(self, path): ...

    def latest_checkpoint(self, path): ...
    def prune_checkpoints(self, path, keep): ...

Approach

The spec used here. Paths are absolute strings. The grader checks exact return values, so the edge cases are the question.

Level	Methods	Rules
1	`mkdir(path)`, `write(path, content)`, `read(path)`, `ls(path)`	`mkdir` creates missing parents (like `mkdir -p`) and returns `False` if a file is in the way. `write` needs the parent directory to exist and fails on a directory. `read` gives `None` when missing or a directory. `ls` gives sorted child names for a directory, `[name]` for a file, `None` when missing.
2	`rm(path)`, `mv(src, dst)`	`rm` is recursive and never removes `/`. `mv` fails if `dst` exists, if its parent is missing, or if a directory would move into itself.
3	`find(path, suffix="")`, `du(path)`	`find` returns full paths of files under `path` ending with `suffix`, sorted. `du` sums content length under `path`.
4	`latest_checkpoint(dir)`, `prune_checkpoints(dir, keep)`	Checkpoints are files named `step-<n>.ckpt`. Latest is the highest `n` (numerically). Prune deletes all but the `keep` newest and returns the deleted paths, oldest first.

Normalize every path in one place. "/a//b/./c/../d/" must mean /a/b/d. Split on /, drop empty parts and ., pop on .. (and stay at the root when .. goes above it). Reject relative paths. Every method calls _parts(path) first, so no method handles slashes on its own. This one helper removes most of the edge-case bugs.

The tree. A directory is a dict of name to node; a file is a small object holding its content. Walking to a node is a loop over the parts. Keep a helper _parent(parts) that returns the parent directory and the last name, since write, rm and mv all need exactly that.

Traversal. find is a depth-first walk with children visited in sorted order, so output comes out in tree order without a final sort. Tree order is not always plain string order of the full paths: /r/a/x comes before /r/a-b in the tree, but - sorts before / as a character. Ask which one the grader wants; this answer uses tree order. An explicit stack avoids recursion limits on deep trees.

Level 4 traps. Sorting checkpoint names as strings puts step-10 before step-9. Parse the integer. Ignore files that only look similar (step-x.ckpt, step-3.ckpt.tmp): a half-written checkpoint is usually written as .tmp and renamed, and treating it as the latest would load a corrupt model.

Code

import re

CKPT = re.compile(r"step-(\d+)\.ckpt")


class File:
    def __init__(self, content=""):
        self.content = content


class FileSystem:
    def __init__(self):
        self.root = {}  # a directory is a dict: name -> dict | File

    # -- helpers -----------------------------------------------------------
    @staticmethod
    def _parts(path):
        if not path.startswith("/"):
            raise ValueError(f"not absolute: {path!r}")
        parts = []
        for p in path.split("/"):
            if p in ("", "."):
                continue
            if p == "..":
                if parts:
                    parts.pop()
            else:
                parts.append(p)
        return parts

    def _node(self, parts):
        node = self.root
        for p in parts:
            if not isinstance(node, dict) or p not in node:
                return None
            node = node[p]
        return node

    def _parent(self, parts):
        if not parts:
            return None, None
        parent = self._node(parts[:-1])
        return (parent, parts[-1]) if isinstance(parent, dict) else (None, None)

    @staticmethod
    def _join(parts):
        return "/" + "/".join(parts)

    # -- level 1 -----------------------------------------------------------
    def mkdir(self, path):
        node = self.root
        for p in self._parts(path):
            child = node.setdefault(p, {})
            if not isinstance(child, dict):
                return False  # a file is in the way
            node = child
        return True

    def write(self, path, content):
        parent, name = self._parent(self._parts(path))
        if parent is None or isinstance(parent.get(name), dict):
            return False
        parent[name] = File(content)
        return True

    def read(self, path):
        node = self._node(self._parts(path))
        return node.content if isinstance(node, File) else None

    def ls(self, path):
        parts = self._parts(path)
        node = self._node(parts)
        if node is None:
            return None
        return sorted(node) if isinstance(node, dict) else [parts[-1]]

    # -- level 2 -----------------------------------------------------------
    def rm(self, path):
        parent, name = self._parent(self._parts(path))
        if parent is None or name not in parent:
            return False
        del parent[name]
        return True

    def mv(self, src, dst):
        s, d = self._parts(src), self._parts(dst)
        sp, sname = self._parent(s)
        dp, dname = self._parent(d)
        if sp is None or sname not in sp or dp is None or dname in dp:
            return False
        if d[: len(s)] == s:
            return False  # into itself
        dp[dname] = sp.pop(sname)
        return True

    # -- level 3 -----------------------------------------------------------
    def find(self, path, suffix=""):
        parts = self._parts(path)
        node = self._node(parts)
        if node is None:
            return []
        out, stack = [], [(parts, node)]
        while stack:
            p, n = stack.pop()
            if isinstance(n, File):
                if p[-1].endswith(suffix):
                    out.append(self._join(p))
                continue
            for name in sorted(n, reverse=True):  # reversed so pops come out sorted
                stack.append((p + [name], n[name]))
        return out

    def du(self, path):
        return sum(len(self.read(f)) for f in self.find(path))

    # -- level 4 -----------------------------------------------------------
    def _checkpoints(self, path):
        parts = self._parts(path)
        node = self._node(parts)
        if not isinstance(node, dict):
            return []
        found = []
        for name, child in node.items():
            m = CKPT.fullmatch(name)
            if m and isinstance(child, File):
                found.append((int(m.group(1)), self._join(parts + [name])))
        return sorted(found)

    def latest_checkpoint(self, path):
        found = self._checkpoints(path)
        return found[-1][1] if found else None

    def prune_checkpoints(self, path, keep):
        found = self._checkpoints(path)
        doomed = found[: max(0, len(found) - keep)]
        for _, p in doomed:
            self.rm(p)
        return [p for _, p in doomed]

Complexity

Let d be the path depth, c the children of one directory and N the nodes under a path.

mkdir, write, read, rm, mv: O(d) dict steps.
ls: O(c log c) for the sort.
find, du: O(N log c) (sorting children at each level).
Checkpoint methods: O(c log c) for one directory.

Test cases

from solution import FileSystem


def test_mkdir_write_read_ls():
    fs = FileSystem()
    assert fs.mkdir("/a/b") is True
    assert fs.write("/a/b/x.txt", "hi") is True
    assert fs.read("/a/b/x.txt") == "hi"
    assert fs.ls("/a") == ["b"]
    assert fs.ls("/a/b/x.txt") == ["x.txt"]
    assert fs.ls("/missing") is None


def test_paths_are_normalized():
    fs = FileSystem()
    fs.mkdir("/a/b")
    fs.write("/a//b/./c.txt", "1")
    assert fs.read("/a/b/../b/c.txt") == "1"
    assert fs.ls("/../a/") == ["b"]


def test_files_and_dirs_do_not_mix():
    fs = FileSystem()
    fs.mkdir("/a")
    fs.write("/a/f", "x")
    assert fs.mkdir("/a/f/g") is False
    assert fs.write("/a", "y") is False
    assert fs.write("/nope/f", "y") is False
    assert fs.read("/a") is None

from solution import FileSystem


def test_rm_recursive_and_root_protected():
    fs = FileSystem()
    fs.mkdir("/a/b")
    fs.write("/a/b/f", "x")
    assert fs.rm("/a") is True
    assert fs.ls("/") == []
    assert fs.rm("/") is False
    assert fs.rm("/a") is False


def test_mv_rules():
    fs = FileSystem()
    fs.mkdir("/a/b")
    fs.mkdir("/c")
    fs.write("/a/b/f", "x")
    assert fs.mv("/a/b", "/a/b/inner") is False
    assert fs.mv("/a/b", "/c") is False          # destination exists
    assert fs.mv("/a/b", "/zz/b") is False       # no parent
    assert fs.mv("/a/b", "/c/b") is True
    assert fs.read("/c/b/f") == "x"
    assert fs.ls("/a") == []

from solution import FileSystem


def test_find_sorted_with_suffix_and_du():
    fs = FileSystem()
    fs.mkdir("/r/z")
    fs.mkdir("/r/a")
    fs.write("/r/z/1.py", "abc")
    fs.write("/r/a/2.py", "de")
    fs.write("/r/a/3.md", "f")
    fs.write("/r/b.py", "")
    assert fs.find("/r") == ["/r/a/2.py", "/r/a/3.md", "/r/b.py", "/r/z/1.py"]
    assert fs.find("/r", ".py") == ["/r/a/2.py", "/r/b.py", "/r/z/1.py"]
    assert fs.du("/r") == 6
    assert fs.find("/missing") == []

from solution import FileSystem


def make():
    fs = FileSystem()
    fs.mkdir("/run/ckpt")
    for name in ["step-9.ckpt", "step-10.ckpt", "step-100.ckpt", "step-200.ckpt.tmp", "notes.txt"]:
        fs.write("/run/ckpt/" + name, "w")
    return fs


def test_latest_is_numeric_and_ignores_partial_files():
    fs = make()
    assert fs.latest_checkpoint("/run/ckpt") == "/run/ckpt/step-100.ckpt"
    assert fs.latest_checkpoint("/run") is None


def test_prune_keeps_newest():
    fs = make()
    assert fs.prune_checkpoints("/run/ckpt", 1) == ["/run/ckpt/step-9.ckpt", "/run/ckpt/step-10.ckpt"]
    assert fs.ls("/run/ckpt") == ["notes.txt", "step-100.ckpt", "step-200.ckpt.tmp"]
    assert fs.prune_checkpoints("/run/ckpt", 5) == []

Follow-ups

Real filesystems use inodes. Separate names from objects: directories map names to inode numbers, and inodes hold content and metadata. Hard links (two names, one inode) and mv become pointer updates, and rm frees an inode only when its link count reaches zero.
Atomic checkpoint writes. Write step-n.ckpt.tmp, flush and fsync, then rename to step-n.ckpt. Rename is atomic within one directory, so readers see either the old set or the new file, never half a file. That is why Level 4 ignores .tmp.
Retention policies. Keep the last k plus every 10,000th step, plus the best by eval loss. Prune computes the set to keep first and deletes the rest, so a crash mid-prune never deletes a keeper.
Large directories. ls and find on millions of entries need pagination (a cursor of the last name returned) and a sorted structure per directory instead of sorting a dict on every call.
Object stores. On S3-style storage there are no directories, only keys with prefixes. find becomes a prefix list, mv of a directory is a copy of every object plus a delete (not atomic), and "latest checkpoint" is usually a small pointer file written last.

Interviewer expectations

Mid-level (L4)

Builds the tree with dicts and gets read, write, mkdir and ls right for normal paths.
Handles missing paths and file-versus-directory conflicts with the specified return values.
Implements recursive delete and a sorted traversal.

Senior (L5)

Normalizes every path in one helper (empty parts, ., .., trailing slash, root) before any method touches the tree.
Gets mv edge cases: destination exists, missing parent, moving a directory into itself.
Sorts checkpoints numerically and ignores partial files, explaining why.

Staff (L6+)

Explains inodes, links and atomic rename, and how checkpoint writers rely on them.
Designs retention that is safe under crashes and discusses object-store semantics.
Keeps the code small enough that each level is an addition, with tests for every edge case listed.