6.30面试小记

今天参加了太能沃可和百度的面试。前者是前几天看到胡冰学长在校内上发的太能沃可的招聘信息,便试着投了一下。对方的回复很快,不久便电话通知确定面试时间,而且联系我的葛MM在邮件里还说明了具体的到达路线,从哪个地铁站出以及要走多远都讲得一清二楚,原因虽然可能与公司的规模并不是很大有关,但对于前来面试的人来说,相比我之前确定IBM环宇大厦所费的折腾,这的确让人觉得贴心不少。

说实话,先前还真不知道太能沃可这家公司(后来才知道是Talent Walker的音译),也没想过去做Social Game,于是在网上查了一下该公司的信息,并试了试其发布的一项游戏。个人觉得,在投简历之前了一下解对方的相关背景还是非常有必要的,而不要看到有招聘启示就想试试,这样做可以让你更好的专注于几家心仪的公司,也更能明确自己的目标。

整个过程分笔试加面试,笔试的题目不多,但只给二十分钟。两道算法,三道技术常识,最后还有道综合题。

算法题1需要在一个无序不重复数组中找出最大的连续自然数长度,如给出数组a={1,3,5,4,9,7},其中有连续的序列345,故此时要求的值为3。

最开始的时候想着是不是应该用动态规划,但后来觉得不行,因为在前i个数的后面一个数的引入或许会造成长度的合并。后来用的是将数组排序后从头开始检索,找出最长的连续自然数序列长度,于是整个算法的复杂度就上了n^2。当然,如果外循环的index不是用for而是用while来实现跟踪式的增加(比如a排序后得到134579,检测到345符合条件后下一次直接从7开始而不是从4再重复计算,可我当时用的是for循环-_-),并且当剩下的元素小于已经找到的最大长度max时就可以停止,还是可以有小小的提升吧。

后来想了一下,这题还可以用数字区间合并的方式进行统计,方法如下:建立一个有序链表,表中各项为当前输入的数所覆盖的区间,初始时置为空,随后从原数组中逐个添加并合并。如在读取{1,3,5}时,建立的链表为[1,1]->[3,3]->[5,5](其中[a,b]项表示a至b的连续自然数都在其中),当添加4时由于4与3连续,合并为[1,1]->[3,4]->[5,5]。最后再检查新添加的数是否与后边的能合并,得到[1,1]->[3,5]。这样的方式建立链表的复杂度为n,定位至合适的位置也为n,添加的数最多只能将原有的两个区间合并故复杂度为常数,整体的复杂度为n。

算法题2则是检验两个字符串数组的内容是否相等。当时做的时候想复杂了,用了有序链表的增加删减,其实应该是先判断下长度是否一致,如果相同则将第一个数组放到一个HashSet中,再逐个地检查第二个数组的元素是否在HashSet内,不在就直接判否,在的话则从HashSet中删除,最后返回HashSet是否为空即可。其实放进哈希表的复杂度和检查是否在表中的复杂度都是nlogn,不过都让系统来处理了。

综合题是给出缩短网址服务的实现原理、关键部分代码以及解决对应冲突的方式。其实先前上Twitter的时候就有想过这个问题,不过当时只是一闪而过,也没有具体去了解一下。现在想想,自己还是缺少份专业敏感性和钻研的精神啊。到Wikipedia上查了一下,大致的方法如下:

Every long URL is associated with a key, which is the part after http://domain.tld/. For example http://tinyurl.com/m3q2xt has a key of m3q2xt.

There are several techniques to implement a shortening.

这题最关键的是如何处理哈希表的同名冲突,可是具体的处理冲突办法我没答好。

其实更多的时候还是和面试官之间的交流。接待我的面试官名叫李一,先前是在Google工作的,人如其名,话不多,但都说在点子上。我介绍项目的时候问的地方都挺细,而且还很快指出项目中可能存在的问题,功力深厚让人望尘莫及啊。后来闲聊公司的一些状况,以及员工的规模及工作方式等等。呵呵,游戏公司确实还是需要热爱游戏的人来制造游戏的规则的呀。

后来还和推荐人胡冰学长见了一面,呵呵,感觉他看上去有些腼腆,其实还是挺健谈的。而且由于工作的缘故,他对互联网及社交游戏的理解自然比我更深刻不少。因为先前曾看过他的博客,也就有了不少相关的话题。以博会友的说法之前虽然听过,但听学长说到写博客的目的时还是感觉收获颇多(在这里推荐下他的博文《人人都需要自己的独立博客》)。后来与其大致聊了一下公司的发展历程及前景,或许正像他说的那样,现在正是Social Game浪潮正澎湃的时候吧。

中午到本部休息了一会,随便借了几本书。本部的资源的确丰富不少,只是还书时还要跑过来还,回想当年厦大还可以跨海预借,然后学校会专车送过来并通知取书,不禁又感叹一番。

下午三点百度面试。上次去IBM时经过百度大厦,所以找起来倒没费什么气力。毕竟是新建的大厦,内部装饰设备都挺豪华。接待的面试官顾先生非常和蔼,也可以看出顾先生是个细心的人,因为他在我简历上感兴趣的地方都有标注,还说来看过我的博客:)整个面试过程也很轻松。由于我在简历中写自己最近在学习Android开发,他还主动掏出自己的G2和我聊了一阵。呵呵,看来百度里面应该也有不少Google的粉丝呀,然后我邪恶地想到微软禁止员工使用iPhone的情景。。。

期间聊到一个IP段合并的算法题,由于先前在《编程之美》上看到类似的题目,我当时把IP当作32位的数直接映射到数轴上处理。当然这样的空间浪费度非常大。其实这题和上午的面试题有些类似,将各个IP段读入并进行合并,记录下区间即可。另外问的数据库更新优化的问题没答好,而且太久没直接写SQL了,后面的写语句也没答上来。这两天是需要好好重温下数据库了。

本来顾先生还想让经理过来当场二面的,可惜对方没有时间。呵呵,希望下周的面试能顺利吧。

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: