CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 8 of 8 · 2 min read

Exercises

Easy

Easy 1: Rate (20 minutes)

500 million clicks a day. Give the average per second and the peak at 5 times the average.

Done when: you write about 5,787 and about 28,935 per second.

Hint

500,000,000 / 86,400.

Easy 2: Storage (20 minutes)

With 0.1 KB per click, give the GB per day and TB per year.

Done when: you write 50 GB a day and 18.25 TB a year.

Hint

500,000,000 × 0.1 KB.

Easy 3: Count by ad (20 minutes)

A minute holds clicks for ads 1, 2, 1, 3, 1, 2. Give the count for each ad.

Done when: you write ad 1: 3, ad 2: 2, ad 3: 1.

Hint

Tally each id.

Medium

Medium 1: Route by key (30 minutes)

Route ads 4 to 9 to three aggregate nodes using ad id modulo 3.

Done when: you write node 1 for 4 and 7, node 2 for 5 and 8, node 0 for 6 and 9.

Hint

Take the remainder after dividing by 3.

Medium 2: Watermark (30 minutes)

A window 12:00 to 12:01 has a 15-second watermark. Event A has event time 12:00:50 and arrives at 12:01:10. Event B has event time 12:00:30 and arrives at 12:01:20. Which is counted?

Done when: you write A is counted and B is missed.

Hint

The window is final at 12:01:15.

Medium 3: Merge top lists (30 minutes)

Node 1 reports a 120, b 100, c 80. Node 2: d 110, e 90, f 70. Node 3: g 130, h 60, i 50. Give the top 3.

Done when: you write g 130, a 120 and d 110.

Hint

Merge all nine and sort.

Hard

Hard 1: Draw the pipeline (60 minutes)

Draw the pipeline with log watcher, two queues, map, aggregate and reduce nodes, writer, database and query service. Mark the exactly-once step.

Done when: a diagram with at least nine parts and the atomic commit marked.

Hint

The read position and the result are saved together.

Hard 2: Hot ad (60 minutes)

One ad gets 40 per cent of 50,000 clicks per second. One node can count 10,000 per second. Show how to spread the load and how the parts are merged.

Done when: a plan with 20,000 per second for the ad, at least 2 sub-keys, and a merge step.

Hint

20,000 divided by 10,000 gives the number of sub-keys.

Hard 3: Mock interview (60 minutes)

Answer "design ad click aggregation" 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.