Facebook 黑经

dokolo 发表于 2016-12-6 11:25
我把代码放下面了，O(M)时间复杂度，我自己的测试没有发现问题...
不对还请指教...

这样做时间空间都是O(W*H) 吧？有一个O(W*H)的preprocessing

yangluphil 发表于 2016-12-6 11:58
这样做时间空间都是O(W*H) 吧？有一个O(W*H)的preprocessing

这个是不可避免的，因为面试官要求自己初始化，但是这个初始化之外的是O(M)

dokolo 发表于 2016-12-6 12:06
这个是不可避免的，因为面试官要求自己初始化，但是这个初始化之外的是O(M)

用线下算法的话不可避免初始化，但是线上算法比如reservoir sampling就不需要初始化所有元素，所以我觉得这个初始化的复杂度要算进去的。否则LC381的做法反而比reservoir sampling快了，其实跑下来两者复杂度一样，reservoir更快因为不需要hash。

理论上如果input space是未知的N个数，那不可能O(M)做出，因为你至少需要看一眼每个元素。但这题的input space是已知的(0,0) -> (W-1, H-1)，所以理论上有可能不需要把每个元素过一遍，就能直接生成M个随机元素，只是算法上能不能实现就不知道了。

比如如果要求在1-1,000,000的一维空间里随机生成10个数，我们不需要把1,000,000个数存到一个数据结构里再getRandom，在m/n很小的情况下用随机算法生成m个元素amortize下来是O(m)。但是如果m/n不可忽略的话就需要更好的算法。

补充内容 (2016-12-6 12:52):
所以我觉得可以问问面试官m与n的关系，use case是什么样的，一来是valid point，二来可以拖拖时间，三来万一中彩这就是他想要你指出的地方。

yangluphil 发表于 2016-12-6 12:50
用线下算法的话不可避免初始化，但是线上算法比如reservoir sampling就不需要初始化所有元素，所以我觉得 ...

我觉得本质上就是考察在(0,W*H-1)中随机取M个数。开空间的这个消耗是显然的。

dokolo 发表于 2016-12-6 13:19
我觉得本质上就是考察在(0,W*H-1)中随机取M个数。开空间的这个消耗是显然的。

开空间的消耗reservoir sampling就不需要。可能你的意思是时间复杂度O(W*H)是显然的，但是这题的input比reservoir sampling要友善。

1. W*H个数中随机取M个数，那么时间上O(W*H)作为lower bound是显然的。
2. 这题的input不是W*H个任意数，而是排好序的(0, W*H-1)，我不知道广泛适用的O(m)算法是什么，但是O(W*H)是lower bound并不“显然”。极端例子1B个数里任取其一，lower bound是1B，但是(0, 1B-1)里任取其一只需要一个function call。所以我觉得时间空间都O(m)的算法may exist until proven otherwise.

yangluphil 发表于 2016-12-6 13:55
开空间的消耗reservoir sampling就不需要。可能你的意思是时间复杂度O(W*H)是显然的，但是这题的input比r ...

可能我没有说清楚，这题的input是W,H,M
output是一个W*H的二维数组，而且数组是要初始化的，我不清楚C++里的memset是什么时间复杂度，但是Python的话这个lower boundry是肯定的。
时间上O(M)的算法我在上面PO了，你可以看下？我自己测试没问题的

天竺面试官？可能看完你简历，还没有面你就已经想挂你了，和你水平如何完全无关。
面试的随机性还是很大的。

dokolo 发表于 2016-12-6 11:25
我把代码放下面了，O(M)时间复杂度，我自己的测试没有发现问题...
不对还请指教...

http://www.geeksforgeeks.org/reservoir-sampling/   请参考这里，我不是太懂python，看的很吃力
reservoir在leetcode也有原题，我记得讨论区还有个对于大数据版本抽样，复杂度一样但常数项更快的解法