LeetCode Design TinyURL
2024-09-25 15:46:14
原题链接在这里: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();
}
}
最新文章
- ASCII 计算机码
- Java日期格式化及其使用例子收集
- [HDU 4549] M斐波那契数列
- NET笔记——IOC详解和Unity基础使用介绍
- 浅析五大ASP.NET数据控件
- jQuery Validation让验证变得如此easy(一)
- 【IDE】IntelliJ IDEA (Mac) 运行速度优化(问题起因:debug模式突然变得巨慢)
- 手把手设计MyBatis
- Create Maximum Number
- win10安装MySql 5.7.23
- linux:awk修改输出分隔符
- SQL Server 递归查询上级或下级组织数据(上下级数据通用查询语法)
- [数据结构与算法分析(Mark Allen Weiss)]不相交集 @ Python
- QT读文件夹内所有文件名
- Physical&#160;Limits&#160;of&#160;ASM
- Eclipse安装Git插件(在线和离线)
- 51Nod 1058: N的阶乘的长度(斯特林公式)
- Cloudera Manager Server CDH 5.15部署
- ubuntu开机执行指令或脚本
- Redis(1):入门