面试中如何化解懵逼,从一个短网址服务说起

来自:寒食君(微信号:program_hacker),作者:寒食君i

我觉得面试题可以分为两种,一种是“客观题”,比如考察面试者知不知道那个知识点、面试者对这个知识点的理解有多深。比如,面试官可能会问你:“知道Java的内存模型吗?来说说吧。”

另外一种是“主观题”,即抛出一个场景问题,考察在主观上,面试者将会如何动用自己的知识去解决。比如,面试官会这样问你:“假如需求中有一个注册登录模块,你会怎么去设计实现它?”

两者比较,我觉得第二种问题难度更大。因为客观题是可以通过刷题和记忆来提升自己的,而主观题就考察了你对这些知识是否真的理解、能够将它们组织运用起来、是否有关的实战经验等。

下面我将针对第二种问题,以一个我实际遇到过的真实面试问题来展开。当然,和实际开发有些不同的是,面试更需要保持冷静、随机应变、有逻辑地思考问题、清晰流畅的语言表达,尤其是面对从未涉足过,一时半会毫无头绪的问题。

记得在实习面试的时候,我遇到了这个问题:现在市面上有一些将长网址变为短网址的服务(百度的dwz.cn就是这样的一个服务,可以去体验一下),比如你短信里收到的链接就是短网址,这些是如何实现的呢?

我当时听到这个问题有点懵,这面试官不按套路出牌啊,怎么不问我面经里的知识点?

懵归懵,心态一定不能炸,于是我故作镇定:不好意思,这个问题我之前没接触过,请先给我两分钟思考下。

我首先梳理了一下问题,总结出这个问题所要达成的目标:

1.使网址变短2.依然可用(不会产生冲突)

我的第一反应是:长网址变短网址,这不是数据的压缩吗?那么怎么才能将一个字符串压缩成另一个字符串呢?而且不会产生冲突。我想到了签名算法,比如MD5这种,它可以将任意长的字符串经过签名后都变成指定的相同长度。

但是呢,它存在问题,首先,MD5在理论上也是可能产生碰撞的。可以尝试换用SHA-1或其他散列算法。其次,输出的签名是定长,比如说32位,那么无论原网址多长,输出输出的短网址都是32位,对于原长度小于32位的网址来说,它不仅没有缩短,反而加长了,所以这在通用性上存在问题。

此时我又想到了另一种方法。在ASCii字符集中,一个字符占一个字节,我能不能自己定义一个新的字符集和编码方式,比如用四位来确定一个字符,通过这种方式让数据尽量“挤”一些。仔细一想,这应该是无法实现的,因为128个字符最少也需要7位来表示,无论如何4位也无法胜任。既然4位无法胜任,那么6位呢?因为有一个著名的Base64编解码方法,可以将64个字符从一个字节的8位,重新编排为6位,这样就能使得字符串变短了。

Base64的方法看上去可以,但实际是行不通的,因为在Base64表中,不存在像“-”、“.”、“:”这种网址中出现的字符。

眼看两分钟就过去了,没办法,我只能先把面试官稳住。我告诉了他我刚才的想法,然后又自己否决了它,为了再争取一点思考的时间。把你思考的痕迹展现出来,说明你是真的在思考,假如你思考的内容是有逻辑的话,面试官也会理解。如果你实在没有头绪,也可以尝试向面试官要一些提示。

于是我继续考虑这个问题,因为信息本身的长度,使用自定义编码的方式其实是收效甚微的。难道我走错了方向?既然都是映射,我我什么一定要在字符串本身做文章呢?

我灵光一闪,或许我可以这样,直接来一个网址,我自增一个,用来作为这个网址的key。比如:来一个google.com 我编号1,来一个github.com 我编号2....

此时,我看面试官已经等了一会儿了,不能再拖了,于是我赶紧把上面的想法说了,面试官一边应答,一边听了我的想法,然后问我:“那么遇到相同的长网址呢?查表吗?”

我回答:“每次遇到请求都去查表的话,一旦请求数量上去了,可能会遇到阻塞的问题。可以使用内存数据库来做缓存,但是如果被查询的长网址的量非常大,内存好像也存在问题。”

面试官说:“不一定要存全量的,其实只要存一些热门的,当请求过来,判断是否击中缓存,若击中,就刷新失效时间,这样,热门的一直在缓存中,而非热门的就会被缓存淘汰。若未击中,就查表或重新生产,具体是查表快,还是重新生产快,这个需要测试。”

“那么,如果对一个热度不高的长网址进行了多次生产的方式,出现了多个不同的短网址的话,就无法一对一了吧?”这下变成我反过来提问了。面试官说:“为什么一定要一对一呢?不热门的网址,本身出现的可能性较低,多生产几次,不会浪费很多空间。”

我恍然大悟,原来自己的思维一直被自己限制着。如何跳脱这种桎梏,只有多见识,多实践才可以弥补。

推荐↓↓↓
Web开发
上一篇:从 GFS 失败的架构设计来看一致性的重要性 下一篇:Vue+Node+高德地图+Echart做一款出行可视化全栈webapp