Design the Linux 'find' Command
Composable filters (name/size/type) combined with And/Or/Not — a Specification + Composite exercise.
Problem Statement
Design the object model for a simplified Linux 'find' command. Given a root directory, traverse the file tree, evaluate each node against composable filter predicates, and apply an action to every matching node.
The core interview challenge is not path parsing or operating-system calls. It is designing a traversal engine that is closed for modification while filters remain open for extension. Adding OwnerFilter, ModifiedAfterFilter, or PermissionFilter should mean adding a class, not changing FindCommand.
Business context
Search tools appear in developer platforms, backup systems, sync engines, document stores, and admin consoles. A clean 'find' design tests whether a candidate can separate traversal from matching policy and from output behavior.
Interviewers use this problem to probe composition, recursion, iterators, and the open/closed principle. The strongest solution treats filters as a predicate tree: leaf filters check one fact, logical filters combine other filters, and the command only asks one question: does this node match?
Functional Requirements
Represent a directory tree containing directories and files.
Traverse the tree from a provided root in deterministic depth-first order.
Support filtering by exact file or directory name.
Support filtering by file extension, ignoring directories for extension checks.
Support filtering by exact size and minimum size for files.
Combine filters with AND, OR, and NOT without changing traversal logic.
Apply an action to every matching node, such as printing the name or collecting results.
Allow new filters to be introduced by implementing the same Filter interface.
Non-Functional Requirements
Open for filters
The traversal engine must depend only on Filter. New leaf filters and new logical filters should not require edits to FindCommand.
Predictable traversal
The command should visit nodes in a stable depth-first order so dry runs, tests, and user output are easy to reason about.
Small memory footprint
Traversal should use an iterator stack proportional to tree depth rather than flattening the whole tree before matching.
Safe composition
Composite filters should validate their children and hide their internal lists so callers cannot mutate a predicate after construction.
Separation of concerns
Tree structure, predicate evaluation, traversal, and matched-node action must live in separate classes.
Requirement Clarification
QAre we designing a full POSIX-compatible 'find' command?
No. The scope is an in-memory LLD model that demonstrates traversal, composable filters, and actions. Real command-line parsing, symbolic links, permissions, and file-system errors are production extensions.
QShould filters match directories as well as files?
Name filters can match any node. Extension and size filters match files only, because those predicates are file-specific in this simplified model.
QHow are AND, OR, and NOT represented?
They are filters too. AndFilter, OrFilter, and NotFilter implement Filter and hold child filters, creating a Composite predicate tree.
QWhat does applying an action mean?
The command receives an Action strategy. It can print, collect, delete, archive, or emit metrics for a match without changing traversal or filtering.
QDo we need lazy streaming of results?
The reference design applies actions as it traverses. A production variant can expose an iterator or stream of matches using the same filter tree.
UML Class Diagram
Sequence Diagram
Entity Identification
FileNode
Represents either a directory or a file. It owns child nodes for directories and exposes a depth-first iterator plus a visitor entry point.
Filter
Predicate interface for all matching rules. The traversal engine depends only on matches, plus convenience composition methods.
NameFilter
Leaf predicate that matches a node by exact name. It works for both directories and files.
ExtensionFilter
Leaf predicate that matches file extensions after normalizing case and ignoring an optional leading dot.
SizeFilter
Leaf predicate that supports exact-size and minimum-size comparisons for files.
AndFilter / OrFilter / NotFilter
Composite predicates that hold child filters. They let callers build arbitrarily nested boolean expressions.
FindCommand
Traversal coordinator. It visits nodes, asks the configured filter whether a node matches, and invokes the configured action.
Action
Strategy for what happens to each matching node. Printing is only one possible action.
Design Patterns Used
AndFilter, OrFilter, and NotFilter are filters that contain other filters. This makes a complex boolean expression look like a single Filter to the traversal engine.
Filter is the matching strategy and Action is the match-handling strategy. FindCommand is configured with both and does not know the concrete policy.
FileNode.accept receives a visitor, and FindCommand implements the visit operation. This keeps node traversal and node processing decoupled.
FileNode implements Iterable and returns a depth-first iterator. Traversal state lives in the iterator stack, not in the command.
Step-by-Step Design
1Start with a tree node that can be traversed
Represent both files and directories as FileNode so traversal logic is uniform. A directory owns children; a file has size and no children.
public final class FileNode implements Iterable<FileNode> { private final String name; private final boolean directory; private final long sizeBytes; private final List<FileNode> children = new ArrayList<>(); }2Define a small predicate interface
Filter is the only concept the command needs for matching. The default composition methods make client code read like a query expression.
@FunctionalInterface public interface Filter { boolean matches(FileNode node); default Filter and(Filter other) { return new AndFilter(this, other); } }3Implement leaf filters independently
Each leaf filter checks one field and owns its own boundary rules. ExtensionFilter ignores directories; SizeFilter ignores directories and supports exact or minimum size.
4Make logical operators filters too
Logical filters implement the same interface as leaf filters. This is the Composite move: AndFilter can contain OrFilter, which can contain NotFilter, and the command still sees one Filter.
public final class AndFilter implements Filter { private final List<Filter> filters; public boolean matches(FileNode node) { for (Filter filter : filters) { if (!filter.matches(node)) { return false; } } return true; } }5Keep traversal ignorant of concrete filters
FindCommand receives a root, a filter, and an action. It visits nodes and delegates both decisions: whether the node matches and what to do with it.
6Treat actions as another extension point
Printing, collecting, deleting, or archiving matches should not create subclasses of the command. They are Action implementations passed into the command.
Complete Java Implementation
Explanation of Every Class
FileNode
Unified tree node for files and directories. It protects the directory invariant, exposes child views safely, implements Iterable, and accepts a visitor for traversal-time processing.
Filter
Tiny predicate interface used by every matching rule. Its default and, or, and negate methods are convenience factories for composite filters.
NameFilter / ExtensionFilter
NameFilter checks exact names for any node. ExtensionFilter normalizes the requested extension and only matches files.
SizeFilter
Encapsulates size comparisons for files. Static factories make the caller choose exact size or minimum size without exposing enum details.
AndFilter / OrFilter / NotFilter
Composite filters. They store immutable child filters and implement short-circuit boolean logic while still presenting the same Filter interface.
FindCommand / Action
FindCommand is the visitor and coordinator. Action is the pluggable behavior for matches, so the command does not know whether matches are printed, collected, or deleted.
Main
Small demo wiring: builds a tree, composes extension, size, and NOT predicates, and prints the nodes that satisfy the final filter.
Dry Run
Sample input
Tree: repo contains README.md 1200B, src/App.java 4000B, src/AppTest.java 8000B, logs/app.log 6500B, logs/debug.log 900B. Filter: (extension java OR extension log) AND min-size 5000 AND NOT name AppTest.java. Action: print match.
| Step | Visited node | Extension or name result | Size and NOT result | Action |
|---|---|---|---|---|
| 1 | repo | false because directory has no extension | not evaluated after OR false | skip |
| 2 | README.md | false | not evaluated after OR false | skip |
| 3 | src | false because directory has no extension | not evaluated after OR false | skip |
| 4 | App.java | true | 4000B is below 5000B | skip |
| 5 | AppTest.java | true | 8000B passes size but NOT name fails | skip |
| 6 | logs | false because directory has no extension | not evaluated after OR false | skip |
| 7 | app.log | true | 6500B passes and NOT name passes | print app.log |
| 8 | debug.log | true | 900B is below 5000B | skip |
Only app.log reaches the action. Notice that the traversal never changes when the predicate becomes more complex; only the filter tree changes.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| execute traversal | O(N × F) | O(H) | N nodes, H tree height, F cost of evaluating the filter tree for one node. |
| leaf filter match | O(1) | O(1) | Name, extension, exact size, and min-size checks are constant-time over stored metadata. |
| AND or OR filter match | O(K) | O(1) | K child filters in the composite; short-circuiting often stops earlier. |
| NOT filter match | O(C) | O(1) | C is the wrapped child filter cost. |
| building a composite filter | O(K) | O(K) | Children are copied into an immutable list for safety. |
For ordinary in-memory metadata, traversal dominates. In a real file system, I/O and permission checks dominate, so the same design should stream nodes and handle errors without materializing all matches.
Extensibility
Add a new leaf filter
Create a class such as OwnerFilter or ModifiedAfterFilter that implements Filter. No change is needed in FindCommand or any existing composite filter.
Add a new logical operator
A filter such as XorFilter can also implement Filter and hold children. It plugs into the same predicate tree.
Add a new action
Implement Action to collect matches, delete files, archive files, or emit events. Traversal and matching stay untouched.
Switch traversal policy
Replace the depth-first iterator with breadth-first or parallel traversal behind FileNode.iterator or a dedicated traversal strategy while keeping filter semantics unchanged.
Alternative Designs
Return a list of matches
Instead of applying an action during traversal, FindCommand could collect and return a list of matched nodes.
Tradeoffs
Simpler for small trees and tests, but it uses O(M) memory for M matches and delays action execution until traversal completes.
Parse an expression into filters
Introduce a parser that turns user input such as name, extension, and size flags into the same filter tree.
Tradeoffs
Better user-facing realism, but parsing is a separate concern and can distract from the LLD core if introduced too early.
Chain of filters
Model filtering as a pipeline where each filter either passes the node to the next filter or rejects it.
Tradeoffs
Readable for pure AND logic, but OR and NOT become awkward. A Composite predicate tree is more natural for arbitrary boolean expressions.
Visitor per operation
Make every operation a separate visitor over FileNode, such as printing, counting, or deleting visitors.
Tradeoffs
Strong separation for many tree operations, but matching policy can get duplicated unless those visitors still delegate to Filter.
Common Mistakes
- ×
Putting a large if-else chain for name, extension, and size directly inside FindCommand.
- ×
Representing AND and OR as flags on one filter class instead of making logical filters composable.
- ×
Making SizeFilter match directories, which creates surprising results for directory nodes with synthetic size zero.
- ×
Flattening the whole tree before matching, which wastes memory and prevents streaming actions.
- ×
Hard-coding print behavior in the traversal engine instead of injecting an Action.
- ×
Exposing mutable child lists from FileNode, allowing callers to mutate traversal state unexpectedly.
- ×
Treating NOT as a special case in the command rather than as another filter.
Follow-up Interview Questions
QHow would you add a modified-after date filter?
Add timestamp metadata to FileNode or an external metadata provider, then implement ModifiedAfterFilter implements Filter. The command and composite filters stay unchanged.
QHow would you support user input like find root -name app.log -size +5k?
Add a parser layer that converts tokens into a Filter tree and an Action. Keep parsing outside the domain model so the core design remains testable.
QHow do you prevent cycles caused by symbolic links?
In production, track visited inode or canonical path identifiers in the iterator and skip already-seen directories. The in-memory interview model assumes a tree.
QCan this be parallelized?
Yes for independent subtrees if filters are immutable and actions are thread-safe. The current design already helps because filter state is read-only after construction.
QWhy prefer Composite filters over a single enum-based filter class?
A single enum class usually grows a switch for each new predicate or operator. Composite filters keep every new rule additive and preserve open/closed behavior.
Production Considerations
Real file-system adapter
Use an adapter around platform APIs to stream file metadata into FileNode-like views. Do not bake OS calls into filters or command orchestration.
Permission and I/O errors
Traversal should decide whether to skip unreadable directories, report errors, or fail fast. Keep that policy explicit and testable.
Symlink and cycle handling
Track stable file identifiers to avoid infinite traversal when symbolic links point to ancestors.
Action safety
Destructive actions such as delete should support dry-run mode, audit logging, and confirmation boundaries.
Large trees
Use streaming traversal and backpressure for very large trees. Avoid collecting all matches unless the caller explicitly asks for it.
What Interviewers Look For
Did the candidate make filters composable instead of adding conditionals to traversal?
Can the candidate explain why logical filters are also filters?
Is the traversal order deterministic and memory-conscious?
Are action, filter, and traversal responsibilities separate?
Can a new predicate be added without editing FindCommand?
Did the candidate identify real-world concerns such as symlinks, permissions, and large directories as extensions rather than core distractions?
Quiz
0/5 answered
1.Why should **FindCommand** depend on **Filter** instead of concrete filters?
2.Why are **AndFilter** and **OrFilter** examples of Composite?
3.What should **SizeFilter.atLeast(5000)** do when it receives a directory node?
4.Which choice best preserves the open/closed principle for a new **OwnerFilter**?
5.What is the role of **Action** in the design?
Practice Variants
Add date and owner filters
IntermediateExtend FileNode metadata and add ModifiedAfterFilter plus OwnerFilter. Verify FindCommand stays untouched.
Build a query parser
AdvancedParse a small command syntax into a filter tree with parentheses, AND, OR, and NOT precedence.
Implement safe delete action
AdvancedAdd an Action that supports dry-run output, confirmation, and audit logging before deleting files.
Flashcards
Cheat Sheet
Core model: FileNode represents both files and directories; Filter represents one match predicate; FindCommand traverses and applies Action.
Filters: NameFilter, ExtensionFilter, and SizeFilter are leaves. AndFilter, OrFilter, and NotFilter are composite filters.
Patterns: Composite for filter trees; Strategy for Filter and Action; Visitor for node processing; Iterator for depth-first traversal.
Flow: execute(root) -> root.accept(visitor) -> iterator yields nodes -> filter.matches(node) -> action.apply(node) on matches.
Open/closed rule: add new filters by implementing Filter. Do not edit FindCommand for new predicates.
Complexity: traversal is O(N × F) time and O(H) space, where F is filter evaluation cost and H is tree height.
Production extensions: parser, symlink cycle detection, file-system adapter, permission handling, and safe destructive actions.
References
- BookDesign Patterns: Elements of Reusable Object-Oriented Software — Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides
- DocsRefactoring Guru — Composite Pattern
- DocsOracle Java Documentation — Iterator Interface — Oracle
- DocsPOSIX find utility specification — The Open Group