CSE Roadmap

Specialist tier · about 5 hours · 7 parts

Part 7 of 7 · 2 min read

Exercises

Easy

Easy 1: Update rate (20 minutes)

200 million daily users navigate 40 minutes a week. GPS points are sent every 10 seconds. Give the points per second, using an average over 7 days.

Done when: you write about 79,000 per second.

Hint

Minutes per week × 60 / 7 days / 10 seconds per point, then divide by seconds a day.

Easy 2: Tile series (20 minutes)

The top level holds 80 PB and each lower level a quarter of the one above. Sum the infinite series.

Done when: you write about 107 PB (80 × 4/3).

Hint

Sum of a geometric series is the first term over (1 − 1/4).

Easy 3: Tile count (20 minutes)

At zoom 3, how many tiles cover the world, and at zoom 10?

Done when: you write 64 and 1,048,576 (4 to the power of the zoom level).

Hint

Each zoom level multiplies the tiles by 4.

Medium

Medium 1: Data per trip (30 minutes)

A user drives 45 minutes at 30 km/h, using 25 tiles of 100 KB per km². Treat the path as a strip 1 km wide. Give the tile data downloaded.

Done when: you write 22.5 km × 2.5 MB = about 56 MB.

Hint

45 minutes at 30 km/h is 22.5 km.

Medium 2: CDN share (30 minutes)

Peak CDN output is 100,000 MB a second over 250 POPs. Give the average per POP, and per POP if 20 per cent of POPs serve 60 per cent of traffic.

Done when: you write 400 MB a second, and 60,000 / 50 = 1,200 MB a second for a busy POP.

Hint

Divide by the number of POPs.

Medium 3: Reroute check (30 minutes)

1 million active routes, each with a chain of 3 tiles. A tile has an incident. Give the checks needed by the chain method, and by the naive method if each route lists 100 tiles.

Done when: you write 1 million and 100 million.

Hint

One check per route for the chain method.

Hard

Hard 1: Draw the design (60 minutes)

Draw all services of the maps design, the stores and the stream, with numbered flows for location update, route request and tile fetch.

Done when: a diagram with at least 12 parts and three numbered flows.

Hint

Put the stream in the middle.

Hard 2: Routing tile format (60 minutes)

Design a routing tile file: header, nodes, edges, cross-tile links. Say how three levels connect.

Done when: a format description and a small worked example of a route across two tiles.

Hint

A cross-tile link stores the neighbour's geohash and node number.

Hard 3: Live traffic (60 minutes)

Design the traffic update service: input events, a per-road speed estimate, update rate and storage.

Done when: a design with a window for the average speed, a storage choice and a latency estimate.

Hint

Average speeds over a short moving window.