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(数字))位编码. 确保了唯一性.代码如下:

     
  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. 返回给用户.