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:
- *Base 62 conversion *- converts the same number between its different number presentations
- 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.
Top comments (0)