Show the Level 2 solution
1. 10,000 ÷ 4 = **2,500 writes a second**.
2. 111 × cos(12.97°) ≈ 111 × 0.974 ≈ **108 km**. At 60°N: 111 × 0.5 ≈ **56 km**. A degree "box" is much narrower in km up north.
3. 9 cells ≈ 9 × 4.8 × 4.9 ≈ **210 km²**, out of 900 km², so about 5,000 × 210 ÷ 900 ≈ **1,170 candidates** (the code's random spread gave 1,140). The circle is π × 2² ≈ 12.6 km², so about 5,000 × 12.6 ÷ 900 ≈ **70** are inside (the code found 71).
4. 20 km/h ≈ 5.6 m/s, so about **22 m** between pings. 600 ÷ 22 ≈ **27 pings** per cell change, about once every 2 minutes. Over an hour: 900 pings, about 33 cell changes, exactly what the code shows.
1Show the Level 3 solution
2Tested solution (Python 3), the key parts:
3
4```python
5BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"
6
7def geohash_encode(lat, lng, precision):
8 lat_lo, lat_hi, lng_lo, lng_hi = -90.0, 90.0, -180.0, 180.0
9 out, bits, value, even = [], 0, 0, True
10 while len(out) < precision:
11 if even: # longitude bit
12 mid = (lng_lo + lng_hi) / 2
13 if lng >= mid: value, lng_lo = value * 2 + 1, mid
14 else: value, lng_hi = value * 2, mid
15 else: # latitude bit
16 mid = (lat_lo + lat_hi) / 2
17 if lat >= mid: value, lat_lo = value * 2 + 1, mid
18 else: value, lat_hi = value * 2, mid
19 even = not even
20 bits += 1
21 if bits == 5:
22 out.append(BASE32[value])
23 bits, value = 0, 0
24 return "".join(out)
25
26
27def geohash_neighbours(gh):
28 lat_lo, lat_hi, lng_lo, lng_hi = geohash_bounds(gh)
29 clat, clng = (lat_lo + lat_hi) / 2, (lng_lo + lng_hi) / 2
30 dlat, dlng = lat_hi - lat_lo, lng_hi - lng_lo
31 return {geohash_encode(clat + i * dlat, clng + j * dlng, len(gh))
32 for i in (-1, 0, 1) for j in (-1, 0, 1)}
33
34
35def haversine_km(lat1, lng1, lat2, lng2):
36 p1, p2 = math.radians(lat1), math.radians(lat2)
37 dp, dl = p2 - p1, math.radians(lng2 - lng1)
38 a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2
39 return 2 * 6371.0 * math.asin(math.sqrt(a))
40
41
42class GeohashIndex:
43 def nearby(self, lat, lng, radius_km):
44 found = []
45 for cell in geohash_neighbours(geohash_encode(lat, lng, self.precision)):
46 for rider, (rlat, rlng) in self.cells.get(cell, {}).items():
47 d = haversine_km(lat, lng, rlat, rlng)
48 if d <= radius_km:
49 found.append((round(d, 3), rider))
50 return sorted(found)
51```
52
53All checks pass: the test vector matches; the 9-cell search and the quadtree both return exactly the brute-force answer (71 riders within 2 km of 5,000); the one-cell search misses a rider 44 m away; and a moving rider changes cell 33 times in 900 pings. The full file, including `geohash_bounds` and the `QuadTree`, is in `code/ch18_geospatial.py`.
1Show the Level 4 solution
2**The bug:** it searches **only the user's own cell**. Whenever the user is near a cell border, riders just across it are invisible, however close they are. In the tested demo, a rider **44 m** away in the cell below is missed entirely, while riders much farther away inside the same cell would be found.
3
4**The fix:** search the cell **and its 8 neighbours**, then filter by exact distance, and make sure the cell size is at least the search radius:
5
6```python
7def nearby(index, lat, lng, radius_km):
8 found = []
9 for cell in geohash_neighbours(geohash_encode(lat, lng, index.precision)):
10 for r, (a, b) in index.cells.get(cell, {}).items():
11 d = haversine_km(lat, lng, a, b)
12 if d <= radius_km:
13 found.append((d, r))
14 return sorted(found)
15```
1Show the Level 5 (sketch) solution
21. **Latest positions:** an in-memory geo index per city (Redis GEO sets keyed by city, or an in-memory cell map), storing rider → (lat, lng, last_seen). Availability (free, assigned, off shift) is kept alongside.
32. **Query:** find the store's 5-character cell and 8 neighbours (or `GEOSEARCH ... BYRADIUS 2 km ASC COUNT`), filter by haversine and by "available and seen in the last 30 s", sort, take 5. If fewer than 5, return what's there and either widen the radius by a set step or queue the order and retry shortly.
43. **Updates:** riders send pings to a location service that validates and rate-limits them, updates the in-memory index (moving between cells only on cell change), and appends to a log for history in batches. Riders not seen for 30 s are skipped by queries and swept out by a background job.
54. **Sharding:** one shard per city, busy cities split by cell prefix. Stores near a shard boundary query both shards and merge.
65. **No double assignment:** the matcher proposes candidates; assignment is an atomic conditional update ("set assigned if still available", Chapter 17). The losing order moves to its next candidate.