Implement an HTTP Router That Resolves Handlers for Paths with Named Parameters

Implement an HTTP router: the component that maps the path of an incoming request to the handler registered for it. It supports two operations: - `register(pattern, handler)` stores a handler for a path pattern. - `get(path)` finds the handler whose pattern matches a concrete request path and returns it together with the values of the pattern's parameters. Some patterns contain parameters and some do not. Assume a parameter is written as `:name` and stands for exactly one path segment: `/users/:id/profile` matches `/users/42/profile` with `id = "42"`, while `/about` matches only `/about`. You do not need to write the code that splits a path into segments; assume this helper already exists: ```python def split_path(path: str) -> list[str]: """"/users/42/profile" -> ["users", "42", "profile"]; "/" -> []""" ``` A possible interface (adjust it as you clarify): ```python from typing import Callable Handler = Callable[..., object] class Router: def register(self, pattern: str, handler: Handler) -> None: ... def get(self, path: str) -> tuple[Handler, dict[str, str]] | None: ... ``` ```hint Do not compare against every route Many patterns begin with the same segments. Look for a structure in which a lookup walks the request path once, segment by segment, instead of testing it against each registered pattern. ``` ```hint Where the names live Decide where a parameter's name is stored so that a lookup can report the value it matched, and what a lookup should do when a fixed segment and a parameter could both match at the same position. ``` ### Constraints and Clarifications - The parameter syntax (`:name`, occupying one whole segment) is an assumption; confirm it. - Splitting is handled by `split_path`, and the query string has already been removed from the request path. ### Clarifying Questions - If both a fixed pattern and a parameterized pattern match a request, such as `/users/me` and `/users/:id` for the path `/users/me`, which one wins? - If a fixed branch matches the first segments but has no route for the rest, should the router fall back to a parameterized pattern? For example, with `/users/me/settings` and `/users/:id/posts` registered, what should `/users/me/posts` return? - What should registering the same pattern twice do, and what about two patterns that differ only in parameter names, such as `/users/:id` and `/users/:user_id`? - Is the HTTP method part of the route? Are there wildcards that match the rest of the path? - Are trailing slashes significant, and are paths case-sensitive? - What should `get` return when no pattern matches? ### What a Strong Answer Covers - Settles the parameter syntax, the precedence between fixed and parameter segments, duplicate registrations and the no-match result before coding - A structure keyed by path segments that shares common prefixes, with a clear place for each handler and its parameter names - A lookup that returns the right handler and parameter values under the chosen precedence, including when a preferred branch dead-ends - Time and memory complexity in terms of path length and the number of registered routes - Tests for the root path, overlapping patterns, conflicting registrations and misses ### Follow-up Questions - The same path can now have different handlers for GET and POST, and a path that exists under another method must be distinguishable from one that does not exist. What changes? - Add a catch-all parameter that matches the rest of the path, such as `/static/*filepath`. Where does it rank against the other kinds of segment? - What is the worst-case cost of one `get` call in your design, and which sets of registered patterns trigger it? - Routes are registered at startup and then read by many request threads. What, if anything, needs locking, and what changes if routes can be added while traffic is being served?