Unix Find Command
medium · tree traversal, composable filters
Brief-reported interview attribution (unverified): Amazon
How to approach an LLD roundRequirements
- 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
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter