A cafe 50 metres away, invisible to your nearby search

transcript

There's a cafe 50 metres from you. You search for cafes nearby. It doesn't show up.

Near is a circle. A database index wants a range. So chop the map into cells. Geohash names each cell with a string. A shared prefix means a shared cell. Five characters, about 4 point 9 kilometres. Seven, about 150 metres.

Here's the trap every interviewer waits for. Two places can be neighbours, and share no prefix at all.

You're in Bengaluru. Near the north edge of cell t d r 1 y. The cafe is 50 metres north. In the next cell: t d r 4 n. Neighbours. But the names split at the fourth character. Search your own prefix only, and the cafe is simply missed.

The fix: read your cell and its 8 neighbours. Nine lookups. That gives a few hundred candidates. Compute the exact distance to each. Drop anything outside the radius. Exact distance: 50 metres. The cafe is back.

One condition. Pick the finest cell that's still as wide as the radius. Then nine cells always cover the circle. Wherever you stand.

Prefixes find cells. They don't measure distance. Read nine cells. Then measure.

Full breakdown in the lecture.