06 — Unix File Search System

“Design a library that finds files under a directory. Like find.”

The Unix find command hides a design problem in plain sight: a search library is only as good as the queries it can express, and the way to make queries expressive is to make them objects.

By the end you will be able to:

• explain why a function with optional keyword arguments cannot express the one requirement that decides this interview;
• build a small algebra of filter objects that combines with and, or and not;
• model a directory tree so that files and folders answer the same questions;
• say precisely what all of that costs — because the composed design is genuinely worse than the naive one in three specific ways, and naming them is what separates a designer from someone reciting patterns.

What goes in, and what comes out

The deliverable is a library with one entry point. Fix its shape before drawing any classes.

The sketch below is not code: it names the three inputs, the one output, and then shows a sample call with the first few results it would print.

IN   root     a Node -- the top of the directory tree to search
IN   where    a Filter -- one object whose matches(node) returns True or False
IN   descend  an optional Filter -- which directories are worth walking into

OUT  an iterator of Nodes: results handed back one at a time, as they are found,
     in pre-order (a directory is reported before the things inside it)

find(root, (LargerThan(10 * MB) | Extension(".log")) & ~UnderPath("/tmp"))
  -> /                     <- yes, a directory: see section 6 on Directory.size()
  -> /usr
  -> ...
  -> /var/log/syslog.log
  -> /var/log/old.log

The interesting thing about that signature is what is not in it: no name=, no size=, no extension=. The entire query is one argument, because the query is one object. This interview is decided in the first ninety seconds, by the signature you write.

The signature almost everybody writes

Almost everybody writes find(directory, name=None, size=None, extension=None) and then defends it.

It survives exactly until the requirement is “files over 10 MB or ending in .log, but not anywhere under /tmp”.

At that point a parameter list has no way to express the sentence, because supplying two parameters can only ever mean “both must hold”. A parameter list is an implicit AND and nothing else.

The signature that gets hired

The answer that gets hired turns each criterion into an object with one method, and lets those objects compose with and, or and not. Adding a search criterion stops being an edit to a signature and becomes a new class.

That is the open-closed principle doing visible work rather than being quoted. A design is open for extension if you can add behaviour to it, and closed for modification if doing so requires no edit to code that already works.

The directory tree gets the same treatment from the other direction. File and Directory are made to answer the same questions through one interface — a set of methods a caller can rely on without knowing which class supplies them. Given a name, that arrangement is the Composite pattern, and it is what makes the traversal one short recursive function instead of two mutually recursive ones.

For the interview method — how to spend the 45 minutes — see 02 — the object-oriented design (OOD) framework. For the same patterns treated as topics in their own right, see 03 — object-oriented programming (OOP) fundamentals. Neither is required to follow this chapter.

1. Clarifying questions that change the design

Four questions are worth asking here, on the usual test: does the answer add or delete a class?

Each row commits you to one of two designs, depending on the interviewer’s answer — and both columns are real answers; the “no” column is not a booby prize.

The five terms that table uses

• Algebra — a set of values plus operations that combine them into more values of the same kind. Integers with + are an algebra; so are filters with “and”.
• Abstract type — a class that declares methods without implementing them, existing only to be subclassed.
• Stream — hand results back one at a time as they are found, rather than collecting them all first.
• Prune — decline to walk into a directory at all, so nothing beneath it is ever examined.
• Index — a precomputed lookup table. It is the difference between find, which walks the disk every time, and locate, which consults a nightly database and can be wrong.

Volunteer the last row

The fast-versus-expressive row is worth raising before the interviewer does, because the answer changes what you are building.

A generic matches(node) predicate — a function that takes one thing and answers yes or no — forbids the single biggest optimisation available.

That optimisation is pushing the criterion down to something that already knows the answer: a name index, or the filesystem’s own readdir directory listing. A predicate that can only be handed a fully-built node cannot be pushed anywhere, because there is nothing to inspect and nothing to translate.

So if the interviewer wanted locate rather than find, the object model is the wrong artefact entirely. Saying that early buys you the rest of the design.

Out of scope, said out loud: content search (grep, a different traversal over a different axis), permissions and access-control-list evaluation, and network filesystems.

2. Actors and use cases

Naming the actors takes two minutes, and it exists here to surface a third participant that is not a person and does not hold still.

The third actor is the one that makes streaming a design question rather than a performance tweak. The tree is allowed to mutate while you walk it. Any design that pretends otherwise is describing a snapshot — a frozen picture of one instant — that it does not actually have.

3. Core objects, and why not one searcher with options

Five responsibilities make up this design, and each earns its separation for a different reason — including one that looks like it should not be an object at all.

Write the naive draft first so you know what you are rejecting. It has two classes: a FileSystem that walks, and a SearchQuery struct of optional fields. It puts every criterion inside the walker, so the walker knows about sizes, extensions and timestamps — three reasons to change one class.

The five responsibilities

Each row pairs a job the library has to do with the place that job lives — and two of those places are not classes at all.

Only three of those five responsibilities are objects. walk is a module-level function and the sink is whatever the caller does with the iterator, which is why neither appears in the class diagram below.

Three words in that table need defining:

• A leaf is a node with nothing below it — a file.
• A branch is a node that contains others — a directory.
• The sink is wherever results end up: printed, collected, counted. The design deliberately refuses to decide, which is why find returns an iterator and not a list.

Why And is a Filter and not a keyword

And being a Filter is the entire trick.

It is what makes the structure a tree rather than a list, and a tree is what lets (a | b) & ~c exist at all.

A design where combination lives in the search function instead of in the type can express a list of criteria and never an expression. Lists nest zero levels deep; trees nest as far as the query needs.

4. Class diagram

The diagram below is the whole design in one picture — and the shape it draws locks in assumptions worth naming out loud.

Reading the notation

The notation is UML — the Unified Modeling Language, the standard boxes-and-arrows notation for class models. Four marks carry all the meaning here.

• A box is a class, and + marks a member visible to callers: +int size_bytes is a public integer field, +matches(node) bool a public method returning a boolean.
• <<abstract>> marks a class that cannot be instantiated on its own — it exists to be subclassed and declares methods its subclasses must supply. <<interface>> is the same promise with no state at all behind it.
• <|-- is inheritance, read as “is a”: Node <|-- File says a file is a node and can stand wherever a node is expected.
• *-- is composition — the part cannot outlive the whole, which creates and destroys it. o-- is aggregation — the whole merely holds a reference to something with its own independent life. --> is a plain association: this class knows about that one.
• The quoted numbers are multiplicities: "1" exactly one, "0..*" zero or more, "2..*" two or more.

The diagram

Two things to notice as you read it. First, Node and Filter are both abstract, each with a leaf-and-branch pair under it. Second, there is no Searcher class anywhere — the traversal is a plain function.

classDiagram
    class Node {
        <<abstract>>
        +str name
        +float mtime
        +path() str
        +size() int
    }
    class File {
        +int size_bytes
    }
    class Directory {
        +add(node) Directory
    }
    class Filter {
        <<abstract>>
        +matches(node) bool
    }
    class Clock {
        <<interface>>
        +now() float
    }
    class And
    class Or
    class Not
    class NameMatches
    class LargerThan
    class Extension
    class UnderPath
    class ModifiedWithin

    Node <|-- File : inheritance
    Node <|-- Directory : inheritance
    Directory "1" *-- "0..*" Node : composition
    Filter <|-- And
    Filter <|-- Or
    Filter <|-- Not
    Filter <|-- NameMatches
    Filter <|-- LargerThan
    Filter <|-- Extension
    Filter <|-- UnderPath
    Filter <|-- ModifiedWithin
    And "1" o-- "2..*" Filter : operands
    Or "1" o-- "2..*" Filter : operands
    Not "1" o-- "1" Filter : operand
    ModifiedWithin "1" --> "1" Clock : injected

Read the arrows out as sentences:

• A file and a directory are both nodes, by inheritance.
• A directory owns zero or more nodes, by composition.
• Every criterion and every combinator is a Filter.
• And and Or each hold two or more filters as operands, and Not holds a single operand, all by aggregation.
• ModifiedWithin has a Clock injected into it, meaning handed in at construction rather than reached for from inside.

Why one Composite uses *-- and the other uses o--

There are two Composites in one diagram and they are the same shape: an abstract type, a leaf, and a branch that holds a collection of the abstract type. The arrows differ, and the difference is a claim about lifetime.

Directory *-- Node is composition because removing a directory removes its contents.

And o-- Filter is aggregation because a filter object is intended to be shared between two queries.

Nothing in the code enforces that sharing safely. Extension('.log').ext = '.txt' mutates a filter that two live queries are holding, and both silently change meaning. Freeze them (@dataclass(frozen=True)) if you mean it; if you do not, the honest arrow is composition.

What this class structure assumes

A class diagram is a frozen bet about what will change. Every abstract type says “I expect this to vary”; every fixed method signature says “I expect this to hold forever”. Naming those bets out loud is the transferable skill here — the specific find clone is not going to be your job, but the habit is. The general version of this argument is What a class structure assumes.

Assumed to vary — and therefore given an abstract type or a parameter. The right-hand column is the bill you would pay if the bet were wrong in the other direction.

Assumed fixed — and therefore baked into the structure.

The load-bearing assumption is the signature matches(node) -> bool. Those four tokens commit to three things at once.

1. A match is decidable from one node in isolation. No criterion may depend on another node, which quietly forbids “the ten largest files”, “files that are duplicates of each other”, and “files newer than their sibling”.
2. A match is a boolean, not a score. There is no ranking, so no fuzzy name matching and no “best” results.
3. The criterion is opaque code rather than inspectable data. That is what forbids pushing it into an index.

Beyond the signature, four more things are assumed fixed:

• The tree is finite and fully walkable. Directory.add must enforce this, because p.add(c); c.add(p) is one line and walk, size() and path all recurse forever after it.
• Each node is visited at most once. The same guard buys this, by refusing a node a second parent.
• Traversal order is pre-order, and is not part of the query. You cannot ask for results depth-first-post-order or sorted by size.
• A node knows its parent, so that path can be derived by walking upwards instead of stored.

What a different assumption would have produced

This is the part interviewers reach for when they want to know whether you understood your own design. Each bullet flips one assumption and names the artefact you would build instead.

• If speed were the requirement instead of expressiveness, the whole artefact changes. Criteria become entries in an inverted index — a lookup table from name or extension straight to the matching paths — And and Or become set intersection and union over posting lists, and the filter tree stops being code to run and becomes a query plan to rewrite. The objects survive only if a query optimiser can read them, which means filters have to be data. That is the same requirement that shows up in What interviewers probe under “why not just pass lambdas”.
• If criteria had to be relational — “the ten largest”, “duplicates” — matches(node) -> bool is simply the wrong signature and no amount of composition rescues it. The design becomes a pipeline of stream operators — transform, filter, take the largest ten — where each stage sees the whole stream. That is a different object model with a different failure mode: stages that must buffer.
• If results had to be ranked, matches returns a score instead of a boolean, And and Or become something like multiply and maximum, and the results must be sorted — which means buffering everything, which destroys the streaming property that Extension 3 stream instead of building a list spends a whole section defending.
• If the tree were remote and paginated, as it is for cloud object storage, Directory.children cannot be a list. Children become an iterator that makes network calls, size() stops being a cheap sum, and pruning stops being an optimisation and becomes the difference between a query that finishes and one that does not.
• If queries had to be saved to disk and reloaded, filters need a stable serialised form, and you would add a visitor or a to_dict() to every criterion — turning a five-line class into a fifteen-line one, paid across every criterion in the library.

5. Decision 1: the parameter list, and the requirement that kills it

How much can a keyword-argument search function actually express? The question has an exact numeric answer, and computing it — then watching where the edit lands when a new criterion arrives — is what buries the shape.

The naive version, written honestly

Write the naive one first. It is not a straw man; it is a perfectly reasonable v1. Notice the shape of the loop body: five if ... continue guards in a row, each one silently meaning “and”.

from __future__ import annotations

from abc import ABC, abstractmethod
from fnmatch import fnmatch
from typing import Iterator, Protocol


def find_naive(root, name=None, min_size=None, extension=None, is_dir=None):
    """Every criterion is optional; supplying two means AND. There is no third option."""
    out = []
    for node in walk(root):
        if name is not None and not fnmatch(node.name, name):
            continue
        if min_size is not None and node.size() < min_size:
            continue
        if extension is not None and not node.name.endswith(extension):
            continue
        if is_dir is not None and isinstance(node, Directory) != is_dir:
            continue
        out.append(node)
    return out

That block also carries the imports the rest of the chapter needs, so three of them are worth a line each:

• from __future__ import annotations makes Python treat type annotations as plain text instead of evaluating them, which is what lets Filter | None — syntax introduced in Python 3.10 — run on Python 3.9.
• ABC is Python’s abstract base class: a class that refuses to be instantiated while any method marked @abstractmethod is still unimplemented, so forgetting to write matches fails at construction rather than at call time.
• fnmatch matches a filename against a shell wildcard pattern such as *.txt.

find_naive names walk and Directory, which this chapter defines later, in Decision 2 composite for the tree and what size then means. That is fine — Python resolves those names when the function runs, not when it is defined. Working python the query the parameter list could not express runs it against a real tree and shows exactly which results it loses.

Now the requirement: over 10 MB OR ending in .log, and not under /tmp. There is no argument list that says it. Adding size_or_extension=True is the moment the design is lost.

Counting what each shape can express

Call each of the five criteria an atom — an indivisible yes/no fact about a node — and count how many distinct questions each design can ask. The arithmetic below is four numbers; the last one is the point.

criteria available                             5
combinations a flag list can express (AND only)
  2 ^ 5                                       =  32
distinct boolean predicates over 5 atoms
  2 ^ 32                                      =  4294967296
fraction of them the flag list reaches
  32 / 4294967296                             =  0.00000000745

Where the two exponents come from is worth one sentence each.

The flag list reaches 2 ^ 5 queries because each of the five criteria is independently either supplied or omitted, and supplying several can only mean and.

The full space is 2 ^ 32 because five yes/no atoms have 2 ^ 5 = 32 possible combinations of truth values, and a boolean question is nothing more than a choice of which of those 32 rows to accept — one independent yes/no decision per row.

The parameter list reaches 32 of 4.3 billion expressible queries, and the 32 it reaches are the conjunctions — a conjunction being a query built only from and. That is the sentence to say.

Every OR, every NOT, and every parenthesised mixture is outside its range, and no amount of extra keyword arguments closes the gap, because the gap is doubly exponential: adding one criterion doubles the flag list’s reach and squares the space it is failing to reach.

Where the edit lands

The other cost is maintenance. Take one concrete new criterion — “modified in the last 7 days” — and ask what each design makes you touch.

Cyclomatic complexity is a count of independent paths through a function — roughly, one plus the number of branches. It matters because it is also the number of test cases needed to cover the function.

Every criterion added to find_naive adds a branch to a function that already exists and must be retested. Every criterion added to the filter design adds a class that starts with no callers.

What composition costs — say this before you are asked

A query is now a tree of small objects. A failing search gives you “0 results” from a seven-node expression with no indication of which node did the rejecting. Debugging needs an explain() walk that the flag version got for free by being one function.

Indirection also hides evaluation order. And short-circuits left to right, so an expensive ModifiedWithin placed first stats every node, and nothing in the design stops you.

Two terms there. To short-circuit is to stop evaluating as soon as the answer is settled: an And that sees a False never asks the rest. To stat a file is to make the system call that fetches its metadata — size, timestamps — which is the expensive part.

A flag list, being one hand-written function, put the cheap checks first by accident.

6. Decision 2: Composite for the tree, and what size() then means

Now the tree half of the design: one interface shared by files and directories, the short traversal that falls out of it, and the one question that interface cannot answer honestly.

Composite is the pattern of giving a leaf and a branch the same interface so that callers never ask which they are holding. Here that interface is Node, and the two questions it promises to answer are path and size().

The Node interface and its two subclasses

Three classes below. Read Node first — it holds everything both subclasses share and declares the one thing neither can skip. Then compare the two size() implementations at the bottom of File and Directory: one returns a stored number, the other recurses.

class Node(ABC):
    def __init__(self, name: str, mtime: float = 0.0) -> None:
        self.name, self.mtime = name, mtime
        self.parent: Directory | None = None

    @property
    def path(self) -> str:
        if self.parent is None:
            return self.name
        base = self.parent.path
        return f"{base}/{self.name}" if base != "/" else f"/{self.name}"

    @abstractmethod
    def size(self) -> int: ...


class File(Node):
    def __init__(self, name: str, size_bytes: int, mtime: float = 0.0) -> None:
        super().__init__(name, mtime)
        self.size_bytes = size_bytes

    def size(self) -> int:
        return self.size_bytes


class Directory(Node):
    def __init__(self, name: str, mtime: float = 0.0) -> None:
        super().__init__(name, mtime)
        self.children: list[Node] = []

    def add(self, *children: Node) -> "Directory":
        for c in children:
            if not isinstance(c, Node):
                raise TypeError(f"not a Node: {c!r}")
            if c.parent is not None:                   # a tree, not a DAG: a second
                raise ValueError(f"{c.name} already has a parent; "
                                 "a tree is not a DAG")   # parent rewrites `path`
            n = self
            while n is not None:                       # d.add(d) is a one-line cycle
                if n is c:
                    raise ValueError("that would make a cycle")
                n = n.parent
            c.parent = self
            self.children.append(c)
        return self

    def size(self) -> int:                    # the branch delegates to its leaves
        return sum(c.size() for c in self.children)

Three pieces of Python syntax in there do real design work:

• @abstractmethod on size is the enforcement mechanism. Node inherits from ABC, so any subclass that fails to define size cannot be instantiated at all. The promise the interface makes is checked by the language rather than by a comment.
• @property lets path be written as a method but read as a field (node.path, no parentheses), which keeps the caller from caring that it is computed by walking up the parent chain.
• mtime is the standard Unix name for a file’s modification time, stored as seconds since 1970.

Why add is where the tree invariants live

add looks like bookkeeping. It is really where two of What this class structure assumes’s fixed assumptions are enforced, because nothing else in the design can hold them up.

Re-parenting. Setting c.parent = self unconditionally would mean that adding a node to a second directory silently moves it. The node then reports its new path in the old tree as well as the new one, so UnderPath starts answering differently for queries that were built before the move, and walk reports the same node twice. The if c.parent is not None guard is what refuses that.

Cycles. p.add(c); c.add(p) builds a cycle in one line, after which walk, size() and path each recurse until Python gives up. The while n is not None loop walks up from the new parent looking for the child; finding it means the link would close a loop.

A tree is not a DAG and not a graph, and the only place that can say so is the method that builds one.

What Directory.size() costs

Directory.size() summing the subtree is a decision, not an obvious truth, and it changes what a query means.

Real find -size +10M tests the directory entry’s own st_size, typically one block (4096 bytes on ext4), so a directory effectively never matches. This implementation makes /var match a 10 MB filter because its contents total 32 MB.

Both are defensible; only one is what your user expects. Working python the query the parameter list could not express asserts the difference rather than describing it.

The cost of Composite here is exactly this: the uniform interface invites you to ask leaf questions of branches, and some of those questions have no leaf-shaped answer.

size() is one. mtime on a directory is another — it is the time the directory’s own entry list changed, not the newest file inside it, which is a distinction that has burned every “sync only what changed” tool ever written.

The traversal

Here is where Composite pays. walk is pre-order — each node is reported before the nodes beneath it — recursive, and it never asks what kind of node it has except to decide whether there is anything below it.

Four of its lines are the traversal proper (yield node, the isinstance check, the loop, the yield from); the three-line if in the middle is the pruning clause, and deleting it leaves a working walker.

def walk(node: Node, descend: "Filter | None" = None) -> Iterator[Node]:
    yield node
    if isinstance(node, Directory):
        for child in node.children:
            if isinstance(child, Directory) and descend is not None \
                    and not descend.matches(child):
                continue                       # prune: skip the whole subtree
            yield from walk(child, descend)

yield makes this a generator: calling walk runs no code at all, and each yield hands one node back to the caller and freezes the function until the caller asks for the next one. yield from delegates to a nested generator, relaying everything the recursive call produces.

Together they are why the traversal can be infinite-in-principle and cheap-in-practice, which Extension 3 stream instead of building a list prices.

descend is a second predicate, and Extension 2 not and why negation does not commute with traversal is about why it cannot be the first one.

7. Decision 3: the filter algebra

Now the predicate half: one abstract type, three combinators, and the Python operators that make a query read like a sentence.

The abstract type and its three combinators

Filter declares one method and supplies three. The one it declares — matches — is what every criterion must write. The three it supplies build combinations, and the key detail is their return types: every one of them returns a Filter.

from __future__ import annotations

class Filter(ABC):
    @abstractmethod
    def matches(self, node: Node) -> bool: ...

    def __and__(self, other: "Filter") -> "Filter":
        return And(self, other)

    def __or__(self, other: "Filter") -> "Filter":
        return Or(self, other)

    def __invert__(self) -> "Filter":
        return Not(self)


class And(Filter):
    def __init__(self, *parts: Filter) -> None:
        self.parts = parts

    def matches(self, node: Node) -> bool:
        return all(p.matches(node) for p in self.parts)


class Or(Filter):
    def __init__(self, *parts: Filter) -> None:
        self.parts = parts

    def matches(self, node: Node) -> bool:
        return any(p.matches(node) for p in self.parts)


class Not(Filter):
    def __init__(self, part: Filter) -> None:
        self.part = part

    def matches(self, node: Node) -> bool:
        return not self.part.matches(node)

And, Or and Not inherit from Filter and hold Filters, which is the same leaf-and-branch shape as the tree — applied to the predicate instead of to the data. Given its own name, that shape is the Specification pattern: a business rule wrapped as an object that can be combined with other rules.

Defining __and__, __or__ and __invert__ is the Python-specific move. Those are the hooks Python calls when it sees the &, | and ~ operators, so the query reads as (a | b) & ~c instead of And(Or(a, b), Not(c)).

That convenience costs one gotcha worth naming. & binds tighter than | in Python, so a | b & c means a | (b & c) and the parentheses in (a | b) & ~c are not optional. And neither operator short-circuits the way the keywords and/or do, so a | b always evaluates both — both constructors, not both predicates, since evaluation happens later, inside matches.

The criteria themselves

With combination handled by the type, each criterion shrinks to a constructor and one method. Read them for what they do not mention: no traversal, no other criterion, no configuration.

class NameMatches(Filter):
    def __init__(self, pattern: str) -> None:
        self.pattern = pattern

    def matches(self, node: Node) -> bool:
        return fnmatch(node.name, self.pattern)


class Extension(Filter):
    def __init__(self, ext: str) -> None:
        self.ext = ext

    def matches(self, node: Node) -> bool:
        return node.name.endswith(self.ext)


class LargerThan(Filter):
    def __init__(self, nbytes: int) -> None:
        self.nbytes = nbytes

    def matches(self, node: Node) -> bool:
        return node.size() > self.nbytes


class UnderPath(Filter):
    def __init__(self, prefix: str) -> None:
        self.prefix = prefix

    def matches(self, node: Node) -> bool:
        p = self.prefix.rstrip("/") or "/"     # "/tmp/" and "/tmp" mean the same
        sep = "" if p == "/" else "/"          # or the root builds the prefix "//"
        return node.path == p or node.path.startswith(p + sep)


class IsFile(Filter):
    def matches(self, node: Node) -> bool:
        return isinstance(node, File)


def find(root: Node, where: Filter,
         descend: Filter | None = None) -> Iterator[Node]:
    """Traversal, predicate and sink are three separate things."""
    return (n for n in walk(root, descend) if where.matches(n))

None of those criteria runs past a handful of lines, and each mentions nothing but the node in front of it. IsFile is three lines and needs no constructor at all; UnderPath is the longest because prefix normalisation is genuinely fiddly, and Working python the query the parameter list could not express asserts why those two lines exist.

find itself is a single generator expression. It pulls nodes from walk and forwards the ones where accepts, and it knows the name of no criterion at all — which is precisely why adding one requires no edit to it.

8. Working Python: the query the parameter list could not express

Running the design against a small tree is what makes it concrete, and the most useful assertion below is the one that is correct and still not what the user meant.

The tree

Twelve nodes: seven directories and five files. Every later assertion counts against this shape, so it is worth memorising the sizes — python3 is 20 MB, old.log is 30 MB, junk.log is 50 MB, syslog.log is 2 MB, and doc.txt is 1 KB.

MB = 1024 * 1024
root = Directory("/").add(
    Directory("usr").add(
        Directory("bin").add(File("python3", 20 * MB)),
        Directory("share").add(File("doc.txt", 1024)),
    ),
    Directory("var").add(
        Directory("log").add(File("syslog.log", 2 * MB), File("old.log", 30 * MB)),
    ),
    Directory("tmp").add(File("junk.log", 50 * MB)),
)

assert [n.path for n in walk(root)][:4] == ["/", "/usr", "/usr/bin", "/usr/bin/python3"]
assert root.size() == (20 + 30 + 2 + 50) * MB + 1024

The first assertion pins the traversal order: /, then /usr, then /usr/bin, then the file inside it — a parent always before its children.

The second confirms that root.size() really does sum the whole subtree: the four multi-megabyte files total 102 MB, plus the 1024-byte text file.

The killer query

This is the requirement from Decision 1 the parameter list and the requirement that kills it, written as one expression. Look at how the English maps onto the operators, then look at how many directories are in the answer.

# "over 10 MB OR ending in .log, and not under /tmp"
query = (LargerThan(10 * MB) | Extension(".log")) & ~UnderPath("/tmp")
hits = sorted(n.path for n in find(root, query))
assert hits == ["/", "/usr", "/usr/bin", "/usr/bin/python3",
                "/var", "/var/log", "/var/log/old.log", "/var/log/syslog.log"], hits

That assertion is the one worth pointing at. It is correct, it is exactly what the composition asked for, and it is not what the user meant — which is the honest state of a design decision, not a bug.

Eight hits, and five of them (/, /usr, /usr/bin, /var, /var/log) are directories. They are there because Decision 2 composite for the tree and what size then means made Directory.size() mean “everything underneath”, so /usr reports 20 MB and clears the filter.

The one-object fix, and one new criterion

Two things happen below, and both are the payoff. Adding IsFile() to the front of the query corrects the result without touching any existing class. Then SmallerThan — a criterion the library never anticipated — is defined and used, again with no edit to walk, find or Filter.

files_only = IsFile() & query
assert sorted(n.path for n in find(root, files_only)) == [
    "/usr/bin/python3", "/var/log/old.log", "/var/log/syslog.log"]


# Adding a criterion is a new class, not an edit. Nothing above changes.
class SmallerThan(Filter):
    def __init__(self, nbytes: int) -> None:
        self.nbytes = nbytes

    def matches(self, node: Node) -> bool:
        return node.size() < self.nbytes


tiny_docs = IsFile() & SmallerThan(4096) & NameMatches("*.txt")
assert [n.path for n in find(root, tiny_docs)] == ["/usr/share/doc.txt"]

The fix is one object prepended to an existing query, and the extension is one class with no registration step. That is the whole return on Decision 3 the filter algebra.

The guards, asserted rather than described

Directory.add refuses three things, and the block below proves each one. The first two cases share a loop: a string is not a Node at all, and /usr already has a parent. The third case builds a two-node tree and tries to close it into a cycle.

# `Directory.add` is the only place that can keep a tree a tree.
for bad in ("/etc/passwd",            # not a Node at all
            root.children[0]):        # /usr already has a parent: adding it here
    try:                              # would rewrite its path in the FIRST tree
        Directory("d").add(bad)
        raise AssertionError(f"add accepted {bad!r}")
    except (TypeError, ValueError):
        pass

p = Directory("p").add(Directory("c"))
try:
    p.children[0].add(p)              # p.add(c); c.add(p) -- one line, and walk(),
    raise AssertionError              # size() and path all recurse forever
except ValueError:
    pass

A re-parented node reports a different path in the tree it came from, so a query built before the move quietly changes meaning. A cycle makes walk, size() and path recurse until the interpreter stops them. Neither can be caught anywhere but here.

Why UnderPath normalises its prefix

Those two lines in UnderPath look like defensive noise. They are not. "/" + "/" is "//", which is a prefix of nothing, and a trailing slash on "/tmp/" makes the prefix "/tmp//".

# UnderPath at the root, and with a trailing slash: "/" + "/" is not a prefix.
assert [n.path for n in find(root, UnderPath("/tmp/"))] == ["/tmp", "/tmp/junk.log"]
assert len(list(find(root, UnderPath("/")))) == 12          # every node, not one
assert list(find(root, ~UnderPath("/"))) == []              # and nothing at all

Without the normalisation, UnderPath("/") would match only the root; ~UnderPath("/") — the natural way to write “everything below the root” — would keep every node except the root; and UnderPath("/tmp/") would silently match nothing at all.

The naive function, on the same tree

Now run Decision 1 the parameter list and the requirement that kills it’s find_naive against this tree, so the expressiveness gap stops being arithmetic and becomes two lists of paths.

The requirement is “over 10 MB or ending in .log, and not under /tmp”. Supplying both min_size and extension is the closest the parameter list can get, and it means and.

# Two criteria means AND, so this asks for ">10 MB AND .log" -- under-matching:
# /var/log/syslog.log is a 2 MB .log file and the requirement wanted it.
assert [n.path for n in find_naive(root, min_size=10 * MB, extension=".log")] == [
    "/var/log/old.log", "/tmp/junk.log"]

# Drop the size and it over-matches instead: /tmp/junk.log is back, and there is
# no argument that says "not under /tmp".
assert [n.path for n in find_naive(root, extension=".log")] == [
    "/var/log/syslog.log", "/var/log/old.log", "/tmp/junk.log"]

Two results or three, and neither list is the answer. The filter version got it in one expression and, with IsFile() prepended, returned exactly /usr/bin/python3, /var/log/old.log and /var/log/syslog.log.

9. Extension 1: files modified in the last 7 days

A new criterion should cost one class and nothing else, and “modified in the last 7 days” puts that claim to the test — it is also the first criterion whose answer depends on something other than the node.

It costs exactly one class, with no edit to walk, find, Filter, or any existing criterion.

Three classes below, and only the last one is a criterion. Clock describes what a source of “now” must look like; FakeClock is a test double that freezes time; ModifiedWithin is the criterion, and the thing to notice is that it never calls time.time().

class Clock(Protocol):
    def now(self) -> float: ...


class FakeClock:
    def __init__(self, t: float) -> None:
        self.t = t

    def now(self) -> float:
        return self.t


class ModifiedWithin(Filter):
    def __init__(self, seconds: float, clock: Clock) -> None:
        self.seconds, self.clock = seconds, clock

    def matches(self, node: Node) -> bool:
        return self.clock.now() - node.mtime <= self.seconds


DAY = 86400.0
clock = FakeClock(t=100 * DAY)
recent = Directory("/r").add(File("fresh.log", 10, mtime=97 * DAY),
                             File("stale.log", 10, mtime=80 * DAY))
week = ModifiedWithin(7 * DAY, clock)
assert [n.path for n in find(recent, IsFile() & week)] == ["/r/fresh.log"]
assert [n.path for n in find(recent, IsFile() & ~week)] == ["/r/stale.log"]

A Protocol, in Python, is a type that describes a shape rather than an ancestry: anything with a now() returning a float counts as a Clock, so FakeClock satisfies it without inheriting from it or being registered anywhere.

Pinning “now” at day 100 makes the assertions pure arithmetic. The file touched on day 97 is three days old and inside the seven-day window; the one touched on day 80 is twenty days old and outside it; and ~week — the same object, negated — picks out exactly the complement.

What changes: one class. What does not: everything. Why: the traversal never enumerated the criteria, so it has nothing to learn about a new one.

What it costs. ModifiedWithin is the first criterion that depends on something other than the node, so it takes a Clock. Handing an object its collaborators at construction time instead of letting it reach for a global is called dependency injection. The same argument is made over a 120-second seat hold in 05, arriving here for a different reason.

It also breaks a property the other filters had. matches is no longer a pure function of the node — one that returns the same answer for the same input every time — so the same query object gives different answers at different times, and caching results is now unsound.

10. Extension 2: NOT, and why negation does not commute with traversal

Here is the deepest idea in the chapter: the same filter object means two different things depending on which argument you pass it to, and no design can infer which you meant.

Not is six lines and already written. The interesting part is that there are now two places a predicate can go, and negation means different things in each.

• As a matcher: ~UnderPath("/tmp") visits every node under /tmp, evaluates it, and discards it.
• As a pruner: descend=~UnderPath("/tmp") never enters the directory at all.

The size of the difference

Same result set here. Wildly different work. The arithmetic below assumes a million-node tree of which 700,000 nodes sit under the subtree being excluded — the shape you get when one enormous directory is the thing you are trying to skip.

nodes under the root                           1000000
nodes under the pruned subtree                 700000
nodes evaluated with /tmp as a matcher
  1000000                                     
nodes evaluated with /tmp as a pruner
  1000000 - 700000                            =  300000
work avoided
  700000 / 1000000                            =  0.7

Seventy percent of the walk disappears, and nothing about the answer changes.

Measuring it on the real tree

The result sets are not always the same, though, which is the trap. To see the difference you need to count nodes visited, not nodes returned — so wrap the filter in something that keeps a tally.

counted: list[str] = []


class Counting(Filter):
    """Wraps a filter and records every node it is asked about."""

    def __init__(self, inner: Filter) -> None:
        self.inner = inner

    def matches(self, node: Node) -> bool:
        counted.append(node.path)
        return self.inner.matches(node)


not_tmp = ~UnderPath("/tmp")

counted.clear()
as_matcher = sorted(n.path for n in find(root, Counting(IsFile() & not_tmp)))
visited_matching = len(counted)

counted.clear()
as_pruner = sorted(n.path for n in find(root, Counting(IsFile()), descend=not_tmp))
visited_pruning = len(counted)

assert as_matcher == as_pruner                     # same answer
assert visited_matching == 12                      # every node, including /tmp/junk.log
assert visited_pruning == 10                       # /tmp and its child never existed

Counting is a decorator: an object that implements the same interface as the thing it wraps and adds behaviour by calling through to it. Here it records every node it is asked about, which is how the two visit counts are measured rather than asserted.

The tree from Working python the query the parameter list could not express has twelve nodes. Pruning /tmp removes the directory and the one file inside it, leaving ten.

Ten, not eleven: this walk prunes before yielding, so the pruned directory is not reported either. Real find -prune reports the directory and skips its contents. That is a third semantic, and the fact that a seven-line traversal has three defensible readings of “skip” is why the predicate cannot be inferred.

The same object, two meanings

Now negate a predicate about node type instead of location. IsFile() is the sharpest case, because as a pruner it makes the walk collapse to nothing.

# As a matcher, "not a file" means "do not report files".
assert len(list(find(root, ~IsFile()))) == 7       # the 7 directories

# As a pruner, the same object means "do not enter directories", so no
# directory is ever entered and the walk yields only the root.
assert len(list(find(root, IsFile(), descend=IsFile()))) == 0
assert [n.path for n in walk(root, IsFile())] == ["/"]

The second assertion is the whole lesson in one line. IsFile() as a pruner says “only descend into things that are files”; no directory is ever a file; so every child directory of the root is skipped before it is even reported, and the walk yields exactly one node — the root, which is not a file either, hence zero results from find.

The third assertion pins that: not “stops at depth 1” but “never reaches depth 1”.

Negation is not a property of a criterion; it is a property of a criterion in a position. The find command exposes this as the difference between -not -path and -prune, and the reason -prune is famously confusing is that it is an action masquerading as a test. Keeping matches and descend as two arguments makes the distinction structural instead of folkloric.

What it costs. Two predicates is one more thing to explain, and a caller who passes the wrong one gets a silently wrong result rather than an error.

The alternative — inferring pruning from the match expression — is a query optimiser. Writing a correct one requires knowing which criteria are monotone down the tree, meaning that if the criterion is false for a directory it is false for everything inside it. UnderPath is monotone; LargerThan is not, because a small directory can contain a huge file.

11. Extension 3: stream instead of building a list

The last decision is whether to hand results back one at a time or collect them all first — and the costs of streaming deserve more space than its benefits, because the costs are the half candidates skip.

find already returns a generator, which was a choice, and it is worth pricing both directions.

What laziness looks like when you count

Three ways of consuming the same query, with the Counting decorator from Extension 2 not and why negation does not commute with traversal reporting how much of the tree each one actually touched.

from itertools import islice

counted.clear()
first = next(iter(find(root, Counting(Extension(".log")))))
assert first.path == "/var/log/syslog.log"
assert len(counted) == 9        # stopped 3 nodes early, mid-tree

counted.clear()
everything = list(find(root, Counting(Extension(".log"))))
assert len(counted) == 12       # the whole tree, every time
assert len(everything) == 3

assert [n.path for n in islice(find(root, Extension(".log")), 2)] == [
    "/var/log/syslog.log", "/var/log/old.log"]

next() pulls exactly one result and stops, which is why the counter reads 9 out of 12 nodes: the walk was abandoned the moment the first .log file appeared.

list() drains the generator and therefore always visits all twelve.

islice takes the first n items of any iterator without materialising the rest, so asking for two costs two.

What streaming buys on a real root

Twelve nodes hides the point. Scale the same walk to a million nodes at two microseconds each, and assume most of them match.

nodes walked                                   1000000
per-node work, microseconds                    2
seconds before a list returns its first result
  1000000 x 2 / 1000000                       =  2
bytes retained per match by a list             200
peak memory for a 1 M-match list, bytes
  1000000 x 200                               =  200000000

A list cannot return anything until it has walked all million nodes, which is two seconds of silence. If most of them match, holding 200 bytes per result costs 200 MB.

A generator returns the first hit in microseconds and holds nothing but a recursion stack proportional to the depth of the tree.

What streaming costs

This table is what interviewers want, and it is the half most candidates never reach: each row is a property you gave up, paired with how it bites.

Two of those rows have standard mitigations.

For deferred exceptions, use a policy object — on_error(node, exc) -> bool — rather than a try inside walk, because walk cannot know whether a permission error should end the search or be skipped.

For yield from depth, use os.walk-style iteration with an explicit stack, meaning the traversal keeps its own list of pending directories instead of using the call stack. It is faster and reads worse, so profile before paying that.

12. What interviewers probe

These are the follow-ups the design invites, and the answer that lands for each. The right column is meant to be said out loud, roughly as written.

Three terms from that table:

• A symlink is a file whose contents are a path to another file, so a directory can contain a link back to its own ancestor and a naive walk loops forever.
• st_dev and st_ino are the device number and inode number the filesystem reports; together they identify a file uniquely no matter how many names point at it.
• A lambda is an anonymous inline function — lambda n: n.size() > 10 — which does the same job as a filter object and can be called but not asked about.

Cheat sheet

Related: 02 for the six steps of the interview and 03 for open-closed, Composite and Specification treated as topics in their own right. 05 — Movie Ticket Booking argues for the injected clock that ModifiedWithin needs. 07 — Vending Machine sits at the opposite end of this spectrum: behaviour that lives in states rather than in composed predicates.