CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 4 of 7 · 3 min read

The short code

How long, and where it comes from.

How long? The code uses 62 possible characters. For length n there are 62^n codes. Find the smallest n for which 62^n is at least 365 billion.

  • n = 6: 62^6 = 56,800,235,584, about 56.8 billion. Too small.
  • n = 7: 62^7 = 3,521,614,606,208, about 3.5 trillion. Enough, and about 9.6 times the 365 billion needed.

So the code is 7 characters long.

Approach A: hash and fix collisions. Run the long URL through a known hash such as CRC32, MD5 or SHA-1 and keep the first 7 characters. Even the shortest of these, CRC32, gives more than 7 characters, so it must be cut. Cutting causes collisions: two different long URLs with the same 7 characters. The fix is to check the database, and if the code is taken, add a fixed string to the long URL and hash again, until a free code appears.

Two problems. First, every request needs a database lookup to check for a collision, which is costly. A Bloom filter, a compact structure that can say "definitely not present" for most codes, cuts that cost. Second, the chance of collision is not small. A short worked check (made up, computed by script): with 7 characters from 62 symbols and 1 million URLs, the chance of at least one collision is about 13 per cent. At 100 million URLs it is practically certain. If the hash is written in hex, with only 16 symbols, 7 characters give just 268 million codes, so it could not even hold 365 billion.

Approach B: base 62 of a counter. Give each new URL a unique number from the ID generator (module 2). Then write that number in base 62. Each position uses one of the 62 characters: 0 to 9 stand for 0 to 9, a to z for 10 to 35, and A to Z for 36 to 61.

The book's example. The number 11157 in base 10 is 2 × 62² + 55 × 62 + 59, so its digits are [2, 55, 59], which are written 2, T, X. The code is 2TX. A second example from the book: the ID 2009215674938 becomes zn9edcu, which is 7 characters. Both were checked by script.

Hash and fix collisions Base 62 of an ID
Code length Fixed at 7 Grows with the number, 7 for these numbers
Needs an ID generator No Yes
Collisions Possible, must be checked None, since each ID is unique
Next code guessable No Yes, since codes follow the counter

The book's design uses base 62, since it never collides. Its cost is that a person could guess the next code from the last one. If that matters, hide the counter: add a secret offset, scramble the bits, or use an ID layout that is not sequential. Say so in an interview.

Check yourself: 1. Why is 6 characters not enough? 2. What is the base 62 code for the number 61? And for 62? 3. Why does approach B never collide?