Design a short url for system design interview

This article is a personal note from "System Design Interview - An Insider's Guide by Alex Xu". It's intended as a memory refresher for system design interview in hurry.

hash funciton

• to generate a shorter URL, use a hash function to map between short URLs and long URLs. For example, hash functions like CRC, MD5 and SHA-1 are used.

hash value

• to generate short URLs of length "n", find the value that meets "back-of-the-envelope" estimation. For example, a system is identified to support 365 million unique URLS, then given the system generates using [0-9,a-z,A-Z], "n" has to be 62^n >= 365 M (roughly 7).

hash collision

• to generate unique short URLs, two approaches can be taken:
  
  
  
  
  1. *Base 62 conversion *- converts the same number between its different number presentations
  
  
  2. Hash the first "n" number of characters and append it to the rest to generate a short URL. If the length of the result still exceeds "n", repeat the process.
     
     
     
     
     • As this can be time-consuming, "bloom filter" can be used to improve performance. Bloom Filter is a space-efficient probablistic technique to test if an element in a number of a set.