经典面试题28 - 短链接

问题

设计一个类似于TinyURL的缩短链接长度的服务，用户在访问短链接的时候可以自动跳转到长链接。

例子长链接：

https://zhuanlan.zhihu.com/p/21320786

生成的短链接:

https://tinyurl.com/yb7x49ea

解答

根据系统对外提供了存取服务，可以看到系统中两个主要模块：

• 根据传入的长链接字符串https://zhuanlan.zhihu.com/p/21320786 生成短链接 https://tinyurl.com/yb7x49ea，段链接的关键字段是yb7x49ea。
• 根据请求https://tinyurl.com/yb7x49ea 可以取出长链接https://zhuanlan.zhihu.com/p/21320786，这就是可以根据关键字段 yb7x49ea 在我们设计的数据库里取出已经存储的长链接。

简单来说就是设计一套方案可以把长链接和短链接一一映射起来，可以由不同长链接生成不同的ID，且可以根据ID取出长链接。

这里不讨论大并发的场景下，分布式策略不做考虑，只需关注映射算法即可。

这里一个常见的误区是设计一个Hash算法，根据长链接生成一个唯一值，因为我们无法预知外部输入什么样的长链接，这样很能保证Hash算法一定可以把不同的长链接映射为不同的短链接，那必然会有出现碰撞的风险，也就是多个长链接转成了同一个短链接。

我们建立一个如下的数据结构，有自增ID， 长链接和短链接。
核心部分就是自增ID永远不会重复，而我们会把自增ID转换称短链接核心部分，这样短链接也不会重复。

Table Tiny_Url(
  ID : int PRIMARY_KEY AUTO_INC,
  Original_url : varchar,
  Short_url : varchar
)

有人称这种方案为发号策略，即给每一个过来的长链接，发一个号即可，而这个号是自增的，永远不会有发生冲突的风险。短链接的核心部分我们可以设计成一个由62进制组成的字符串“abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789” ， 具体长度自定。

//ID 到短链接
string idToShortURL(long int n)
{
    // 62进制
    char map[] = "abcdefghijklmnopqrstuvwxyzABCDEF"
                 "GHIJKLMNOPQRSTUVWXYZ0123456789";
  
    string shorturl;
  
    while (n)
    {
        shorturl.push_back(map[n%62]);
        n = n/62;
    }
  
   
    reverse(shorturl.begin(), shorturl.end());
  
    return shorturl;
}
  
// 短链接到ID
long int shortURLtoID(string shortURL)
{
    long int id = 0;  
  
    
    for (int i=0; i < shortURL.length(); i++)
    {
        if ('a' <= shortURL[i] && shortURL[i] <= 'z')
          id = id*62 + shortURL[i] - 'a';
        if ('A' <= shortURL[i] && shortURL[i] <= 'Z')
          id = id*62 + shortURL[i] - 'A' + 26;
        if ('0' <= shortURL[i] && shortURL[i] <= '9')
          id = id*62 + shortURL[i] - '0' + 52;
    }
    return id;
}

补充问题：如果需要保证同一个长链接，每次转出来都是一样的短链接，可以在存储长链接之前，去系统检查长链接是否有没有对应的短链接(不用查询所有数据)，有的话直接返回，否则继续自增。

更多

经典面试100题 - 持续更新中

获取更多内容请关注微信公众号豆志昂扬:

• 直接添加公众号豆志昂扬；
• 微信扫描下图二维码；