Low-level design · Problem P15 of 15 · Bigger designs

File search (Unix find)

Asked at several big companies as "design the find command". The test is extensibility: adding a new search criterion, or combining existing ones, should never mean editing the search code.

1. The prompt

The prompt"Design an API that finds files in a directory tree matching criteria: by extension, by size, by name. Users must be able to combine criteria with AND, OR and NOT, and we'll add new criteria later."

2. Clarify the requirements

Spend the first five minutes here. Ask, then write the answers down where the interviewer can see them.

Ask	Assume (unless told otherwise)
Directories in the results?	Files only.
Order?	Sorted by path.
Symlinks?	Ignored for now; loops are a follow-up.

Must do

Walk a directory tree
Filter files by extension, minimum size, name
Combine filters with and, or, not

Must be

New criteria without editing the walker
Deep trees must not overflow the stack
Predictable output order

Out of scope

Real disk access (use an in-memory tree)
Symlinks and permissions (follow-ups)
Indexing

3. The classes

The class diagram: arrows show who uses or holds whom.

Class	Its one job
Node	What files and directories share: a name
File / Directory	A leaf with a size; a container of nodes (composite)
Filter	One question: does this file match?
Extension, MinSize, NameContains	Leaf criteria
AllOf, AnyOf, Not	Combine other filters; the specification pattern

4. How it works

Build a query from two filters and an operator, and run it on the demo tree. The expression line is how the same query reads in the Python code.

5. Patterns and why

Pattern	Where	Why it's worth it here
Composite	File and Directory share Node	The walker treats the tree uniformly; nested directories need no special code
Specification	Filter with And/Or/Not	Any combination of criteria, and new criteria are one small class
Iterative traversal	An explicit stack	Deep trees can't overflow the call stack

Memory hook: "Small filters, combined"Each filter answers one question; and, or and not build any query from them, so the walker never changes.

6. The code

Python overloads &, | and ~ so queries read naturally; TypeScript and Java use and(), or() and not().

from __future__ import annotations
from abc import ABC, abstractmethod
from dataclasses import dataclass, field


class Node(ABC):
    """Composite: a file and a directory share one interface, so the search walks both the same way."""

    def __init__(self, name: str) -> None:
        self.name = name

    @abstractmethod
    def is_dir(self) -> bool: ...


class File(Node):
    def __init__(self, name: str, size: int) -> None:
        super().__init__(name)
        self.size = size

    def is_dir(self) -> bool:
        return False

    @property
    def extension(self) -> str:
        return self.name.rsplit(".", 1)[-1] if "." in self.name else ""


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

    def is_dir(self) -> bool:
        return True


class Filter(ABC):
    """Specification pattern: small filters that combine with &, | and ~ instead of one method per combination."""

    @abstractmethod
    def matches(self, f: File) -> bool: ...

    def __and__(self, other: Filter) -> Filter:
        return AllOf([self, other])

    def __or__(self, other: Filter) -> Filter:
        return AnyOf([self, other])

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


@dataclass
class Extension(Filter):
    ext: str

    def matches(self, f: File) -> bool:
        return f.extension == self.ext


@dataclass
class MinSize(Filter):
    bytes: int

    def matches(self, f: File) -> bool:
        return f.size >= self.bytes


@dataclass
class NameContains(Filter):
    text: str

    def matches(self, f: File) -> bool:
        return self.text in f.name


@dataclass
class AllOf(Filter):
    parts: list[Filter] = field(default_factory=list)

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


@dataclass
class AnyOf(Filter):
    parts: list[Filter] = field(default_factory=list)

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


@dataclass
class Not(Filter):
    inner: Filter

    def matches(self, f: File) -> bool:
        return not self.inner.matches(f)


def find(root: Directory, flt: Filter) -> list[str]:
    """Depth-first walk with an explicit stack (deep trees can't overflow the call stack)."""
    out, stack = [], [(root, root.name)]
    while stack:
        node, path = stack.pop()
        if isinstance(node, Directory):
            for child in node.children:
                stack.append((child, f"{path}/{child.name}"))
        elif isinstance(node, File) and flt.matches(node):
            out.append(path)
    return sorted(out)


MB = 1024 * 1024

if __name__ == "__main__":
    root = Directory("app", [
        File("README.md", 2_000),
        Directory("src", [File("main.py", 12_000), File("utils.py", 3_000), Directory("tests", [File("test_main.py", 4_000)])]),
        Directory("logs", [File("app.log", 5 * MB), File("old.log", 200_000), File("debug.txt", 2 * MB)]),
    ])
    print("*.log over 1 MB:", find(root, Extension("log") & MinSize(MB)))
    print("python, not tests:", find(root, Extension("py") & ~NameContains("test")))
    print("over 1 MB or markdown:", find(root, MinSize(MB) | Extension("md")))

/** Composite: a file and a directory share one shape, so the search walks both the same way. */
abstract class FsNode {
  constructor(readonly name: string) {}
}

class FsFile extends FsNode {
  constructor(name: string, readonly size: number) { super(name); }
  get extension(): string { return this.name.includes(".") ? this.name.slice(this.name.lastIndexOf(".") + 1) : ""; }
}

class Directory extends FsNode {
  constructor(name: string, readonly children: FsNode[] = []) { super(name); }
}

/** Specification pattern: small filters that combine with and(), or() and not() instead of one method per combination. */
abstract class Filter {
  abstract matches(f: FsFile): boolean;
  and(other: Filter): Filter { return new AllOf([this, other]); }
  or(other: Filter): Filter { return new AnyOf([this, other]); }
  not(): Filter { return new Not(this); }
}

class Extension extends Filter {
  constructor(private ext: string) { super(); }
  matches(f: FsFile): boolean { return f.extension === this.ext; }
}
class MinSize extends Filter {
  constructor(private bytes: number) { super(); }
  matches(f: FsFile): boolean { return f.size >= this.bytes; }
}
class NameContains extends Filter {
  constructor(private text: string) { super(); }
  matches(f: FsFile): boolean { return f.name.includes(this.text); }
}
class AllOf extends Filter {
  constructor(private parts: Filter[]) { super(); }
  matches(f: FsFile): boolean { return this.parts.every((p) => p.matches(f)); }
}
class AnyOf extends Filter {
  constructor(private parts: Filter[]) { super(); }
  matches(f: FsFile): boolean { return this.parts.some((p) => p.matches(f)); }
}
class Not extends Filter {
  constructor(private inner: Filter) { super(); }
  matches(f: FsFile): boolean { return !this.inner.matches(f); }
}

/** Depth-first walk with an explicit stack (deep trees can't overflow the call stack). */
function find(root: Directory, flt: Filter): string[] {
  const out: string[] = [];
  const stack: [FsNode, string][] = [[root, root.name]];
  while (stack.length) {
    const [node, path] = stack.pop()!;
    if (node instanceof Directory) for (const c of node.children) stack.push([c, `${path}/${c.name}`]);
    else if (node instanceof FsFile && flt.matches(node)) out.push(path);
  }
  return out.sort();
}

const MB = 1024 * 1024;
const show = (xs: string[]) => `[${xs.map((x) => `'${x}'`).join(", ")}]`;
const root = new Directory("app", [
  new FsFile("README.md", 2_000),
  new Directory("src", [new FsFile("main.py", 12_000), new FsFile("utils.py", 3_000), new Directory("tests", [new FsFile("test_main.py", 4_000)])]),
  new Directory("logs", [new FsFile("app.log", 5 * MB), new FsFile("old.log", 200_000), new FsFile("debug.txt", 2 * MB)]),
]);
console.log("*.log over 1 MB:", show(find(root, new Extension("log").and(new MinSize(MB)))));
console.log("python, not tests:", show(find(root, new Extension("py").and(new NameContains("test").not()))));
console.log("over 1 MB or markdown:", show(find(root, new MinSize(MB).or(new Extension("md")))));

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.stream.Collectors;

/** Composite: a file and a directory share one type, so the search walks both the same way. */
sealed interface FsNode permits FsFile, Directory {
    String name();
}

record FsFile(String name, long size) implements FsNode {
    String extension() {
        int i = name.lastIndexOf('.');
        return i < 0 ? "" : name.substring(i + 1);
    }
}

record Directory(String name, List<FsNode> children) implements FsNode {}

/** Specification pattern: small filters that combine with and(), or() and not() instead of one method per combination. */
@FunctionalInterface
interface Filter {
    boolean matches(FsFile f);

    default Filter and(Filter other) {
        return f -> matches(f) && other.matches(f);
    }

    default Filter or(Filter other) {
        return f -> matches(f) || other.matches(f);
    }

    default Filter not() {
        return f -> !matches(f);
    }

    static Filter extension(String ext) {
        return f -> f.extension().equals(ext);
    }

    static Filter minSize(long bytes) {
        return f -> f.size() >= bytes;
    }

    static Filter nameContains(String text) {
        return f -> f.name().contains(text);
    }
}

class FileSearch {
    private record Item(FsNode node, String path) {}

    /** Depth-first walk with an explicit stack (deep trees can't overflow the call stack). */
    static List<String> find(Directory root, Filter flt) {
        List<String> out = new ArrayList<>();
        Deque<Item> stack = new ArrayDeque<>();
        stack.push(new Item(root, root.name()));
        while (!stack.isEmpty()) {
            Item it = stack.pop();
            switch (it.node()) {
                case Directory d -> d.children().forEach(c -> stack.push(new Item(c, it.path() + "/" + c.name())));
                case FsFile f -> { if (flt.matches(f)) out.add(it.path()); }
            }
        }
        Collections.sort(out);
        return out;
    }
}

public class Main {
    static final long MB = 1024 * 1024;

    static String show(List<String> xs) {
        return xs.stream().map(x -> "'" + x + "'").collect(Collectors.joining(", ", "[", "]"));
    }

    public static void main(String[] args) {
        Directory root = new Directory("app", List.of(
                new FsFile("README.md", 2_000),
                new Directory("src", List.of(new FsFile("main.py", 12_000), new FsFile("utils.py", 3_000),
                        new Directory("tests", List.of(new FsFile("test_main.py", 4_000))))),
                new Directory("logs", List.of(new FsFile("app.log", 5 * MB), new FsFile("old.log", 200_000), new FsFile("debug.txt", 2 * MB)))));
        System.out.println("*.log over 1 MB: " + show(FileSearch.find(root, Filter.extension("log").and(Filter.minSize(MB)))));
        System.out.println("python, not tests: " + show(FileSearch.find(root, Filter.extension("py").and(Filter.nameContains("test").not()))));
        System.out.println("over 1 MB or markdown: " + show(FileSearch.find(root, Filter.minSize(MB).or(Filter.extension("md")))));
    }
}

Output (the same in all three languages)

*.log over 1 MB: ['app/logs/app.log']
python, not tests: ['app/src/main.py', 'app/src/utils.py']
over 1 MB or markdown: ['app/README.md', 'app/logs/app.log', 'app/logs/debug.txt']

7. Concurrency and edge cases

Symlink loops make a walk infinite: track visited directories by their real identity (device and inode).
Huge trees: return results as a lazy iterator/stream so the caller can stop early; walk directories in parallel with a work queue if the disk allows.
Permissions: unreadable directories should be skipped and reported, not crash the search.

8. Follow-up questions

What interviewers ask once the core works, and a short answer for each.

Add 'modified in the last 7 days'?: One new Filter class (ModifiedAfter); nothing else changes. That's the point of the design.
Why not one search method with many optional parameters?: Every new criterion changes its signature, and AND/OR/NOT combinations can't be expressed.
How would you search a huge filesystem quickly?: Build an index (like locate's database) updated periodically, and query that instead of walking.
Search by content?: A ContentContains filter that reads the file; put cheap filters first in AllOf so expensive ones run rarely.

9. Common mistakes

A search method per combinationfindBySizeAndExtension, findByNameOrSize… grows without end.

Recursion on very deep treesCan overflow the stack; use an explicit stack.

Mixing traversal and filtering logicThen every new criterion edits the walker.

10. Check yourself

Which pattern lets you combine filters with and, or and not?

Small predicates plus combinators.

Why do File and Directory share a base type?

Composite pattern.

A new 'modified after' criterion is needed. What changes?

Open for extension, closed for modification.

Your turn

Add ModifiedAfter (5 min). Give files a modified day and filter on it.
Make results lazy (10 min). Return a generator / iterator instead of a list.