← Questions

URL router with single-segment wildcards

0
GoogleTeslaCodingLast asked Oct 2026

Build a small URL router.

class Router:
    def __init__(self) -> None:
        pass

    def add_route(self, pattern: str, handler: str) -> None:
        pass

    def route(self, path: str) -> str:
        return ""
  • 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.

def example_router():
    r = Router()
    r.add_route("/shop/*/items", "shop_items")
    r.add_route("/shop/main/items", "main_items")
    r.add_route("/*/*/items", "any_items")
    r.add_route("/x/y/z", "xyz")
    r.add_route("/*/y/w", "any_y_w")
    return r


def test_exact_match():
    assert example_router().route("/shop/main/items") == "main_items"


def test_one_wildcard_beats_two():
    assert example_router().route("/shop/9/items") == "shop_items"


def test_two_wildcards():
    assert example_router().route("/blog/9/items") == "any_items"


def test_backs_out_of_a_dead_end():
    assert example_router().route("/x/y/w") == "any_y_w"


def test_wrong_number_of_segments():
    assert example_router().route("/shop/items") == ""


def test_earlier_literal_wins_a_tie():
    r = Router()
    r.add_route("/x/*", "x_star")
    r.add_route("/*/y", "star_y")
    assert r.route("/x/y") == "x_star"

def test_empty_router():
    assert Router().route("/anything") == ""


def test_empty_segments_are_ignored():
    r = Router()
    r.add_route("/a/b/", "ab")
    assert r.route("/a/b") == "ab"
    assert r.route("a/b") == "ab"
    assert r.route("//a//b//") == "ab"


def test_root_is_the_empty_path():
    r = Router()
    r.add_route("/", "root")
    assert r.route("/") == "root"
    assert r.route("") == "root"
    assert r.route("/a") == ""


def test_star_matches_exactly_one_segment():
    r = Router()
    r.add_route("/a/*", "a_star")
    assert r.route("/a/x") == "a_star"
    assert r.route("/a") == ""
    assert r.route("/a/x/y") == ""


def test_registering_again_replaces_the_handler():
    r = Router()
    r.add_route("/a/*", "old")
    r.add_route("/a/*", "new")
    assert r.route("/a/zzz") == "new"


def test_fewer_wildcards_beat_an_earlier_literal():
    r = Router()
    r.add_route("/a/*/*", "two_stars")
    r.add_route("/*/b/c", "one_star")
    assert r.route("/a/b/c") == "one_star"


def test_a_tie_is_decided_at_the_first_difference():
    r = Router()
    r.add_route("/*/b/c", "star_first")
    r.add_route("/a/*/c", "literal_first")
    assert r.route("/a/b/c") == "literal_first"


def test_backs_out_from_deep_down():
    r = Router()
    r.add_route("/a/b/c/d", "literal")
    r.add_route("/*/*/*/e", "stars")
    assert r.route("/a/b/c/e") == "stars"
    assert r.route("/a/b/c/d") == "literal"

def test_ten_thousand_routes():
    r = Router()
    for i in range(10_000):
        r.add_route(f"/api/v{i % 10}/svc{i}/*", f"h{i}")
    r.add_route("/api/*/*/health", "health")
    for i in range(0, 10_000, 7):
        assert r.route(f"/api/v{i % 10}/svc{i}/x") == f"h{i}"
    assert r.route("/api/v3/svc3/health") == "h3"
    assert r.route("/api/v3/svc4/health") == "health"
    assert r.route("/api/v3/svc3") == ""


def test_twenty_segments():
    segs = [f"s{i}" for i in range(20)]
    r = Router()
    r.add_route("/" + "/".join(segs[:-1] + ["other"]), "almost")
    r.add_route("/" + "/".join(["*"] * 20), "all_stars")
    r.add_route("/" + "/".join(["*"] + segs[1:]), "one_star")
    assert r.route("/" + "/".join(segs)) == "one_star"
    assert r.route("/" + "/".join(["z"] * 20)) == "all_stars"
    assert r.route("/" + "/".join(segs[:-1] + ["other"])) == "almost"


def test_the_latest_star_wins_among_equals():
    # Every pattern has one * at a different place; the path matches them all.
    n = 16
    r = Router()
    for i in range(n - 1):
        r.add_route("/" + "/".join(["a"] * i + ["*"] + ["a"] * (n - i - 2) + ["x"]), f"p{i}")
    r.add_route("/" + "/".join(["*"] * (n - 1) + ["y"]), "y")
    assert r.route("/" + "/".join(["a"] * (n - 1) + ["x"])) == f"p{n - 2}"
    assert r.route("/" + "/".join(["a"] * (n - 1) + ["y"])) == "y"

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

Write and test your solution herePython in your browser, the question's tests level by level, every submission kept for you.Sign in to start coding