Implement a URL router that matches request paths against patterns with placeholders

Implement a URL request router for a web service. The router supports two operations: 1. `processHandler(String handler)` registers a handler pattern, for example `/users/delete` or `/users/{userId}/photo/{photoId}`. 2. `getHandler(String url)` takes a real request path, for example `/users/123/photo/456`, and returns the previously registered handler pattern that matches it. For that example the answer is `/users/{userId}/photo/{photoId}`. A pattern segment in braces, such as `{userId}` or `{photoId}`, is a placeholder that matches any one URL segment. Every other segment must equal the corresponding URL segment. Choose a data structure, implement both operations, and give the time and space complexity of each. ```hint Work segment by segment Split paths on `/` and look for a structure in which registered patterns that share leading segments also share lookup work. ``` ```hint Dead ends Picture a URL whose first segments follow a literal branch that later fails, while a placeholder branch at the same depth would have matched. ``` ### Constraints and Clarifications - A placeholder matches exactly one segment, never zero or several, so a URL can match a pattern only if both have the same number of segments. - URLs passed to `getHandler` are concrete request paths and contain no placeholders. - The value returned by `getHandler` is the registered handler pattern itself. ### Clarifying Questions - When several registered patterns match the same URL, for example `/users/delete` and `/users/{userId}` for the URL `/users/delete`, which one should be returned? - What should `getHandler` return when no registered pattern matches: a null value, a default handler, or an error? - What should happen if a pattern is registered twice, or if two patterns differ only in their placeholder names, such as `/users/{id}` and `/users/{userId}`? - Should a trailing slash, an empty segment or a query string in the URL affect matching? - Is the router built once at startup and then only read, or can registrations happen while lookups are running? ### What a Strong Answer Covers - A segment-level structure (such as a trie) with literal children and a single placeholder child per position, and a clear place to store the handler - An explicit precedence rule for overlapping matches, and a lookup that stays correct when the preferred branch dead-ends - Complexity of registration and lookup in terms of segment count and number of registered patterns, including the worst case - Handling of no match, duplicate or conflicting registrations, and path normalization - Concrete test cases: literal versus placeholder overlap, segment-count mismatch, a prefix of a registered pattern, the root path ### Follow-up Questions - How would you also return the extracted placeholder values, for example `userId = 123` and `photoId = 456`? - How would you add a wildcard segment that matches the rest of the path, such as `/static/*`? - How would you route on the HTTP method as well as the path? - If many threads call `getHandler` and new handlers can be registered at runtime, how do you keep lookups fast and safe?