Practice/Amazon/Design a File Search and Directory Traversal System

Design a File Search and Directory Traversal System

CodingMust

Problem

Build a flexible file system search engine that can traverse hierarchical directory structures and locate files based on customizable filter criteria. Your implementation should support multiple search parameters including file extensions, size ranges, and be extensible to accommodate additional filters in the future.

The file system is represented as a tree structure where each node can be either a file or a directory. Directories can contain multiple files and subdirectories. Your solution should efficiently traverse this structure and return the paths of all files that match the specified search criteria.

Design your system using object-oriented principles with a focus on extensibility and maintainability. The filter mechanism should allow easy addition of new search criteria without modifying existing code.

Requirements

1. Implement a file system search that traverses a tree-like directory structure
2. Support filtering by file extension (e.g., ".py", ".txt", ".js")
3. Support filtering by minimum and/or maximum file size in bytes
4. Allow combining multiple filters (all must match)
5. Return a list of file paths relative to the root directory
6. Use object-oriented design with extensible filter classes
7. Implement either depth-first or breadth-first traversal
8. Handle edge cases such as empty directories and non-existent criteria

Constraints

• The directory tree can have up to 1000 nodes (files + directories)
• Maximum directory nesting depth: 20 levels
• File names contain only alphanumeric characters, dots, and underscores
• File sizes are non-negative integers representing bytes
• Extension strings include the dot (e.g., ".txt" not "txt")
• Time complexity should be O(n) where n is the total number of nodes
• Space complexity should be O(h) for DFS or O(w) for BFS, where h is height and w is maximum width

Examples

Example 1: Simple extension filter

` Input: Directory: { "type": "directory", "name": "project", "children": [ {"type": "file", "name": "main.py", "size": 2048}, {"type": "file", "name": "data.json", "size": 1024}, {"type": "file", "name": "test.py", "size": 512} ] } Criteria: {"extension": ".py"}

Output: ["main.py", "test.py"]

Explanation: Both Python files match the extension filter `

Example 2: Size-based filter

` Input: Directory: { "type": "directory", "name": "docs", "children": [ {"type": "file", "name": "small.txt", "size": 100}, {"type": "file", "name": "large.txt", "size": 5000}, {"type": "file", "name": "medium.txt", "size": 1500} ] } Criteria: {"minSize": 1000}

Output: ["large.txt", "medium.txt"]

Explanation: Files with size >= 1000 bytes are returned `

Example 3: Nested directories

` Input: Directory: { "type": "directory", "name": "root", "children": [ { "type": "directory", "name": "src", "children": [ {"type": "file", "name": "app.js", "size": 3000}, { "type": "directory", "name": "components", "children": [ {"type": "file", "name": "header.js", "size": 800} ] } ] }, {"type": "file", "name": "config.json", "size": 200} ] } Criteria: {"extension": ".js"}

Output: ["src/app.js", "src/components/header.js"]

Explanation: Traverses nested structure and finds all JavaScript files `

Example 4: Combined filters

` Input: Directory: { "type": "directory", "name": "mixed", "children": [ {"type": "file", "name": "big.py", "size": 3000}, {"type": "file", "name": "small.py", "size": 500}, {"type": "file", "name": "big.txt", "size": 4000} ] } Criteria: {"extension": ".py", "minSize": 2000}

Output: ["big.py"]

Explanation: Only files matching both extension AND size criteria `