• 欢迎来到Greenss官方中文网站www.jldzled.com

【长文】Google口试官分步解析本身泄露前的口试题,超多干货和建议

Google greenss 713次浏览 0个评论

​​

本文翻译自Google工程师/口试官Alex Golec的文章:Google
Interview Questions Deconstructed: The
Knight’s Dialer;翻译:试验楼扫地姨妈;原文链接

作为一名Google的工程师和口试官,今天是我第二次发文分享科技公司口试建议了。这里先声明:本文仅代表我小我私家的察看、定见和建议。请勿看成来自Google或Alphabet的官方建议或声明。

下面这个问题,是我口试生活生计中第一个问题;也是第一个被泄露出来,以及第一个被禁失的问题。我喜欢这个问题,由于它有以下长处:

  • 问题很容易表述清晰,也容易懂得。
  • 这个问题有多个解。每个解都须要不同水平的算法和数据构造常识。并且,还须要一点点遥见。
  • 每个解都可以简朴几行代码实现,很是合适有时光限定的口试。

假如你是学生,或者求职者,我但愿你经由过程本文可以或许相识到,口试问题一般会是怎么样的。假如你也是口试官,我很高兴愿意分享本身在口试中的作风和设法主意,怎样更好地转达信息、征求定见。

留意,我将使用Python写代码;我喜欢Python由于它易学,简练,并且有海量的尺度库。我碰到的良多口试者也很喜欢,绝管我们奉行“不限制语言”的政策,我口试90%的人都用Python。并且,我用的Python 3由于,托付,这都2018年了。

问题
把你的手机拨号页想象成一个棋盘。棋子走只能走“L”外形,横着两步,竖着一步;或者竖着两步,横着一步。

此刻,假设你拨号只能像棋子一样走“L”外形。每走完一个“L”形拨一次号,肇始地位也算拨号一次。问题:从某点开端,在N步内,你可以拨到几多不同的数字?

会商

每次口试,我基础城市分成两个部门:起首我们找出算法方案,然后让口试者在代码中实现。我说“我们找出算法方案”,由于这个进程我不是缄默沉静的专制者。在如许高压下,设计并实现一种算法,45分钟时光并不算充分。

我凡是会让口试者主导会商,让他们往发生设法主意,我嘛,就在阁下,时时时地泄露一点点“天机”。口试者们才能越强,我须要泄露的“天机”就越少;可是今朝为止,我还没碰到一点都不须要我提醒的口试者。

有一点我想夸大一下,主要的很:作为口试官,我的职责可不是坐那望着各人掉败搞砸。我想要给各人正面的反馈,给各人机遇往铺现各人最善于的点。给他们提醒,就像是在说:呐,这一步路我给你展上,但这只是为了让你铺示给我,你在后面的路上能走的更遥。

当听完口试官的问题,你应当做什么?切记不要立即就往写代码,而是在黑板上试着一步一步往分化问题。分化问题可以或许匡助你寻找到纪律,特例等等,逐渐在年夜脑中形成解决方案。好比,你此刻从数字6开端走,能走2步,会有如下组合:

    6–1–8
    6–1–6
    6–7–2
    6–7–6
    6–0–4
    6–0–6

一共有6种组合。你可以试着用铅笔在纸上画,相信我,有时辰下手往解决问题会产生意想不到的事,比你盯着在脑壳里想更神奇。
怎么样?你脑海里有方案了吗?

第0阶:达到下一步

使用这个问题口试,最让我惊讶的是,太多人都卡在了计较从某个特定点跳出时,一共有几多种可能,即邻Neighbors。我的建议是:当你不断定时,先写个占位符,然后哀求口试官可否晚点实现这一部门。

这个问题的庞杂性并不在Neighbors的计较;我在意的是你怎样计较出总数。所有破费在计较Neighbors上的时光实在都是铺张。

我会接收“让我们假设有一个函数能给出我Neighbors”。当然,我也可能会让你后面有时光再往实现这一步,你只须要如许写,然后继承。

并且,假如一个问题的庞杂性不在这里,你也可以问我能不克不及先略过,一般我都是答应的。我却是不介怀口试者不知道问题的庞杂性在哪里,尤其刚开端他们还没有周全相识问题的时辰。

至于Neighbors函数,由于数字永遥不变,你可以直接写一个Map然后返归切合的值。

第1阶:递回

智慧的你可能留意到了,这个问题可以经由过程列举出所有切合前提的数字,然后计较。这里可以使用递回发生这些值:

这个方式可以,并且是在口试中最广泛的方式。可是请留意,我们发生了这么大都字却并没有使用他们,我们计较完他们的个数后,就再也不往碰了。以是我建议各人碰到这种情形,绝量往想一下望有没有更好的方案。

第2阶:数不数数

怎么在不发生这些数字的情形下计较出个数?可以做到,但须要一点点机智。留意从特定点跳出N次可以或许拨到的数字个数,即是从它所有邻近的点跳出N-1次可以或许拨到的数字个数的总和。我们可以表达为如许的递回关系:

假如你如许想,就会很直观了,跳一次时:6有3个neighbors(1,7和0),当跳0次时每个数字自己算一次,是以每次你只能拨到3个数字。

怎么会发生如许机智的设法主意?实在,假如你学了递回,而且在黑板上好好研讨,这一点就会变得显而易见。如许你就能继承往解决这个问题,现实上就这一点就有多种实现方式,下面这个就是口试中最常见的:

便是如许,联合这个函数计较出neighbors 就可以了。这时辰,你就可以捏捏肩膀苏息下了,由于到这里,你已经刷失良多人了。

接下来这个问题我常常问:这个方案的算法理论速率怎样?在这个实现中,每次挪用count_sequences()城市递回地挪用count_sequences()至少2次,由于每个数字至少有2个neighbors。如许会导致runtime成指数增长。

对付跳1次到20次如许的次数还可以,可是到更年夜的数字,我们就要碰鼻。500次可能就须要整个宇宙的暖量来完成运算。

第3阶:影象

那么,我们能做的更好么?使用上面的方式,并不克不及。我喜欢这个问题,也是由于他能一层一层带出各人的聪明,找到更高效的方式。为了找到更好的方式,让我们望下这个函数是怎么挪用的,以count_sequences(6, 4)为例。留意这里用C作为函数名简化。

你可能留意到了,C(6, 2)运行了3次,每次都是同样的运算并返归同样的值。这里最枢纽的点在于这些反复的运算,每次你使用过他们的值之后,就没有必要再次计较。

怎么解决这个问题?影象。我们那些雷同的函数挪用和成果,而不是让他们反复。如许,在后面我们就可以直接给出之前的成果。实现方式如下:

第4阶:动态设计

假如你再望望前面的递回关系,就会发明递回影象的方案也有一点局限性:

留意跳N次的成果仅仅取决于跳N-1次后挪用的成果。同时,缓存中包括着每个次数的所有成果。我之以是说这是个小局限,由于确凿不会造成真的问题,当跳的次数增永劫,缓存也只是线性增长。可是,究竟,这仍是不敷高效。

怎么办?让我们再来望一望方案和代码。留意,代码中是从最年夜的次数开端,然后直接递回到最小的次数:

假如你把整个的函数挪用图想象成某种虚拟的树,你就会发明我们在执行深度优先策略。这并没有什么问题,可是它没有应用到浅依靠这个属性。

怎样实现广度优先策略?这里便是一种实现方式:

这个版本比前面递回版幸亏哪里?实在并没有好良多,可是这个不是递回的,是以纵然处置超年夜数据也很难瓦解。其次,它使用的是常量内存;最后,它仍然是线性增长,即便处置200000次跳也只用不到20秒。

评估

到这里,基础就算完了。设计并实现一个线性时的、常量内存的方案,在口试中长短常好的成果。在我的口试中,假如有口试者写出动态编程设计,我凡是会给他一个极高的评价:excellent!

当评估算法和数据构造的时辰,我常常会说:口试者对问题熟悉清楚,而且斟酌到各方面的可能,当指出不足时他也能迅速改良并进步;终极,实现了一个不错的解决方案。

当评估代码的时辰,我最抱负的说法是:口试者迅速并切确地把设法主意转化为了代码;代码构造严谨,容易浏览。所有特别情形都有归纳综合,而且当真检讨测试了代码,确保了没有Bug。

总结

我知道,这个口试问题望上往好像有点吓人,尤其整个诠释下来很是繁琐。但本文的目标和口试中完整纷歧样。最后,一点口试相干的技能,以及一些好的习性,分享给各人:

  • 必定要手动来,从最小的问题开端解决。
  • 当你的步伐在做无用的运算时,必定要留意往优化。削减不必要的运算可以或许让你的解决方案越发简练,说不定能是以发明更高效的方案。
  • 相识你的递回函数。在现实出产中,递回经常很容易出问题,但它仍然长短常强盛的算法设计和策略。递回方案也老是有优化和进步的余地。
  • 要经常往寻找影象的机遇。假如你的函数是目标性的,而且会多次挪用雷同的值,那么就试着往存储起来。

本日推举:

12周,从0基本到Python工程师

Linux年夜神养玉成攻略

6周成为数据剖析与发掘工程师
J2SE焦点开发实战

Python 图片转字符画 

Go语言编程进门

​​​​


版权所有www.jldzled.com丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明【长文】Google口试官分步解析本身泄露前的口试题,超多干货和建议
喜欢 (1)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址