Facebook 黑经

11月17号面的

题目是给定W*H的Grid，给出算法在其中随机均匀地放M颗地雷。
水塘抽样，O(m)的算法BUG FREE写出来了。其实我面试前在地里还回答过这个问题的帖

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

回复思路是有点乱的，实际的做法跟这道题类似

相当于不断的getRandom, pop

bumbing 发表于 2016-12-6 10:20
我的onsite面过这道题，reservori sampling的复杂度和knuth shuffle是一样的，只是空间小而已
还有一种解 ...

我把代码放下面了，O(M)时间复杂度，我自己的测试没有发现问题...
不对还请指教...

1. from random import randint
   
2. def mines(W,H,M):
   
3.         grid = [[0 for _ in range(W)] for __ in range(H)]
   
4.         marked = {}
   
5. 
   
6.         mines = [None]*M
   
7.         for i in range(M):
   
8.                 probe = H*W-1-i
   
9.                 pos = randint(0,probe)
   
10.                 shouldBe = marked.get(pos,pos)
    
11. 
    
12.                 marked[pos], marked[probe] = marked.get(probe,probe) , shouldBe
    
13.                 mines[i] = shouldBe
    
14. 
    
15. 
    
16.         mines = [divmod(mine,W) for mine in mines]
    
17.         return mines
    

复制代码

  1 import random
  2 def test(m, n, k):
  3     if m == 0 or n == 0 or k > m*n : return
  4     arr = [[0] * n for _ in range(m)]
  5     while k > 0:
  6         print("here")
  7         a = random.randint(0, m-1)
  8         b = random.randint(0, n-1)
  9         if arr[a][b] == 1:
10             continue
11         else:
12             arr[a][b] = 1
13             k-=1

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，二来可以拖拖时间，三来万一中彩这就是他想要你指出的地方。

是不是题目做少了？面试确实主观因素很大。

honghunan 发表于 2016-12-6 04:48
是不是题目做少了？面试确实主观因素很大。

前面聊了15分钟，这题做了15分钟，然后我问他下一题什么，他说咱们再聊聊天吧，不用做题了

dokolo 发表于 2016-12-6 04:49
前面聊了15分钟，这题做了15分钟，然后我问他下一题什么，他说咱们再聊聊天吧，不用做题了

那我觉得他可能想挂你了。是不是前面简历的聊天，有一些问题你答得不够好？题目的话，要不是沟通的问题？还是你说ready，但是之后自己找了一些bug。其实题目做出来，一般就给你过的。不过你至少谷歌过了，还有很多人啥都没有呢，继续加油~

这么长时间hr才回复的吗。。。好坑

wangyuesong2 发表于 2016-12-6 05:08
这么长时间hr才回复的吗。。。好坑

是的
我一直以为FB是move fast，结果G家效率高太多

honghunan 发表于 2016-12-6 04:53
那我觉得他可能想挂你了。是不是前面简历的聊天，有一些问题你答得不够好？题目的话，要不是沟通的问题？ ...

我问了下FB的学姐，她说纯粹是我运气不好... :(

dokolo 发表于 2016-12-6 05:19
我问了下FB的学姐，她说纯粹是我运气不好... :(

看的我心里一凉，bug free都挂了...难道现在坑已经没了么？

darksteel 发表于 2016-12-6 05:21
看的我心里一凉，bug free都挂了...难道现在坑已经没了么？

纯粹看运气吧...
我同学早我1周面的，merge intervals，写出两个BUG最后也给了二面

求LZ大致代码参考下。。