Uber Routing Lab

Nearest driver, route optimization, ETA calculation, dynamic pricing

Walkthrough

How Uber Routing Works

Step-by-step from ride request to dropoff

Rider Requests a Ride

A rider opens the app and enters their pickup and dropoff locations. The request includes the rider's location, destination, and optional preferences (UberX, XL, Comfort).

Rider

📍

Pickup → Drop

1 / 5

City Map

Nearest Driver

KD-Tree recursively partitions driver positions along alternating X/Y axes, enabling O(log n) nearest-neighbor queries by pruning half the search space at each level.

Steps:

1.Build tree from driver coordinates
2.Traverse to find candidate leaf
3.Backtrack checking nearer planes
4.Return closest driver with distance

Complexity Analysis

KD Tree (Build)

O(n log n)/O(n)

KD Tree (Search)

O(log n)/O(1)

A* Search

O(b^d)/O(b^d)

Dijkstra's

O((V+E) log V)/O(V)

Heap Insert

O(log n)/O(1)

Heap Extract

O(log n)/O(1)

Algorithms

Algorithm Explanations

How each data structure powers Uber's core features

Nearest Driver

KD Tree

KD-Tree recursively partitions driver positions along alternating X/Y axes, enabling O(log n) nearest-neighbor queries by pruning half the search space at each level.

Route Optimization

A* Search

A* extends Dijkstra with a heuristic (Manhattan distance) to guide search toward the destination, significantly reducing explored nodes in city grid environments.

ETA Calculation

Dijkstra's

Dijkstra's algorithm computes shortest paths from a source to all nodes in a weighted graph, forming the backbone of ETA systems with traffic-aware edge weights.

Dynamic Pricing

Heap / PQ

Min/Max heaps maintain a dynamic set of demand scores per zone, enabling O(log n) insertion and O(1) retrieval of the highest-priority pricing region.

Practice

Interview Questions

Common questions from Uber engineering interviews

Design a real-time driver-rider matching system for 1M+ active users.

Use geohashing for spatial indexing, a pub-sub queue for ride requests, and a greedy assignment worker pool.

How would you implement surge pricing that updates every 30 seconds?

Maintain a per-zone demand heap and supply counter; compute ratio and map to price tiers via a lookup table.

Compute an accurate ETA considering live traffic without recomputing from scratch.

Use incremental Dijkstra with cached paths; re-weight edges based on traffic data and propagate changes.

Design a route optimization service that handles 10k concurrent ride requests.

Batch requests per region, solve with a min-cost flow model, and distribute across sharded graph workers.