Map matching service
Design a map-matching service that snaps noisy GPS traces to the road network. Input is a stream of raw GPS points (each with a lat/lng and accuracy radius, sampled every 1-5 seconds, sometimes drifting 20-50m off the true road, sometimes dropping out in tunnels). Output is the actual sequence of road segments the vehicle traveled. This feeds ETA, trip pricing, and driver-quality scoring, so accuracy matters. The service must handle 100k concurrent trips and produce matched segments in near real time. Describe the matching algorithm, how you handle ambiguity at junctions and parallel roads, and the latency vs accuracy trade-off of online vs offline matching.
Clarify scale and constraints first. Propose a clean component breakdown, then go deep on the hard parts (data model, bottlenecks, consistency, failure modes) and name the trade-offs you are making.