Katkat
Back

Design a Ride-Hailing Matching System

AmazonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This question evaluates competence in large-scale real-time system design, covering high-throughput ingestion and burst absorption, stream deduplication, geospatial indexing, and low-latency matching and caching for ride-hail workflows.

Design a ride-hailing matching system similar to a taxi or rideshare application (e.g. Uber, Lyft, DiDi).

The interview focuses on the driver-location pipeline and nearby-driver lookup: how high-frequency GPS updates from drivers are ingested, cleaned, and absorbed without overwhelming downstream services, and how a rider's pickup request is matched to nearby available drivers with low latency. Your design should cover requirements, the public API, data storage, the geospatial index, scaling, reliability, and the key trade-offs.

At minimum, address each of the six areas below. They build on one another.

  1. High-frequency GPS ingestion — drivers continuously upload GPS coordinates. How do you accept this write volume?
  2. Deduplication — drop noisy / redundant / out-of-order GPS updates.
  3. Burst absorption — smooth traffic spikes and protect downstream services from write bursts.
  4. Nearby-driver lookup — a rider requests a ride; efficiently find nearby available drivers and match.
  5. Geospatial indexing trade-offs — compare approaches such as Quadtree vs H3 (hexagonal hierarchical grid).
  6. In-memory geospatial cache — explain how Redis GEO (or a similar in-memory geo store) fits in.

Constraints & Assumptions

You are not given exact production numbers, so state your own and design to them. Reasonable assumptions for a single large metro:

  • Drivers: ~100K online drivers in a busy city; each available driver emits a GPS update every ~1–4 seconds → on the order of $10^4$–$10^5$ location writes/second per city.
  • Riders: thousands of ride requests per minute at peak; each request needs a nearby-driver lookup.
  • Latency: nearby-driver lookup should return within a few hundred milliseconds (p99).
  • Freshness: matching should only consider driver locations seen in roughly the last 5–15 seconds.
  • Scope: focus on online matching (ingestion → index → match). Pricing, navigation/routing, payments, and the rider/driver mobile UX are out of scope except where they constrain the design.
  • Geography: the system is partitioned by city/region; the vast majority of requests are served by drivers in the same metro.

Clarifying Questions to Ask

  • What scale are we targeting — one metro, one country, or global? What's the peak QPS for GPS writes and for ride requests?
  • How fresh must driver locations be for matching, and what p99 latency is acceptable for the lookup?
  • Do we need to persist the full historical GPS trail (for ETA models, fraud, replay), or only the current location?
  • Is matching one-to-one (offer to a single best driver) or broadcast (offer to several, first-accept wins)?
  • Are there vehicle types / pooling / driver-preference constraints that filter the candidate set?
  • What are the consistency requirements — can the location cache be eventually consistent if trip assignment is strongly controlled?

Hints

Hint 1

Where to start — the central insight: The write path (driver GPS) and the read path (rider lookup) have completely different characteristics: writes are huge-volume and lossy-tolerant; reads are latency-sensitive and must be correct. **Decouple them.** Don't write every GPS point to your matching store synchronously.

Hint 2

Ingestion & burst absorption: Where should a sudden burst of writes pile up — in your matching store, or somewhere cheaper that the read path never touches? Think about what sits *between* the accept-fast ingestion API and whatever updates the index, what property keeps one driver's updates in order, and how that buffer behaves when the index consumers fall behind.

Hint 3

Deduplication signals: What distinguishes an update worth keeping from one you can safely throw away? Reason along a few independent axes — identity (is this literally the same point?), magnitude of movement, ordering relative to what you've already accepted, and physical plausibility — and ask what cheap, client-supplied token would let you make the ordering call as a single comparison.

Hint 4

Nearby-driver lookup — what the index holds and how you query it: Should the hot lookup index hold *every* driver, or a filtered subset — and keyed by what? When your first search comes back with too few candidates, what's your move? And before you trust a driver the index returned, what properties should you re-check, and on what signal would you order the survivors?

Hint 5

Quadtree vs H3: Contrast on: adaptivity to density, stable global cell IDs, ease of distributed sharding, neighbor/ring expansion, and boundary handling. A Quadtree adapts to density but is a custom structure that's awkward to shard; H3 gives stable hexagonal cell IDs that shard and expand by ring trivially but is a fixed-resolution approximation needing post-filtering.

Hint 6

Redis GEO & double-assignment: What is the minimal set of operations your hot index has to support as drivers move and go on/offline, and does your chosen in-memory geo store expose them directly? Separately, notice that two riders can race for the *same* driver: name where that race lives and what kind of atomic claim (think state machine + a single-winner transition) prevents both offers from landing.

Follow-up questions

  • A driver sits exactly on a cell/shard boundary, or a rider requests pickup there. How do you guarantee they aren't missed?
  • The location-index cluster for one city loses a node (or the whole Redis instance is cold-restarted). How do you rebuild the index and what's the user-visible impact?
  • How would you extend this to support surge pricing or ETA-based ranking without slowing the lookup path?
  • Drivers report being shown ride offers they never received, or being offered to two riders at once. Where in the design does this break, and how do you fix it?