0

Unix find command with pluggable filters

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Unix find command with pluggable filters

Companies: Google, Amazon

Difficulty: Hard

Problem statement

Implement a small version of the Unix find command over an in-memory file system.

The file system holds directories and files. Each file has a name and a size in bytes. Its extension is the text after the last dot in its name.

Implement a FileSystem class:

  • mkdir(path) creates a directory and any missing parents.
  • add_file(path, size) adds a file, creating missing parent directories. Adding an existing path replaces that file.
  • find(path, filter) returns the full paths of all files in the directory path and in all of its subdirectories that pass filter. Return the paths in sorted order. Directories are never returned.

Filters share one interface:

class Filter(ABC):
    @abstractmethod
    def apply(self, file: File) -> bool: ...

Implement three filters:

  • MinSizeFilter(n): the file size is greater than n.
  • ExtensionFilter(ext): the file has extension ext.
  • NamePrefixFilter(prefix): the file name starts with prefix.

The design must make it easy to add new filter types later without changing find.

Example

add_file("/srv/logs/app.log", 2048)
add_file("/srv/logs/old/app-2024.log", 90)
add_file("/srv/config.yaml", 300)

find("/srv", ExtensionFilter("log"))
  -> ["/srv/logs/app.log", "/srv/logs/old/app-2024.log"]
find("/srv", MinSizeFilter(200))
  -> ["/srv/config.yaml", "/srv/logs/app.log"]
find("/srv/logs", NamePrefixFilter("app-"))
  -> ["/srv/logs/old/app-2024.log"]

Constraints

  • Paths are absolute and use / as the separator.
  • Up to 10^5 files; directory depth up to 10^4.
  • find on a path that does not exist raises an error.

A common next part: let callers combine filters with AND, OR and NOT (for example, .log files larger than 1 KB).

Approach

This is an object-oriented design question with a small amount of tree traversal. The interviewer cares most about two things: filters must be easy to add without touching the search code, and the walk must cover every subdirectory under the start path.

Model. One File node type, with name, size, is_dir and children (a dict from name to node). A directory is a node with is_dir=True. The extension is derived from the name (the text after the last dot, and a leading-dot name such as .bashrc has none). The root is an unnamed directory.

Filters. Each criterion is a class with one method, apply(file) -> bool. That is the Strategy pattern. The search code knows only the Filter interface, so a new criterion is one new class and no change to find (open/closed principle). The three required filters are:

  • MinSizeFilter(n): size strictly greater than n (say which comparison you choose; the interviewer usually accepts either).
  • ExtensionFilter(ext): exact extension match. It accepts "txt" or ".txt".
  • NamePrefixFilter(p): the file name starts with p.

Combining. "Files over 5 MB that are .xml" is the natural next part, so add the Composite pattern now. AndFilter, OrFilter and NotFilter are themselves filters that wrap other filters, so any boolean expression becomes a tree of filters. The Python operators &, | and ~ are small sugar on top.

Search. find(path, filter) resolves the start directory, then walks its subtree. A brute-force approach would collect every file under the start and then filter the list. Applying the filter during the walk is the same O(n) but does not build a second list. An explicit stack (iterative DFS) avoids Python's recursion limit on very deep trees. Filters apply only to files. Directories are traversed and never returned.

Invariants. Every path component on the way to a file is a directory. A name is unique within its parent. find visits each node under the start exactly once and returns full paths, sorted so the output is deterministic.

Code

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


@dataclass
class File:
    name: str
    size: int = 0
    is_dir: bool = False
    children: dict[str, "File"] = field(default_factory=dict)

    @property
    def extension(self) -> str:
        dot = self.name.rfind(".")
        return self.name[dot + 1:] if dot > 0 else ""


class Filter(ABC):
    @abstractmethod
    def apply(self, file: File) -> 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)


class MinSizeFilter(Filter):
    def __init__(self, min_size: int) -> None:
        self.min_size = min_size

    def apply(self, file: File) -> bool:
        return file.size > self.min_size


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

    def apply(self, file: File) -> bool:
        return file.extension == self.ext


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

    def apply(self, file: File) -> bool:
        return file.name.startswith(self.prefix)


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

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


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

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


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

    def apply(self, file: File) -> bool:
        return not self.inner.apply(file)


class FileSystem:
    def __init__(self) -> None:
        self.root = File("", is_dir=True)

    def _walk(self, path: str, create: bool) -> File:
        node = self.root
        for part in (p for p in path.split("/") if p):
            child = node.children.get(part)
            if child is None:
                if not create:
                    raise FileNotFoundError(path)
                child = node.children[part] = File(part, is_dir=True)
            if not child.is_dir:
                raise NotADirectoryError(path)
            node = child
        return node

    def mkdir(self, path: str) -> None:
        self._walk(path, create=True)

    def add_file(self, path: str, size: int) -> None:
        parent_path, _, name = path.rstrip("/").rpartition("/")
        if not name:
            raise ValueError("file needs a name")
        parent = self._walk(parent_path, create=True)
        existing = parent.children.get(name)
        if existing is not None and existing.is_dir:
            raise IsADirectoryError(path)
        parent.children[name] = File(name, size)

    def find(self, path: str, flt: Filter) -> list[str]:
        start = self._walk(path, create=False)
        base = "/" + "/".join(p for p in path.split("/") if p)
        results: list[str] = []
        stack: list[tuple[File, str]] = [(start, base.rstrip("/"))]
        while stack:  # iterative DFS: no recursion limit on deep trees
            node, node_path = stack.pop()
            for name, child in node.children.items():
                child_path = f"{node_path}/{name}"
                if child.is_dir:
                    stack.append((child, child_path))
                elif flt.apply(child):
                    results.append(child_path)
        return sorted(results)

Complexity

Let n be the number of nodes (files and directories) under the start directory, d the depth of a path, and k the number of matches.

  • mkdir(path) and add_file(path, size): O(d) time. O(d) new nodes at most.
  • find(path, filter): O(d + n * c + k log k) time, where c is the cost of one apply (O(1) for the base filters, O(size of the filter tree) for a combined one). O(h + k) extra space, where h is the widest stack the DFS holds (bounded by n).
  • Total memory: O(N) for N nodes in the file system.

Test cases

Setup: files /home/ana/notes.txt (120), /home/ana/photo.jpg (4000), /home/ana/drafts/plan.txt (900), /home/ben/plan.md (50), and an empty directory /tmp.

  • find("/home", ExtensionFilter("txt")) returns ["/home/ana/drafts/plan.txt", "/home/ana/notes.txt"]. The search reaches the nested drafts folder.
  • find("/home", MinSizeFilter(500)) returns ["/home/ana/drafts/plan.txt", "/home/ana/photo.jpg"].
  • find("/", NamePrefixFilter("plan")) returns ["/home/ana/drafts/plan.txt", "/home/ben/plan.md"]. Prefix applies to the file name, not the path.
  • find("/home", ExtensionFilter("txt") & MinSizeFilter(500)) returns ["/home/ana/drafts/plan.txt"].
  • find("/home/ana", ExtensionFilter(".jpg") | NamePrefixFilter("no")) returns ["/home/ana/notes.txt", "/home/ana/photo.jpg"]. A leading dot in the extension is accepted.
  • find("/home/ben", ~ExtensionFilter("md")) returns [].
  • Empty directory: find("/tmp", MinSizeFilter(0)) returns [].
  • Boundary: find("/home", MinSizeFilter(4000)) returns [], because the comparison is strict.
  • Missing start directory: find("/nope", ...) raises FileNotFoundError.
  • Dotfile: File(".bashrc").extension is "".
  • Overwrite: adding /home/ana/notes.txt again with size 10 replaces the old entry.

Follow-ups

  1. Combine filters with AND/OR/NOT. This is usually part 2. The composite classes above already handle it. Discuss short-circuit evaluation and putting the cheapest filter first (for example, check the extension before a costly content check).
  2. More filter types (modified time, owner, permissions, regex name, file content). Add attributes to File and write one class per criterion. find does not change. For content filters, read lazily and only after the cheap filters pass.
  3. Parse a command line like find /home -size +5M -name "*.xml". Write a small parser that maps each flag to a filter constructor through a registry (dict from flag to factory), and joins consecutive clauses with AndFilter. Supporting -o, ! and parentheses means a small recursive-descent parser that builds the filter tree.
  4. Search a real or very large file system. Use os.scandir instead of the in-memory tree. Return a generator so results stream instead of building a list. Handle permission errors and symlink loops (track visited inode numbers). Optionally add maxdepth and prune whole subtrees with a directory-level predicate.
  5. Repeated queries on a static tree. Precompute indexes: extension to files, a sorted size list (binary search for size > n), and a trie over names for prefix queries. Then intersect the candidate sets for AND queries. Indexes must be updated on every add and delete, so this pays off only when reads dominate.

Interviewer expectations

Mid-level (L4)

  • Defines a Filter interface and the three concrete filters correctly.
  • Traverses all subdirectories (recursively or with a stack) and returns only files.
  • Handles the basic edge cases: empty directory, no matches, missing path.

Senior (L5)

  • Names the design choices: Strategy for filters, Composite for AND/OR/NOT, and the open/closed reason behind them.
  • Separates the tree model, the filters and the search, and keeps find unaware of concrete filters.
  • Chooses iterative DFS for deep trees, states the size boundary, handles dotfiles, and gives correct complexity.

Staff (L6+)

  • Moves to the real-system concerns without prompting: streaming results, symlink loops, permissions, very large directories.
  • Discusses filter ordering by cost, subtree pruning, and when secondary indexes are worth their write cost.
  • Sketches how a command-line expression becomes a filter tree, and how new filters plug in through a registry.

Sign in to comment, vote or remix.