Ride Sharing HLD: Finding the Nearest Driver Without Asking All of Them

"Design Uber." You tap a pin on a map, and in the next few seconds the app says "finding your driver." Hold on those seconds — they're the whole interview. Somewhere out there are fifty thousand drivers scattered across the city, their dots crawling around the map as they drive. Your job, in a few milliseconds: find the handful closest to you, pick one, and make sure that the rider three blocks away who tapped at the same instant doesn't get offered the same car. The obvious answer — measure the distance from you to all fifty thousand and take the smallest — is a catastrophe: fifty thousand di…