最差的答案实现了一种将长地址转换为短地址的算法。实现多空一一对应。然后实现其逆运算，将短地址转换回长地址。这个回答看起来还不错，候选人也会说现在时间比较短。如果你给我时间，我会找到这个算法并解决问题。但是稍有计算机或信息论知识的人就会发现，这个算法就像一个永动机，永远找不到。即使我们将短地址定义为100位。那么它的变化就是62的100次方。62=10个数字+26个大写字母+26个小写字母。不管这个数字有多大，也不可能比世界上可能存在的长地址更大。因此，不可能实现一一对应。反驳一下，如果有这样的算法和逆运算，那么基本上现在的压缩软件就可以不工作了，世界上所有的信息都可以压缩到100个字符。这可能吗？另一个不好的答案和上面一样，也找了一个算法把长地址转换成短地址，但是没有逆运算。我们需要将短到长的关系存储在DB中，通过short检查长度时，需要检查DB。怎么说呢，本质没变。如果有这样的算法，必然会出现冲突，即多个长地址转换成同一个短地址。因为我们无法预测什么样的长地址会被输入到这个系统中，所以不可能实现这样一个永不冲突的哈希函数。对于不好的答案，让我们使用哈希算法。我承认它会碰撞。碰撞后，我在碰撞后加上1、2、3。ok，在这种情况下，hash算法计算出来之后，我们可能需要做一个btree式的大于小于或类似的查找，才知道应该在末尾加1、2或3。这也可能是由于长输入地址集的不确定性。导致地址生成时间短的不确定性。同样不好的答案是随机生成一个短地址，看看是否被使用过，用过后再随机化，以此类推，直到随机化出一个没有被使用过的短地址。正确的原则上面是几个典型的错误答案，下面直接说说正确的原则。正确的原则是通过发号策略给每个传入的长地址发号，小系统可以直接用mysql的自增索引搞定。对于大型应用程序，可以将各种分布式键值系统视为发行者。只是不断增加。第一个使用这个服务的人得到短地址http://xx.xx/0第二个是http://xx.xx/1第11个是http://xx.xx/a依次类推实现一个62进制的自增字段。几个子题1.如何用数据库或者KV存储做16进制？其实我们在storage中不需要使用62进制，直接使用10进制即可。比如第10000个长地址，我们给它的短地址对应的数字是9999，我们通过storageauto得到9999后-increment，我们会做一个十进制到十六进制的转换，转换成十六进制数。.你完全可以自己实现这个从10到62的转换。2、如何保证每次传输的长地址相同，短地址相同？在上面的发号原则中，不判断长地址是否已经转出。就是说，用百度首页地址转发，我给你一个http://xx.xx/abc，等一会你再转发，我再给你一个http://xx.xx/xyz。这看起来很糟糕，但这有什么问题呢？不好的是没有一一对应，而是一长一短。这不是我们的共产主义基因，所以还有什么问题？有人说这是浪费空间，他们是对的。同一个长地址生成多个短地址记录，显然是一种空间浪费。那么我们如何避免浪费空间呢？很快就有人回答我了，创建一个长对短的KV存储就可以了。嗯，这听起来很合理，但是。..这种KV存储本身就是一种巨大的空间浪费。所以我们是用空间换空间，好像是用大空间换小空间。是不是真的值得吗？这个问题需要考虑。当然，也不是没有办法解决。我们无法做到真正的一一对应，那有没有可能打折呢？这个问题的答案太多了，各有千秋。最简单的解决方案是创建一个long-to-shorthashtable，相当于以空间换空间，同时换取优雅的设计（真正的一对一）。实际情况是有很多性价比高的折扣方案可供选择，而这个方案的设计因人而异。那么让我告诉你我的计划吧。我的解决方案是：使用key-value存储来保存“最近”生成的长短对应关系。注意这里是“最近的”，也就是说我没有保存全部的多空关系，只保存最近的。比如使用一小时过期机制来实现LRU淘汰。这样的话，从长到短的过程就变成了这样：查“recent”表，看长地址是否有对应的短地址，然后直接返回，延长这个key-value的过期时间pairtoonehour如果没有，通过发号器生成一个短地址，放到“recent”表中，过期时间为1小时，所以当一个地址被频繁使用时，它会一直在key-value中表，并且可以一直返回最开始生成短地址的时候，不会出现重复的问题。如果不经常使用，long-to-shortkey会过期，LRU机制会自动淘汰。当然，这并不能保证同一个长地址100%的转入同一个短地址。比如你取一个不常见的url，每小时传输一次，你会得到不同的短地址。但这真的重要吗？3、如何保证发号器的大并发和高可用上面的设计中似乎有一个单点，那就是发号器。如果做成分布式，那么必须保持多个节点同步加1，多个点同时写入。那么，从CAP理论的角度来看，是不可能真正做到的。其实解决这个问题很简单。我们可以退一步考虑，能不能实现两个发号器，一个发单号，一个发双号，让单点变成多点？以此类推，我们可以实现1000个逻辑发号器，发号尾号从0到999，每发一个号，每个发号器加1000，而不是1。这些发号器独立工作，互不干扰。而且在实现上，也可以先逻辑化，然后压力变大，再拆分成独立的物理机单元。1000个节点，估计人类应该够用了。如果你真的想要更多，理论上是可以的。4、具体存储如何选择就不赘述了。每个人都有自己的方式。下面主要考察对存储的理解。了解缓存的原理，了解市面上DB和Cache系统的可用性、并发性和一致性。5、跳转用301还是302也是一个有趣的话题。首先当然是考查考生对301和302的理解。对浏览器缓存机制的理解。然后考察他的经商经历。301是***重定向，302是临时重定向。短地址一旦生成就不会改变，所以使用301是符合http语义的。同时，服务器的压力也会降低。但是如果使用301，我们将无法统计短地址的点击次数。而这个点击次数对于大数据分析来说是一个非常有趣的数据源。可以分析的东西太多了。所以选择302会增加服务器的压力，但我认为是更好的选择。就是这样。
