Design a URL shortener
A counter hands out numbers, base 62 turns each one into a short code, and a cache answers most of the reads. The round is about which of those three breaks first, and at what load.
Should a URL shortener use a hash of the URL or a counter?
A counter, handed out to servers in blocks. A hash truncated to seven characters can collide, so every write has to read the table first and retry on a clash, and the chance of a clash grows as the table fills. A counter gives each link a number no other link can have, so a write is one insert. The cost is that the counter is shared state, which is why servers lease a thousand numbers at a time instead of asking for each one.
How long should a short code be?
Long enough for every link you will ever keep. Work out how many links the retention period adds up to, then find the smallest length whose 62 to the power of length is bigger. At 20 million links a day kept for ten years that is 73 billion links, and six characters give only 56.8 billion, so the answer is seven.
Should the redirect be a 301 or a 302?
A 302 if the owner wants click counts, and most do. A 301 tells the browser the move is permanent, so it remembers the target and later clicks from that browser never reach your servers. That saves you load and loses you every count after the first. A 302 means every click comes through you, so you can count it and you can change or expire the link later.
What does the cache in front of a URL shortener buy?
It keeps the database under its limit at the busiest hour. Reads are ten times the writes, and a small share of links draws most of the reads, so a cache holding that hot share answers about nine reads in ten. Without it the database is asked for more than it can serve at the peak; with it the database sees under a third of its capacity.
How do you stop people guessing other short links?
Codes from a plain counter are sequential, so anyone can walk them. Scramble the number before you encode it with a keyed permutation, a function that maps every number to a different number of the same size and can be undone. The codes stay unique and the same length, but the next one tells you nothing about the last. It does not make a link private; anything behind a short link should be treated as public.