Practice: five levels

Assignments

Five levels. Do them in order. Answers are in "Solutions" at the end, so try first.

Level 1: Think (no code)

A. True or false? Explain in one line.

1. An index on (lat, lng) makes "riders within 2 km" fast.
2. Two points with the same 6-character geohash are in the same cell.
3. Two points 40 m apart always share a long geohash prefix.
4. A quadtree has the same cell sizes everywhere.
5. Every rider ping should be written to the main SQL database.

B. Geohash, quadtree, H3, or a managed tool (Redis GEO, PostGIS)? One line each.

1. A small startup needs "restaurants within 3 km" next week.
2. Surge-pricing zones where every neighbouring zone should be the same distance away.
3. An in-memory index of riders where density varies hugely between the centre and suburbs.
4. Storing places in an existing database and searching by a string prefix.

Level 2: Calculate

1. 10,000 riders ping every 4 seconds. How many location writes per second?
2. One degree of longitude is about 111 km × cos(latitude). Roughly how many km is it at 12.97°N (Bengaluru) and at 60°N?
3. 5,000 riders are spread evenly over a 30 km × 30 km area. You search 9 cells of 4.8 km × 4.9 km. About how many candidates do you fetch, and about how many are inside a 2 km circle?
4. A rider moves at 20 km/h and pings every 4 seconds. How far between pings? With cells about 0.6 km tall, roughly how often (in pings) do they change cell when heading north?

Level 3: Build

In Python:

1. geohash_encode(lat, lng, precision) and geohash_bounds(gh). Check the well-known vector (57.64911, 10.40744) → u4pruydqqvj.
2. geohash_neighbours(gh) returning the cell and its 8 neighbours.
3. haversine_km(lat1, lng1, lat2, lng2).
4. A GeohashIndex with update(rider, lat, lng) and nearby(lat, lng, radius_km) that matches a brute-force check.
5. A QuadTree that splits at 16 points and answers the same radius query.

Level 4: Debug

Customers complain: "The app said no riders nearby, but a rider was standing right outside." The code:

1. Find the bug and explain exactly when it happens.
2. Fix it.

Level 5: Design

Design rider matching for the grocery app in three cities, with about 10,000 riders on shift pinging every 4 seconds, and stores asking "the 5 nearest available riders within 2 km" for each new order.

Deliver:

1. Where the latest rider positions live and how they're indexed.
2. How a "5 nearest within 2 km" query runs, including what happens if there are fewer than 5.
3. How location updates are handled at 2,500 per second, and how offline riders are removed.
4. How the system is sharded, and what happens near a city's boundary.
5. How two stores are stopped from assigning the same rider at the same moment (hint: Chapter 17).