Part 8 of 8 · 2 min read
Exercises
Easy
Easy 1: Redo the rate (20 minutes)
5 million DAU make 8 searches a day, and each search sends 15 requests. Give the average and peak (twice average) requests per second.
Done when: you write about 6,944 and 13,889 per second.
Hint
5,000,000 × 8 × 15 = 600,000,000 requests a day.
Easy 2: Daily growth (20 minutes)
With the same users, a query of 18 bytes and 20 per cent new queries, how much new data is added each day?
Done when: you write 5,000,000 × 8 × 18 × 0.2 = 144,000,000 bytes, about 0.144 GB.
Hint
Multiply, then take 20 per cent.
Easy 3: Read the trie (20 minutes)
Using the trie in this page, give the top 2 queries for the prefix "t".
Done when: you write true (35) and try (29).
Hint
Look at all queries that start with "t".
Medium
Medium 1: Build a trie (30 minutes)
Draw a trie for tree, true, try, toy, wish and win with frequencies 10, 35, 29, 14, 23 and 50. Write the cached top 2 at nodes "t", "tr" and "w".
Done when: a drawing and lists true, try; true, try; win, wish.
Hint
Each node's list is the best of the queries below it.
Medium 2: Sampling (30 minutes)
200 million searches a day are logged at 1 in 100. How many records a day? If "twitter" shows 3,000 times in the sample, what is the estimate of its real count?
Done when: you write 2,000,000 records and about 300,000.
Hint
Multiply the sample count by 100.
Medium 3: Update cost (30 minutes)
"beer" moves from 10 to 30. List the nodes whose cached lists may change in the trie of this page's style, not counting the root.
Done when: you write b, be, bee and beer, 4 nodes.
Hint
The ancestors that spell the prefixes of "beer".
Hard
Hard 1: Shard plan (60 minutes)
Given counts of queries by first letter (invent a table of 26 numbers with some letters 10 times bigger than others), split into 6 shards and show each shard's share.
Done when: a table of 6 shards with shares within 25 per cent of each other, and a shard map.
Hint
Sort letters by count, then group so totals are close.
Hard 2: Trending (60 minutes)
Design the second structure for trending queries. State how counts are decayed, how it is merged, and how big it stays.
Done when: a diagram, a decay rule with a number, and a size estimate.
Hint
Halving counts every hour is a simple decay.
Hard 3: Mock interview (60 minutes)
Answer "design search autocomplete" 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.