• ㊗️
• 大家
• offer
• 多多！

## Problem

Note: This is a companion problem to the System Design problem: Design TinyURL.

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design a class to encode a URL and decode a tiny URL.

There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Implement the Solution class:

• Solution() Initializes the object of the system.
• String encode(String longUrl) Returns a tiny URL for the given longUrl.
• String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.

Example 1:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after deconding it.


Constraints:

• 1 <= url.length <= 10^4
• url is guaranteed to be a valid URL.

## Code

1. URL 的范围受到整数大小的限制，如果强制加入，会 overwrite
2. 编码方式很容易被预测
public class Codec {
Map<Integer, String> map = new HashMap<>();
int i = 0;

public String encode(String longUrl) {
map.put(i, longUrl);
return "http://tinyurl.com/" + i++;
}

public String decode(String shortUrl) {
return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
}
}


1. URL 的数量仍然受到整数大小的限制，因为用到了 count
2. 编码可预测
public class Codec {

String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
HashMap<String, String> map = new HashMap<>();
int count = 1;

public String getString() {
int c = count;
StringBuilder sb = new StringBuilder();

while (c > 0) {
c--;
sb.append(chars.charAt(c % 62));
c /= 62;
}

return sb.toString();
}

public String encode(String longUrl) {
String key = getString();
map.put(key, longUrl);
count++;

return "http://tinyurl.com/" + key;
}

public String decode(String shortUrl) {
return map.get(shortUrl.replace("http://tinyurl.com/", ""));
}
}


• HashCode()并不能保证产生 unique 的编码，因此有可能重复
• 预测很困难
public class Codec {
Map<Integer, String> map = new HashMap<>();

public String encode(String longUrl) {
map.put(longUrl.hashCode(), longUrl);

return "http://tinyurl.com/" + longUrl.hashCode();
}

public String decode(String shortUrl) {
return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
}
}


• 无法预测
• 数量受限
public class Codec {
Map<Integer, String> map = new HashMap<>();
Random r = new Random();
int key = r.nextInt(Integer.MAX_VALUE);

public String encode(String longUrl) {
while (map.containsKey(key)) {
key = r.nextInt(Integer.MAX_VALUE);
}
map.put(key, longUrl);

return "http://tinyurl.com/" + key;
}

public String decode(String shortUrl) {
return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
}
}


• 降低了编码长度，固定为 6
• 很难重复
• 可以通过增加字符长度增加编码数量
• 无法预测
public class Codec {
String alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
HashMap<String, String> map = new HashMap<>();
Random rand = new Random();
String key = getRand();

public String getRand() {
StringBuilder sb = new StringBuilder();
// 长度固定为6
for (int i = 0; i < 6; i++) {
// 随机字符对应
sb.append(alphabet.charAt(rand.nextInt(62)));
}

return sb.toString();
}

public String encode(String longUrl) {
while (map.containsKey(key)) {
key = getRand();
}

map.put(key, longUrl);

return "http://tinyurl.com/" + key;
}

public String decode(String shortUrl) {
return map.get(shortUrl.replace("http://tinyurl.com/", ""));
}
}


## System Design - Design a URL Shortener

### Step 1: Understand the problem and establish design scope

1. Can you give me an example?
2. What is the traffic volume?
• 100 million URLs are generated pre day.
3. How long is the shortened URL?
• As short as possible
4. What characters are allowed in the shortened URL?
• Shortened URL can be 0-9, a-z, A-Z
5. Can shortened URLs be deleted or updated?
• For simplicity, let’s assume shortened URLs cannot be deleted or updated
6. What are the basic use cases?
• 1) URL shortening: given a long URL, return a shorter URL
• 2) URL redirecting: given a shorter URL, redirect to the original URL
• 3) High availability, scalability, and fault tolerance considerations
7. Estimation
• 1) Write operation: 100 million URLs are generated per day
• 2) Write operation per second: 100 million / 24 / 3600 = 1160
• 3) Read operation: assuming ratio of read operation to write operation is 10:1, so read operation per second: 1160 * 10 = 11600
• 4) Assuming the URL shortener service will run for 10 years, this means we must support 100 million * 365 = 36.5 billion records.
• 5) Assume average URL length is 100.
• 6) Storage requirement over 10 years: 365 billion * 100 bytes * 10 years = 365 TB

### Step 2: Propose high-level design and get buy-in

#### 1. URL shortening - create new short URL

POST api/v1/data/shorten

{
longUrl: longUrlString
}

return shortUrl


#### 2. URL redirecting - redirect short URL to long URL

GET api/v1/shortUrl

return longURL for HTTP redirection


Redirection messages 300 - 308

• 301: moved permanently, browser will remember the redirected URL instead of check server
• 302: moved temporarily (not recommended)
• 303: same as 302, but convert any requests to GET
• 307: same as 307, but keep HTTP methods, use case like submit form

### Step 3: Design deep dive

#### 1. Database

CREATE TABLE Url (
id int NOT NULL AUTO_INCREMENT,
short_url varchar(255) NOT NULL,
long_url varchar(255) NOT NULL,
PRIMARY KEY (id)
);

id|short_url|long_url


#### 2. Hash function

1) Length

365 billion, 62 characters => 62 ^ 6 = ~56 billion, 62 ^ 7 = ~3521 billion

2) Base 62 conversion

id: 11157 十进制 -> (2)(55)(59) 62进制 -> 2TX -> https://www.tynyurl.com/2TX

3) Logic

if(longUrl in DB) {
return shortUrl
} else {
id = generateId() // ID generator service - distributed system
shortUrl = generateShortUrl(id)
saveToDB(id, shortUrl, longUrl)
return shortUrl
}


#### 3. Performance

1) Save short/long URL into cache, when users hit shortURL, check cache

2) Use right HTTP status code, like 301

### Step 4: Wrap up

1. Rate limit
2. Database scaling: replication, sharding
3. Availability, consistency, reliability …