walk: prune the subtree, not just the results

Reimplement Path.walk‘s traversal contract — including the in-place pruning side channel — and use it to find large files while skipping whole subtrees.

The tree is supplied as data so the exercise is deterministic and filesystem-free:

class Node(TypedDict):
    dirs: list[str]
    files: dict[str, int]      # name -> size in bytes

tree maps an absolute POSIX directory path to its Node. Child paths are f"{parent}/{name}", except under the root /, where they are f"/{name}".

def child(parent: str, name: str) -> str: ...

def walk(
    tree: Mapping[str, Node], top: str
) -> Iterator[tuple[str, list[str], list[str]]]: ...

def find_large_files(
    tree: Mapping[str, Node], root: str, min_bytes: int, *, skip: set[str]
) -> list[str]: ...

def solve(
    tree: dict[str, Node], root: str, min_bytes: int, skip: list[str]
) -> list[str]: ...

walk yields (dirpath, dirnames, filenames) top-down, and must honour the caller mutating dirnames in place: after yielding, it recurses into whatever the list contains at that moment. A top that is not in tree yields nothing.

find_large_files prunes skip directory names, collects files of at least min_bytes, and returns their full paths sorted by size descending, then path ascending.

The pruning side channel is the point. dirnames[:] = [...] mutates the list the generator is holding; dirnames = [...] rebinds your local name and the generator still iterates the original — so every subtree gets visited, silently. Both lines type-check identically and both look the same to a reviewer skimming a diff. The tests plant a very large file inside a skipped directory: filtering the results by name instead of pruning the traversal finds it and fails.

Pruning is not an optimisation you can skip. On a real repository node_modules is frequently more files than the rest of the project by an order of magnitude.

To make the side channel work, the generator must yield the list first and iterate it afterwards, so the caller’s edit lands in between. That ordering is the whole implementation.

Typing. Path.walk() yields tuple[Path, list[str], list[str]] — the directory and file names are plain str, not Path. Building a child is dirpath / name. This problem mirrors that with str throughout so the distinction stays visible.

Two real-pathlib notes while you are here: Path.walk landed in 3.12 and uses os.scandir internally, so it avoids the stat-per-check cost of a hand-rolled rglob loop; and 3.13 silently changed glob/rglob with a trailing ** to return files and directories, with no deprecation warning.