CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Check the arithmetic (20 minutes)

Redo the numbers for 50 million new URLs per day, a read ratio of 20 to 1, and 5 years. Give writes per second, reads per second, records and storage at 120 bytes each.

Done when: you write about 579 writes and about 11,574 reads per second, 91.25 billion records, and 10.95 TB.

Hint

50,000,000 / 86,400 is about 579.

Easy 2: Code length (20 minutes)

How many characters does a 62-symbol code need for 100 billion records? For 10 trillion? For 365 billion with only 36 symbols (digits and lower case)?

Done when: you write 7, 8 and 8, with the powers shown (62^6 is only 56.8 billion).

Hint

Find the smallest n with 62^n at least the count.

Easy 3: Base 62 by hand (20 minutes)

Convert 3,844 and 100 to base 62 using the book's symbol order.

Done when: you write 3,844 as 100 (1 × 62²) and 100 as 1C (1 × 62 + 38, and symbol 38 is C).

Hint

In base 62 the symbols are 0-9, then a-z for 10 to 35, then A-Z for 36 to 61.

Medium

Medium 1: Write the converter (30 minutes)

Write functions to turn a number into base 62 and back. Test with 11157 and 2009215674938.

Done when: results are 2TX and zn9edcu, and a round trip works on 1,000 random numbers.

Hint

Divide by 62 and collect the remainders.

Medium 2: Collision estimate (30 minutes)

Using the approximation 1 - exp(-n(n-1) / (2 × 62^7)), compute the chance of a collision for 10,000, 1 million and 100 million URLs.

Done when: a table shows about 0.0014 per cent, 13 per cent, and close to 100 per cent.

Hint

Use a script with natural logarithms.

Medium 3: 301 or 302 (30 minutes)

A marketing team needs click counts per country. An internal tool only needs fast links. Pick a status for each and say what extra work each needs.

Done when: two answers with reasons, and one line on how counting is done off the redirect path.

Hint

302 sends every click through the service.

Hard

Hard 1: Non-guessable codes (60 minutes)

Make the codes hard to guess without collisions. Compare a secret offset, a bit shuffle, and a random code checked against the database. Give the cost of each.

Done when: a table with three methods, their collision behaviour, and the extra cost.

Hint

A random code needs a check and a retry on clash.

Hard 2: Custom names (60 minutes)

Add custom short names. Define the table or index, the atomic insert, the clash rule with generated codes, and the abuse limits.

Done when: a design with a schema, the insert statement idea, and one race handled.

Hint

A unique index makes the database refuse the second insert.

Hard 3: Mock interview (60 minutes)

Answer "design a URL shortener" 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.