Katkat
Back

Design a trie-based URL router with wildcards

AtlassianSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Design a trie-based URL router with wildcards evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Question

Implement a URL routing matcher that supports adding route patterns and matching request paths, using a trie (prefix tree) as the core data structure. Paths are split into /-delimited segments. Support static segments (e.g., /a/b/c) and a single-segment wildcard * that matches exactly one segment (e.g., /a/*/c).

Design and implement the following:

  1. APIs. Provide addRoute(pattern, handler), removeRoute(pattern), and match(path) -> (matchedHandler, matchedPattern). Routes must be addable and removable at runtime.
  2. Wildcard matching. * matches exactly one path segment. For example, /a/*/c matches /a/x/c and /a/y/c but not /a/c or /a/x/y/c.
  3. Precedence rules. Define and implement deterministic precedence when multiple registered patterns could match a path — for example, prefer a more specific (static) match over a wildcard match.
  4. Complexity. Analyze the time and space complexity of insertion, removal, and lookup.
  5. Concurrency. Explain strategies for making the structure thread-safe when reads and writes (route add/remove) happen concurrently.
  6. Tests. Provide unit tests covering edge cases such as leading/trailing slashes, the root path /, duplicate routes, and overlapping wildcard patterns.