Unix find command with pluggable filters

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).

Clarifying questions

• Does add_file onto a path that is already a directory raise?
• Is the extension compared case-sensitively, and does a name with no dot have no extension?
• Should find on a file path (not a directory) return that file or raise?
• Is sorted order plain string order of full paths?

What a strong answer covers

• Models a tree of Directory nodes with child maps and File objects (name, size, path, extension), so mkdir and add_file are O(depth).
• Walks the subtree iteratively (an explicit stack, since depth can reach 10^4) and keeps files where filter.apply(file) is true; O(subtree size) plus the sort.
• Defines the Filter interface so find never knows the filter types: open for extension, closed for change.
• Implements the three filters precisely: strictly greater than n, text after the last dot, prefix of the name only (not the path).
• Raises on a missing start path, and tests nested directories, a dotless name, a dotfile, and a replaced file's new size.

Follow-ups

• Combine filters with AND, OR and NOT as composite filters.
• Add filters on modified time or depth limits, like -mtime and -maxdepth.
• Stream results lazily instead of building the full list for huge trees.