Katkat
Back

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

GoogleSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

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.

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.

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?

Hints

Hint 1

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 2

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.

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?