Facebook 黑经

lz 后来面试官有回你inMail吗

BillSky 发表于 2017-2-22 04:08
lz 后来面试官有回你inMail吗

没有，我现在是FB的坚定黑...

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

我对python 不是特别熟，看代码感觉像是shuffle card的做法。先从[0,hw-1] 选一个数存起来，再从[0,hw-2] 选一个存起来......最后从[0,hw-m]中选个数存起来，这样的话是hw个位置中选m个的permutation，概率是1/(hw) * 1/(hw-1) * 1/(hw-2) *...* 1/(hw-m) 。并不是题目要求的hw个位置选m个combination。

guzi 发表于 2017-4-10 09:22
我对python 不是特别熟，看代码感觉像是shuffle card的做法。先从[0,hw-1] 选一个数存起来，再从[0,hw-2] ...

本质其实就是水塘抽样记录下标。
你用这种方法算概率很头疼的，直接证明每个坐标被选到的概率是m/hw就可以了

dokolo 发表于 2017-4-11 01:10
本质其实就是水塘抽样记录下标。
你用这种方法算概率很头疼的，直接证明每个坐标被选到的概率是m/hw就可 ...

那个O(m)的算法，怎么证明被选到的cell是也是m/hw的概率被选中的呢？

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

您onsite的时候用了 O(m)解法了吗？ m是雷的个数。我看另外面经上要求优化成时间 O(m).  reservoir sampling, knuth shuffle都是  O(hw)

dokolo 发表于 2017-4-11 01:10
本质其实就是水塘抽样记录下标。
你用这种方法算概率很头疼的，直接证明每个坐标被选到的概率是m/hw就可 ...

怎么证明啊？ 能否再证明一下？

能不能这样。有个while m>0. 然后长宽随机。如果已经是雷就continue。放了雷了就m-=1

  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 11:25
我把代码放下面了，O(M)时间复杂度，我自己的测试没有发现问题...
不对还请指教...

大哥，我今天看了一天你这个算法。意思是不是一共选m次，每一次选出一个数来。然后把这个数从0-n-1里面删除掉？ 用数组，删除操作，就是把最后一个数跟选出来的那个数交换位置？这样保证后面选的数不会跟前面的重复，而且概率是对的？