Uber Interview: Graphs, Maps, and Real-Time Systems

Why Uber Interviews Are Different

Uber operates one of the world's largest real-time marketplaces. Every second, they process millions of driver location updates, match riders to drivers, calculate routes, and handle dynamic pricing. The technical challenges are uniquely interesting.

Expect interview questions that reflect this reality: graph algorithms for routing, geospatial data structures for finding nearby drivers, and system design for handling massive real-time throughput.

Graph Algorithms: The Core of Uber

Cities are graphs. Intersections are nodes. Roads are edges. Every Uber trip starts with graph algorithms - finding the best route from A to B with real-time traffic.

Shortest Path with Dynamic Weights

Dijkstra's algorithm works for static graphs, but traffic changes constantly. Uber uses variants like A* search with heuristics (straight-line distance) and dynamic edge weight updates.

Bipartite Matching for Ride Assignment

When you request an Uber, the system doesn't just find the nearest driver. It solves a maximum weighted bipartite matching problem: given N drivers and M requests, find the assignment that maximizes total score (considering ETA, driver heading, ratings).

The Hungarian algorithm solves this optimally in O(n³). At Uber scale, approximation algorithms and batching strategies are used.

Geospatial Problems

Working with geographic data requires specialized thinking. Uber interviewers expect you to know:

Distance on a Sphere

You can't use Euclidean distance (straight line) for GPS coordinates. Earth is spherical. The Haversine formula calculates great-circle distance. For city-scale distances, the error is small, but for longer distances it matters.

Spatial Indexing

Finding "all drivers within 2 miles" requires spatial data structures:

ETA Prediction

Uber's ETA predictions are remarkably accurate. This is a machine learning problem that combines:

• Historical trip data (how long do trips usually take on this route?)
• Real-time traffic (current speeds on road segments)
• Time of day and day of week patterns
• Special events (sports, concerts)
• Weather conditions

Real-Time Systems

Uber receives millions of driver location updates per second. Processing this requires careful architecture.

CAP Theorem Trade-offs

During network partitions, Uber chooses availability over consistency. Riders need rides, even if the system isn't perfectly consistent.

This means regions can operate independently during partitions. After healing, conflicts (same driver matched to two riders) are resolved. Design questions will test your understanding of these trade-offs.

Matching and Optimization

The core business logic - matching riders to drivers - is surprisingly complex.

Batch vs. Instant Matching

Should you match riders to drivers immediately (first-come-first-served) or batch requests over a small window?

Instant matching is greedy and can be globally suboptimal. Batching for 1-2 seconds enables better matching (maybe the perfect driver is about to drop off nearby), at the cost of slight latency. The optimal strategy depends on request density.

Dispatch Scoring

Which driver gets the ride? The scoring function considers:

• ETA - But not just distance; heading direction matters
• Driver rating - Higher-rated drivers may be preferred
• Supply/demand balance - Don't cluster all drivers in busy areas
• Fairness - Drivers need rides distributed reasonably

Coding Interview Tips

Uber coding interviews often feature:

Graph Problems

Practice problems involving shortest paths, connected components, and cycle detection. Know when to use BFS vs. DFS, when Dijkstra vs. BFS applies.

Intervals and Time Windows

Overlapping intervals (booking conflicts), merging time ranges, and scheduling problems come up frequently.

Matrix and Grid Problems

Cities are often modeled as grids. BFS/DFS on 2D arrays, finding regions, and path-finding are common patterns.

What Uber Looks For

Problem Solving Under Pressure

Uber operates 24/7. Engineers debug production issues at 3 AM. Can you stay calm, think systematically, and solve problems when stakes are high?

Scale Thinking

"How does this scale to 100M users?" is a natural follow-up. Think about data volume, latency, and failure modes.

Collaboration

Uber is a large organization. Do you communicate well? Can you work across teams? Pair programming rounds assess this.

Preparation Strategy

Algorithms (2-3 months)

• Master graph algorithms (BFS, DFS, Dijkstra, A*)
• Practice interval and scheduling problems
• Know heap operations and use cases
• 150+ LeetCode problems, emphasizing graphs

System Design

• Study real-time streaming architectures
• Understand geospatial data structures
• Practice designing marketplaces

Domain Knowledge

• Read Uber engineering blog
• Understand the ride-sharing business model
• Think about trade-offs in real-time systems

Final Thoughts

Uber interviews test skills that transfer well to any company building real-time systems at scale. Graph algorithms, geospatial thinking, and streaming architectures are valuable everywhere.

The problems are challenging but interesting. If you find yourself excited thinking about how to match millions of riders to drivers efficiently, you'll enjoy working at Uber.