CSE Roadmap

Specialist tier · about 5 hours · 8 parts

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.