Loading...
墨滴

凝神长老

2022/01/02  阅读:48  主题:自定义主题1

Google 面试技巧

Google 面试技巧

—— 那可是 Google 啊,Google 哪有那么好进……

—— Google 嘛,感觉是个人都拿到 Offer 了呀……

别骂了别骂了

OA 通过之后就是要准备 VO 了,也就是所谓的面试。北美大厂的面试风格各不相同,所以下面我总结的面试技巧不见得能够应付所有的公司,但是以 Google 为代表的这种面试技巧,应付绝大多数公司的面试是毫无压力的。除了 Meta。

Meta 的话就只有一个方法:买 LeetCode 会员,一遍又一遍地刷他家公司 Tag 的题。

另外有些中小厂可能会要在真实 Coding 环境中写代码,最后要运行的,那种就需要特别对待了。大多数大厂给的是一个带高亮但是无代码补全的文档平台,就相当于在白板上 Coding 了,那么就可以适用以下 Google 面试技巧。

大厂面试的差异和特点:Meta 原题多,题库庞大,注重结果,不注重优化过程,题目难度较高,上来就要求最优解;Microsoft 难度相对较低,考基础算法、数据结构的快速实现;Amazon 原题多、题库更新慢,图论问题较多;Google 注重解题过程和思路。

面试的核心是:展示自己的解题能力,让面试官觉得自己有一个可以放心合作的同事,而不是以考生和考官的姿态完成面试。由此,Communication 就非常重要。Google 甚至专门有一栏 Communication 的打分,重要程度不亚于算法和数据结构。Communication 优秀会疯狂加分。

Technical 的 Interview 一般是 40 - 45 分钟,一旦开始,那就是要片刻不停地说,不要沉默太久。有些公司的面试官会有硬性指标,例如连续 15 秒或者 20 秒没有说话,就直接挂人了,但是大多数公司没有这么离谱的时间,主要看面试官的主观感受——你思考和沉默的时间是不是超过了预期值。

Google 的面试会频繁更换面经的题,也就是今天在帖子上看到的面经题,可能明天是能遇到,但是可能后天就换题了。除非运气真的很好能遇到原题,否则这就非常考验基本素养了,只有掌握了问题的本质才能顺利通过 Google 的面试。

面试开始的时候,面试官基本会有一个自我介绍,然后告诉你接下来的 45 分钟会进行一道 Coding(或者 2 道 Coding,那么这种情况下就要把下面的流程时间对应压缩和调整),接着可能会要求面试者进行简短的自我介绍,也可能没有。如果面试官要求了自我介绍,那可以稍微多说一点,不然的话就自己要求加一段自我介绍会比较合适,比如 “Shall I have a quick self introduction? I am XXX from XXX university and am looking for XXX.”

这一步一般会在 1-2 分钟之内结束。

接下来就是做题了,一般会给出题面和 1-2 个样例,就像这个样子(LeetCode 496):

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Google 的题很少出现 Hard,基本以 Easy 和 Medium 为主。所以如何分析题目并展示解题思路就成了重中之重,而不仅仅是要写出一个能够运行的代码。

对于刷了很多题的人来说,这道题并不会太难,很多细节可能在脑海中已经过了一遍了,已经觉得自己可以写代码了。但这是面试,面试是要展示自己的解题过程和思路,所以那些一闪而过的内容都需要说出来。

第一步首先是抽象题目,或者说,形式化题目。

这道题比较直接,已经以数组的形式展示了,那就基本是复述题面,提炼关键词。

而有些图论的题目会这样说:有一个机器人……在森林/田野里面……需要找到……最终……。

遇到这种情况,一定要把故事抽象为:给定一个 的矩阵,其中 表示……、……表示……,要求给定……,从……开始寻找一个……直到……,最后输出……。

换言之,这里我们要做的事情就是约定输入输出。类似的表达可以是:

  • We are asked to have a function, taking two parameters and return a positive integer.
  • Given a string, the task asks me to have a solution to find the maximum number of substrings that satisfies …
  • I will define a function to solve this problem. The input is an array with a positive integer indicating the array index, and the output is the sum of …

看题的时间不能太久,所以为了避免冷场(以及某些公司的所谓 15 秒指标),可以在读到关键词的时候直接复述:

  • Oh, so we are having an array of strings now, and they are guaranteed to be capitalized.

  • And then we have a new definition, the next greater element.

  • This sentence promises the answer must exist because …

**约定完输入输出,就是最重要的 Clarification Questions 的环节。**这部分可以这样开头:I have read and understood the problem, but I have some clarification questions and let’s discuss about them.

这一部分在我看来是整个面试的灵魂,如果这一部分表现糟糕,基本上整个面试就无了。这个一般会很难,因为初读题目可能并没有太多的 Clarification 可以问。那就不妨从数据范围入手,因为数据范围往往还能暗示最后的算法应该在什么时间复杂度的范围内,例如对于一个长度为 50万 的数组,可能暴力解法 就不太可能了。

上面的这个例题中,原题还有一些 Constraints(LeetCode 496),但是作为面试题,这些 Constraint 未必会在一开始就展示出来,因为面试官需要考察的就是发现问题分析问题的能力。如果从数据范围开始提问,我们首先可以问的就是:Anything I can know about the range of these values? Can you tell me the size of the array? What is the maximum possible number in this array?

但是其实你可以发现,数据范围在这道题目中并不是那么地关键。这数组的最大的长度是 1000 有用吗?是 10000 又如何呢?他会影响我使用的算法嘛?好像未必。所以这种情况下,这些次要的 Clarification 可以不那么着急地问。除非实在问不出来,那就先问这些问题撑时间,给自己更多时间思考。(也许会有用,例如本题 LeetCode 496 的数组长度是 1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 104,这是在暗示可以先从暴力解法开始,但是如果已经有了明确思路,知道自己不会用暴力解法,那么简单提一句就可以,也不一定要专门把这当作很重要的事情来说)

对于这道题来说,有些 Clarification 已经在题目中暗示了,那么就可以复述,或者更好的方法是用自己的话 rephrase 一下,然后问面试官自己这样的理解是不是对的,是不是和你的理解一样:

  • Since the problem says nums1 is a subset of nums2, we can know that all the integers of nums1 also appear in nums2, so if we iterate the elements in nums1, it is promised that we can find at least one elements in nums2 to be equal to that value.
  • And by saying the “distinct”, does it mean all integers in nums1 and nums2 are unique? Is this understanding correct?

除此以外还有能问的问题是如果答案不存在怎么办,一定保证答案存在嘛?

  • What should I do if there is no valid answer? Do you want me to throw and exception? Or simply return a special value such as zero/negative one or negative infinity?
  • Oh in this problem, this sentence tells us if we can’t find the next greater element, we should return a special value -1.

接着面试官就会说形如 Oh to save our time you can assume the answers exist. / Our inputs are promised to have one and only one valid answer. / It’s up to you, you can simply throw an exception if you find the answer doesn’t exist. 的回答,那就知道后续代码中需要小心哪些地方了。

LeetCode 496 这道题原题给的 Constraints 是这样的:

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • All integers in nums1 and nums2 are unique.
  • All the integers of nums1 also appear in nums2.

另外是但凡做了假设的地方,都要重申这是自己做的 assumption。

比如,题目问,给定一个字符串,输出这个字符串中大写字母的个数。

这个问题简单吗?简单。能直接开始写代码了吗?用一个变量 int count,然后遍历字符串,如果在 'A'-'Z' 之间就 count++。可以吗?

谁告诉你最终结果一定是在 int 范围内?为什么不用 long long?万一 long long 也不够呢?确实,对于一般的编程题来说,在数据范围上恶心人是很无聊的表现,但解题人必须严谨,这里我们做了一个假设,那就是答案就是 int 范围就够了,它只是展示解题思路的一部分,至于它 int 能不能存下,我不关心,这不重要。所以我们可以说:To keep it simple, I assume the final output is in the range of C integers, saying .

同样,如果是说给定一个 array of numbers,例如 [1, 4, 4, 7],要求 double 每一个数字,变成 [2, 8, 8, 14]。样例给了整数,但题目只说了 of numbers,所以如果我们约定的输入是 int[] 和输出 int[],那这也是一个 assumption。assumption 都需要明确地提出来:To save time, I assume that the numbers in the array are integers, but my solution keeps the same if they are floating numbers. In this way, my function takes an array of integers and returns an array of integers with the same length.

在看完了给的样例之后,如果能发现 Edge Cases,这时候也都一起提出来就好:There is one more edge case that I want to share with you: If the array is empty, then we will … / Or if the number is 0, the output may be influenced by XXX so we will need to have a special condition here to protect …

无论如何到这一步应该 10 分钟是要的,所以 10 分钟之前我认为是不应该动手写代码的,动手了,那 Communication 可能就已经有问题了。

在 10 分钟左右的时候,可以开始准备写代码了。

先 explicitly 说出自己的算法和数据结构,如果可以的话,也加上时间和空间复杂度。

  • With these clarifications, I will use BFS to solve this problem.
  • This is a typical topological sorting problem, so I will use priority queue and XXX to solve it.
  • Now I am going to use Union-Find to calculate the XXX.

别急着动手。接下来可以先跑一个样例,并再次重申自己的算法步骤。

  • Here I want to use the example one to show my ideas. First I will iterate the array, [1, 3, 2], and for each element, at this point, it is 1, I doubled it, so it becomes 2, and …
  • After we find the 2 in the stack we can pop it, and the stack is now [B, C] …
  • 6 is less than 9 so we will stop the loop and return 6 as our final answer.

用一个真实的案例来跑一遍代码,一来可以让面试官彻底听懂自己的思路,二来可以给自己理清楚代码的结构并为接下来的 Coding 节省时间,三来是可以发现一些特殊的处理和需要注意的 Edge Cases,四来可以撑满时间避免冷场。

时间差不多来到 15 分钟,可以开始写代码了:Based on the ideas above, the solution takes in time complexity and in space complexity. Shall I start coding now?

上面这道题目(LeetCode 496),比较合适的解法是单调栈,或者单调队列,Whatever。那就需要明确提出 Monotonic Stack 这个单词,并用一个真实的样例来说一下每一步。可以把每一步 栈 的变化情况一行一行以注释的形式写在面试文档中。

如果实在看不出算法和数据结构,那就只能硬着头皮从 Brute Force 开始了:Obviously, we can iterate the first array and for each element, we use an inner loop to find the location of that element in the second array. Because nums1 is guaranteed to be the subset of nums2 and all integers in num1 and nums2 are unique, we are sure we can find it with in the loop. Once we find it, we go over the rest numbers in the second array after that location, and to check if there is the next greater element. However, this is not an optimal solution, do you want me to code now or keep optimizing it?

这时面试官或者会回答:Just start here and if we have time, we can optimize it. 或者会给一些提示让你优化:Yeah this is a bad solution, so why it is slow? Do you do some duplicated operations? What about XXX when XXX.

这时候你大概就知道了面试官的心理预期:他是只要先有 Working Solution,还是需要一个 Better Solution。由此可以调整自己的心态和后半场面试的技巧。

写的时候依旧不能冷场,每写几行关键的代码都要说话:Here I am using a loop to XXX. Now, we need to check the X with Y and if X is less than Y, we need to XXX using this if condition. 如果代码中出现了 Clarification 中的重要部分,或者处理了 Edge Case,记得再强调一嘴。

但是也不用细致到这个程度,这太离谱了:I use a flag to indicate XXX so it is false by default. If the XXX, I set it to true and break the loop. If the flag is true, I need to XXX.

代码不会太长,所以应该在 10 - 15 分钟之内写完,于是时间来到了 25 - 30 分钟。写完代码,立刻主动提出花 1 - 2 分钟用刚才那个样例再跑一遍代码,也可以用一个新的样例:因为 XXX 所以这里我们在循环里面,因为这个 Edge Case 所以 XXX 是 0 了所以 break 了……

一场 45 分钟的面试,于是还剩下 15 - 20 分钟。

按常规,下面是一个 Follow Up。一般面试官会准备 1 - 2 个难度不同,甚至方向不同的 Follow Up,根据面试者的表现来给出不同的题目。

Follow Up 往往是加减一个条件,或者改一个条件,或者要求优化一类的,所以套路是一样的,理解题目的意思,然后指出之前的 Clarification 仍然成立的部分,并指出在修改或者增删条件之后,Clarification 不再成立的部分。例如:

  • Without the constraint of XXX, we can’t …
  • Since the elements is not unique now …
  • The array is XXX so we can do it in a simpler way, but we need to care about two more edge cases.

一样的过程,简述算法和数据结构,说理由,说思路,用一个案例来跑一下步骤,确保面试官听懂,然后把代码写出来。

比如这道题的 Follow Up 可以是 LeetCode 503,数组变成 a circular integer array。环形数组的常见处理方法是循环取余,或者直接收尾衔接,把 [1, 2, 1] 变成 [1, 2, 1, 1, 2, 1] 来确保一次遍历能涵盖所有的前驱后继关系。

也可能就是简单的优化:Can you solve it in time complexity?

或者说:What will happen if the integers are not unique? You can provide any (或者 all) possible solutions. 或者 You should return the first element showing in the second array 诸如此类。

一样对待就好,只不过因为不是全新的题目,所以花的时间更少,十多分钟。

最后剩下 3 - 5 分钟,是 Q&A 环节,是向面试官提问。

自由发挥,看个人习惯。

但是一般有两个雷区是绝对不要去问:① 不要问面试表现:你觉得我还有哪里可以提高?你觉得我表现怎么样?② 不要问题目:这道题的正确解法是什么?如何确保 复杂度?

因为不见得面了就能工作,可能很多人在未来的几年中都不会再和这家公司有交集,所以这是一个很好的窗口去了解公司,公司也乐意用这个机会向外宣传,这是 Q&A 的本意。但是记住面试官开心了他的 Feedback 才能写得很好,所以尽量问一下能够有来有回,能够把天聊下去的话题。

“这个岗位需要有哪些知识储备?它平时是主要做什么工作?”

类似这种问题能不能问?想问就问呗。但是很难聊下去,容易冷场:这些知识储备你会的话还好,能扯两句,万一不会怎么办?Oh I will start learning now?也不需要这么暴露自己的能力吧。听完它平时做什么工作,Oh that’s interesting?万一人家面试官这两天刚好比较 Struggle,Suffering 怎么办…… Sounds boring to me 就更不行了,那你来干嘛的。

容易的问题是能够夸,能够你来我往打乒乓球:最后 3 分钟了,大家愉快度过呗。你开心,帮我写两句好话,实在不行,好聚好散,你继续上班,我找别家面试。因此就把它当作反向 BQ 来问就行了。BQ 是问我问题,凸显我的厉害,反向 BQ 那就是要让面试官回答出面试官的厉害。

所以我个人会常问的问题有:你做过最自豪的项目是什么。不论他回答什么,Google Map 也好,GCP 也好,YouTube 也好,我都可以说,Oh that‘s really an excellent product. I can’t live without it. 我每天吃完饭都要刷 YouTube、我每天出门没有 Google Map 我活不下去了。我最喜欢 Google Map 的离线导航,我前两天去国家公园没有信号我也可以使用它。噢,苹果的这个算法太厉害了,它使得我拍照的时候 XXXX。Amazon 的 AWS 使用体验很棒,快速故障恢复使我在某一次 XXXX。

你觉得工作最难的是什么。不论他回答什么,Oh 我深有同感,有一次我 XXX,就和你说的一样,但是最后 XXX 所以你们还是把它做出来了,感谢你们的努力,这个产品很棒。

所以,每家公司面试前,不管喜不喜欢,还是要准备一下他家的信息。

另外根据面试官的年龄,以及可能他自己在这家公司工作的年份,我可能还会问:Work From Home 的体验有什么不一样的吗?如果可以回到园区上班,你最想做的事情是什么?公司会有活动嘛?不管他回答什么,他喜欢 Hiking 我就喜欢 Hiking,他喜欢 Escape Room 我就喜欢 Escape。我不管我以前喜欢什么,反正就三分钟,你喜欢的就是我喜欢的。

愉快结束面试。

按这个技巧,最差不应该低于 Weak Hire,甚至可以冲击 Strong Hire。

我见过刷了几百题,VO 说都做出来的,结果挂了的,也见过没刷多少题面完觉得要无了的,最后拿到了 Offer。究其原因还是在于:面试不在于你要把结果做的多漂亮,而是要展示你思考和解决问题的思路,是如何一步一步分析的,是如何展示自己的能力的。如果没能展示出来,那么即使写出了代码,也会被挂,而且挂的一点也不怨。

另一个非常重要的点是,一边写,一边说,两边的速度都会被拖慢。这东西需要练,平时刷题就要刻意卡着时间去说着写。以及面试前找人 Mock 非常重要。除非你像我一样厉害敢去裸面。

小结一下:

第 1 - 2 分钟完成自我介绍、热身。

第 3 - 10 分钟完成读题,完成 Clarification。

第 10 - 15 分钟交代解题思路,Dry-Run 一个样例,并分析复杂度。

第 15 - 25/30 分钟完成 Coding,并跑样例。

第 25/30 - 40 分钟完成 Follow Up。

第 40 - 45 分钟完成 Q&A。

重点依旧是:展示自己的解题能力,有完整的分析过程(哪怕有点错误),分析逻辑紧密,环环相扣(哪怕不是最优解),是一个可以信赖的合作者,是可以一起学习进步的人。而不是给人一种“这肯定是背题的,这分析逻辑都不能自洽,会出现断层”。

凝神长老

2022/01/02  阅读:48  主题:自定义主题1

作者介绍

凝神长老