URL to TinyURL 生成短链接

最近好像这个面试题很流行, 因为考点很多, 而且出题人可以从这个题延展到很多基础知识, 所以是很好的面试题, 也是很好的准备基础知识的题, 大概设计的考点如下:

1. Hash vs Encoding: 一般会问, 生成url的时候, 为什么不能通过生成hash来查找? 回答: hash有冲突. 1个tinyurl, 在decode的时候会map到多个url上. Encoding利用了URL中字符串的可能字符为定值(a->z, A->Z, 0->9, 符号不算), 把每位字符转换成数字, 然后对其用62(26(小写)+26(大写)+10(数字))位编码. 确保了唯一性.代码如下:

      private static final String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
   
       public static int encode(String s) {
           int res = 0;
           for (int i = 0 ; i < s.length(); i++) {
               if ('a' <= s.charAt(i) && s.charAt(i) <= 'z')
                   res = res*62 + s.charAt(i) - 'a';
               if ('A' <= s.charAt(i) && s.charAt(i) <= 'Z')
                   res = res*62 + s.charAt(i) - 'A' + 26;
               if ('0' <= s.charAt(i) && s.charAt(i) <= '9')
                   res = res*62 + s.charAt(i) - 'a' + 26 + 26;
           }
           return res;
       }
       public static String decode(int i) {
           StringBuffer sb = new StringBuffer();
           while (i > 0){
               sb.insert(0,alphabet.charAt(i%62));
               i/=62;
           }
           return sb.toString();
       }

    

2. 如何存储URL: 这个问题就是分布式设计了, 上来要回答设计的出发点,即CAP(Consistency, Availability, Partition(Network Failure)), 中的取舍, 然后设计的corn case, 比如说数据的rollback(Replication)的同时如何确保一致性. 下图是技术vsCAP的说明 转自Github:
3. 存储url时, 数据库会自动生成一个ID, 我们通过这个id, 生成一个全局唯一的id, 这个过程可能包括添加唯一的主机ip地址,或者压缩mac地址, 面试时, 面试官会问如何生成一个全局unique的id, 这时需要考虑数据库的设计, 比如,当用户retrieve的时候, 需要通过这个id, 解析到对应的host上, 并且host还要返回对应的url. 生成唯一的id后, 我们用上边的decode方法, 把id变成String. 返回给用户.