Part 8 of 8 · 2 min read
Exercises
Easy
Easy 1: Search rate (20 minutes)
40 million DAU make 6 searches a day each. Give the average searches per second.
Done when: you write 240,000,000 a day and about 2,778 per second.
Hint
40,000,000 × 6 / 86,400.
Easy 2: Pick a length (20 minutes)
Give the geohash length for radii of 0.5, 2 and 20 km using the table.
Done when: you write 6, 5 and 4.
Hint
Use the radius table.
Easy 3: Count leaves (20 minutes)
50 million places, at most 100 per leaf. How many leaf nodes at least?
Done when: you write 500,000.
Hint
50,000,000 / 100.
Medium
Medium 1: Quadtree memory (30 minutes)
With the node sizes of this page, give the memory for 500,000 leaves and one third as many internal nodes.
Done when: you write 416 MB for leaves, about 10.7 MB for internal nodes, and about 427 MB in all.
Hint
500,000 × 832 bytes, then 166,667 × 64 bytes.
Medium 2: Neighbour search (30 minutes)
A cell holds 40 places on average. How many cells are searched for one query and how many candidates are filtered by distance?
Done when: you write 9 cells and 360 candidates.
Hint
The own cell and its 8 neighbours.
Medium 3: Widen the search (30 minutes)
A length-5 cell is 4.9 × 4.9 km. A length-4 cell is 39.1 × 19.5 km. How many times larger is the area of the second?
Done when: you write 24.01 km², 762.45 km², and about 32 times.
Hint
Multiply each pair, then divide.
Hard
Hard 1: Design the tables (60 minutes)
Write the table layout for businesses and the geospatial index. Give the primary keys, the insert and delete statements for a business, and the search query for 9 cells.
Done when: two tables with keys, three statements and a reason for the compound key.
Hint
The key of (geohash, business id) makes each row unique.
Hard 2: Choose an index (60 minutes)
A taxi app needs the 8 nearest cars to a rider, and cars move every 3 seconds. Compare geohash and quadtree. Give your choice and the update cost.
Done when: a comparison with an update rate, a choice and one risk.
Hint
Moving objects make writes the main load.
Hard 3: Mock interview (60 minutes)
Answer "design a nearby places service" aloud in 35 minutes and mark yourself on the four steps. List two missed topics.
Done when: a recording, a score on each step, and two named gaps.
Hint
Use the four-step framework as a checklist.