Practice this topic in a realistic system design interview
Finding things near a point is a common system design problem. A maps app needs nearby restaurants. A ride-sharing app needs nearby drivers. A game needs nearby objects. Checking every point works for a few thousand points, but not for millions.
A quadtree helps by dividing a map into smaller and smaller regions, but only where the data is dense. During a search, it can skip whole regions that can't contain a match.
In this chapter, we'll learn what a quadtree is, how it divides a map into smaller regions based on where the data actually is, how it answers nearby searches, and where systems use it in practice.
Loading simulation...
Suppose you're building an app that shows nearby places, like restaurants, cafes, and gas stations. You have 100 million places around the world, each with a latitude and longitude. When a user opens the app, you need to quickly find the places closest to them.
One approach is to divide the map into a fixed grid of equal-sized cells. Each place is assigned to the cell it falls into. When a user searches, you check their cell and the surrounding cells.
This works, but there's a problem. Places are not distributed evenly. A cell in downtown Manhattan might contain thousands of places. But a cell of the same size in the middle of a desert might contain none.
Ideally, we want a grid that adapts to the data, with smaller cells in dense areas and larger cells where places are spread out.