CWYAlpha

Just another WordPress.com site

Thought this was cool: Google面试

leave a comment »


两个星期之前的一个周五下午,我正在家里寂寞的学着JS,一封突然到来的邮件打破了我宁静的生活——”Greeting from Google!”。眼看明年的工作还没着落,我欣然接受了邮件里的面试邀请。跟一个Google中国的HR用英文发邮件是件很奇怪的事儿,不过HR很给力,我的面试日期很快就定下来了。

Google面试的风格跟我面的其他公司很不一样,每次都会要求自我介绍——就是介绍自己的项目。各位有志于Google的童鞋最好先准备一下。顺便提一句,我每次说的项目都不一样哦。

一面是这样的,首先是自我介绍——blablabla说了点。然后是一道很无趣的遍历二叉树的题,面试官规定了我需要实现的函数的原型,让我先说说想法然后写代码。我说了一个做法,然后实现了另外一个(囧)。最后面试官给了一道题目:

求一个数字集合里最长的连续数字串的长度。例如{ 1 2 9 10 11 3 12 7}中的{ 9 10 11 12}

我的第一反应当然是排序了。面试官问有没有更好的解法,经过他的提示我想到了Hash。但是在估计复杂度的时候,面试官坚决不同意我“可以认为Hash中的冲突很少”的看法。所以我得到了O(N^2)的复杂度。事后我一想,不能认为Hash冲突很少我还用个毛Hash 啊!面试完的那个晚上我没有睡着,脑子里全是这个问题,但是没有找到更好的方法。请问各路大神,这题有没有更优的解法?

二面同样给我留下了深刻的印象。自我介绍,blablabla。面试官出的第一题是从一个数字串中找到最长的递增子串。很显然是O(N)的对吧,面试官问我有没有更优的。我嗯啊呀哈了五分钟之后,面试官说,如果要求递增的差为1,有没有更优的方法?我….扯了一个没有用的方法给他。第二题是二合一,首先面试官要求我求出一个线段集合里相交的线段。我先搞了一个naive的线段合并,可以判断出某线段是否和别的线段相交。之后面试官增加了要求:

输出线段集合中的相交线段的子集,如果线段A, B, C, D中,A, B, D两两相交,B和C相交,A和C不相交,输出集合{A B D}和{B C}。

我首先给出了离散化并查集的O(N^2)方法。有没有更优的?我当场怀疑这样的集合会有O(N)个,每个会有O(N)个元素。但是当时没有找到这样的例子,于是扯了一个Splay延迟标记维护的方法并号称是O(NlogN)的。事实证明,还是存在能让输出复杂度达到O(N^2)的例子的。我又花了一个晚上才想到的这个例子。

不管怎么样,我拿到了Onsite的资格(八成是考虑到竞争对手的Offer吧)。Onsite就靠谱多了,至少题目都是可以答的。

一面第一步照例是自我介绍,blablabla。第二步是个不太难的题目,跟线段相关的。题目不重要,重要的是面试官首先要求我详细的叙述我的想法,之后在纸上写伪代码,最后要求我翻译成代码,并且要用设计合理的函数完成这个程序。第三步是个加强版的题目,因为时间不多了我草草写了几笔。

中午跟面试官一起吃了饭,畅谈了一下人生理想。面试官建议我不要急着工作,先去旅旅游见见世面,还跟我分享了他当年单独去越南旅游的经历。我本来还想明年先来实习呢,但是现在觉得,玩儿命工作还是享受人生,这是个问题。顺便说一句,Google上海的自助餐厅大概只能容纳100人,借此可以估计一下Google上海的规模。另外,盛传Google中国没有什么技术类的活,其实不是的,他们还是负担着非常多的开发任务的。

二面的面试官是一个比较威严的工程师。他的题目也很有意思,都是比较偏向于数学的,每次除了描述想法之外,还要求有非形式化的证明。他在我证明的过程中要求我澄清几乎每个概念,力求严谨。猴神可能会比较喜欢这样的题目。两道这样的题目之后,面试官出了一道Design的题目,要求我设计一个关于指针的工具类,并独立做出各种决策。在考虑了N多问题之后,我卡在了拷贝的实现策略中,超时了。面试官安慰我说这样的题目是没有一个固定的答案的,讨论的过程更重要。

这样我的四次面试就结束了。虽然我自我感觉良好,但是我的表现实在不很完美。也许我应该等结果出来再来写这篇得瑟的博客。但是现在,我还是抓紧享受一下生活吧。


0

   

0

IT 牛人博客聚合网站(udpwork.com) 聚合
|
评论: 0
|
10000+ 本编程/Linux PDF/CHM 电子书下载

from IT牛人博客聚合网站: http://www.udpwork.com/item/7976.html

Written by cwyalpha

八月 21, 2012 在 9:26 上午

发表在 Uncategorized

发表评论

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 博主赞过: