马海祥博客是一个专注于分享SEO优化、网站制作、网络营销和运营思维的自媒体博客!
马海祥博客 > 职场人生 > 职场法则 > 我是如何为Google面试做准备的

我是如何为Google面试做准备的

时间:2015-01-26   文章来源:马海祥博客   访问次数:

如果你有一段时间没有面试过,根据我的经验,有个非常有用的提醒你应该接受,就是:你往往会在前几次面试中的什么地方犯一些错误,简单而言就是,不要首先去你梦想的公司里面试,面试中有多如牛毛的应该注意的问题,你可能全部忘记了,所以,先去几个不太重要的公司里面试,它们会在这些方面对你起教育(再教育)作用。

我是如何为Google面试做准备的-马海祥博客

很多年前,我初进硅谷人才市场,当时是想找一份高级工程师的职位,我第一家面试的公司叫做gofish,据我所知,gofish这家公司如今的情况跟我当时面试时完全的不同,我几乎能打保票的说,当时我在那遇到的那些人都已不再那工作了,虽说这家公司的实际情况跟我们这个故事并不是很相关,但在其中的面试却是十分相关的,对我进行技术性面试的人是一个叫做Guy的家伙。

Guy穿了一条皮裤子,众所周知,穿皮裤子的面试官通常是让人“格外”恐怖的,而Guy也没有任何让人失望的意思,他同样也是一个技术难题终结者,而且是一个穿皮裤子的技术难题终结者——真的,我做不到他那样。

我永远不会忘记他问我的一个问题,事实上,这个问题是非常的普通——在当时也是硅谷里标准的面试题。

问题是这样的:

假设这有一个各种字母组成的字符串,假设这还有另外一个字符串,而且这个字符串里的字母数相对少一些,从算法上讲,什么方法能最快的查出所有小字符串里的字母在大字符串里都有?

比如,如果是下面两个字符串:

String 1: ABCDEFGHLMNOPQRS

String 2: DCGSRQPOM

答案是true,所有在string2里的字母string1也都有,如果是下面两个字符串:

String 1: ABCDEFGHLMNOPQRS

String 2: DCGSRQPOZ

答案是false,因为第二个字符串里的Z字母不在第一个字符串里。

当他问题这个问题时,不夸张的说,我几乎要脱口而出,事实上,对这个问题我很有信心(提示:我提供的答案对他来说显然是最糟糕的一种,从面试中他大量的各种细微表现中可以看出来)。

对于这种操作一种幼稚的做法是轮询第二个字符串里的每个字母,看它是否同在第一个字符串里。

从算法上讲,这需要O(n*m)次操作,其中n是string1的长度,m是string2的长度。就拿上面的例子来说,最坏的情况下将会有16*8 = 128次操作。

一个稍微好一点的方案是先对这两个字符串的字母进行排序,然后同时对两个字串依次轮询,两个字串的排序需要(常规情况)O(m log m)+ O(n log n)次操作,之后的线性扫描需要O(m+n)次操作。

同样拿上面的字串做例子,将会需要16*4 + 8*3 = 88加上对两个字串线性扫描的16 + 8 = 24的操作。(随着字串长度的增长,你会发现这个算法的效果会越来越好)

最终,我告诉了他一个最佳的算法,只需要O(n+m)次操作,方法就是,对第一个字串进行轮询,把其中的每个字母都放入一个Hashtable里(成本是O(n)或16次操作),然后轮询第二个字串,在Hashtable里查询每个字母,看能否找到。

如果找不到,说明没有匹配成功,这将消耗掉8次操作——这样两项操作加起来一共只有24次,不错吧,比前面两种方案都要好。

Guy没有被打动,他把他的皮裤子弄的沙沙响作为回应,“还有没有更好的?”他问道。

我的天?这个家伙究竟想要什么?我看看白板,然后转向他。“没有了,O(n+m)是你能得到的最好的结果了——我是说,你至少要对每个字母至少访问一次才能完成这项操作——而这个方案是刚好是对每个字母只访问一次”,我越想越确信我是对的。

他走到白板前说道:“如果这样呢——假设我们有一个一定个数的字母组成字串——我给每个字母分配一个素数,从2开始,往后类推,这样A将会是2,B将会是3,C将会是5,等等,现在我遍历第一个字串,把每个字母代表的素数相乘,你最终会得到一个很大的整数,对吧?然后——轮询第二个字符串,用每个字母除它,如果除的结果有余数,这说明有不匹配的字母,如果整个过程中没有余数,你应该知道它是第一个字串恰好的子集了,这样不行吗?”

每当这个时候——当某个人的奇思异想超出了你的思维模式时,你真的需要一段时间来跟上他的思路,现在他站在那里,他的皮裤子并没有帮助我理解他(具体可查看马海祥博客《求职面试中最常见问题的回答技巧及注意事项》的相关介绍)。

现在我想告诉你—— Guy的方案(不消说,我并不认为Guy是第一个想出这招的人)在算法上并不能说就比我的好,而且在实际操作中,你很可能仍会使用我的方案,因为它更通用,无需跟麻烦的大型数字打交道。

但从“巧妙水平”上讲,Guy提供的是一种更、更、更有趣的方案。

我没有得到这份职位,也许是因为我拒绝了他们提供给我的一些讨厌的工作内容和其它一些东西,但这都无所谓了,我还有更大更好的目标呢!

接着,我应聘了become,在跟CTO的电话面试中,他给我布置了一道“编程作业”,这个作业有点荒唐——现在回想起来,大概用了我3天的时间去完成。

我得到了面试,得到了那份工作——但对于我来说,最大的收获是这道编程作业强迫我去钻研并有所获,我需要去开发一个网页爬虫,一个拼写检查/纠正器,还有一些其它的功能,不错的东西,然而,最终,我拒绝了这份工作。

终于,我来到了Google面试,我曾说过Google的面试过程跟外面宣传的很一致,冗长——严格,但诚实的说,相当的公平。

他们在各种面试过程中尽最大的努力去了解你、你的能力,并不是说他们在对你做科学研究,但我确信他们是努力这样做。

我在Google的第四场面试是一个女工程师,老实话,是一场很无聊的面试,在前面几场面试中我表现的很好,感觉到我的机会非常的大,我相信如果不做出什么荒唐事情来,十拿九稳我能得到这份工作。

她问了我一些关于排序或设计方面的非常简单的问题,我记不清了,但就在45分钟的面试快要结束时,她对我说:“我还有一个问题,假设你有一个一定长度的由字母组成的字符串,你还有另外一个,短些,你如何才能知道所有的在较短的字符串里的字母在长字符串里也有?”

哇塞!Guy附身了!

现在,我完全可以马上结束这场面试,我可以对她说“哈哈,几个星期前我就知道答案啦!”,这是事实。

但就是在几个星期前被问到这个问题时——我给出的也是正确的答案,这是我本来就知道答案的问题,看起来就好像是Guy为我的这次面试温习过功课一样。

而且,可恶的是人们通常是通过上网来搜集面试问题,而我,我可以毫不客气的说,对于这些问题,我不需要任何“作弊”,我自己知道这些答案!

现在你们可能认为——就在她问出了问题之后,在我准备开始说出在脑海里构思完成的最后的演讲之前——你们可能会想,我应该是,当然该,从情理上讲,镇定的回答出这个问题,并且获得赞赏。

可糟糕的是,事实并不是这样,打个比喻,就像是她问出来问题后,我在脑子里立即举起了手,并大叫着“我!嗨!嗨!我知道!让我来回答吧!”我的大脑试图夺走我对嘴巴的控制权(这事经常发生),幸亏我坚强的毅力让我镇定下来。

于是我开始回答,平静的,带着不可思议的沉着和优雅,带着一种故意表现出来的——带着一种,我认为,只有那种完全的渊博到对古今中外、不分巨细的知识都精通的人才能表现出来的自信。

我轻描淡写的说出来那种很幼稚的方案,就好象是这种方案毫无价值,我提到了给它们排序,就好像是在给早期的星际迷航中的一个场景中的人物穿上红T恤似的。

最后,平淡的,就好像是我决定了所有事情的好坏、算法上的效率,我说出了O(n+m)一次性方案。

我要告诉你,尽管我表明上的平静,这整个过程我却在做激烈的挣扎,内心里我在对自己尖着——“你个笨蛋,赶紧告诉她素数方案!”

当我完成了对一次性算法的解释后,她完全不出意外的认可的点了下头,并开始在笔记本上记录,这个问题她以前也许问过了一百次,我想大部分的人都能回答上来,她也许写的是“回答正确,无聊的面试,正确的回答了无聊的字符串问题,没有惊喜,无聊的家伙,但可以留下(具体可查看马海祥博客《程序员跟人事部HR在简历阅读和打分上有什么不同》的相关介绍)。”

我等了一会,我让这种焦灼的状态持续的尽可能的长,我可以发誓的说,如果再耽搁一分钟,我一定会憋出脑血栓、脱口说出关于素数的未解之谜。

我打破了沉默,说道:“你知道吗,还有另外一个,可能是更聪明的算法。”

她二目空空的抬头看了一眼,仅在瞬间闪现过一丝希望。

“假设我们有一定长度的字符串,我们可以给每个字母分配一个素数,从2开始,然后我们把大字串中的每个字母代表的素数相乘得出一个数,用小字串中的每个字母代表的素数去除它,如果除的过程中没有产生余数,则小字串是大字串的一个子集。”

在此时,我猜,她看起来就像是Guy当时把相同的话说给我听时我表现出来的样子,而我演讲时泰然自若的表情没了,眼睛瞪大,说话时稍微带出来一些唾沫星子。

一会儿后,她不得不说了,“可是…等一下,有可能…是的,可以这样!可是如何…如果…噢,噢,可行!简洁!”

我得意洋洋的吸了一口气,我在我的面试记录里写下了“她给了我一个‘简洁’的评语!”在她提出这个问题之前我就确信能得到这份工作,现在我更加确信了,还有一点我十分确信的是,我(更准确的说是Guy)给了她今天的好心情。

我在Google干了3年,生活的十分愉快,我在2008年辞职去到一个小公司里做CTO,之后又开办了一个自己的公司,大概是一年前,我偶然的在一个创业论坛会上遇到了Guy,他记不得我了,当我向他细述这段往事时,他对他那条皮裤子大笑不已。

最后,在这些陈年旧账里发现的一点技术瑕疵:字母有可能重复而字符串可能会很长,所以必须要有统计,用那个最幼稚的解决方案时,当在大字符串里找到一个字符后就把它删掉,当这样仍然是 O(n*m)次,在Hashtable里我们会有一个key->value的计数,Guy的方案在这种情况下仍然好用。

马海祥博客点评:

话说回来,如果这个故事里有什么教育意义的话,那就是永远不要冒失的第一个去应聘你梦想的公司,应先去应聘那些你不看好的职位,你除了能从这些面试中获得经验外,你指不定能遇到某个能为你的更重要的面试铺路的人呢,事实上,这个经验在你生活中的很多其它事情上也适应。

本文发布于马海祥博客文章,如想转载,请注明原文网址摘自于http://www.mahaixiang.cn/zcfz/1054.html,注明出处;否则,禁止转载;谢谢配合!

相关标签搜索: Google   面试  

上一篇:老板与员工之间不为人知的一些事
下一篇:如何工作生活才能成为一名“新富族”?

您可能还会对以下这些文章感兴趣!

  • 如何工作生活才能成为一名“新富族”?

    为什么我每周工作时间不到四小时,每个月赚到的钱却比过去一整年还要多?我要老实告诉你真相:这跟一群沉默的次文化人士有关,他们叫“新富族”,所谓的新富族,指的是抛弃延后享受的人生计划,在当下创造奢华的生活风格,并使用新富族的货币:时间与机动性,这是一门艺……【查看全文

    阅读:537关键词: 工作   新富族   日期:2015-02-11
  • 网络公关案例解析:如何选择你的对手?

    最近发生的两个事件对于广大在企业内做公关的朋友来讲,都是非常有教育意义的案例,错过了今天,以后可能再也赶不上这么好的案例比对了。头一件事儿,就是阿里公关团队对知名自媒体人葛甲开火了。第二件事是奇虎360与百度的ROBOT协议案,法院一审判决,认定奇虎360赔偿百度公……【查看全文

    阅读:530关键词: 网络公关   公关案例   案例解析   对手   日期:2014-08-09
  • 开会技巧的装逼指南

    如今已经要步入2014年最后一个月了,很多公司都开始忙着写年终结,开年终会议了,像每个人一样,我也非常希望自己能在会议中表现出机智敏捷,但这却是件很难的事情,尤其是当你开始神游,开始暗自考虑吃喝玩乐等琐碎事情的时候,如果发生这种情况,采用一些备用的技巧……【查看全文

    阅读:866关键词: 开会技巧   装逼指南   开会   日期:2014-11-28
  • 职场加班加点算是功劳?还是苦劳?

    最近,听到公司很多的同事都在讨论加班加点算是功劳?还是苦劳?这件事,我也想稍微对这件事情聊几句:很多人会以加班来当成我对工作很投入的一种表态,并期待能因此获得老板的肯定。但我得说,如果你是抱持这想法在加班,那恐怕就是对于职场丛林的生态体系有些误解……【查看全文

    阅读:778关键词: 职场   加班加点   功劳   苦劳   加班   日期:2014-06-02
  • 《琅琊榜》教会我们的职场法则与管理手段

    在《琅琊榜》这部剧里,梅长苏除了是江左盟宗主外,还有一重身份是靖王谋士,他好比是一个企业的管理者,为决策者出谋划策,无论遇到何种情况,都能处乱不惊,拥有大局观;在紧张的局面中进退有度,淡定从容;善于换位思考,几乎算无遗策,把所有的可能性和别人的心理都……【查看全文

    阅读:1111关键词: 琅琊榜   职场法则   日期:2016-03-30
  • 程序员跟人事部HR在简历阅读和打分上有什么不同?

    近日,看到一张在国外传播甚广的图片,是一个关于程序员面试时的简历,被人事部门和程序员本身评审的角度不同的图片。当然,这是一个从国外面试的视角制作的图片,不过,可以看出,其中还是有很多东西都是和国内是相同的。虽然说这个打分并不一定是完全标准的,但这其中……【查看全文

    阅读:852关键词: 程序员   人事部   简历   阅读简历   简历打分   日期:2014-06-14
  • 26岁营销总监写的一封辞职信

    某企业,曾花了半年时间,到另一家著名企业去挖来了一位营销总监。在不到三个月的时间里,这位年仅26岁的营销总监就把工作搞得有声有色颇有成绩。然而,就在大家都普遍看好这位年轻的营销总监时,他却毅然决然地辞职而去。这又是为什么呢? 在此,我将这位营销总监的辞……【查看全文

    阅读:791关键词: 营销总监   辞职信   营销信   总监辞职信   日期:2013-10-18
  • 职场心得:如何成为一名好员工?

    这是第一次,我不是因为和老板闹翻而离职;这是第一次,我带着晋升的喜悦而离职;这是第一次,我带着满满的收获而离职。我曾经认为,我永远不会成为一个好员工,因为我太挑剔,是个不喜欢听话的员工,而且讨厌一切想要改变我的人。但这五年,我改变了不少,我必须承认……【查看全文

    阅读:2093关键词: 职场心得   好员工   日期:2014-07-18
  • 给应届毕业生的一些面试建议

    无论是哪一种面试,主要就看三个方面:现在能力如何?未来潜力如何?人品如何?第一个因素是最重要的,因为后面两个因素有太多的人为判断因素,无法量化。对于现在能力如何是很难有大的改变,后面两个因素是可以短时间做一些准备的。面试的时候,记得带三样东西:一份简……【查看全文

    阅读:2542关键词: 应届毕业生   毕业生   面试建议   面试   日期:2014-05-21
  • 企业危机公关该如何应对柯震东吸毒事件

    据了解《小时代4》《我的情敌是超人》等影视作品的制作、投资和发行方涉及乐视影业、光线传媒和华策影视等公司,“如果有柯震东拍完了但还没发行的影片,可能拿不到上映许可证”一位业内人士表示。那么,作为曾被柯震东代言过的一些企业品牌,又该如何做好这次危机公关……【查看全文

    阅读:2151关键词: 企业公关   危机公关   柯震东   吸毒事件   日期:2014-08-28
↓ 点击查看更多 ↓

互联网更多>>

SEO优化 更多>>

如何利用极客精神优化网站的网络组件和代码 一个完整的企业网站首页应该具备什么因素?