Facebook Intern 面经

生成一个(w*h)大小的数组A， 初始化A[i] = i
for i=0 to m-1, swap(A[i], A[i + rand()%(w*h-i)]);


补充内容 (2016-11-16 10:27):
想想直接抽样就好，
for i=0 to m-1, A[i] = i+rand()%(w*h-i);

补充内容 (2016-11-16 10:36):
貌似有问题

同关注这个问题。。。

关注followup。。。。。。

个人觉得要做到每个点被选为零的概率是m/(h*2)的话，复杂度不能做到O(m),可能面试官就是钓鱼执法。。。故意这么问的

补充内容 (2016-11-23 12:01):
打错字，m/(h*w)

yun5260561 发表于 2016-11-14 05:31
感觉o(m)是能做的,就跟一维的一样

我也认为不可能做到O（m）啊。。。 上面的那个算法出来的概率应该不对的。 因为你到第二个雷，它的可以替换的range就少了右下角那个点，应该不太对的吧。。。

还有一个问题，就是如何保证产生的你第一个for loop里面每次产生的随机数不一样呢？ 这个是无法做到的。如果有重复的话（即你的cur变量一样），在第二个loop里面不就出现两个雷被放到了同一个位子？这样应该不太对吧。。。

求问楼主是网投简历吗？还是找了内推？

yun5260561 发表于 2016-11-14 05:31
感觉o(m)是能做的,就跟一维的一样

感谢分享！但是我写了一下，发现你的code生成出来的matrix的概率不对。我写了reservoir sampling的code，O(hw)的，出来的概率就是对的。 我把code贴出来你看看哈：

1. /**************************************************************
   
2. * Problem: Given a matrix h*w, and randomly generate m mines
   
3. *************************************************************/
   
4. 
   
5. #include <vector>
   
6. #include <iostream>
   
7. 
   
8. using namespace std;
   
9. class Solution{
   
10. public:
    
11.   // idea: reservoir sampling
    
12.   vector<vector<int> > generate(int h, int w, int m){
    
13.     vector<vector<int> > matrix(h, vector<int>(w, 0));
    
14.     // reservoir sampling:
    
15.     for(int i = 0; i < h*w; ++i){
    
16.       if(i < m)  matrix[i/w][i%w] = i;
    
17.       else{
    
18.         int j = rand()%(i+1);
    
19.         if(j < m)  matrix[j/w][j%w] = i;
    
20.       }
    
21.     }
    
22. 
    
23.     // put the mines
    
24.     for(int i = 0; i < m; ++i){
    
25.       int val = matrix[i/w][i%w];
    
26.       matrix[i/w][i%w] = 0;
    
27.       matrix[val/w][val%w] = 1;
    
28.     }
    
29.     return matrix;
    
30.   }
    
31.   vector<vector<int> > generateOther(int h, int w, int m){
    
32.     vector<vector<int> > matrix(h, vector<int>(w, 0));
    
33.    
    
34.     // other's approach:
    
35.     int tail = h*w;
    
36.     for(int i = 0; i < m; ++i){
    
37.       tail--;
    
38.       matrix[tail/w][tail%w] = rand()%(tail+1);
    
39.     }
    
40. 
    
41.     for(int i = 0; i < m; ++i){
    
42.       int cur = matrix[tail/w][tail%w];
    
43.       matrix[cur/w][cur%w] = 1;
    
44.       matrix[tail/w][tail%w] = 0;
    
45.       tail++;
    
46.     }
    
47.   
    
48.     return matrix;
    
49.   }
    
50. };
    
51. 
    
52. void printMatrix(vector<vector<int> > v){
    
53.   int m = v.size(), n = v[0].size();
    
54.   cout<<"***************************"<<endl;
    
55.   for(int i = 0; i < m; ++i){
    
56.     for(int j = 0; j < n; ++j)
    
57.       cout<<v[i][j]<<" ";
    
58.     cout<<endl;
    
59.   }
    
60.   cout<<"***************************"<<endl;
    
61.   cout<<endl;
    
62. }
    
63. 
    
64. int main(int argc, char ** argv){
    
65.   Solution s;
    
66.   vector<vector<int> > target({{1,0,1},{0,0,0},{0,1,0}});
    
67.   double cnt_r = 0, cnt_o;
    
68.   for(int i = 0; i < 1000000; i++){
    
69.     if(s.generateOther(3,3,3) == target)  cnt_o++;
    
70.     if(s.generate(3,3,3) == target) cnt_r++;
    
71.   }
    
72.   cout<<"The probablity obtained under reservoir: "<<cnt_r/1000000.0<<endl;
    
73.   cout<<"The probablity of another approach: "<<cnt_o/1000000.0<<endl;
    
74.   cout<<"The ideal probablity is "<<6.0/(9*8*7)<<endl;
    
75.   return 0;
    
76. }
    
77. 
    
78. /****************************************************
    
79. * Output:
    
80. * The probablity obtained under reservoir: 0.012127
    
81. * The probablity of another approach: 0.003875
    
82. * The idea probablity is 0.0119048
    
83. ****************************************************/
    

复制代码

不知道这样写对不对。

1. 
   
2. import random
   
3. def solution(h, w, m):
   
4.    
   
5.     res = []
   
6.     cnt = 0
   
7.     for i in range(h):
   
8.         for j in range(w):
   
9.             if cnt < m:
   
10.                 res.append((i, j))
    
11.             else:
    
12.                 if random.randint(1, cnt) <= m:
    
13.                     res[random.randint(0, m-1)] = (i, j)
    
14.             cnt += 1
    
15.     return res
    

复制代码

补充内容 (2016-12-6 15:12):
只返回放雷的横纵坐标

这题为啥不能用传统的reservoir sampling来做， 难道不是在h*w 里面选random subset of K? 为啥不能用这个方法啊？http://www.geeksforgeeks.org/reservoir-sampling/
赞同楼上写的，除了这两行

1. if random.randint(1, cnt) <= m:
   
2.                     res[random.randint(0, m-1)] = (i, j)

复制代码

这里我感觉应该用同一个数字而不是random两遍

jolesiawu 发表于 2016-12-13 03:21
这题为啥不能用传统的reservoir sampling来做， 难道不是在h*w 里面选random subset of K? 为啥不能用这个 ...

赞同，的确需要保留之前的随机数