A mapping app hides two genuinely hard computer science problems behind a clean interface. The first is spatial search: given my location, find the coffee shops, gas stations, or friends near me. The second is routing: find the fastest way from here to there across a road network with millions of edges. They need different tools, and understanding why is most of the design.
Start with spatial search, because it exposes a nice trap. Say you store every place with a latitude and longitude. To find things near me, the naive query is "give me every place whose distance to my point is less than one kilometer." That works, and it is also a disaster, because it forces the database to compute distance to every single place before filtering. There is no index that a plain distance formula can use. You need a way to turn two dimensional position into something a normal index can handle.
That is what geospatial indexing does, and there are two common approaches. One is a tree structure such as a quadtree, which recursively divides the map into four cells, then divides busy cells again, so dense areas like city centers get fine grained cells and empty areas stay coarse. To find nearby places you walk down to the cell containing your point and look at that cell and its neighbors, instead of scanning the whole world. The other approach is a grid or geohash system, which chops the surface into cells and gives each a short string id, where nearby places tend to share a prefix. Then "find things near me" becomes "find things whose cell id matches this prefix," which an ordinary index handles well. The trade-off between them is roughly flexibility versus simplicity. Trees adapt beautifully to uneven density but are more work to maintain. Grid and geohash schemes are simple and index friendly but need care at cell boundaries, because two points can be physically close while sitting in different cells. Either way, the win is the same: you replace a scan of everything with a lookup of a small local region.
Now routing, which is a different beast entirely. The road network is a graph. Intersections are nodes, roads are edges, and each edge has a cost such as time or distance. Finding the fastest route is a shortest path problem. The textbook answer is Dijkstra's algorithm, and it is correct. It is also far too slow to run across a continent scale graph on every request, because it explores outward in all directions until it reaches the destination, touching an enormous number of nodes for a long trip.
So the real decisions in routing are about not running the full search every time. The first improvement is to guide the search toward the destination instead of expanding blindly, which is the idea behind A star: use an estimate of remaining distance so the search leans in the right direction. That helps, but for very long routes it is still not enough. The bigger idea is precomputation. You process the graph offline to build shortcuts, so that at query time you can skip across large stretches of the map in a few hops instead of crawling road by road. Techniques in this family precompute a hierarchy of the network, importantly ranking, so that long distance routing hops along a small set of major connections much like a human plans a trip by highways first and local streets last. The trade-off is heavy offline computation and extra storage in exchange for query responses fast enough to feel instant. For a service answering an enormous number of route requests, moving cost from query time to precompute time is exactly right.
Two more layers make it usable. Real routing needs live traffic, so edge costs are not fixed. They are updated from current conditions, which means the precomputed structures have to tolerate changing weights without being rebuilt from scratch. And the map itself is served as tiles, small pre rendered images or vector chunks per zoom level and region, delivered through a CDN so panning and zooming pull cached tiles instead of rendering the world on demand. That tiling is the same pre compute and cache idea showing up again in a different place.
How does the real company do it? Google Maps uses hierarchical spatial indexing to answer nearby queries and heavy offline preprocessing of the road graph so that routing at query time is closer to a lookup than a full search. Traffic data continuously adjusts edge costs, and the visible map is served as cached tiles through a global CDN. The recurring theme is precomputation: do the expensive graph and rendering work ahead of time so the request path stays cheap.
The interview takeaway is to separate the two problems clearly. Spatial search wants a geospatial index. Routing wants a graph plus precomputed shortcuts. Answering both with one tool is the mistake.
I wrote the full breakdown, with diagrams and the data model, here: https://www.systemdesign.academy/interview/design-google-maps
Top comments (0)