Uber engineers don't want you to know this.

Here's how Uber computes ETA:

1 They represent the physical map as a graph

2 They compute ETA by finding shortest path in a directed weighted graph

3 They don't use Dijkstra’s algorithm because it won't scale with O(n*logn) time complexity

4 They partition graph & then precompute the best path within each partition

5 They reduce the time complexity from O(n^2) to O(n) by partitioning graph

6 They populate the edge weights of the graph with traffic information

7 They use Kalman filter & Viterbi algorithm for map matching to find ETA accurately

What else would you add?

===

👋 PS - I put together a detailed case study on my newsletter (with visuals):

Read right now:

→ newsletter.systemdesign…

===

💾 Save this for later & restack to help others learn system design.