Katkat
Back

Event Topic Router With Named Placeholders and Tail Wildcards

GoogleSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Build a router for a telemetry message bus that maps dot-separated topics to registered subscription patterns with named placeholders and a trailing multi-segment wildcard; tests trie design, precedence rules and backtracking.

A logistics company streams telemetry from its trucks over a message bus. Every message carries a topic made of dot-separated segments, such as fleet.t42.gps or fleet.depot.engine.e17. Services register patterns, and the bus must decide which single pattern handles each incoming topic.

Part 1 - Literals and named placeholders

Implement a class:

class TopicRouter:
    def add(self, pattern: str) -> None: ...
    def resolve(self, topic: str) -> tuple[str, dict[str, str]] | None: ...
  • A pattern segment written as <name> is a placeholder that matches exactly one topic segment. Any other segment must match literally.
  • resolve returns the matching pattern and the placeholder bindings, or None if nothing matches.
  • Precedence: if several patterns match, compare them segment by segment from the left; at the first position where they differ, a literal beats a placeholder.
  • Registering the same pattern twice is a no-op. Registering a pattern that differs from an existing one only in placeholder names (e.g. fleet.<truck>.gps vs fleet.<vehicle>.gps) raises ValueError.
  • Empty segments (fleet..gps) are invalid input.
add("fleet.<truck>.gps")
add("fleet.depot.gps")
add("fleet.<truck>.engine.<code>")
add("fleet.depot.engine.status")

resolve("fleet.t42.gps")          -> ("fleet.<truck>.gps", {"truck": "t42"})
resolve("fleet.depot.gps")        -> ("fleet.depot.gps", {})
resolve("fleet.depot.engine.e17") -> ("fleet.<truck>.engine.<code>", {"truck": "depot", "code": "e17"})
resolve("fleet.t42.brakes")       -> None

Note the third case: the literal depot branch is tried first but dead-ends at e17, so the router must back up and try the placeholder.

Part 2 - Tail wildcard

Allow ** as the last segment of a pattern. It matches one or more remaining segments and binds them (joined with dots) under the key "**". At any position it has the lowest precedence: literal, then placeholder, then **.

add("fleet.**")
add("fleet.<truck>.engine.**")

resolve("fleet.t42.brakes")        -> ("fleet.**", {"**": "t42.brakes"})
resolve("fleet.t9.engine.oil.temp")-> ("fleet.<truck>.engine.**", {"truck": "t9", "**": "oil.temp"})
resolve("fleet.t9.engine.e3")      -> ("fleet.<truck>.engine.<code>", {"truck": "t9", "code": "e3"})
resolve("fleet")                   -> None

Part 3 - Analysis

State the time and space complexity of add and resolve, and argue why resolve cannot blow up exponentially on a fixed set of patterns.

Constraints

  • Up to 10^5 patterns, up to 32 segments per topic, segment length up to 64.
  • resolve is called far more often than add.

Hints

Hint 1

Store patterns in a trie keyed by segment. Each node needs a map of literal children and at most one placeholder child (placeholder names don't affect matching).

Hint 2

Search depth-first: literal child first, then the placeholder child, and only return a hit once a full path succeeds.

Hint 3

A '**' pattern can be stored on the node *before* the wildcard - when you reach that node with segments left, it is a fallback match.

Hint 4

For bindings, re-walk the winning pattern's segments alongside the topic instead of storing names in the trie.

Follow-up questions

  • Return all matching patterns in precedence order (fan-out delivery) instead of only the best one.
  • How would you support a single-segment anonymous wildcard '*' alongside named placeholders, and what conflicts arise?
  • How would you make add and resolve safe for concurrent use with millions of lookups per second?
  • Add type constraints such as <truck:int>; how does that change precedence and the trie?