Unix Find Command

medium · tree traversal, composable filters

Brief-reported interview attribution (unverified): Amazon

How to approach an LLD round

Requirements

  • Functional: build a file tree, search it by exact name, type (file/dir) and size (strict greater/less), with filters ANDed; the starting path itself matches too; filter trees must compose (AND/OR/NOT) without touching the walk.
  • Non-functional: walking the tree and matching a path must be separate (a new filter must not touch the walk); size filters never match a directory.
  • Out of scope: regex/glob patterns, permissions, symlinks.

Statement

Implement the core of the Unix find command over an in-memory file tree. add_dir creates directories (parents as needed); add_file creates a file with a size in bytes (parents as needed). find(path, ...) walks the tree below path and returns every matching path, sorted. Filters combine with AND: name (exact match on the last component), type ("f" for files, "d" for directories), size_gt / size_lt (file size in bytes; a size filter never matches a directory). Filters are Filter objects that compose into trees: AndFilter/OrFilter/NotFilter combine them (find ANDs its keyword filters with AndFilter).

class UnixFind:
    def __init__(self):
    def add_dir(self, path):
        # creates all missing directories along the path
    def add_file(self, path, size):
        # creates the file (parents as needed); -> False for an empty/invalid path
    def find(self, path, name=None, type=None, size_gt=None, size_lt=None):
        # -> sorted list of absolute paths that match all given filters
        # (the starting path itself is included when it matches; [] for a missing path)

Rules. A filter that is None is ignored. size_gt/size_lt are strict (size > size_gt, size < size_lt). find on a file path returns that file alone when it matches, and [] when it does not. The root / is a directory and is included in results when it matches.

Filter API: every leaf or composite implements matches(path, last_name, is_file, size) -> bool. path is the full path, last_name is its final component, is_file is a boolean, and size is the file size (or None for a directory). Construct leaves with NameFilter(name), TypeFilter(type_) ("f" or "d"), or SizeFilter(size_gt=None, size_lt=None) (strict bounds; directories never match). AndFilter(*filters) matches all children; with no children it returns True. OrFilter(*filters) matches any child; with no children it returns False. NotFilter(inner) negates one child. Trees can nest arbitrarily. The existing find keyword arguments are combined with AND; its signature is unchanged.

Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.

Class design (SOLID)

Directory (subdirs + files; SRP). Filter (ABC interface; one predicate; SRP) with NameFilter/TypeFilter/SizeFilter leaves and AndFilter/OrFilter/NotFilter composites — a filter tree is itself a Filter (Composite/Specification; OCP — a new filter or a new combination is a new class, not a new if). find builds an AndFilter from its keyword arguments. UnixFind walks the tree and applies the combined filter. Pattern: Specification/Composite (filters).

Public demo

# Public demo: run after implementing the class API above.
f = UnixFind()
for path, size in [('/a/b/f1.txt', 100), ('/a/b/f2.log', 500), ('/a/c/f3.txt', 50), ('/a/readme.md', 1000), ('/d/x.py', 200)]:
    f.add_file(path, size)
print(f.find('/', type='f'))

Reference solution and hidden tests

Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.

Concurrency

Reads dominate: many find calls, few add_dir/add_file. A single lock around mutations is enough; in production, a read-write lock (concurrent finds, one writer) scales better. The reference is single-threaded; the lock is described here.

Trade-offs & extensions

The walk visits every node under the path (O(nodes)) — fine for a small tree. Extending: a RegexFilter (same interface) and an index (name → paths) for O(1) name lookups.

Starter code

from abc import ABC, abstractmethod

class Directory:

    def __init__(self, name):
        """Initialize the state described in the problem."""
        pass

    def add_dir(self, name):
        """creates all missing directories along the path"""
        pass

    def add_file(self, name, size):
        """creates the file (parents as needed); -> False for an empty/invalid path"""
        pass

class Filter(ABC):

    @abstractmethod
    def matches(self, path, last_name, is_file, size):
        """Implement the return value and rules in the API contract."""
        pass

class NameFilter(Filter):

    def __init__(self, name):
        """Initialize the state described in the problem."""
        pass

    def matches(self, path, last_name, is_file, size):
        """Implement the return value and rules in the API contract."""
        pass

class TypeFilter(Filter):

    def __init__(self, type_):
        """Initialize the state described in the problem."""
        pass

    def matches(self, path, last_name, is_file, size):
        """Implement the return value and rules in the API contract."""
        pass

class SizeFilter(Filter):

    def __init__(self, size_gt=None, size_lt=None):
        """Initialize the state described in the problem."""
        pass

    def matches(self, path, last_name, is_file, size):
        """Implement the return value and rules in the API contract."""
        pass

class AndFilter(Filter):

    def __init__(self, *filters):
        """Initialize the state described in the problem."""
        pass

    def matches(self, path, last_name, is_file, size):
        """Implement the return value and rules in the API contract."""
        pass

class OrFilter(Filter):

    def __init__(self, *filters):
        """Initialize the state described in the problem."""
        pass

    def matches(self, path, last_name, is_file, size):
        """Implement the return value and rules in the API contract."""
        pass

class NotFilter(Filter):

    def __init__(self, inner):
        """Initialize the state described in the problem."""
        pass

    def matches(self, path, last_name, is_file, size):
        """Implement the return value and rules in the API contract."""
        pass

class UnixFind:

    def __init__(self):
        """Initialize the state described in the problem."""
        pass

    def add_dir(self, path):
        """creates all missing directories along the path"""
        pass

    def add_file(self, path, size):
        """creates the file (parents as needed); -> False for an empty/invalid path"""
        pass

    def find(self, path, name=None, type=None, size_gt=None, size_lt=None):
        """-> sorted list of absolute paths that match all given filters (the starting path itself is included when it matches; [] for a missing path)"""
        pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. The GraderCharacter joke · No posting date

    Edge case? Never met her.

  2. InterviewerCharacter joke · No posting date

    Walk me through your thinking. No, not out loud. In code. In silence. While I watch.

  3. Me at 2amCharacter joke · No posting date

    My code works. I have no idea why. I am afraid to touch it. I am going to bed.