Design Unix file search

Question: Design Unix file search

Companies: Amazon

Difficulty: Hard

Problem statement

Model a find-like file search over a directory tree with composable filters (name pattern, size, type, extension) that are easy to extend.

Requirements

• Search a directory tree from a root and return every entry that matches a filter, like find.
• Built-in filters: name glob (*.py), size (more than, less than, or exactly N bytes; regular files only, so a directory never matches), type (file, directory, symlink), extension (case-insensitive, one or many).
• Filters compose with AND, OR and NOT to any depth, for example (*.log OR *.md) AND NOT old*.
• Adding a new filter (modified time, owner, content) means adding one class. The searcher and the other filters do not change.
• Search options: max depth, min depth, BFS or DFS order, follow symlinks or not, and a prune filter (do not descend into directories that match, such as .git). Results stream lazily, so the caller can stop after the first N matches.
• Unreadable directories and symlink loops are reported and skipped. They never abort the search.
• Out of scope: actions on results (-exec, -delete), parsing a find command line, content indexing (locate), and network file systems.

Core objects

• FileType (enum): FILE, DIRECTORY, SYMLINK.
• Node: one entry in the tree: name, type, size, inode, children (directories), target (symlinks), readable flag.
• Filter (ABC): matches(node) -> bool. It also overloads &, | and ~, so filters compose like expressions.
• NameFilter, SizeFilter, TypeFilter, ExtensionFilter: leaf predicates. Each one checks a single attribute.
• AndFilter, OrFilter, NotFilter: composite filters that combine child filters, with short-circuit evaluation.
• Comparison (enum): GT, LT, EQ for SizeFilter. Order (enum): BFS or DFS, the traversal strategy.
• SearchOptions: immutable settings for one search (depth limits, order, symlinks, prune).
• FileSearcher: walks the tree, applies the filter, and yields Match results (the path at which the node was reached, plus the node). It keeps no state between calls.

Class design

{"type":"excalidraw","elements":[
 {"type":"text","id":"legend","x":0,"y":560,"text":"Solid arrows: extends Filter. Dashed arrows: holds child Filters.","fontSize":16},
 {"type":"rectangle","id":"name","x":0,"y":0,"width":220,"height":70,"label":{"text":"NameFilter\npattern: str"}},
 {"type":"rectangle","id":"size","x":260,"y":0,"width":220,"height":70,"label":{"text":"SizeFilter\nop, size"}},
 {"type":"rectangle","id":"type","x":520,"y":0,"width":220,"height":70,"label":{"text":"TypeFilter\ntype: FileType"}},
 {"type":"rectangle","id":"ext","x":780,"y":0,"width":220,"height":70,"label":{"text":"ExtensionFilter\nextensions"}},
 {"type":"rectangle","id":"filter","x":370,"y":220,"width":260,"height":80,"label":{"text":"Filter (abstract)\nmatches(node)"}},
 {"type":"rectangle","id":"and","x":110,"y":440,"width":220,"height":70,"label":{"text":"AndFilter\nfilters: List"}},
 {"type":"rectangle","id":"or","x":390,"y":440,"width":220,"height":70,"label":{"text":"OrFilter\nfilters: List"}},
 {"type":"rectangle","id":"not","x":670,"y":440,"width":220,"height":70,"label":{"text":"NotFilter\ninner: Filter"}},
 {"type":"arrow","id":"name-f","x":110,"y":70,"width":300,"height":150,"start":{"id":"name"},"end":{"id":"filter"}},
 {"type":"arrow","id":"size-f","x":370,"y":70,"width":100,"height":150,"start":{"id":"size"},"end":{"id":"filter"}},
 {"type":"arrow","id":"type-f","x":630,"y":70,"width":-100,"height":150,"start":{"id":"type"},"end":{"id":"filter"}},
 {"type":"arrow","id":"ext-f","x":890,"y":70,"width":-300,"height":150,"start":{"id":"ext"},"end":{"id":"filter"}},
 {"type":"arrow","id":"and-f","x":190,"y":440,"width":210,"height":-140,"start":{"id":"and"},"end":{"id":"filter"}},
 {"type":"arrow","id":"and-h","x":250,"y":440,"width":190,"height":-140,"start":{"id":"and"},"end":{"id":"filter"},"strokeStyle":"dashed"},
 {"type":"arrow","id":"or-f","x":470,"y":440,"width":10,"height":-140,"start":{"id":"or"},"end":{"id":"filter"}},
 {"type":"arrow","id":"or-h","x":530,"y":440,"width":-10,"height":-140,"start":{"id":"or"},"end":{"id":"filter"},"strokeStyle":"dashed"},
 {"type":"arrow","id":"not-f","x":750,"y":440,"width":-190,"height":-140,"start":{"id":"not"},"end":{"id":"filter"}},
 {"type":"arrow","id":"not-h","x":810,"y":440,"width":-210,"height":-140,"start":{"id":"not"},"end":{"id":"filter"},"strokeStyle":"dashed"}
]}

The searcher and what it works on:

{"type":"excalidraw","elements":[
 {"type":"rectangle","id":"searcher","x":0,"y":140,"width":240,"height":110,"label":{"text":"FileSearcher\nsearch(root, filter,\nopts, on_error)\nresolve(node, opts)"}},
 {"type":"rectangle","id":"opts","x":520,"y":0,"width":240,"height":110,"label":{"text":"SearchOptions\nmax_depth, order\nfollow_symlinks\nprune"}},
 {"type":"rectangle","id":"filter","x":520,"y":280,"width":240,"height":80,"label":{"text":"Filter (abstract)\nmatches(node)"}},
 {"type":"rectangle","id":"node","x":0,"y":440,"width":260,"height":110,"label":{"text":"Node\nname, type, size, inode\nchildren, target\nreadable, extension()"}},
 {"type":"arrow","id":"s-opts","x":240,"y":175,"width":280,"height":-120,"start":{"id":"searcher"},"end":{"id":"opts"},"label":{"text":"uses"},"strokeStyle":"dashed"},
 {"type":"arrow","id":"s-filter","x":240,"y":215,"width":280,"height":105,"start":{"id":"searcher"},"end":{"id":"filter"},"label":{"text":"applies"},"strokeStyle":"dashed"},
 {"type":"arrow","id":"opts-filter","x":640,"y":110,"width":1,"height":170,"start":{"id":"opts"},"end":{"id":"filter"},"label":{"text":"prune"}},
 {"type":"arrow","id":"node-node","x":260,"y":460,"width":1,"height":70,"points":[[0,0],[80,0],[80,70],[0,70]],"start":{"id":"node"},"end":{"id":"node"},"label":{"text":"children"}}
]}

Key flows

1. Build a filter. The caller combines leaf filters with operators: TypeFilter(FILE) & ExtensionFilter({"py"}) & SizeFilter(GT, 10_000). Each & returns an AndFilter. The result is an immutable expression tree, so one filter can be reused across searches and threads. Put cheap checks (type, extension) to the left of expensive ones (content, a stat call), because AndFilter stops at the first false.

2. Search (FileSearcher.search).

1. Put (root, root.name, depth 0) on a deque. BFS takes from the left. DFS takes from the right, with children pushed in reverse so that output stays in directory order.
2. Take the next entry. If the entry is a symlink and follow_symlinks is on, resolve it to its target. A dangling link stays a symlink.
3. If depth >= min_depth and filter.matches(node), yield a Match. The generator pauses here until the caller asks for more.
4. Decide whether to descend, using the table below. If yes, push each child with path/child and depth + 1.

Code

from __future__ import annotations
import fnmatch, itertools, operator
from abc import ABC, abstractmethod
from collections import deque
from dataclasses import dataclass, field
from enum import Enum
from typing import Callable, Iterator, Optional
_inodes = itertools.count(1)
class FileType(Enum):
    FILE = "f"
    DIRECTORY = "d"
    SYMLINK = "l"
@dataclass(eq=False)
class Node:
    name: str
    type: FileType
    size: int = 0
    children: list[Node] = field(default_factory=list)
    target: Optional[Node] = None
    readable: bool = True
    inode: int = field(default_factory=lambda: next(_inodes))
    @property
    def extension(self) -> str:
        dot = self.name.rfind(".")
        return self.name[dot + 1:].lower() if dot > 0 else ""   # ".bashrc" has none
class Filter(ABC):
    @abstractmethod
    def matches(self, node: Node) -> bool: ...
    def __and__(self, other: Filter) -> Filter: return AndFilter((self, other))
    def __or__(self, other: Filter) -> Filter: return OrFilter((self, other))
    def __invert__(self) -> Filter: return NotFilter(self)
@dataclass(frozen=True)
class NameFilter(Filter):
    pattern: str
    def matches(self, node: Node) -> bool:
        return fnmatch.fnmatchcase(node.name, self.pattern)
class Comparison(Enum):
    GT = "+"
    LT = "-"
    EQ = "="
_OPS = {Comparison.GT: operator.gt, Comparison.LT: operator.lt, Comparison.EQ: operator.eq}
@dataclass(frozen=True)
class SizeFilter(Filter):
    op: Comparison
    size: int
    def matches(self, node: Node) -> bool:
        return node.type is FileType.FILE and _OPS[self.op](node.size, self.size)
@dataclass(frozen=True)
class TypeFilter(Filter):
    type: FileType
    def matches(self, node: Node) -> bool:
        return node.type is self.type
@dataclass(frozen=True)
class ExtensionFilter(Filter):
    extensions: frozenset[str]
    def __post_init__(self) -> None:
        object.__setattr__(self, "extensions",
                           frozenset(e.lower().lstrip(".") for e in self.extensions))
    def matches(self, node: Node) -> bool:
        return node.extension in self.extensions
@dataclass(frozen=True)
class AndFilter(Filter):
    filters: tuple[Filter, ...]
    def matches(self, node: Node) -> bool:
        return all(f.matches(node) for f in self.filters)   # short-circuits
@dataclass(frozen=True)
class OrFilter(Filter):
    filters: tuple[Filter, ...]
    def matches(self, node: Node) -> bool:
        return any(f.matches(node) for f in self.filters)
@dataclass(frozen=True)
class NotFilter(Filter):
    inner: Filter
    def matches(self, node: Node) -> bool:
        return not self.inner.matches(node)
class Order(Enum):
    BFS = "bfs"
    DFS = "dfs"
@dataclass(frozen=True)
class SearchOptions:
    max_depth: Optional[int] = None
    min_depth: int = 0
    order: Order = Order.DFS
    follow_symlinks: bool = False
    prune: Optional[Filter] = None
@dataclass(frozen=True)
class Match:
    path: str
    node: Node
class FileSearcher:  # stateless: per-search state is local, so concurrent searches are safe
    def search(self, root: Node, flt: Filter, opts: SearchOptions = SearchOptions(),
               on_error: Callable[[str], None] = lambda msg: None) -> Iterator[Match]:
        frontier: deque[tuple[Node, str, int]] = deque([(root, root.name, 0)])
        visited: set[int] = set()
        while frontier:
            raw, path, depth = frontier.popleft() if opts.order is Order.BFS else frontier.pop()
            node = self._resolve(raw, opts)
            if depth >= opts.min_depth and flt.matches(node):
                yield Match(path, node)
            if node.type is not FileType.DIRECTORY:
                continue
            if (opts.max_depth is not None and depth >= opts.max_depth) or \
                    (opts.prune is not None and opts.prune.matches(node)):
                continue
            if node.inode in visited:
                on_error(f"already visited (loop or alias): {path}")
                continue
            visited.add(node.inode)
            if not node.readable:
                on_error(f"permission denied: {path}")
                continue
            kids = node.children if opts.order is Order.BFS else reversed(node.children)
            frontier.extend((c, f"{path}/{c.name}", depth + 1) for c in kids)
    @staticmethod
    def _resolve(node: Node, opts: SearchOptions) -> Node:
        if node.type is FileType.SYMLINK and opts.follow_symlinks and node.target:
            return node.target
        return node
def d(name: str, *kids: Node) -> Node: return Node(name, FileType.DIRECTORY, children=list(kids))
def f(name: str, size: int) -> Node: return Node(name, FileType.FILE, size)
if __name__ == "__main__":
    logs = d("logs", f("app.log", 5_000_000), f("old.log", 9_000_000))
    root = d("home", d("src", f("main.py", 2_000), f("util.py", 40_000), f("README.md", 900)),
             logs, d(".git", f("x.py", 50_000)), Node("latest", FileType.SYMLINK, target=logs))
    searcher = FileSearcher()
    big_py = TypeFilter(FileType.FILE) & ExtensionFilter(frozenset({".PY"})) \
        & SizeFilter(Comparison.GT, 10_000)
    opts = SearchOptions(prune=NameFilter(".git"))
    print([m.path for m in searcher.search(root, big_py, opts)])   # ['home/src/util.py']
    docs = (ExtensionFilter(frozenset({"log"})) | NameFilter("*.md")) & ~NameFilter("old*")
    opts = SearchOptions(follow_symlinks=True, order=Order.BFS)
    print([m.path for m in searcher.search(root, docs, opts, on_error=print)])
    # prints "already visited (loop or alias): home/latest", then
    # ['home/src/README.md', 'home/logs/app.log']  (BFS: shallower first)

Design patterns

• Composite: AndFilter, OrFilter and NotFilter are Filters that hold Filters. A tree of any depth gets evaluated through the single matches call. This is what makes the filters composable.
• Specification: each leaf filter is a reusable boolean rule about a Node. The operator overloads (&, |, ~) give a small DSL that reads like the find expression it replaces.
• Strategy: Order selects BFS or DFS with the same loop. The deque end changes and nothing else does. A pluggable Filter used as prune is a second strategy, for deciding where not to descend.
• Iterator (generator): search yields matches lazily. Memory stays proportional to the frontier, not the result set, and callers can stop early.

Extensions

• New predicates (modified time, owner, permissions, empty file): add one Filter subclass that reads a new Node field. Nothing else changes. A ContentFilter(regex) is expensive, so put it last in an AndFilter. The short-circuit then reads a file only after cheaper checks pass.
• Real file system: put a FileSystem interface (list_dir, stat, readlink) behind Node, with an os.scandir adapter and an in-memory one for tests. scandir gives type without a stat call, so stat lazily only when a size or time filter asks.
• Parallel search on huge trees: replace the deque with a thread-safe work queue. Workers take a directory, list it, and push its subdirectories. The visited set becomes a lock-protected set, or a set sharded by inode. Filters are immutable, so workers share them freely. Output order is no longer deterministic. Say so, or sort at the end.
• find-style command line and actions: a parser (Interpreter) turns -name '*.py' -a ! -size +10k into the same filter tree. -print, -delete and -exec become Action objects (Command pattern) run on each Match, so actions stay out of the filters.

Interviewer expectations

Mid-level (L4)

• Defines a Filter interface with name, size, type and extension implementations, and a recursive walk that applies one filter. Supports AND of several filters, even if only through a list.
• Code runs and handles files compared with directories correctly.

Senior (L5)

• Uses Composite for AND, OR and NOT, with short-circuit evaluation and a readable composition API.
• Writes an iterative traversal (no recursion limit on deep trees) with max depth, pruning and lazy results.
• Brings up symlink loops, permission errors and dangling links without prompting, and handles each without aborting. Makes filters immutable and the searcher stateless, so concurrent use is safe.

Staff (L6+)

• Discusses cost-ordering of predicates, lazy stat calls, and the I/O-bound nature of the walk (scandir, readdir batching).
• Designs a parallel walker: work queue, shared visited set, and the trade-off against deterministic output.
• Separates the concerns clearly: the expression tree (what matches), the traversal (where to look) and the actions (what to do). Shows how a parser, an index or a remote file system plugs into each without changing the others.