Implement ad matching and delivery routing
Overview
This prompt evaluates algorithm and data-structure design plus optimization skills across two domains: efficient ad-matching with dynamic updates and budgeted targeting, and route planning on weighted graphs for near-optimal delivery sequences.
Part A: Implement a data structure for an ad-matching service that supports add(campaign), remove(campaign), and match(request), where a request has attributes (e.g., location, device, interests) and campaigns specify targeting predicates and budgets. Optimize for fast matching and frequent updates; discuss complexity and trade-offs. Part B: Given a weighted road graph with nonnegative edges, a depot, and N delivery stops, implement plan_route(graph, depot, stops) to produce a near-optimal route. Compare exact versus heuristic approaches (e.g., shortest paths plus TSP heuristics), analyze complexity, and handle practical constraints such as capacity or time windows.