Part 8 of 8 · 2 min read
Exercises
Easy
Easy 1: Location load (20 minutes)
1.5 million drivers online, an update every 5 seconds, 120 bytes each. Give updates a second and MB/s.
Done when: you write 300,000 per second and 36 MB/s.
Hint
1,500,000 / 5.
Easy 2: Trips a second (20 minutes)
12 million trips a day. Give the average a second and the peak at 6 times.
Done when: you write about 139 and about 833 a second.
Hint
12,000,000 / 86,400.
Easy 3: Memory for the index (20 minutes)
2.5 million drivers, 150 bytes each for the latest position and state. Give the memory in MB.
Done when: you write 375 MB.
Hint
2,500,000 × 150 bytes.
Medium
Medium 1: Candidates (30 minutes)
Cells have 15 free drivers on average. A search reads the rider's cell and 8 neighbours. Give the candidates read, and the number after filtering to the nearest 10.
Done when: you write 135 and 10.
Hint
9 cells × 15.
Medium 2: Race (30 minutes)
Two requests both pick driver D. Write the steps with a read-then-write, and with compare-and-set. Say which outcome each gives.
Done when: two traces, one with a double offer and one with a single offer.
Hint
The read and the write are two steps.
Medium 3: Fare (30 minutes)
Base 2.00, 1.10 per km, 0.30 per minute, surge 1.5. A trip of 8 km and 20 minutes. Give the fare.
Done when: you write 25.20, from (2.00 + 8.80 + 6.00) × 1.5.
Hint
Add the three parts before the multiplier.
Hard
Hard 1: Draw the system (60 minutes)
Draw rider and driver apps, gateway, location, dispatch, trip, pricing, ETA, notification and payments. Number the flow from request to match.
Done when: a diagram with at least 8 parts and a numbered flow.
Hint
Dispatch talks to location, ETA and trip.
Hard 2: Batch matching (60 minutes)
Design matching in 3-second windows for 400 requests and 600 drivers. Say the objective, the method and the time limit.
Done when: a design with an objective (total pickup time), a method (greedy or assignment algorithm) and a time budget.
Hint
Total pickup time is the cost to minimise.
Hard 3: Region failover (60 minutes)
A region loses its data centre. Describe what happens to active trips, driver locations and new requests.
Done when: a plan with trip recovery from replicas, rebuilding the index from new updates, and a statement about the pause.
Hint
The index rebuilds itself from the update stream.