Search a Unix-Like File Tree with Composable Filters

Problem

Search an in-memory Unix-like file tree from a given directory. Return every physical file whose name contains a query string and whose size is greater than a supplied minimum. The caller chooses "AND" or "OR" combination. Symbolic links may point to files or directories and may form cycles.

Each node has stable identity, name, and type (file, directory, or symlink). Files have size and a canonical path. Directories have child nodes. A symlink has a target node or a broken null target.

Function Contract

Implement searchFiles(startDirectory, nameQuery, minSize, mode, followSymlinks).

• Return canonical paths sorted lexicographically.
• Return each physical file identity at most once, even if several links reach it.
• When followSymlinks is false, ignore links.
• When true, follow valid targets without looping; broken links contribute nothing.

Constraints & Assumptions

• At most 300,000 distinct node identities are reachable.
• mode is "AND" or "OR".
• Name matching is case-sensitive substring matching.
• minSize >= 0.
• The start node is a directory.

Clarifying Questions to Ask

• Does size equality pass? No, the comparison is strictly greater than the minimum.
• Are results logical link paths or physical files? Return each physical file's canonical path once.
• Can links create cycles? Yes.
• Does an empty name query match every file name? Yes.

Example

nameQuery = "report"
minSize = 100
mode = "AND"

Only files whose names contain report and whose sizes are greater than 100 are returned, regardless of whether reached directly or through a symlink.

Evaluation Focus

• Traverses arbitrary depth without recursion overflow.
• Handles broken links, directory-link cycles, and duplicate aliases.
• Applies AND/OR predicates exactly.
• Runs in O(v + e + r log r) time for reachable nodes/edges and r results.

Extensions to Discuss

1. What changes if results must preserve every logical link path?
2. How would permissions and mount boundaries affect traversal?
3. How could file-system events keep a search index current?