0

URL router with single-segment wildcards

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: URL router with single-segment wildcards

Companies: Google, Tesla

Difficulty: Hard

Problem statement

Build a small URL router.

class Router:
    def add_route(self, pattern: str, handler: str) -> None: ...
    def route(self, path: str) -> str: ...
  • A pattern and a path are split on / into segments. Empty segments are ignored, so /a/b/ is the same as /a/b, and / is the empty path.
  • A pattern segment is either a literal, which must equal the path segment, or *, which matches exactly one segment of any value. A pattern matches a path only if they have the same number of segments.
  • add_route registers handler for pattern. Registering the same pattern again replaces its handler.
  • route returns the handler of the most specific matching pattern, or "" if no pattern matches.
    • The pattern with the fewest * segments wins.
    • If two matching patterns have the same number of *, compare them left to right: at the first segment where they differ, the one with the literal wins.

Aim for lookups that do not scan every registered route.

Constraints: up to 10^4 routes; up to 20 segments per path; segments are non-empty strings without /.

Example

add_route("/shop/*/items", "shop_items")
add_route("/shop/main/items", "main_items")
add_route("/*/*/items", "any_items")
add_route("/x/y/z", "xyz")
add_route("/*/y/w", "any_y_w")

route("/shop/main/items")  -> "main_items"   # exact match
route("/shop/9/items")     -> "shop_items"   # 1 wildcard beats 2
route("/blog/9/items")     -> "any_items"
route("/x/y/w")            -> "any_y_w"      # the /x/... branch dead-ends
route("/shop/items")       -> ""             # wrong number of segments

With /x/* and /*/y both registered, route("/x/y") returns the handler of /x/*, because its first segment is a literal.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Clarify first. A pattern and a query path are both split on / into segments. Pin these down before coding:

  • Segments. Empty segments are dropped, so /a/b, a/b and /a/b/ are the same path. The root / is the empty path.
  • * matches exactly one segment. It never matches zero segments or several. So /a/* matches /a/x but not /a or /a/x/y. Lengths must be equal.
  • Most specific wins. The winner is the matching pattern with the fewest *. Ask how to break a tie between two patterns with the same count, such as /a/* and /*/b for /a/b. A sensible rule, and the one used here: compare left to right, and at the first segment where they differ the literal beats the *. So /a/* wins, because it fixes the earlier segment. This is also how most production routers behave.
  • No match returns "". Registering the same pattern again replaces its handler.

Brute force. Keep a list of (segments, handler). For a query, test every pattern of the same length segment by segment, and keep the best by (wildcard count, tie-break key). A query costs O(P * L) for P patterns of length L. This is fine for a handful of routes and is a good first answer, but it touches every route on every request.

Optimal: a segment trie. Each node has a map from literal segment to child, plus one optional * child. A node that ends a pattern stores its handler. To route a path, walk the trie with a DFS. At each depth i there are at most two ways forward: the child for the literal segments[i], and the * child.

  • Why a DFS and not a greedy walk. Taking the literal whenever it exists can fail. With patterns /a/b/c and /*/b/d, the path /a/b/d dead-ends under the literal a and only matches through *. So we must be able to back up.
  • Why it stays cheap. Every trie node sits at one fixed depth and is reached by one path, so the DFS visits each node at most once per query. The cost is bounded by the number of trie nodes that are consistent with the query, never by the number of 2^L literal/* choices.
  • Tie-break for free. Try the literal child before the * child. The DFS then finds matches in exactly the tie-break order (literal before *, left to right). Keep a match only if it has strictly fewer wildcards than the best so far. The first match found for any wildcard count is therefore the preferred one for that count.
  • Pruning. Carry the wildcard count down. If it already equals the best count found, stop: no deeper match can win. If the best is 0 (an exact match), stop the whole search.

Invariant. When the DFS is at node n with depth i and w wildcards used, the path from the root to n matches segments[0:i] and contains exactly w stars. best always holds the most specific match among the patterns already explored.

Code

from __future__ import annotations


class _Node:
    __slots__ = ("children", "star", "handler")

    def __init__(self) -> None:
        self.children: dict[str, _Node] = {}
        self.star: _Node | None = None
        self.handler: str | None = None


def _split(path: str) -> list[str]:
    return [seg for seg in path.split("/") if seg]


class Router:
    WILDCARD = "*"

    def __init__(self) -> None:
        self._root = _Node()

    def add_route(self, pattern: str, handler: str) -> None:
        node = self._root
        for seg in _split(pattern):
            if seg == self.WILDCARD:
                if node.star is None:
                    node.star = _Node()
                node = node.star
            else:
                node = node.children.setdefault(seg, _Node())
        node.handler = handler  # re-registering replaces the handler

    def route(self, path: str) -> str:
        segments = _split(path)
        best_count = len(segments) + 1  # worse than any real match
        best_handler = ""

        def dfs(node: _Node, i: int, wildcards: int) -> None:
            nonlocal best_count, best_handler
            if wildcards >= best_count:
                return  # cannot beat the current best
            if i == len(segments):
                if node.handler is not None:
                    best_count, best_handler = wildcards, node.handler
                return
            literal = node.children.get(segments[i])
            if literal is not None:
                dfs(literal, i + 1, wildcards)  # literal first: tie-break
            if node.star is not None and best_count > 0:
                dfs(node.star, i + 1, wildcards + 1)

        dfs(self._root, 0, 0)
        return best_handler


if __name__ == "__main__":
    r = Router()
    r.add_route("/users/*/posts", "user_posts")
    r.add_route("/users/me/posts", "my_posts")
    r.add_route("/*/*/posts", "any_posts")
    r.add_route("/a/b/c", "abc")
    r.add_route("/*/b/d", "star_bd")
    r.add_route("/a/*", "a_star")
    r.add_route("/*/b", "star_b")
    r.add_route("/", "root")

    assert r.route("/users/me/posts") == "my_posts"
    assert r.route("/users/42/posts") == "user_posts"
    assert r.route("/teams/7/posts") == "any_posts"
    assert r.route("/a/b/d") == "star_bd"      # needs backtracking
    assert r.route("/a/b") == "a_star"         # tie: earlier literal wins
    assert r.route("/a/b/c/") == "abc"         # trailing slash ignored
    assert r.route("/") == "root"
    assert r.route("/a") == ""                 # * needs one segment
    assert r.route("/users/42/likes") == ""
    r.add_route("/a/*", "a_star_v2")
    assert r.route("/a/zzz") == "a_star_v2"
    print("ok")

Complexity

Let L be the number of segments in a path and S the total number of segments over all registered patterns.

  • add_route: O(L) time (one dict lookup or insert per segment). The trie uses O(S) space in total.
  • route: O(L) to split, then the DFS visits each trie node at most once, so O(min(S, K)) where K is the number of trie nodes consistent with the query's prefixes. With no wildcards near the root it is O(L). The worst case is many patterns that all start with *. Recursion depth is O(L).
  • Brute force for comparison: O(P * L) per query, O(S) space.

Test cases

Routes: /users/*/posts → user_posts, /users/me/posts → my_posts, /*/*/posts → any_posts, /a/b/c → abc, /*/b/d → star_bd, /a/* → a_star, /*/b → star_b, / → root.

  • /users/me/posts → my_posts (exact match, 0 wildcards).
  • /users/42/posts → user_posts (1 wildcard beats 2).
  • /teams/7/posts → any_posts.
  • /a/b/d → star_bd. The literal branch /a/... dead-ends, so the search must back up.
  • /a/b → a_star. Both /a/* and /*/b have one wildcard; the earlier literal wins.
  • /a/b/c/ → abc (trailing slash ignored).
  • / → root.
  • /a → "". * never matches an empty segment, and /a itself is not registered.
  • /users/42/likes → "" (no match).
  • Empty router, any path → "".
  • Register /a/* again as a_star_v2; /a/zzz → a_star_v2 (replace).

Follow-ups

  1. Capture parameters. Patterns use :id instead of *, and route returns the handler plus {"id": "42"}. Store the parameter name on the * child (reject two different names at the same node, or keep them per pattern on the terminal node). During the DFS push the matched segment onto a list and record a copy when a new best is found.
  2. Multi-segment wildcard **. It matches one or more (or zero or more) trailing segments. Add a double_star child; when the DFS reaches it, it can consume any number of the remaining segments. Rank it below any number of * (or count it as L wildcards). The trie walk is still bounded by the nodes visited, but a ** in the middle of a pattern turns matching into a small DP over (node, i); memoize to keep it polynomial.
  3. HTTP methods and 405. Store a method → handler map on terminal nodes. A path that matches but has no handler for the method returns "405 Method Not Allowed" rather than "404". Decide whether a less specific pattern that does support the method should win instead; most routers say no.
  4. Remove routes and very large route tables. remove_route clears the handler and prunes empty nodes on the way back up. For thousands of routes, compress chains of single-child literal nodes (radix tree), and precompute for each node the minimum wildcard count of any handler below it so the DFS can prune before it descends.
  5. Different tie-break rules. If the interviewer wants "most recently registered wins" or "longest literal prefix wins", store a registration sequence number on each handler and compare (wildcards, -seq) or (wildcards, position of first star reversed) when updating the best. Only the comparison and the pruning condition change.

Interviewer expectations

Mid-level (L4)

  • Splits paths into segments and handles leading or trailing slashes.
  • Gets a correct brute force, then builds a trie with a separate * child.
  • Returns "" on no match and passes the basic examples.

Senior (L5)

  • Spots that a greedy literal-first walk is wrong and uses backtracking, with a counterexample.
  • Asks about and states a tie-break rule, and gets it from the literal-before-* search order.
  • Prunes on the wildcard count and explains why each trie node is visited at most once.
  • Handles parameter capture cleanly when asked.

Staff (L6+)

  • Compares the design with real routers (static over param over catch-all, radix trees) and explains why the specificity rule should be predictable to users.
  • Handles **, HTTP methods, 404 versus 405, and conflicting registrations, and says which should be errors at registration time.
  • Discusses route-table scale: compile-time conflict checks, precomputed subtree bounds, immutable tries swapped atomically on config reload, and the cost of a route lookup on the hot path.

Sign in to comment, vote or remix.