Sign in to track progress, unlock prep layers, and browse your pipeline.Sign in
Design a trie-based URL router with wildcards
Problem Description
Design and implement a URL routing matcher that supports adding route patterns and matching request paths. The core data structure must be a trie.
Requirements
- Route Patterns: Support static path segments (e.g.,
/a/b/c) and single-segment wildcards (e.g.,/a/*/c). - API Design: Expose the following APIs:
addRoute(pattern, handler): Adds a new route pattern and its associated handler.removeRoute(pattern): Removes an existing route pattern.match(path): Given a request path, returns thematchedHandlerand thematched pattern.
- Precedence Rules: Establish clear precedence rules for scenarios where multiple patterns could match a given path. For instance, prioritize more specific matches over wildcard matches (e.g.,
/a/b/cshould match/a/b/cbefore/a/*/c). - Complexity Analysis: Provide a time and space complexity analysis for all operations.
- Unit Tests: Include unit tests to cover edge cases such as leading/trailing slashes, duplicate route additions, and overlapping wildcard patterns.
AI interview prep
Core dilemma
The central engineering conflict is balancing efficient trie traversal for path matching, especially with wildcards and complex precedence rules, against the need for efficient and correct route addition and removal, while maintaining a robust and extensible design.
Mid-level signals3
Senior signals3
Red flags3
3 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Design a trie-based URL router with wildcards
Problem Description
Design and implement a URL routing matcher that supports adding route patterns and matching request paths. The core data structure must be a trie.
Requirements
- Route Patterns: Support static path segments (e.g.,
/a/b/c) and single-segment wildcards (e.g.,/a/*/c). - API Design: Expose the following APIs:
addRoute(pattern, handler): Adds a new route pattern and its associated handler.removeRoute(pattern): Removes an existing route pattern.match(path): Given a request path, returns thematchedHandlerand thematched pattern.
- Precedence Rules: Establish clear precedence rules for scenarios where multiple patterns could match a given path. For instance, prioritize more specific matches over wildcard matches (e.g.,
/a/b/cshould match/a/b/cbefore/a/*/c). - Complexity Analysis: Provide a time and space complexity analysis for all operations.
- Unit Tests: Include unit tests to cover edge cases such as leading/trailing slashes, duplicate route additions, and overlapping wildcard patterns.