CSE Roadmap

Core tier · about 4 hours · 8 parts

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.