f**********e
发帖数: 288 | 1 别认面金， 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够大就行。感觉这个面试比较惨。 |
p********n
发帖数: 165 | 2
。
基本算法不扎实， BFS 求最短路径要求uniform cost， 你得assume好。 另外BFS 停
下来如何判定要清楚。
two_heap in memory + hard disk 可以搞定
【在 f**********e 的大作中提到】
: 别认面金， 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把多余的扔掉。我又挣扎说了一些其他方法，都不大行。 最后他说你用
|
b**********5
发帖数: 7881 | 3 1) for each每个food 的点， bfs traverse到每个1， 记住bfs时候的level number
2）i think 2 heaps is ok. u can ask the interviewer if he can do an
estimate of the median. if u can do an estimate of the median, then u can
do bucket sort. To improve the accuracy, u can first sample the stream.
btw, i learned this from my failed interview at Twitter... those goddamn
chinese interviewers...
。
【在 f**********e 的大作中提到】
: 别认面金， 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把多余的扔掉。我又挣扎说了一些其他方法，都不大行。 最后他说你用
|
b**********5
发帖数: 7881 | 4 基本算法不扎实...
一看又是一个傻逼嘚瑟的猥琐男。。。 这题就是BFS， 是从每个2， bfs每个 1
你自己算法没有给， 还说人家不扎实。。 再看了看你的以前帖子， 就知道又是一个
嘚瑟猥琐男。。还是回去操你妈逼去把
【在 p********n 的大作中提到】
:
: 。
: 基本算法不扎实， BFS 求最短路径要求uniform cost， 你得assume好。 另外BFS 停
: 下来如何判定要清楚。
: two_heap in memory + hard disk 可以搞定
|
l******s
发帖数: 3045 | 5 第二问可以考虑分布式系统的2 heaps方案，将机器编号，每加一个新数字时需要将每
台机器上的heap比较然后考虑移位到另一台机器的heap，这样扩展下去可以搞无限内存
。这大概是他期待的答案吧。
。
【在 f**********e 的大作中提到】
: 别认面金， 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把多余的扔掉。我又挣扎说了一些其他方法，都不大行。 最后他说你用
|
l*******2
发帖数: 8 | 6 第二题想到一个解法，还是用2 heaps，但是heap里面不直接存number，存一个class，
class里面存number和这个number出现的次数。heap还是以number的值排序。
这样一来max heap和min heap里面总共的数出现的次数不一定相等，需要用两个number
来记一下。另外插入新数的时候比较麻烦，需要用一个hashmap来记一下number到class
的查找 |
f**********e
发帖数: 288 | |
a***y
发帖数: 852 | 8 这个是real Number？
number
class
【在 l*******2 的大作中提到】
: 第二题想到一个解法，还是用2 heaps，但是heap里面不直接存number，存一个class，
: class里面存number和这个number出现的次数。heap还是以number的值排序。
: 这样一来max heap和min heap里面总共的数出现的次数不一定相等，需要用两个number
: 来记一下。另外插入新数的时候比较麻烦，需要用一个hashmap来记一下number到class
: 的查找
|
b**********5
发帖数: 7881 | 9 他那个heap存class， 完全就是胡说霸道。。。
【在 a***y 的大作中提到】
: 这个是real Number？
:
: number
: class
|
l*******2
发帖数: 8 | 10 不好意思，我写完才想到是real number。。。
如果是integer的话，这个解法应该可行。real number的话应该精度也总是有限的，知
道精度的话也可以这样做，我觉得。
可能最重要是考察点在哪里，如果说面试官是想要看到distributed design的话，楼上
的解法都可以用
【在 a***y 的大作中提到】
: 这个是real Number？
:
: number
: class
|
r*******g
发帖数: 1335 | 11 你好，能详细说说这个吗？
【在 l******s 的大作中提到】
: 第二问可以考虑分布式系统的2 heaps方案，将机器编号，每加一个新数字时需要将每
: 台机器上的heap比较然后考虑移位到另一台机器的heap，这样扩展下去可以搞无限内存
: 。这大概是他期待的答案吧。
:
: 。
|
a***y
发帖数: 852 | 12 恩，integer的话可以做到constant space。思路很牛！
【在 l*******2 的大作中提到】
: 不好意思，我写完才想到是real number。。。
: 如果是integer的话，这个解法应该可行。real number的话应该精度也总是有限的，知
: 道精度的话也可以这样做，我觉得。
: 可能最重要是考察点在哪里，如果说面试官是想要看到distributed design的话，楼上
: 的解法都可以用
|
