Google onsite 面筋失败经验

原帖地址:一亩三分地

Onsite interview
1.[ 0 2 11 0 10 是障碍物,2是食物,1是可走的路径。 要求着到可以走到所有食物一次最短的点。 我用bfs做出来,最后的时候他说我有个case没考虑到,就是没有最佳路径的时候怎么办。 其他的都没问题。
2. given a infinite stream of real number, 随时找median. 我说用 2 heaps, 但是他说infinite的数字要infinite的空间怎么办。然后我就说2heap应该也可以,就是保证一定size把多余的扔掉。我又挣扎说了一些其他方法,都不大行。 最后他说你用2heap做做吧,我大概做了出来,然后他就给我看了个case说这个方法什么时候会失败。 他最后说其实实际应用中2heap可以用,只要n够大就行。感觉这个面试比较惨。
3. given a probability = [.5 .1 .2 .2], label = [A B C D], write a data structure that generates the label based on the prob. 我说先找cumulative probability[.5, .6, .8 1], 然后弄个0~1之间的random数字比较过去找它的位置就好。他就说有没有更快的方法。 其实他想叫我用binary search,但是我一直以为是不是有什么O(1)的解法,浪费了一些时间后才发现原来他想要binary search, 最后弄出来了。 4. first is summary missing range problem. [0 1 2 45 99] output “3-44,46-98”。 做了出来但是做法没有最优,我说可以改,他就说我相信你可以改就下一题了。second is given a dict of words [aba, cbc], find the letter to letter probability. b->a 50%, b->c 50%. 这个做的还可以,有一个小bug5. hamming distance between a and b, a, b < 2^64. 这题很快就做了出来。就是把a^b>>i 164 次。 然后他就说要想办法speed up,说给我64G的ram。我想了很久最后说可以搞个2^8的字典,然后把a^b分8段比就好。 他就说为什么用8, 然后就问我2^8的字典要用多少空间. 我没记空间大小的那些知识,所以不会做…几经提示后结论是可以用2^32的字典要4G空间,这样比两次就好。他最后又问说如果你用这个方法,但是ram只有2g,那会发生什么情况。 我就说那会有error吧。他就说什么error。我说不出来。他就说“you clearly have never used win 95 swap space”. 然后差不多就结束了。我觉的最后这个哥么应该给我差评了。

总结失败经验:
1. 应该多考虑corner case, 总是写完被人问有什么case会有问题
2. 尽量一次算法最优,像什么能用binary search的时候就不要用O(N)的
3. 一些cs基础的东西要懂,什么swap space的。转行不容易啊。。