Facebook 黑经

楼主有G家很强啦。关于题目，按LC381做，不断getRandom，pop的话确实可以，但如果input does not fit in memory的情况就不行了？这题followup是不是可以用reservoir sampling的思路做，n ＝ w*h个坐标里随机抽取大小为m的子集，只需要space O(m)，http://www.geeksforgeeks.org/reservoir-sampling/

我感觉这个问题可以规约成二维版的Random  shuffle array吧

yangluphil 发表于 2016-12-6 07:56
楼主有G家很强啦。关于题目，按LC381做，不断getRandom，pop的话确实可以，但如果input does not fit in me ...

我在主楼里写的水塘抽样... 其实我是想说reservori sampling，大概是水库或者水池抽样？

WhatsFLAG 发表于 2016-12-6 09:06
我感觉这个问题可以规约成二维版的Random  shuffle array吧

这个不是真正的二维，可以直接用一维的操作。
问题在于shuffle array是需要打乱所有元素，复杂度是O(W*H)

我的onsite面过这道题，reservori sampling的复杂度和knuth shuffle是一样的，只是空间小而已
还有一种解法，可以用augmented tree解，复杂度是nlogn

楼主已经很厉害了，狗狗的实习也挺棒的啦！（求微信，我并不能发站内信）

tkw1110 发表于 2016-12-6 10:37
楼主已经很厉害了，狗狗的实习也挺棒的啦！（求微信，我并不能发站内信）

我微信ID发你站内信了

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
    

复制代码

在Linkedin上给面试官发了封InMail，最后一搏吧...