google和twitter的onsite面经

原帖地址:mitbbs

google 店面

就是如何实现find, insert, delete, getRandom 都是O(1),然后扯了下google的
spanner那篇论文.

twitter 店面

第一轮.
1.如何判断一棵树是BST.
2.用2个栈实现队列。

第二轮
1.讨论hash table和如何解决collision, 各种解决策略的优缺点.

2. 关于图的简单BFS的一道题。

然后就是onsite了,这个我真的是是准备有问题,第一天面的google, 第二天面
twitter, 去google面试第一天坐了8个小时飞机,到了都晚上8点了,搞得第二天不在
状态了。

google onsite

第一轮,一个front end的人就问了一道题,写个程序,接收客户端的请求,如何保证
每秒钟只发送10个请求给服务器。这题他的意思我现在都不明白,他的意思是用平均速
度,看当前请求的时间和上个请求的时间相差多少,如果大于0.1秒就转发,否则就丢
弃。我觉得有问题啊,然后就郁闷了

。。

第二轮,一个印度哥们问如何用mutex和condition variable实现读写锁。这个好久没
碰了,答得也不好。

午饭,觉得吃的一般啊,比twitter的差些。

第三轮,扯点工作经验,然后考了从inorder, preorder数组构建二叉树,我这题写的
有bug, 当时想就废了.

第四轮,国人哥们,安慰了我一下。出了2道题,第一个是给个数组,打乱了,比如

索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置,这样的话数组有环,比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1, 求最长环的长度.

第二题,直线上有一个机器人从原点开始移动,每次可以向左移,也可以向右移,移动
n步,再回到原点的概率是多少, 可以写程序实现。

这两题我答得挺好的,才进入状态。。

第五轮。
就讨论如何一个程序大多数情况下运行的好好的,有时有问题,可能的原因.
感觉答的还可以。

twitter onsite
我觉得twitter onsite的题目我都写对了,面试官没有发现任何bug,本来希望还蛮大
的,但还是被拒了。但反馈说了2点。 1是思路代码写得太快了

,我挺无语的,我写之前都和面试官说了下我的idea啊, 等确认了再写的,题做多了也
不行啊。。2是系统设计能力欠缺。

第一轮, 第一题,一个数组,求连续(每个元素挨着的)的最长递增子序列的长度,如
果数组很长,如何优化.
第二题,就是那个爬梯子的题目了.

第二轮,就是设计一个手机上的下棋的游戏,涉及到客户端服务器端.

第三轮,Subsets problem. 然后扯项目经验.

中午吃饭,twitter的伙食真的很好,比google要强多了。

第四轮,扯扯项目经验,然后给2个sorted array, 求kth largest.

第五轮,n个排序链表,每个有m个元素,如何合并成一个。最开始说的是min heap的方
法,他要求的是O(1) space但是时间效率一样的,想出来了,然后证明时间开销,写了
代码。
mirror a binary tree.

第六轮 我觉得这个可能是个我杯具的原因之一吧,老印老板问的问题都很奇怪,比如
从cache, ram, disk读一个字节需要多少时间。 1个200G的文件在硬盘上是如何存储的
,我没在我简历上说这些啊.

反正2家都杯具还是有点郁闷的,后悔没先其它公司先练练,到google的时候刚开始写
白板都没状态. 没有很难的题目,基本题练好就行了。twitter是家非常好的公司,但
是会很忙,我2次电话面试都因为面试官救火而重新安排的.

但愿这些能给后来的兄弟一些帮助啦。