Facebook电面

zhuyinghua1203 发表于 2017-7-14 08:24
Time complexity 是不是应该永远是O(M)

生成雷的过程和生成随机数列的算法类似，每一次生成一个雷的时间 ...

我不太清楚，我写的就是用hashset记录之前雷的位置，如果hashset里面有这个数再生成一个新的。我说完complexity之后，面试官也没有让优化，估计写成这样就是可以了，然后就直接是followup了

你这样dart throwing 的算法complexity 是会变高

如果格子是10*20的，雷的位置就是0, 1..., 199
把这个数列随机化，每O(1)可以得到一个数字，重复M次就是M个雷的位置

zhuyinghua1203 发表于 2017-7-14 08:39
你这样dart throwing 的算法complexity 是会变高

如果格子是10*20的，雷的位置就是0, 1..., 199

可是生成0，1...199的过程Complexity是不是还是O(H*W)呢？

试试用类似洗扑克牌的方法？

我写完了第一问的代码，然后面试官问完complexity，听面试官说话的感觉还算挺满意的，所以感觉用HashSet记录之前出现的雷就足够了

第一次生成一个0到199的随机数，那个位置的数字就是第一个雷的位置，然后把这个数和倒数第一个数字交换

第二次生成一个0到198的随机数，那个位置的数字就是第二个雷的位置，然后把这个数和倒数第二个数字交换

重复M次

同意水塘抽样。
楼主投的是什么岗？能说一下吗？这边new grad都等这投/推呢~~谢谢啦

dense graph的话应该用resovir samping, 复杂度是H*W。
sparse的话估计有O(M)的做法，因为H*W>>M，所以直接生成M个0-H*W之间的随机数，应该就不会重复，当然可以hashset存一下，如果重复的话再生成一次。

zhuyinghua1203 发表于 2017-7-14 08:47
第一次生成一个0到199的随机数，那个位置的数字就是第一个雷的位置，然后把这个数和倒数第一个数字交换

...

请问这样的复杂度是o（m）吗

张欣 发表于 2017-9-26 11:06
请问这样的复杂度是o（m）吗

是
字数补丁