原题链接在这里：https://leetcode.com/problems/design-tinyurl/description/
题目：
How would you design a URL shortening service that is similar to TinyURL?
Background:
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.
Requirements:
- For instance, "http://tinyurl.com/4e9iAk" is the tiny url for the page
"https://leetcode.com/problems/design-tinyurl". The identifier (the highlighted part) can be any string with 6 alphanumeric characters containing0-9,a-z,A-Z. - Each shortened URL must be unique; that is, no two different URLs can be shortened to the same URL.
Note about Questions:
Below are just a small subset of questions to get you started. In real world, there could be many follow ups and questions possible and the discussion is open-ended (No one true or correct way to solve a problem). If you have more ideas or questions, please ask in Discuss and we may compile it here!
Questions:
- How many unique identifiers possible? Will you run out of unique URLs?
- Should the identifier be increment or not? Which is easier to design? Pros and cons?
- Mapping an identifier to an URL and its reversal - Does this problem ring a bell to you?
- How do you store the URLs? Does a simple flat file database work?
- What is the bottleneck of the system? Is it read-heavy or write-heavy?
- Estimate the maximum number of URLs a single machine can store.
- Estimate the maximum number of queries per second (QPS) for decoding a shortened URL in a single machine.
- How would you scale the service? For example, a viral link which is shared in social media could result in a peak QPS at a moment's notice.
- How could you handle redundancy? i,e, if a server is down, how could you ensure the service is still operational?
- Keep URLs forever or prune, pros/cons? How we do pruning? (Contributed by @alex_svetkin)
- What API would you provide to a third-party developer? (Contributed by @alex_svetkin)
- If you can enable caching, what would you cache and what's the expiry time? (Contributed by @Humandroid)
题解：
是System Design题目. 参考了这篇帖子.
按照SNAKE的方法逐个分析.
AC Java:
public class URLService{
HashMap<String, Integer> ltos;
HashMap<Integer, String> stol;
static int COUNTER;
String elements;
URLService(){
ltos = new HashMap<String, Integer>();
stol = new HashMap<Integer, String>();
COUNTER = 1;
elements = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
}
public String longToShort(String url){
String shortUrl = base10ToBase62(COUNTER);
COUNTER++;
ltos.put(url, COUNTER);
stol.put(COUNTER, url);
return "http://tinyurl.com/" + shortUrl;
}
public String shortToLong(String url){
url = url.substring("http://tiny.url/".length());
int n = base62ToBase10(url);
return stol.get(n);
}
private int base62ToBase10(String s){
int n = 0;
for(int i = 0; i<s.length(); i++){
n = n*62 + convert(s.charAt(i));
}
return n;
}
private int convert(char c){
if(c>='0' && c<='9'){
return c-'0';
}else if(c>='a' && c<='z'){
return c-'a'+10;
}else if(c>='A' && c<='Z'){
return c-'A'+36;
}
return -1;
}
private String base10ToBase62(int n){
StringBuilder sb = new StringBuilder();
while(n != 0){
sb.insert(0, elements.charAt(n%62));
n /= 62;
}
while(sb.length() != 6){
sb.insert(0, '0');
}
return sb.toString();
}
}