Google Pittsburgh Onsite

作者 QIFAN 日期 2017-01-30
Google Pittsburgh Onsite

地里面经看会遇到很多同天面的小伙伴,但是今天只看见了一个女生。本来以为自己迟到了,结果发现是 recruiter 约早了,于是小坐了一会拿了瓶水,前台小妹特别的给了我一个 name tag (虽然最后被收走了),就看见 host 气喘吁吁的跑过来了。

首先是带我们在 office 里逛了一圈,带我们看了后院养的三只鸡(叫 twitter ,Facebook 和另一个没听清)还有蜂箱,真是一个自给自足啊。

然后时间差不多了,就领到了面试房,第一位小哥已经在等我了。

第一轮
中国小哥。
LeetCode 原题 LeetCode 394 - Decode String 。这是全程最后悔的了,小哥最后一路提示。亏我两天前刚做过,早上出门前还特意瞄了一眼。明明我自己用一个栈做出来了,面试的时候用了两个栈还搞不领情。

第二轮
白人小叔?
给定一串单词即对应的值,要求自定数据结构,并设计算法使得每次可以根据单词值的分布 randomly 返回一个单词。Follow up 是怎么 test 。
举例说:
输入:[apple: 2, banana: 3, orange: 1]
分析:
total = 2 + 3 + 1 = 6
freq(apple) = 2/6
freq(banana) = 3/6
freq(orange) = 1/6
如果持续多次的 call ,那最后得到的单词的分布就是 apple : banana : orange = 2 : 3 : 1 。

我一开始还想着用 map ,最后一排脑瓜用数组代表范围,然后 binary search 做出来了。后来问考点在哪儿,小叔说一个是生成 random 怎么去除 0 值,另一个就是 binary search 。

最后也问了几个问题。这一轮感觉还行。

第三轮
一个嬉皮士风格的白人小叔。

先是坐下来唠了一会嗑,问我这学期选了什么课,有没有什么学习计划。然后开始做题。小叔先是介绍了数独,我咯噔一下,这题不会。然后他画风一转,你来实现一个帮助我完成数独的方法吧,就是给你某一列的 sum 和这一列的长度,返回这一类所有可行的结果。(数独规则是某一列不能有重复数字,且数字只能是 1~9 )。
考虑了几个 Corner case 以后开始下手。我用 hashmap + 递归 做的,然后被小叔指出一个 map 的问题,于是做了改进,后来也提出直接用 array 也行。
后面有一小撮时间,看小叔想走了,就随便问了个问题。

这个小叔看我代码总有一种 interesting 的感觉,本来觉得还行,但是看他后面想走又很不踏实,看不出长胡子下面的真正表情。

午饭
巴西帅小哥。这一轮纯粹就是休息吃吃交流。为了保持热情,我只能不停的和他讲话(其实我已经很饿了),还是知道了很多有趣的事情。比如厨房有烹饪课,每周不一样;Googler 转岗很容易;他已经结婚了;这里的晋升系统特别复杂特别公平,不用担心和 manager 处不好影响 career ,就像今天的面试也是通过系统安排,Hiring Committee 通过面试官的 feedback (每个面试者有一份 package),以及代码(我每一轮的代码面试官都会抄到纸上)等等。

第四轮
白人小叔。发现面试官都是瘦小型的。

给定一串 tuple ,形式为(请求时间,完成时间),系统在每次请求是会将任务放入队列中,完成时将任务移除。给定一个时间 t ,要求返回该时间时队列中有多少个请求。

我这题也挺昏的,一直没有搞清楚他的意图。我一开始想用 Priority Queue ,然后他说这样每次都要initialize 要能够处理很多次连续 call 。然后我问他有没有时间和空间的限制,他说他想要只要一次 initialize ,然后以后每次 call 都只要 O(1) 。我想这怎么可能。然后试了 sort + binary search ,他说这样需要两次 sort ,能不能再快一点。总之最后也没有写代码,一直在改和想。我后面又问他这题实际上是怎么做的,他说,嘛,我就是想给你了解一下时间和空间的 tradeoff ,看你有没有不一样的想法,其实我们也很难达到两个都最优的。= =

然后后面带我去出口也聊了一会加州和匹茨堡哪个更好,我就说,tradeoff 嘛。最后前台小妹说我第一次有 T 恤发,那小叔一脸怨念说我当初怎么就没有哈哈哈。



总结一下:第一轮做过的题目没有把握好,嵌套这些的状态存取和转换很容易混,第二轮前面思路卡顿了十分钟吧,后面代码写的还比较顺,第三轮写代码的时候数据结构换的太多,可能在这里让面试官有点疙瘩吧,食堂的菜还行,最后一轮有点蒙圈。感觉运气还不错,没有做到地里那种魔鬼级别的。