Compute sizes and validate a hierarchical file system

01The design, in the six-step framework

1. Requirements and use cases

A file system is given as a flat list of records: each entity has an id, a type, and for directories the ids of its children. A caller asks for the total size of any entity. A second operation validates the whole structure and reports every problem found: a reference to an id that does not exist, a cycle, an entity not reachable from the root, a file with children, a negative size. A file may appear under two directories, which is a hard link and is legal.

Out of scope: reading the records from disk and repairing problems. The reported onsite probed traversal, cycles, missing references, hard links, memoisation and concurrent mutation.

Constraints: depth can be large, so validation cannot rely on recursion; repeated size queries over shared directories should cost one computation each; validate reports all problems rather than stopping at the first; a size query on a broken tree must fail clearly and not hang.

2. Core entities and relationships

• EntityRecord: an immutable description of one entity. Children are ids, not objects, because the input may refer to ids that do not exist.
• Catalog: indexes the records, answers size queries with a memo and runs validation.
• Issue with IssueCode: one structured finding that a program can act on.
• CycleFound: raised by a size query that runs into a loop.

Because children are ids, this is a graph stored as adjacency. It looks like a composite tree, but the input is not guaranteed to be one, and that gap is the whole problem. Building a tree of objects first would fail on exactly the inputs validation exists to catch.

3. Interfaces and key methods

@dataclass(frozen=True)
class EntityRecord:
    entity_id: str
    kind: Kind                         # FILE or DIRECTORY
    size: int = 0                      # files only
    children: tuple[str, ...] = ()     # ids; a file reached twice is a hard link

class Issue(NamedTuple):
    code: IssueCode
    entity_id: str
    detail: str

class Catalog:
    def __init__(self, records: Iterable[EntityRecord], root: str) -> None: ...
    def size(self, entity_id: str, unique: bool = False) -> int:
        """Total bytes under an entity; unique=True counts a hard-linked file once."""
    def validate(self) -> list[Issue]:
        """Every problem in the tree: cycles, missing refs, orphans, bad records."""

Invariants: records never change after loading, so memoised totals stay correct for the catalog's life; every id visited by validate is coloured exactly once as grey and once as black; size with unique=False counts a linked file once per path, and with unique=True once in total.

4. Design patterns and the choices behind them

Three colours for validation

A single visited set cannot separate two situations. Reaching a node that is on the current path is a cycle. Reaching a node that is already finished is a hard link, and it is legal. Grey means on the path and black means done, which is the standard depth-first test and exactly the distinction the interviewer wants. Validation runs iteratively with an explicit stack, so a chain a million levels deep does not overflow.

Separating query from audit

validate collects problems and never raises for them. size assumes a usable tree and raises on a cycle or missing id. A validator that stopped at the first error would make a person run it once per problem, and a size query that returned a partial total would be silently wrong.

Memoisation, and what it does to the path check

With many links, a naive walk revisits shared directories and can go exponential on a diamond chain. Memoising directory totals makes each directory one computation, so a size query is O(nodes plus edges) overall. The memo is checked first, which is safe because a memoised directory was fully walked with no cycle below it.

Two meanings of total size

If a 1 MB file is linked twice under a directory, is the total 1 MB or 2 MB? Summing paths answers "what would a copy cost"; the unique flag answers "how much disk is used". A memo cannot serve the second, because the sets of two subtrees overlap, so _reachable_files walks instead. Ask which is wanted; the answer changes the algorithm.

5. Core flow and code

1. The records are: root holds a and b; a holds file f (100 bytes); b holds f and missing id z; orphan o exists; c holds itself.
2. validate finds nothing wrong per record, then starts at root coloured grey and pushes a.
3. a is walked, f turns grey then black, a turns black.
4. b is walked: f is black, so it is a legal hard link with no issue; z is not in the catalog, so a MISSING_REF issue is recorded for b.
5. The walk ends. o and c were never coloured, so each gets an ORPHAN issue.
6. Had c been reachable, its self-reference would be seen while c is grey, producing a CYCLE issue.
7. With z removed, size("root") gives 200 and size("root", unique=True) gives 100.

from __future__ import annotations
from dataclasses import dataclass
from enum import Enum, auto
from typing import Iterable, NamedTuple

class Kind(Enum):
    FILE = auto(); DIRECTORY = auto()

class IssueCode(Enum):
    MISSING_REF = auto(); CYCLE = auto(); ORPHAN = auto()
    FILE_HAS_CHILDREN = auto(); NEGATIVE_SIZE = auto(); MISSING_ROOT = auto()

@dataclass(frozen=True)
class EntityRecord:
    entity_id: str
    kind: Kind
    size: int = 0
    children: tuple[str, ...] = ()

class Issue(NamedTuple):
    code: IssueCode
    entity_id: str
    detail: str

class CycleFound(Exception):
    pass

WHITE, GREY, BLACK = 0, 1, 2             # unvisited, on the current path, finished

class Catalog:
    def __init__(self, records: Iterable[EntityRecord], root: str) -> None:
        self._by_id = {r.entity_id: r for r in records}
        self._root = root
        self._memo: dict[str, int] = {}

    def size(self, entity_id: str, unique: bool = False) -> int:
        if unique:
            return sum(self._by_id[f].size for f in self._reachable_files(entity_id))
        return self._size(entity_id, set())

    def _size(self, eid: str, path: set[str]) -> int:
        if eid in self._memo:
            return self._memo[eid]
        record = self._by_id.get(eid)
        if record is None:
            raise KeyError(eid)
        if eid in path:
            raise CycleFound(eid)
        if record.kind is Kind.FILE:
            return record.size
        path.add(eid)
        total = sum(self._size(c, path) for c in record.children)
        path.remove(eid)
        self._memo[eid] = total
        return total

    def _reachable_files(self, start: str) -> set[str]:
        files, seen, stack = set(), set(), [start]
        while stack:
            eid = stack.pop()
            if eid in seen or eid not in self._by_id:
                continue
            seen.add(eid)
            record = self._by_id[eid]
            if record.kind is Kind.FILE:
                files.add(eid)
            stack.extend(record.children)
        return files

    def validate(self) -> list[Issue]:
        issues: list[Issue] = []
        for r in self._by_id.values():
            if r.kind is Kind.FILE and r.children:
                issues.append(Issue(IssueCode.FILE_HAS_CHILDREN, r.entity_id, str(r.children)))
            if r.size < 0:
                issues.append(Issue(IssueCode.NEGATIVE_SIZE, r.entity_id, str(r.size)))
        if self._root not in self._by_id:
            return issues + [Issue(IssueCode.MISSING_ROOT, self._root, "root not in catalog")]

        color: dict[str, int] = {}
        stack: list[tuple[str, int]] = [(self._root, 0)]   # iterative: depth may be huge
        color[self._root] = GREY
        while stack:
            eid, i = stack.pop()
            kids = self._by_id[eid].children
            if i == len(kids):
                color[eid] = BLACK
                continue
            stack.append((eid, i + 1))
            child = kids[i]
            if child not in self._by_id:
                issues.append(Issue(IssueCode.MISSING_REF, eid, child))
            elif color.get(child, WHITE) == GREY:
                issues.append(Issue(IssueCode.CYCLE, eid, child))
            elif color.get(child, WHITE) == WHITE:
                color[child] = GREY
                stack.append((child, 0))
            # BLACK: reached a second time, a hard link, which is legal
        for eid in self._by_id:
            if eid not in color:
                issues.append(Issue(IssueCode.ORPHAN, eid, "unreachable from root"))
        return issues

    def snapshot(self, updated: Iterable[EntityRecord]) -> "Catalog":
        """A new catalog with changes applied; this one stays valid for readers."""
        merged = dict(self._by_id)
        merged.update({r.entity_id: r for r in updated})
        return Catalog(merged.values(), self._root)

6. Extensions, concurrency and what interviewers probe

• Concurrent mutation: a size query racing with writes can see half a change. snapshot builds a new immutable version, and readers keep the old catalog. Publishing the new one is a single reference swap, and each version has its own memo.
• Incremental updates: rebuilding on each change costs O(n); with parent links, a size delta can be pushed up each path, and hard links mean there can be several paths.
• Soft links: a new kind pointing at an id. Sizes usually skip them, and they are the normal source of cycles in real file systems.
• Depth of _size: it is recursive for readability. Say that a pathological depth needs the same explicit stack as validate.
• Test first: empty directory, plain tree, hard link counted both ways, a self-loop, a two-node cycle, a missing child, an orphan, a missing root, and a long diamond chain that would time out without the memo.
• Common mistake: one visited set for everything, which reports every hard link as a cycle.

02Where this question was reported

• PracHub · Google onsite (L4 loop downlevelled to L3): traversal, cycles, missing refs, hard links, memoisation, concurrent mutation