Uber Interview Guide: System Design at Scale & Coding

Core Components: 1. Driver Location Service: • Drivers send GPS updates every 3-5 seconds • Store in a geospatial index (e.g., Google S2 cells or H3 hexagonal grid) • Partition the world into cells; each cell tracks active drivers within it • Use Redis with geo commands or a custom geospatial index 2. Matching Engine: • On ride request: query nearby cells for available drivers • Score candidates by: distance, ETA (routing-adjusted, not just straight-line), driver rating, vehicle type match • Send offer to the best candidate with a timeout (15-20 seconds) • If declined or timed out, offer to the next candidate • Optimization: batch nearby ride requests and solve assignment as a bipartite matching problem 3. ETA Service: • Real-time routing engine considering traffic, road closures, and historical patterns • Pre-compute ETAs for common routes during peak hours • Fallback to straight-line distance * regional factor if routing service is slow 4. Dispatch Orchestrator: • State machine managing ride lifecycle: REQUESTED -> MATCHING -> DRIVER_ASSIGNED -> EN_ROUTE -> IN_PROGRESS -> COMPLETED • Handles cancellations, driver no-shows, and re-matching Scaling Strategy: • Shard by geographic region (city-level) • Each city runs its own matching engine independently • Cross-region rides (airports) handled by a coordination layer Failure Modes to Discuss: • Driver location service lag (stale positions) — use timestamp-based freshness checks • Matching engine overload during surge — degrade to simpler distance-only matching • Network partition between regions — each region operates independently with local data

Why Surge Pricing Exists: • Incentivizes more drivers to come online in high-demand areas • Balances supply and demand to reduce wait times • Not just about revenue — it's a marketplace balancing mechanism Architecture: 1. Demand Signal Collection: • Track ride requests per geographic cell per time window (1-5 minutes) • Track unfulfilled requests (rides with no driver match within SLA) • Weight by time: recent requests matter more than 10 minutes ago 2. Supply Signal Collection: • Count available drivers per cell • Track drivers transitioning to available (completing current rides) • Include predicted supply from adjacent cells (drivers who might drive into the area) 3. Surge Multiplier Calculation: • Ratio: demand / supply with smoothing • Apply step functions: 1.0x, 1.2x, 1.5x, 2.0x, 2.5x (avoid jarring jumps) • Hysteresis: require sustained imbalance before increasing, and sustained balance before decreasing (prevents oscillation) • Cap at a maximum multiplier (regulatory and PR constraints) 4. Pricing Service: • When a ride is requested, fetch the surge multiplier for the pickup cell • Lock the price at request time (don't change mid-ride) • Show the multiplier to the rider before they confirm Operational Concerns: • Surge during emergencies: disable or cap during natural disasters, security events • Geographic granularity: too coarse = unfair pricing, too fine = noisy signals • A/B testing: measure impact of surge on rider conversion, driver earnings, and wait times • Regulatory compliance: some cities regulate surge caps

Challenges: • GPS noise: stationary vehicles can report slightly different coordinates each reading (jitter of 5-15 meters) • Tunnel/urban canyon gaps: GPS signal may drop in certain areas • Irregular update intervals: network delays may cause uneven spacing Algorithm: 1. Define a 'stop radius' (e.g., 30 meters to account for GPS noise) 2. Maintain a sliding window: • Track the anchor point (first coordinate in a potential stop) • For each new coordinate, check if it's within the stop radius of the anchor • If yes: update the stop duration (latest timestamp - anchor timestamp) • If no: reset the anchor to the current coordinate 3. Detect stop: • If stop duration >= N minutes, emit a 'vehicle stopped' event • Include: location (centroid of coordinates during stop), start time, duration Handling Edge Cases: • GPS gaps: if no update for > 60 seconds, don't assume still stopped — mark as 'unknown' • Slow movement (parking lot creep): use speed threshold (< 2 km/h) as additional signal • Initial calibration: require at least 3 readings within the radius before starting the stop timer Operational Considerations: • This feeds into trip state detection (is the ride still active?) • False positives (traffic jam vs actual stop) — combine with trip context • Monitoring: track false positive rate and alert if it spikes (indicates GPS quality degradation)