Unix Find with Filters and Links

AmazonPhone screenMedium

You work on an in-memory file tree that models a Unix-like file system. A node is one of three kinds:

a directory {"name": ..., "children": [...]},
a file {"name": ..., "size": ...},
a symbolic link {"name": ..., "target": ...}, where target is an absolute path.

The root is a directory named "". Names are non-empty, contain no /, and are unique among siblings. The canonical path of a node is / followed by the names from the root down to it, joined with /; the root's canonical path is /.

A link's target is looked up as a canonical path, without resolving through other links along the way. A target that names no node in the tree (for example one that goes through a link, such as /x/ln/f where /x/ln is a link), or that names another link, is broken.

Part 1: Find matching files

Implement search_files(root, start, name_query, min_size, mode, follow_links). start is the canonical path of a directory in the tree. Return the canonical paths of the matching files found under start, without duplicates, sorted as plain strings.

A file matches on name when its own name contains name_query (case-sensitive; an empty name_query matches every name). A file matches on size when its size is strictly greater than min_size. With mode "and" a file must match both; with "or" it must match at least one.

The search covers every file under start. When follow_links is False, links are ignored. When it is True, a link leads to its target: a link to a file makes that file a candidate, and a link to a directory makes every file under it a candidate, with links inside it followed in the same way. A broken link is ignored. A file is one physical file however many paths and links lead to it, so it appears once, under its canonical path, and loops made of links must not make the search run forever.

Example 1

mode: "and"
root: {"name":"","children":[{"name":"docs","children":[{"name":"report.txt","size":900},{"name":"report.pdf","size":5000},{"name":"notes.txt","size":20}]},{"name":"logs","children":[{"name":"app.log","size":7000},{"name":"old","children":[{"name":"app.log.1","size":70000},{"name":"app.txt","size":10}]}]},{"name":"report.bak","size":6000}]}
start: "/"
min_size: 1000
name_query: "report"
follow_links: false
Output: ["/docs/report.pdf","/report.bak"]

Why: report.pdf (5000) and report.bak (6000) contain report and are strictly above 1000. report.txt (900) fails the size test and notes.txt fails the name test. The two matching paths come back sorted.

Constraints

The tree has 1 to 3 * 10^5 nodes
mode is "and" or "or"
0 <= size <= 10^12 for every file
0 <= min_size <= 10^12
0 <= len(name_query) <= 50
start is the canonical path of a directory in the tree
Sibling names are unique and contain no /

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question