发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标  题: 不刷题进Google的经历
发信站: BBS 未名空间站 (Thu Jun 11 18:34:25 2015, 美东)

没有马甲，又不想被认出，所以跑到这里发帖，希望有人能转到Jobhunting板上。

在Jobhunting板上混了很久了，看到大家的共识就是：不管你工作多久，想去FLG必须
刷题。（例外也有人提到，但是似乎不是Google research的职位，就是功成名就的大
牛，都不是普通码工的情况）我自己和周围认识人的经历似乎也验证了这一点。不过最
近我终于在没有刷任何题的情况下拿到了G家的offer，看起来这种“共识”也并不是
100%正确的。由于Jobhunting板上这种经历似乎不多，所以详细写一下，供大家分享，
也给像我一样不愿刷题的人鼓励一下。这个帖子主要侧重分享面试经历，面经记不太清
了，不是太多，放在最后。

我自己四年前也曾经认真刷过0.9遍Leetcode题目，去过G家on site一次。当时自我感
觉答得还不错，但是最终还是被拒。不过从那以后，每年都会被G家recruiter骚扰，说
上次你表现很好，已经很接近offer了，要不要再试一次啊之类的。（不知道是不是他
们对每个人都这么说？）我对自己背景相关的专业只是还是比较有信心的，但是对
Leetcode类型的算法题是真心不喜欢，所以不到万不得已实在不想再刷题了（一方面年
纪大了，另一方面家里小孩也忙）。所以每次G家recruiter来骚扰，我的第一个问题就
是“能不能不走BT的general hire，少问算法题，多问实际有用 的东西？”但是第一
次、第二次都得到否定的回答，然后就没有然后了。到了去年（第三年），那个
recruiter说，我们现在改革了，不是general hire了。于是我就高兴地答应再试一次
。结果转到Mountain View的recruiter后（虽然我人就在湾区，但是似乎每次主动联系
我的recruiter都是Texas的，如果确定要开始面试了，就会被转到Mountain View的
recruiter继续）被告知面试的问题还是一样的算法题，只不过面试官可以从跟你背景
相关的组里面找。听到还是一样的面试问题后，我就直接放弃了。

今年已经是第四年了，不出所料，recruiter再次如期来骚扰。这次recruiter再次信誓
旦旦地说，一定不会是general hire了，一定会主要考察背景和工作经验。不过有了去
年的经验后，我对此也是将信将疑。不同的是，这次recruiter说先帮我在内部找对我
背景感兴趣的组，先跟他们电话聊聊，双方多了解一下。我对电话聊聊一向都不拒绝，
就把简历发给他让他去找组。说起来这个recruiter确实很尽力，找的组确实都跟我的
背景兴趣很match的。先找了一个组，先后跟组里的三个人电话聊过（有manager也有比
较senior的engineer）。不是电面那种问问题的，就是介绍一下他们组做什么（其实不
用他们介绍我也基本都已经知道了），然后问问我的背景经历啥的。感觉三个人应该都
还聊得不错，而且这种做法也确实跟我经历过的其他 公司的“正常招聘流程”差不多
，所以感觉这次说不定真的是他们改革了。但是最后recruiter说，尽管他们很喜欢你
，不过他们在你之前已经跟另一个candidate进行到offer阶段了，所以不能跟你继续了
。不知道是真实情况还是婉拒的客套话。

不过这个recruiter并不气馁，接下来很快的时间又找来两个组，说都对我感兴趣。然
后一周内安排了跟两个组的头分别电话。两个电话同样是聊天性质的，同样都感觉还聊
得不错。然后recruiter就告诉我希望进行on site。由于有两个组，所以他说会从两个
组里面各找几个人，最后一共5个面试官一次面完。但是，再次被转到Mountain View的
recruiter安排具体面试时间时，再次被告知面试问题仍然是算法题，白板写code，一
切似乎跟四年前没有两样。因为我已经四年完全没有刷过任何题了，所以当时就想放弃
了。不过这次我当时正在跟另一家（非FLG）公司进行面试，而且很快就可能会拿到
offer，所以想不管如何还是去G家试一把吧，大不了跟四年前一样被拒也没啥，所以就
催着recruiter尽快定了面试时间。

面试当天果然如他所言，五个面试官没有一个人提到过有关我背景和现在工作的一个字
，完全是上来就问问题。问题除了Leetcode类型的题目就是所谓的设计题。Leetcode的
题目大家都知道不刷题的情况直接上后果如何了，设计题也都是我以前几乎完全没涉及
过的多线程、网络相关的东西，所以最后可以说答得一塌糊涂。回去跟LD讲了经过，用
LD的原话说就是“如果这样还能拿到offer简直没有天理了”。

回来后给两个recruiter写信抱怨，他们回信说很抱歉，但是我们想找什么都能干的人
，所以问的问题还是以基础为主啥啥的（可是德州那个recruiter之前跟我保证一定会
考察专业背景的啊，还说问那种算法题是ridiculous的）。不过反正已经这样了，也没
啥好说的了。一周后加州的recruiter说已经拿到所有面试官的feedback，期间还要了
我在G家工作的朋友的内部意见，说会送到hiring committee那里去。

再过一周还没有动静，这时我已经拿到另一家公司的offer，被催着做决定了。所以赶
快联系G家问结果。结果recruiter打电话过来说今天才刚把所有材料送给HC，HC明天上
午11点会开会讨论，明天下午再给我打电话通知结果。我说你不是上周就说送HC了吗？
怎么今天才送？他说因为他在等hiring manager的意见。那个hiring manager去度假了
，一直等到今天才拿到他的supporting opinion。他说他觉得如果没有hiring manager
的意见就送到HC那里的话可能机会不大（好吧，我知道我on site答得很烂）。看起来
这个加州的recruiter确实也是在尽力帮忙。

第二天，说好下午2点打电话，结果一直到快5点才终于等到电话。虽然已经做好被拒的
准备，但是结果竟然被告知HC通过了！下一步就是要了三个external reference的联系
方式，问了我现在收入情况和pending offer的情况，说下周一送交compensation 
committee讨论。第二周，本来说好周四SVP如果review通过后就会有最终结果，结果被
告知SVP当天没有进行每周一次的review，一直等到周五下午快下班时，终于等到了
offer。虽然整个package比网上大家报的差不少，但是毕竟大家都是有多个FLG级别的
offer互相compete来的，我这种只有一个普通offer的拿到这种package也算不错了（而
且后来negotiate之后还涨了一些）。毕竟我这次没有刷题，能拿到offer已经是预料之
外的事了，而且这个offer还是比我现在高了不少的，所以也就愉快地接受了。

我这次的经历说明，只要背景match，就算是非Google research的普通码工职位，也是
有可能不刷题拿到offer的。希望能给象我一样不愿刷题的人多一个参考的样本。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
以下是记得的几个题目

* Multi task design
用户可以法请求要求某一个task在某一时间开始执行。这样的请求可能很多。设计一个
系统处理这样的请求。问如果处理系统是local的（和发请求的在一起）或者是remote
的有哪些设计上的不同。
这个没怎么实际做过，只能随便侃侃，简单写了几行伪代码。

* Quad-tree intersection
一个quad－tree表示一个2D的黑白图，每个节点都是平行于坐标轴的矩形，节点的
value 0和1表示黑和白。如果一个节点全黑或全白就是叶子，否则就继续剖分成四份。
要求写一个函数求两个quad－tree的交。
这个比较简单，写了一个递归的程序，不确定是否有bug。

* Base64 encoding
先解释了一下何谓Base64 encoding（http://en.wikipedia.org/wiki/Base64），然后要求写一个函数将一个字符串按Base64编码。
用位操作实现，写了简单的代码，不确定是否是他想要的答案。

* Swizzle sort
输入一个数组，要求输出满足：a[0]<=a[1]>=a[2]<=a[3]>=…
O(n)，一边扫描即可。发现不符合条件的只要跟前面一个数对调就可以，说明了一下原
因，没时间写代码了。

* Prefix string
给定一个字典，输入一个字符串，输出字典中所有以该字符串开头的单词。
只知道可以用Trie来做，但是具体怎么做记不清了，毕竟工作中没用过。对方讲解了一
下Trie的基本概念，然后假设Trie已经建好了，让写代码找出所有单词。代码匆匆写完
，估计很难bug free，最多大体逻辑正确就不错了。

* Linked list operation
先简单问了一下double linked list进行insert，remove, rank（判断某一节点是第几
个节点）操作的时间复杂度。答分别是O(1), O(1)和O(n)。
然后说如果允许纪录每个节点的位置（也就是rank值），时间复杂度分别是多少？答分
别是O(n), O(n), O(1)。
然后问能否有什么方法平衡一下，让三者复杂度差不多？根据提示构造一个二叉树，同
时每个节点纪录自己左子树中节点的数目，从而使三者的复杂度都为O(log n)。
最后要求写出rank的代码。基本都写出来了，但是期间无数提示。

* DNS design
描述一下如何设计DNS系统，以及如果某一网址的IP更该了，如何更新各DNS。
没接触过这方面的东西，所以只能随便瞎聊。

* Maze design
假设你是大学里的算法TA，老师出一个走迷宫的题目，要求你
1. 设计一个函数头，让学生补充内容；
2. 设计一个maze generator用来检查学生提交的程序。
1写了一个很简单的，不知道还有什么值得补充的。2实在不知道他想要啥，沟通半天也
没弄明白，只能随便敷衍两句。

* 3 sum变种
输入一个数组和一个数x，要求输出满足a+b+c<=x的triplet (a, b, c)的个数。
先写了一个naive的三重循环O(n^3)的，要求改进。写了一个先排序再两重循环O(n^
2log n)的。要求将用到的binary search写出code来。然后问如果查找的数(x-a-b)有
重复或者不在数组种怎么办，根据两种情况修改code，不确定最后是否完全正确。
然后问能否进一步改进，一直弄到时间结束也没弄出来。最后被告知可以不用binary 
search达到O(n^2)，也没明白怎么做。
--