问两道google onsite的题, 请大牛指点啊。。

原帖地址:mitbbs

别认面金, copy 过来的。。有没有巧解, 请大牛们指点。。。

1.
[ 0 2 1
1 0 1
0 是障碍物,2是食物,1是可走的路径。 要求着到可以走到所有食物一次最短的点。
我用bfs做出来,最后的时候他说我有个case没考虑到,就是没有最佳路径的时候怎么
办。 其他的都没问题。

2. given a infinite stream of real number, 随时找median. 我说用 2 heaps, 但
是他说infinite的数字要infinite的空间怎么办。然后我就说2heap应该也可以,就是
保证一定size把多余的扔掉。我又挣扎说了一些其他方法,都不大行。 最后他说你用
2heap做做吧,我大概做了出来,然后他就给我看了个case说这个方法什么时候会失败
。 他最后说其实实际应用中2heap可以用,只要n够大就行。感觉这个面试比较惨。