Linux Find Command: LLD Design

Problem statement (interviewer prompt)

Design the class structure for a Unix-style find command. Support predicates: name (glob), size, mtime, type (file, dir, link); combine predicates with -and, -or, -not; recursive directory traversal with depth limit and follow-symlink option; -exec to run actions on matches. Optimise for extensible filters and clean separation between traversal and predicate evaluation.

The linux find LLD design centres on two orthogonal trees: a file-system tree (directories containing files and other directories) and a filter tree (predicates composed by boolean operators). A traversal layer walks the first tree and asks the second whether each node matches, then hands the survivors to an action.

classDiagram
  class FindCommand {
    +root : Path
    +filter : Filter
    +action : Visitor
    +run()
  }
  class Filter {
    <<interface>>
    +matches(node) bool
  }
  class Node {
    <<abstract>>
    +path, name, size, mtime, type
  }
  class DirectoryNode
  class FileNode
  class SymLinkNode
  class Visitor {
    <<interface>>
    +visit(node)
  }
  Node <|-- DirectoryNode
  Node <|-- FileNode
  Node <|-- SymLinkNode
  FindCommand --> Filter
  FindCommand --> Visitor
  FindCommand --> Node : walks

Requirements

Functional

• Predicates: -name "*.py" (glob), -size +1M, -mtime -7, -type f|d|l.
• Boolean composition: -and (implicit), -or, -not, parentheses for grouping.
• Traversal: recursive descent, -maxdepth, -mindepth, -L follow symlinks.
• Actions: -print (default), -exec cmd {} \;, -delete.
• -prune to cut a subtree out of the walk.

Non-functional

• Stream output as matches are found, no batching.
• Survive directory trees with millions of files (constant memory).
• Skip permission-denied directories with a warning, do not abort.
• Detect symlink cycles in O(1) per check.
• Extensible: adding a new predicate is one class, no changes elsewhere.

Class design

classDiagram
  class FindCommand {
    -root : Path
    -filter : Filter
    -action : Visitor
    -options : TraversalOptions
    +run()
  }
  class TraversalOptions {
    +maxDepth : int
    +minDepth : int
    +followSymlinks : bool
    +crossMounts : bool
  }
  class Node {
    <<abstract>>
    +path : Path
    +name : string
    +size : long
    +mtime : Instant
    +inode : InodeKey
    +accept(v Visitor)
  }
  class FileNode
  class DirectoryNode {
    +children() Iterable~Node~
  }
  class SymLinkNode {
    +target : Path
  }
  class Filter {
    <<interface>>
    +matches(node Node) bool
  }
  class NameFilter {
    -pattern : string
  }
  class SizeFilter {
    -op : char
    -bytes : long
  }
  class MtimeFilter {
    -op : char
    -days : int
  }
  class TypeFilter {
    -kind : char
  }
  class AndFilter {
    -children : List~Filter~
  }
  class OrFilter {
    -children : List~Filter~
  }
  class NotFilter {
    -inner : Filter
  }
  class Visitor {
    <<interface>>
    +visit(node Node)
  }
  class MatchVisitor
  class ExecVisitor {
    -template : List~string~
  }
  Node <|-- FileNode
  Node <|-- DirectoryNode
  Node <|-- SymLinkNode
  Filter <|.. NameFilter
  Filter <|.. SizeFilter
  Filter <|.. MtimeFilter
  Filter <|.. TypeFilter
  Filter <|.. AndFilter
  Filter <|.. OrFilter
  Filter <|.. NotFilter
  AndFilter o-- Filter
  OrFilter o-- Filter
  NotFilter o-- Filter
  Visitor <|.. MatchVisitor
  Visitor <|.. ExecVisitor
  FindCommand --> Filter
  FindCommand --> Visitor
  FindCommand --> TraversalOptions
  FindCommand --> Node : walks

  classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
  classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
  classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;

Two Composites stack here. The file-system Composite is DirectoryNode over Node; the filter Composite is AndFilter / OrFilter / NotFilter over Filter. Visitor crosses them: it walks the first and consults the second.

Filter composition

The shell line find . -type f -name "*.py" -size +1M is parsed into a filter tree. -and is implicit between adjacent predicates.

flowchart TB
  CMD["find . -type f -name *.py -size +1M"] --> ROOT[AndFilter]
  ROOT --> A[TypeFilter type=f]
  ROOT --> B["NameFilter pattern=*.py"]
  ROOT --> C["SizeFilter op=greater bytes=1MB"]

  classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
  classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  class CMD client
  class ROOT service

A more complex query like find . \( -name "*.log" -o -name "*.tmp" \) -not -newer ref.txt:

flowchart TB
  ROOT[AndFilter] --> OR[OrFilter]
  ROOT --> NOT[NotFilter]
  OR --> N1["NameFilter *.log"]
  OR --> N2["NameFilter *.tmp"]
  NOT --> M["MtimeFilter newer-than ref.txt"]

  classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  class ROOT,OR,NOT service

Evaluation short-circuits: AndFilter stops at the first false, OrFilter stops at the first true. Cheap predicates (type, name) go before expensive ones (mtime stat, content regex).

Traversal flow

sequenceDiagram
  participant U as User
  participant FC as FindCommand
  participant D as DirectoryNode
  participant F as Filter
  participant V as MatchVisitor

  U->>FC: run()
  FC->>D: walk(root, depth=0)
  loop each child
    D->>D: stat child
    alt child is DirectoryNode
      D->>F: matches(child)?
      F-->>D: true / false
      D->>V: visit(child) if matched
      D->>D: recurse into child
    else child is FileNode
      D->>F: matches(child)?
      F-->>D: true / false
      D->>V: visit(child) if matched
    end
  end
  V-->>U: prints / execs

The visitor receives every node that the filter accepts. The walk continues into directories regardless of whether they matched, unless -prune is part of the filter.

Code (Python)

import os
import fnmatch
import subprocess
from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from pathlib import Path
from typing import Iterable, List

# Node model
@dataclass
class Node:
    path: Path
    name: str
    size: int
    mtime: float
    kind: str           # 'f', 'd', 'l'
    inode: tuple        # (dev, ino)

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

class NameFilter(Filter):
    def __init__(self, pattern: str): self.pattern = pattern
    def matches(self, n): return fnmatch.fnmatch(n.name, self.pattern)

class TypeFilter(Filter):
    def __init__(self, kind: str): self.kind = kind
    def matches(self, n): return n.kind == self.kind

class SizeFilter(Filter):
    # op in {'+', '-', '='}, bytes is target
    def __init__(self, op: str, bytes_: int):
        self.op, self.bytes_ = op, bytes_
    def matches(self, n):
        if self.op == '+': return n.size > self.bytes_
        if self.op == '-': return n.size < self.bytes_
        return n.size == self.bytes_

class MtimeFilter(Filter):
    def __init__(self, op: str, days: int, now: float):
        self.op, self.cutoff = op, now - days * 86400
    def matches(self, n):
        if self.op == '+': return n.mtime < self.cutoff  # older than
        if self.op == '-': return n.mtime > self.cutoff  # newer than
        return abs(n.mtime - self.cutoff) < 86400

# Composite filters
class AndFilter(Filter):
    def __init__(self, *children): self.children = list(children)
    def matches(self, n): return all(c.matches(n) for c in self.children)

class OrFilter(Filter):
    def __init__(self, *children): self.children = list(children)
    def matches(self, n): return any(c.matches(n) for c in self.children)

class NotFilter(Filter):
    def __init__(self, inner): self.inner = inner
    def matches(self, n): return not self.inner.matches(n)

# Visitor interface and actions
class Visitor(ABC):
    @abstractmethod
    def visit(self, node: Node): ...

class MatchVisitor(Visitor):
    def visit(self, node): print(node.path)

class ExecVisitor(Visitor):
    def __init__(self, template: List[str]): self.template = template
    def visit(self, node):
        cmd = [a.replace('{}', str(node.path)) for a in self.template]
        subprocess.run(cmd, check=False)

# Traversal options
@dataclass
class Options:
    max_depth: int = 1 << 30
    min_depth: int = 0
    follow_symlinks: bool = False

# Iterative DFS, depth tracked on the stack, visited-set for cycle safety
def walk(root: Path, opts: Options) -> Iterable[Node]:
    stack = [(root, 0)]
    visited = set()
    while stack:
        path, depth = stack.pop()
        try:
            st = path.stat() if opts.follow_symlinks else path.lstat()
        except (PermissionError, FileNotFoundError) as e:
            print(f"warn: {path}: {e}")
            continue
        key = (st.st_dev, st.st_ino)
        if key in visited:
            continue
        visited.add(key)
        kind = 'd' if path.is_dir() and not path.is_symlink() else \
               'l' if path.is_symlink() else 'f'
        node = Node(path, path.name, st.st_size, st.st_mtime, kind, key)
        if depth >= opts.min_depth:
            yield node
        if kind == 'd' and depth < opts.max_depth:
            try:
                for child in sorted(path.iterdir()):
                    stack.append((child, depth + 1))
            except PermissionError as e:
                print(f"warn: {path}: {e}")

# Facade
class FindCommand:
    def __init__(self, root: Path, flt: Filter, action: Visitor, opts: Options):
        self.root, self.filter, self.action, self.opts = root, flt, action, opts
    def run(self):
        for node in walk(self.root, self.opts):
            if self.filter.matches(node):
                self.action.visit(node)

# find . -type f -name "*.py" -size +1M -print
if __name__ == '__main__':
    flt = AndFilter(TypeFilter('f'),
                    NameFilter('*.py'),
                    SizeFilter('+', 1 << 20))
    FindCommand(Path('.'), flt, MatchVisitor(), Options()).run()

Edge cases

• Symlink cycles: the visited-set keyed on (dev, inode) guards against a -> b -> a loops. Without -L we use lstat so symlinks are inspected, not followed, and the cycle never forms.
• Permission denied: catch PermissionError on both stat and iterdir, print a warning to stderr, and continue. Aborting on the first locked dir is the most common bug in homemade finds.
• Max depth: depth is tracked on the stack frame, not on the node, so we never need to compare path strings.
• Unicode paths: store Path objects, not raw bytes, and pass through os.fsencode/os.fsdecode at I/O boundaries. Glob patterns are matched on the bare name, not the full path, so non-ASCII just works.
• Very deep trees: iterative DFS with an explicit stack avoids Python's 1000-frame recursion limit. Each frame is 16 bytes-ish, so a 100k-deep tree costs about 1.6 MB.
• Mount boundaries: the GNU -mount flag compares st_dev against the root's st_dev before descending. One extra check, no extra state.
• Interrupt handling: wrap walk in a try / except KeyboardInterrupt so partial output stays flushed.

Concurrency

Single-threaded DFS is the right default. When the bottleneck is disk seeks (lots of small files on SSD) or stat latency (NFS), a worker pool helps. Directories are the unit of work; files inside one directory are walked sequentially because readdir is already cheap.

flowchart LR
  Q[Work queue: directories] --> W1[Worker 1]
  Q --> W2[Worker 2]
  Q --> W3[Worker 3]
  W1 --> V[(Visited set: ConcurrentHashMap)]
  W2 --> V
  W3 --> V
  W1 --> OUT[Output channel]
  W2 --> OUT
  W3 --> OUT
  W1 --> Q
  W2 --> Q
  W3 --> Q

  classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
  classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
  classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
  class Q queue
  class W1,W2,W3 compute
  class V datastore

Workers take a directory, scan it, push any sub-directories back into the queue, and send matches to an output channel. The visited-set is a ConcurrentHashMap<InodeKey, bool> using putIfAbsent to claim each inode atomically. Output is interleaved unless the channel is consumed by a single ordering goroutine that buffers and sorts; most users do not care about order.

Extensions

• -prune: a PruneFilter that, when matched, makes the walk skip descending into that directory. Easiest to implement as a flag on the Node returned to walk, not as a regular Filter.
• -mount: store root_dev on Options and skip directories whose st_dev differs.
• Content predicates: ContentFilter(regex) opens the file, reads in chunks, and short-circuits on first hit. Always combine with a cheap TypeFilter('f') in an AndFilter so directories are never opened.
• Parallel + ordered output: prefix every match with its directory's discovery sequence number and sort at the sink.
• Plugin predicates: register classes via a Filter registry keyed on the flag name; the parser becomes table-driven.

Quick reference

Concern	Mechanism
File-system shape	Composite of DirectoryNode over Node
Predicate composition	Composite of AndFilter / OrFilter / NotFilter over Filter
Walking the tree	Iterative DFS, explicit stack, depth on the frame
Actions on matches	Visitor (MatchVisitor, ExecVisitor)
Cycle safety	Visited set keyed on (dev, inode)
Permission denied	Catch, warn, continue
Streaming	Generator yields nodes; no batching
Parallelism	Directory work queue, concurrent visited set
Memory	O(depth + open dir handles), independent of total file count
Extensibility	One new class per predicate or action

Refs

• GNU findutils source, particularly find/pred.c for the predicate definitions and find/ftsfind.c for the traversal. A clean read on how a real implementation models the same Composite plus Visitor split.
• W. Richard Stevens, Advanced Programming in the UNIX Environment, chapter on directory traversal (ftw, nftw).
• The Gang of Four book, Composite and Visitor chapters, for the underlying patterns.
• "Filters and pipes" chapter of The UNIX Programming Environment by Kernighan and Pike, on how composable command semantics shape the design.

FAQ

How do you design the Linux find command in an LLD interview?

Split it into three concerns: a file system Node model (File, Directory, SymLink) under a Composite, a Filter predicate tree built from name/size/mtime/type leaves combined by And/Or/Not, and a Visitor that walks the tree and runs an action (print or exec) on every node that matches.

Which design pattern fits the find filter system?

Composite plus Specification: each predicate (name, size, mtime, type) is a leaf Filter. AndFilter / OrFilter / NotFilter compose them into a tree. The traversal walks the file system once and asks the root Filter at each node.

Which design pattern fits the directory traversal itself?

Visitor over a Composite tree. The FileNode and DirectoryNode share an accept(Visitor) method. MatchVisitor prints matches, ExecVisitor runs a shell command. Adding a new action (count, archive, hash) means writing a new Visitor, not editing the Node classes.

How do you handle symbolic links and infinite loops?

Keep a set of visited inode keys (device id plus inode number) while descending. Before following a symlink that points to a directory, hash its target's inode and skip if already in the set. By default find does not follow symlinks; the -L flag enables it with the visited-set guard.

How does this scale to millions of files?

Use an iterative DFS with an explicit stack so the recursion does not blow up, stream matches lazily through a generator, and parallelise the directory walk with a thread pool that pulls directories off a work queue. A concurrent visited-set guards cycle detection across workers.

Where does the filter tree get evaluated?

Right after each readdir entry and before descending. The Filter.matches(node) call is short-circuited inside AndFilter and OrFilter so cheap predicates (type, name glob) run before expensive ones (mtime stat, content regex).

Related Topics

• In-Memory Filesystem: the underlying file-tree Composite that find walks
• Trie Autocomplete LLD: another recursive tree walk over a Composite of nodes
• Structural Patterns: Composite used twice here, once for the FS, once for the filter tree
• Behavioral Patterns: Visitor for separating traversal from action