Katkat
Back

Resolve Templated CDN Asset Paths to Their Registered Handlers

GoogleSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Implement a resolver that registers CDN asset path templates containing placeholder segments and, given a concrete request path, returns the matching template's handler along with the captured placeholder values.

A CDN serves images, thumbnails, and other derived assets. Each kind of asset is served by a path template registered ahead of time, such as /images/{assetId}/thumbnail or /images/featured/thumbnail. A template segment written as {name} is a placeholder that matches any single path segment; every other segment must match exactly.

Implement a class with two operations:

class AssetPathResolver:
    def register(self, pattern: str, handler) -> None: ...
    def resolve(self, path: str) -> tuple[object, dict[str, str]] | None: ...
  • register(pattern, handler) adds a template. Registering the same pattern twice, or two patterns that are indistinguishable from each other (e.g. differing only in placeholder name at the same position), must raise an error at registration time rather than silently overwriting.
  • resolve(path) takes a concrete request path (no placeholders) and returns a (handler, captures) tuple, where captures maps each placeholder name along the matched template to the path segment it matched — or None if nothing matches.

Matching rules

  • A path can only match a template with the same number of segments.
  • When a concrete segment could continue down either a literal child or a placeholder child, the literal branch is tried first; if it leads to a dead end further down the path, the resolver must backtrack and try the placeholder branch instead.
  • The returned captures dict contains only the placeholders from the template that actually matched.

Example

register("/images/{assetId}/thumbnail", thumb_handler)
register("/images/featured/thumbnail",   featured_handler)
register("/images/{assetId}/full",       full_handler)

resolve("/images/featured/thumbnail") -> (featured_handler, {})
resolve("/images/42/thumbnail")       -> (thumb_handler, {"assetId": "42"})
resolve("/images/42/full")            -> (full_handler, {"assetId": "42"})
resolve("/images/42/nope")            -> None

register("/cdn/static/logo.png",  logo_handler)
register("/cdn/{bucket}/{key}",   generic_handler)

resolve("/cdn/static/other.png")
-> (generic_handler, {"bucket": "static", "key": "other.png"})   # literal branch dead-ends, backtrack to placeholder

Give the time and space complexity of both operations.

Hints

Hint 1

Split every path on '/' and build a tree keyed segment by segment — patterns that share a prefix should share the traversal, not be compared one by one.

Hint 2

Each tree node needs at most one placeholder child (since a position can only be one placeholder at a time) plus a dict of literal children.

Hint 3

Resolve recursively: try the literal child first, and only recurse into the placeholder child if the literal branch's recursive call returns no match.

Hint 4

Detecting a duplicate registration means checking, at the final node for a pattern, whether a handler is already attached there.

Follow-up questions

  • How would you extend this to support a catch-all tail segment that matches the rest of the path, like `/assets/{*rest}`?
  • If registrations happen concurrently with lookups in a live CDN, what would you need to change to make this thread-safe without locking every lookup?
  • How would you report, at registration time, which existing pattern a new one conflicts with and why, in a way that's useful in an error message?
  • How would you support optional segments, like a version prefix that may or may not be present?