Implement a URL router that matches request paths against patterns with placeholders
Company: Google
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: hard
Interview Round: Onsite
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?
Overview: Implement a URL router that registers path patterns with placeholder segments such as {userId} and returns the registered pattern that matches a concrete request path. It tests choosing a segment-level data structure, defining precedence between literal and placeholder matches, and analyzing registration and lookup complexity.
Read the full Google Software Engineer interview experience this question came from
Community answers
Answer by harbours-cherry-4b
dfghjkl;