Matching and Dispatch

SLIDE 80: Section Intro, Matching and Dispatch

Section 7: Matching and Dispatch

Matching is the core problem that separates a ride-sharing platform from every other type of system you will design in an interview. Content platforms distribute static content. E-commerce platforms match buyers with inventory. A ride-sharing platform must match two moving entities in real time, under tight latency constraints, while preventing conflicts across concurrent requests. The engineering is in the matching, not the map.

This section builds directly on two previous sections. The spatial index from Section 6 provides the “find nearby drivers” query that feeds into matching. The Trip Service orchestrator from Section 4 coordinates the flow between Matching, Dispatch, and ETA. Here, we go inside those services to understand how candidate selection, scoring, offer dispatch, and conflict resolution actually work.

What We’ll Cover:

1. Why matching is not just “find the closest driver”
2. Greedy matching: simple, fast, locally optimal
3. Batch matching: slower, globally optimal
4. Greedy vs batch trade-offs and when to use each
5. Candidate selection pipeline: from 50K drivers to 1 match
6. Multi-factor scoring and ranking
7. Dispatch flow: offer, accept, decline, timeout, cascade
8. Race conditions: two riders competing for the same driver
9. ETA estimation with graph-based routing
10. Geographic partitioning for matching at scale

Interview Pacing:

In a 45-minute interview, matching and geospatial together occupy minutes 20-28. You have approximately 4-5 minutes for matching. Lead with the candidate pipeline (filter, score, rank), explain greedy vs batch as a trade-off, and describe the dispatch offer-accept-decline cycle. If the interviewer pushes on concurrency, discuss the locking strategy for preventing double-booking.

SLIDE 81: The Matching Problem: Not Just Finding the Closest

The naive framing of the matching problem is: “find the closest driver to the rider.” This framing is wrong for three reasons, and interviewers specifically test whether you recognize them.

Problem 1: Closest is not always best.

The closest driver might be 200 meters away but heading in the opposite direction on a one-way street, resulting in a 6-minute pickup. A driver 800 meters away but heading toward the rider on the same road might arrive in 2 minutes. Distance and ETA are different metrics, and ETA is what matters to the rider.

Problem 2: Closest ignores eligibility constraints.

The rider requested an XL vehicle. The closest 5 drivers are all standard sedans. The matching system needs to filter by vehicle type, capacity, and driver status before considering distance. The closest eligible driver might be the 12th closest overall.

Problem 3: Closest creates global inefficiency.

When multiple ride requests arrive simultaneously (which happens constantly in a city with 250 requests/sec), assigning each request to its individually closest driver can produce a globally suboptimal assignment. Two requests might compete for the same nearby driver, leaving one rider with a far driver when a slightly different assignment would have given both riders short pickups.

The Correct Framing:

Matching is a constrained optimization problem. Given a set of ride requests and a set of available drivers, find an assignment that minimizes total pickup time across all requests, subject to constraints (vehicle type, capacity, driver status, acceptance probability).

This framing leads to two algorithmic families: greedy matching (optimize each request individually) and batch matching (optimize across multiple requests simultaneously). Both are valid. The trade-off is between latency and global optimality.

SLIDE 82: Greedy Matching: Pick the Nearest Available Driver

Greedy matching is the simplest approach. For each incoming ride request, independently find the best available driver and assign immediately.

How It Works:

1. Ride request arrives with pickup location and vehicle type
2. Query the spatial index (Section 6) for drivers within a radius (typically 5km)
3. Filter candidates by eligibility (vehicle type, online status, not already in a trip or dispatch)
4. Score remaining candidates on ETA, rating, acceptance rate (covered in SLIDE 85B)
5. Dispatch the ride offer to the top-scored candidate
6. If the driver accepts, the match is complete. If not, cascade to the next candidate (SLIDE 86B)

Performance:

The spatial index query returns results in sub-200ms (Section 6). Scoring is simple arithmetic on a small candidate set (typically 20-50 drivers). The entire matching decision takes 200-500ms per request. This is fast enough for individual ride requests.

When Greedy Works Well:

Greedy matching works well when ride requests are sparse relative to driver supply. If requests arrive every few seconds and there are many available drivers, each greedy assignment is close to globally optimal because there is little competition for the same drivers. In a city with 50,000 drivers and 50 requests per minute, greedy produces good results.

SLIDE 82B: Greedy Matching: Where It Breaks

Greedy matching breaks down when demand density increases. The failure mode is predictable: multiple nearby requests compete for the same drivers, and sequential greedy assignment creates cascading suboptimality.

Worked Example: Three Riders, Three Drivers

The Key Insight:

Greedy assignment is order-dependent. The result changes based on which request is processed first. In a system handling 250+ requests/sec, request ordering is effectively random. This means greedy matching occasionally produces poor assignments that a batch approach would avoid. The question is whether the improvement justifies the added latency.

SLIDE 83: Batch Matching: Collect and Optimize

Batch matching takes the opposite approach from greedy. Instead of assigning each request immediately, it collects ride requests over a short time window (2-5 seconds) and solves the assignment across all pending requests simultaneously.

How It Works:

1. Ride requests arrive and are placed in a batch queue
2. Every 2-5 seconds, the batch window closes and all pending requests are collected
3. For each request, the system queries nearby available drivers (same spatial index query as greedy)
4. The solver finds the assignment that minimizes total pickup ETA across all request-driver pairs
5. All matched pairs receive dispatch offers simultaneously

Why Batching Produces Better Results:

With 250 requests/sec and a 2-second window, each batch contains approximately 500 requests (globally) or 5-50 requests per city. The solver can see all of them at once and avoid the greedy problem of two requests competing for the same driver. It can assign rider A to driver 2 (slightly farther) so that rider B gets driver 1 (much closer), reducing total pickup time.

The Latency Cost:

Every rider waits for the batch window to close before matching begins. A 2-second window means every rider waits an average of 1 second (half the window) plus the solver computation time (100-500ms for city-scale batches). This adds 1-1.5 seconds of latency compared to greedy. For most riders, this is imperceptible. But during low-demand periods when there is no contention, the delay is pure waste.

SLIDE 83B: Batch Matching: The Assignment Problem

The mathematical structure behind batch matching is the assignment problem, specifically bipartite matching.

Bipartite Graph Construction:

Riders are nodes on one side. Available drivers are nodes on the other side. Each rider-driver pair has an edge weighted by the estimated pickup ETA. The goal: find a matching (one driver per rider, one rider per driver) that minimizes the total weight.

The Hungarian Algorithm:

The classic solution to the assignment problem. For n riders and m drivers, it finds the minimum-cost assignment in O(n^3) time. At city scale with 50 requests per batch and 200 candidate drivers, this runs in under 100ms. The algorithm is well-studied and available in standard libraries (scipy.optimize.linear_sum_assignment in Python, for example).

Practical Simplifications:

In practice, the solver does not consider every driver for every rider. Each rider’s candidate set is pre-filtered by the spatial index to nearby eligible drivers (typically 20-50 candidates). This makes the bipartite graph sparse, and the solver runs much faster than the worst-case O(n^3) on the full driver pool.

When Batch Matching Becomes Impractical:

The assignment problem is polynomial for simple one-to-one matching, but becomes NP-hard when additional constraints are added (vehicle type preferences, shared rides, multi-stop trips). Production systems use heuristic solvers (greedy with local search, simulated annealing) that find near-optimal solutions in bounded time rather than guaranteed-optimal solutions.

SLIDE 84: Greedy vs Batch: Comparison and Decision Framework

Decision Framework:

Use greedy when demand is low relative to supply (ratio > 3:1 drivers to requests). Use batch during high demand or surge periods (ratio < 2:1). The transition can be dynamic: monitor the supply-demand ratio per city and switch algorithms when the ratio crosses a threshold.

What Production Systems Actually Do:

Uber uses a hybrid approach. During normal demand, requests are processed greedily with sub-second matching. When demand spikes (concert ends, weather event, rush hour in dense areas), the system switches to batch mode with short windows (2-3 seconds) to optimize across competing requests. The transition is automatic, driven by real-time supply-demand metrics per zone.

This hybrid is the strongest interview answer because it demonstrates that you understand both approaches and recognize that neither is universally superior. The trade-off between individual latency and global efficiency is a judgment call that depends on current conditions, not a fixed design decision.

Interview Tip:

When an interviewer asks about matching, do not commit to one algorithm immediately. State the trade-off: “Greedy is simpler and faster for individual riders, but batch matching produces better global assignments during high demand. In production, I would use a hybrid that switches based on real-time supply-demand ratio.” This shows mature engineering judgment.

SLIDE 85: Candidate Selection Pipeline

Before any scoring or assignment happens, the system must narrow the pool of all active drivers down to a small set of viable candidates for each ride request. This is a funnel with four stages.

Stage 1: Proximity Filter (50,000 to 200)

Query the spatial index (Redis GEOSEARCH from Section 6) for all drivers within a configurable radius of the rider’s pickup location. The default radius is 5km in urban areas, 10-15km in suburban areas. This is the single most important filter because it eliminates 99.6% of drivers in one sub-200ms query.

Stage 2: Eligibility Filter (200 to 50)

Filter the nearby drivers by hard constraints that cannot be traded off:

Vehicle type: rider requested XL, filter out sedans and economy cars.
Driver status: must be “available” (not in another trip, not in an active dispatch).
Capacity: for shared rides, driver must have available seats.
Regulatory: driver must be licensed to operate in this zone (relevant for airport pickups, cross-border areas).

Stage 3: Quality Filter (50 to 20)

Apply soft quality thresholds:

Rating: exclude drivers below a minimum rating threshold (e.g., 4.5 stars) unless the candidate pool would be too small.
Acceptance rate: deprioritize drivers who frequently decline offers (below 70% acceptance rate), but do not hard-exclude them unless the pool is large enough.

Stage 4: Score and Rank (20 to 1)

Score the remaining candidates on multiple weighted factors (next slide) and return a ranked list. The top candidate gets the dispatch offer. The ranked list is retained for cascade if the top candidate declines.

Funnel Numbers at City Scale:

50,000 active drivers in a major city. After proximity filter: ~200. After eligibility: ~50. After quality filter: ~20. After scoring: top 5-10 ranked candidates, with the number 1 candidate receiving the dispatch offer.

SLIDE 85B: Scoring and Ranking Candidates

After the candidate pipeline reduces the pool to 20-50 eligible drivers, each candidate receives a composite score based on multiple factors. The driver with the highest score gets the ride offer.

Scoring Formula:

score = (w1 x ETA_score) + (w2 x rating_score) + (w3 x acceptance_score)
      + (w4 x heading_score) + (w5 x trip_match_score)

Typical weights:
  w1 = 0.40  (ETA / proximity)
  w2 = 0.20  (driver rating)
  w3 = 0.20  (acceptance rate)
  w4 = 0.10  (heading direction)
  w5 = 0.10  (trip distance preference match)

Factor Breakdown:

Why ETA Gets the Highest Weight:

The rider cares most about how fast the driver arrives. A 4.9-star driver who is 8 minutes away is worse for the rider than a 4.7-star driver who is 2 minutes away. ETA dominates because it directly impacts the metric riders care about most: waiting time.

Why Not Just Use ETA Alone:

If matching were purely ETA-based, drivers with low ratings would keep getting dispatched (because they happen to be nearby), leading to poor rider experiences and platform quality degradation. Including rating and acceptance rate ensures that consistently poor or unreliable drivers are deprioritized, even when they are geographically close.

Heading Direction: The Subtle Factor

A driver 500 meters from the rider sounds close. But if the driver is on a highway moving away from the rider at 60 km/h, the actual pickup time is much longer than a driver 800 meters away on a side street heading toward the rider. The heading factor captures this: it computes the angle between the driver’s current direction of travel and the vector from the driver to the rider. A driver heading directly toward the rider scores 1.0. A driver heading directly away scores 0.0.

SLIDE 86: Dispatch Flow: Sending the Ride Offer

Once the Matching Service selects the top-ranked driver, the Dispatch Service takes over to manage the offer-accept-decline communication.

What the Driver Sees:

The ride offer appears on the driver’s screen as a card with key information: rider’s pickup location on a map, estimated distance to pickup, estimated trip distance and duration, estimated fare (in markets where this is shown), and the rider’s rating. The driver has 15 seconds to accept or decline.

The 15-second window is a deliberate design choice. Too short (5 seconds) and drivers cannot evaluate the offer, leading to uninformed declines. Too long (30 seconds) and the rider waits too long, especially if the first driver does not respond. 15 seconds balances driver evaluation time against rider patience.

Offer Delivery Mechanism:

The Dispatch Service does not call the driver directly. It looks up the driver’s WebSocket Gateway connection in Redis (driver_id to gateway_server_id mapping from Section 4), then sends the offer through the WebSocket Gateway to the driver’s persistent connection. This is why the WebSocket infrastructure from Section 4 exists: the offer arrives on the driver’s screen within 100-200ms of the matching decision, with no polling delay.

What Happens on Accept:

The Dispatch Service confirms the match with the Trip Service. The Trip Service transitions the trip state from “matching” to “matched” and then to “driver_en_route.” Both rider and driver apps receive confirmation. The driver’s navigation begins, and the rider sees the driver’s live position on the map via the Tracking Service.

SLIDE 86B: Dispatch: Decline, Timeout, and Re-Dispatch

Not every offer is accepted. The Dispatch Service must handle three outcomes and cascade gracefully.

Outcome 1: Driver Declines

The driver taps “Decline” within the 15-second window. The decline is recorded (it affects the driver’s acceptance rate metric, which feeds back into future scoring). The Dispatch Service immediately sends the offer to the next candidate in the ranked list from the Matching Service. No re-query of the spatial index is needed yet because the ranked list is still fresh (generated seconds ago).

Outcome 2: Driver Times Out

The 15-second window expires without a response. This is treated identically to a decline: cascade to the next candidate. Timeout is the most common non-acceptance outcome. Reasons include: driver is driving and did not see the notification, driver’s phone lost connectivity momentarily, or driver is evaluating another platform’s offer simultaneously.

Outcome 3: Re-Query After Multiple Cascades

After 3-5 consecutive declines or timeouts (configurable per market), the original ranked list is considered stale. During those 45-75 seconds, driver positions have changed, some candidates may have gone offline, and new drivers may have entered the area. The Dispatch Service triggers a re-query: the Matching Service re-runs the full candidate pipeline (spatial index query, eligibility filter, scoring) with a wider radius (e.g., 5km expanded to 8km) to capture drivers who were previously out of range.

Cascade Timeline:

If no driver accepts after 2 re-queries (approximately 2 minutes of total matching time), the system notifies the rider: “No drivers available right now. We will keep trying.” The rider can cancel or wait. This is the graceful degradation path rather than an error state.

Interview Tip:

Describing the full cascade flow (offer, timeout, cascade, re-query with expanded radius) is one of the highest-signal answers in a matching discussion. It shows you understand that matching is not a single-step operation but a multi-round process with fallback strategies.

SLIDE 87: Race Conditions: Two Riders Matched to Same Driver

Concurrent matching creates a specific race condition: two ride requests arrive simultaneously, both query the spatial index, and both find driver_A as the nearest available driver. If both proceed to dispatch, driver_A receives two conflicting offers.

Why This Happens:

The spatial index (Redis) returns a snapshot of available drivers at the moment of the query. Between the query and the dispatch (200-500ms), another Matching Service instance can query the same spatial index and get the same results. The index does not know that driver_A is “about to be dispatched” because the dispatch has not happened yet.

Solution: Optimistic Locking on Driver Status

When the Matching Service selects a driver, it attempts to set a lock on that driver before dispatching. The lock is implemented as an atomic Redis operation:

SET driver:A:dispatch_lock trip_123 NX EX 30

NX means “set only if the key does not exist.” EX 30 means “expire after 30 seconds.” If the SET succeeds, this Matching Service instance owns the lock and proceeds to dispatch. If the SET fails (key already exists), another instance has already locked this driver, and the current instance falls back to the next candidate in its ranked list.

Other Race Conditions in Matching:

Driver goes offline during matching: The driver stops sending GPS updates or explicitly goes offline between the spatial index query and the dispatch. The dispatch push fails or the driver does not respond. Mitigation: TTL on position records (15-20 seconds), and treat dispatch timeout as a signal to remove the driver from the candidate pool.

Driver accepts but Trip Service does not receive confirmation: Network partition between the WebSocket Gateway and the Trip Service. The driver sees “accepted” but the trip is not confirmed. Mitigation: idempotent trip state transitions. The accept message is retried. If the trip has already been assigned to another driver (because the system timed out and cascaded), the late-arriving accept is rejected and the driver is released.

Network partition during acceptance: The driver taps “accept,” but the message is delayed. Meanwhile, the Dispatch Service times out and sends the offer to the next driver, who also accepts. Now two drivers think they have the same ride. Mitigation: the Trip Service is the single source of truth. Only the first accept that reaches the Trip Service is honored. The second accept receives a rejection response, and the second driver is returned to the available pool.

SLIDE 87B: Preventing Double-Booking: Locking Strategies Compared

Three locking strategies can prevent the double-booking race condition. Each has different trade-offs.

Why Optimistic Locking Wins for Ride-Sharing:

Contention is low in practice. At 250 requests/sec globally and 50,000 drivers per city, the probability of two requests targeting the same driver in the same 200ms matching window is small. Optimistic locking (try, fail fast, try next candidate) handles the rare collision without adding latency to the common case. Pessimistic locking would add 5-10ms to every match decision, even when there is no contention.

Lock Lifecycle:

The 30-second TTL on the lock is a safety net. If the Dispatch Service crashes after acquiring the lock but before the driver responds, the lock expires and the driver becomes available again. Without TTL, a crashed dispatch process would permanently lock a driver out of the system.

SLIDE 88: ETA Estimation: Graph-Based Routing with Traffic

The ETA Service calculates how long it takes a driver to reach the rider (pickup ETA) and how long the trip will take (destination ETA). Accurate ETAs are critical for two reasons: they are the highest-weighted factor in matching scores, and they set rider expectations that directly affect satisfaction.

The Road Network as a Graph:

The road network is modeled as a weighted directed graph. Intersections are nodes. Road segments between intersections are edges. Each edge has a weight representing travel time, which depends on three factors: segment length, speed limit, and real-time traffic conditions.

A one-way street is a directed edge (traversable in one direction only). A two-lane road is two directed edges (one per direction, potentially with different traffic weights). Highway on-ramps and off-ramps are edges connecting the local road subgraph to the highway subgraph.

Shortest Path Computation:

Given the driver’s current position and the rider’s pickup location, the ETA Service finds the shortest-time path through the road graph. The standard algorithm is a variant of Dijkstra’s algorithm optimized for road networks (e.g., Contraction Hierarchies, which precompute shortcuts to reduce query time from hundreds of milliseconds to single-digit milliseconds).

In practice, the ETA Service does not run its own routing engine. It calls a Maps API (Google Maps Platform, Mapbox, OSRM) that maintains the road graph, ingests real-time traffic data from probe vehicles and sensors, and returns the ETA and route.

Two Types of ETA:

SLIDE 88B: ETA Updates During a Trip

Once a trip is in progress, the ETA to the destination is not static. Traffic conditions change, the driver might take a different route than initially planned, and road incidents can add delays. The ETA Service recalculates and pushes updated estimates to both the rider and driver apps.

Update Cycle:

Every 30-60 seconds during an active trip, the ETA Service recalculates the destination ETA based on the driver’s current position (from the Location Service) and current traffic conditions (from the Maps API). The updated ETA is pushed to both apps via WebSocket.

Why Continuous Updates Matter:

A rider checking their phone at minute 5 of a trip expects the ETA to reflect current conditions, not the estimate from 5 minutes ago when the trip started. If traffic worsened and the original ETA was 15 minutes but the actual remaining time is now 22 minutes, showing the stale 10-minute estimate erodes trust in the platform.

Cost Optimization for ETA Updates:

Maps API calls are priced per request. A 20-minute trip with 30-second ETA updates generates 40 Maps API calls per trip. At 20 million trips per day, that is 800 million ETA API calls per day just for in-trip updates. At Google Maps Platform pricing ($5-10 per 1,000 requests for directions), this is$4-8 million per day.

Strategies to reduce cost:

Reduce update frequency during stable segments. If the driver is on a highway with no route changes for the next 10km, update every 120 seconds instead of 30. Increase frequency near turns, exits, and traffic changes.

Cache ETAs for common route segments. The ETA for “Highway 401 from Exit 350 to Exit 360 at 5 PM on a weekday” is similar day to day. Cache the segment-level ETAs and compose trip ETAs from cached segments.

Use straight-line estimation with a correction factor for short remaining distances (under 2km). The accuracy loss is small, and it eliminates an API call.

SLIDE 89: Maps API Integration and Fallback

The ETA Service depends on an external Maps API for routing and travel time estimation. This is a critical external dependency that introduces cost, latency, and availability risks.

Why Companies Move Away from Google Maps:

Cost. At Uber’s scale (20M+ trips/day with multiple ETA calls per trip), the Google Maps bill reportedly exceeded $58 million per year. This motivated Uber to build an in-house mapping platform. For an interview, you do not need to design a mapping engine, but you should recognize the cost as a significant architecture consideration.

Fallback Strategy:

If the primary Maps API is unavailable or slow (latency > 500ms), the ETA Service falls back through three tiers:

Tier 1: Secondary Maps API (e.g., Mapbox as backup to Google). Different provider, different infrastructure, unlikely to fail simultaneously.

Tier 2: Cached historical ETAs. For the same origin-destination pair during the same time window on a similar day, cached ETAs are reasonably accurate. Accuracy degrades during unusual events (accidents, road closures) but is better than no estimate.

Tier 3: Straight-line distance with correction factor. Multiply the haversine distance by 1.3 for urban areas, 1.1 for highways. This is the least accurate but always available and requires zero external calls.

SLIDE 89B: Matching Without Perfect ETAs

A common interview question is: “What if the Maps API is slow or unavailable? Does matching break?”

The answer is no, because matching does not require perfect ETAs. It requires relative ordering. If the system can determine that Driver A is probably faster than Driver B, the match quality is preserved even if the absolute ETA values are estimates.

Straight-Line Distance as a Proxy:

When ETA computation is unavailable, the Matching Service can fall back to straight-line (haversine) distance for candidate ranking. This works because, in most urban areas, straight-line distance is a reasonable proxy for relative pickup time. The driver who is 500 meters away in a straight line is almost always faster than the driver who is 3km away, regardless of the road network.

Where this proxy breaks: one-way streets, rivers with limited bridge crossings, highways with distant on-ramps. In these cases, a driver who is geographically close might be far by road. But these cases are rare enough that using straight-line distance as a fallback preserves match quality for the vast majority of requests.

Cached ETA Buckets:

A more sophisticated fallback: pre-compute average ETAs between pairs of H3 or geohash cells for each hour of the day. Store these as a lookup table in Redis. When real-time ETA is unavailable, look up the cached average for the cell pair. This captures road network effects (one-way streets, bridges) without needing a real-time API call.

The cache is refreshed daily from historical trip data. Its accuracy is lower than real-time computation (it does not account for today’s traffic), but it is significantly better than straight-line distance.

SLIDE 90: Matching at Scale: Geographic Partitioning

Matching is inherently a city-local operation. A rider in Mumbai will never match with a driver in Delhi. A rider in Manhattan will never match with a driver in Los Angeles. This geographic locality creates a natural partitioning strategy for scaling the Matching Service.

Partition by City or Region:

Each city (or metropolitan region) gets its own independent Matching Service instance (or cluster of instances). The API Gateway determines the rider’s city from the pickup location and routes the match request to the correct regional Matching Service. Each regional instance handles only local requests and queries only the local driver pool.

Why Geographic Partitioning Works for Matching:

The spatial index query that feeds into matching is already city-local (drivers within 5km of the rider). The candidate scoring uses only local data (nearby driver positions, local surge zones). The dispatch offer goes to a local driver. No step in the matching pipeline requires cross-city data. This means each city can scale independently: Mumbai’s matching infrastructure does not need to grow when New York’s demand increases.

Adding a New City:

Provision a new Matching Service instance, configure the API Gateway routing table to map the new city’s geographic boundary to the new instance, seed the city’s surge zone boundaries, and enable ride requests. The new city’s matching infrastructure is fully independent from existing cities.

Cross-City Edge Cases:

One scenario breaks pure geographic partitioning: rides that cross city boundaries (e.g., a trip from Newark to Manhattan). The pickup location determines the matching city (Newark), so the Newark Matching Service handles the match. The trip itself crosses into Manhattan, but this only affects ETA routing (handled by the Maps API) and fare calculation (handled by the Pricing Service with multi-zone rules). Matching remains single-city.

SLIDE 91: Worked Example: 500 Concurrent Requests in One City

A major concert ends at 10 PM. Over the next 5 minutes, 500 ride requests arrive from a 2km radius around the venue. The city has 50,000 active drivers. How does the matching system handle this?

Initial State:

500 ride requests in 5 minutes = approximately 1.7 requests/sec from this zone (compared to the city’s normal ~4 requests/sec total). Available drivers within 5km of the venue: approximately 800 (1.6% of all city drivers, concentrated around the venue area and nearby streets).

Phase 1: First 50 Requests (0-30 seconds)

Supply is high relative to demand. Greedy matching works well. Each request finds 20+ nearby candidates. Match time: 200-500ms per request. After 50 matches, the available driver pool within 5km drops from 800 to 750.

Phase 2: Requests 50-200 (30 seconds - 2 minutes)

Supply-demand ratio tightens. The system detects elevated demand in this zone and switches to batch matching with 2-second windows. Each batch contains 5-10 requests. The assignment solver distributes drivers more efficiently than greedy would, avoiding the problem of multiple requests competing for the same nearby drivers. Available pool: drops from 750 to approximately 550 as drivers are matched and new drivers enter the zone attracted by surge pricing.

Phase 3: Requests 200-400 (2-4 minutes)

The nearby driver pool within 5km is thinning. The matching system expands the search radius to 8km, pulling in drivers from adjacent neighborhoods. Surge pricing (Section 10) has activated at 2.0-2.5x, which serves two purposes: it reduces marginal demand (some riders decide to wait or take transit) and attracts additional driver supply from surrounding areas. Match times increase to 30-60 seconds as more cascades are needed.

Phase 4: Requests 400-500 (4-5 minutes)

Available nearby drivers are scarce. The system operates in degraded mode: 10km search radius, batch windows extended to 5 seconds, match times of 60-90 seconds. Some riders see “high demand in your area” and estimated wait times of 8-15 minutes. Riders who cancel reduce the demand queue. Drivers arriving from outer areas gradually replenish supply.

Driver Pool Depletion Math:

Start:        800 drivers within 5km
After 50:     750 remaining (50 matched, ~0 new arrivals yet)
After 200:    550 remaining (200 matched, ~50 new from surge attraction)
After 400:    250 remaining (400 matched, ~150 new from surge + wider radius)
After 500:    200 remaining (500 matched, ~250 new arrivals over 5 min)

The system never runs out of drivers. It degrades gracefully: wider radius, longer wait, higher price. This is by design.

SLIDE 91B: Worked Example: Greedy vs Batch Side by Side

Using a simplified version of the concert scenario, compare the outcomes of greedy and batch matching for a single batch window.

Setup: 5 riders, 5 drivers, one 3-second batch window

Key Insight:

Batch matching does not always produce dramatically different results from greedy. Its advantage appears specifically when driver positions create contention: multiple riders are close to the same driver, and greedy’s first-come-first-served approach creates a cascade of suboptimal assignments for later riders. The improvement is statistical: across thousands of matches per hour, batch reduces average pickup time by 10-20% during high-demand periods.

SLIDE 92: Wrong vs Right: Matching and Dispatch Mistakes

Mistake 1: “I would find the closest driver”

Wrong: “The system finds the closest available driver to the rider and dispatches them.”

Better: “The Matching Service runs a candidate pipeline. First, it queries the spatial index for drivers within 5km. Then it filters by vehicle type and availability. Then it scores candidates on multiple factors: ETA has the highest weight, but driver rating, acceptance history, and heading direction also factor in. The top-scored candidate receives the dispatch offer.”

Why it matters: “closest” implies distance is the only factor. Interviewers expect you to recognize that matching is multi-factor optimization, not a nearest-neighbor lookup.

Mistake 2: Ignoring the dispatch timeout and cascade

Wrong: describing matching as if every offer is accepted.

Better: “The driver has 15 seconds to accept. If they decline or time out, the offer cascades to the next candidate in the ranked list. After 3-5 cascades, the system re-queries the spatial index with an expanded radius because driver positions have changed.”

Why it matters: the cascade mechanism is where real-world complexity lives. Interviewers test whether you have thought about what happens when the happy path fails.

Mistake 3: No concurrency handling

Wrong: not mentioning the double-booking race condition.

Better: “Two concurrent requests can both find the same driver as the best candidate. The system uses optimistic locking in Redis: the first Matching Service instance to acquire a dispatch lock on the driver wins, and the second falls back to the next candidate. The lock has a 30-second TTL to prevent deadlocks if the dispatch process crashes.”

Why it matters: at senior level, interviewers expect you to identify and solve the concurrent matching race condition without being prompted.

Mistake 4: Committing to one algorithm without trade-off discussion

Wrong: “I would use batch matching for optimal assignments.”

Better: “Greedy matching is faster (200-500ms) but locally optimal. Batch matching adds 1-2 seconds of latency but optimizes globally. In production, I would use a hybrid: greedy at low demand, batch during surge. The transition is driven by real-time supply-demand ratio.”

Why it matters: the interviewer is testing judgment, not whether you know the Hungarian algorithm.

SLIDE 93: How to Explain Matching Concisely in an Interview

In a 45-minute interview, matching and dispatch should take 4-5 minutes. Here is how to structure those minutes.

Minute 1: The Candidate Pipeline

“When a ride request comes in, the Matching Service queries the spatial index for drivers within 5km of the pickup location. That returns around 200 candidates. I filter by vehicle type and availability, then score the remaining 20-50 candidates on a weighted formula: ETA is the largest factor, plus driver rating, acceptance history, and heading direction. The top-scored driver gets the offer.”

Minute 2: Greedy vs Batch Trade-Off

“For each individual request, greedy matching is simple and fast. But during high demand, multiple riders compete for the same nearby drivers, and greedy assignment order affects results. Batch matching collects requests over a 2-3 second window and solves the assignment globally. In production, I would use greedy at normal demand and switch to batch during surge, driven by supply-demand ratio.”

Minute 3: Dispatch Flow

“The top candidate gets a WebSocket push with the ride details. They have 15 seconds to accept. On decline or timeout, the offer cascades to the next candidate. After 3-5 cascades, the system re-queries with a wider radius.”

Minute 4: Concurrency and Scale

“Two requests can target the same driver simultaneously. I use optimistic locking in Redis to prevent double-booking. Matching is partitioned by city for independent scaling, since a rider in Mumbai never matches with a driver in Delhi.”

If the Interviewer Pushes Deeper:

They will typically push on one of three areas: the scoring formula (explain the factors and weights), the race condition (explain the locking mechanism and TTL), or the batch algorithm (mention the assignment problem and Hungarian algorithm). Be ready to go one level deeper on each but do not volunteer the details unless asked.

SLIDE 94: Interview Practice: Matching and Dispatch

Practice Exercise:

Set a timer for 5 minutes. Explain the matching and dispatch system from scratch as if you were in an interview. Cover: candidate pipeline, scoring, greedy vs batch trade-off, dispatch cascade, and one concurrency concern.

Checklist: What Your Answer Should Include

Candidate pipeline: proximity filter (spatial index), eligibility filter (vehicle type, status), scoring (multi-factor, ETA-dominant), ranked list.

Greedy vs batch: state the trade-off, not just one approach. Mention the hybrid.

Dispatch: offer via WebSocket push, 15-second acceptance window, cascade on decline/timeout, re-query with expanded radius after multiple failures.

Concurrency: double-booking race condition and the locking strategy (optimistic locking in Redis with TTL).

Scaling: geographic partitioning by city.

Self-Assessment:

Did you present matching as multi-factor optimization, or as “find the closest”? Did you mention the dispatch cascade, or describe matching as a single-step process? Did you discuss the greedy vs batch trade-off with a clear recommendation? Did you raise concurrency without being prompted?

How This Connects Forward:

The candidate pipeline depends on the spatial index from Section 6 (geohash, quadtree, or H3 for the proximity filter). The dispatch flow depends on the WebSocket architecture from Section 4 (pushing offers to drivers). The driver scoring formula uses rating and acceptance data stored in the databases covered in Section 8. The surge pricing that influences demand during the concert scenario is covered in Section 10. The geographic partitioning strategy connects to the broader scaling discussion in Section 11.

SLIDE 95: Section Cheat Sheet

Matching Pipeline:

Scoring Weights:

Greedy vs Batch:

Common Interview Mistakes:

Key Numbers to Remember:

15 seconds: dispatch offer acceptance window
3-5 cascades: before re-query with expanded radius
5km: default proximity search radius (urban)
200-500ms: greedy match time per request
1.5-3 sec: batch match time (including window wait)
250 requests/sec: average ride requests globally
50,000 drivers: typical major city active pool
0.40: ETA weight in scoring formula (highest factor)
2-5 seconds: batch window duration
30 seconds: dispatch lock TTL in Redis

How This Connects to Other Sections: