google电面最新挂经

jiajiechen0319 发表于 2016-10-26 05:21
第一题可以生成随机数 [0, 0.5) 生成1，[0.5, 0.8)生成2，[0.8,1]生成3。累计分布。

我擦 有道理 我撒比了……

1. design 一个generator
这个可以用所给的double[] p来构造一个[0, 1]区间以及内部格点：0, p[0], p[0]+p[1], ... , 1 (=sum of all p[i]), 这样就可以用[0, 1]均匀分布的性质了：[0, 1]均匀分布变量落在任意子区间的概率就是子区间的长度。C++中用“(double)rand() / (double)RAND_MAX” 就可以随机得到一个[0, 1]均匀分布变量X，然后用binary search找出X落在哪个子区间即可。这样时间复杂度O(n*log(p.size())) (假设生成随机变量是O(1)的)。空间复杂度O(n+p.size()).
大家还有什么做法？

1. vector<int> getRandomArray(const unsigned int n, const vector<double>& prob) {
   
2.   vector<int> res;
   
3.   // construct partial sum array: psum[i] = prob[0]+...+prob[i-1]
   
4.   vector<double> psum(1, 0.0); for (auto p : prob) psum.push_back(psum.back() + p);
   
5. 
   
6.   for (unsigned int i = 0; i < n; ++i) {
   
7.     double x = (double)rand() / (double)RAND_MAX; // random value in [0,1]
   
8.     // find iterator pointing to the first value in psum greater than x
   
9.     auto pos = upper_bound(psum.begin(), psum.end(), x); // binary search for sorted random access array
   
10.     res.push_back(pos - psum.begin()); // set index of psum to result
    
11.   }
    
12.   return res;
    
13. }

复制代码

补充内容 (2016-10-26 05:33):
这里假设生成数组中的每个元素是int in [1, M] (M=p.size()). 但其实只要是M个任意的object都可以，不影响实现。

dokolo 发表于 2016-10-26 05:22
第一题...
如果是要frequency满足要求，生成满足频率的数组然后洗牌
如果是要possibility满足要求，a = ...

第二题我也觉得我没问全…小哥态度不是很友好…你们就当参考吧…

第一题可不可以先加和概率数组：[0.5, 0.8, 1.0], 然后自己建一个等长数组装element比如[1,2,3]。 random生成0-1.0的一个double，再去概率数组里找这个double落在哪个range，比如<0.5，就去第二个数组里找index=0的， 如果数组元素很多，可以binary search。

lxxxxxxx 发表于 2016-10-26 05:23
第二题感觉意思拓扑排序但是看你给的例子又有重复元素，有重复元素感觉还是有点影响吧....

第一题就例如 ...

理论上来说如果概率比值p[i]/p[j]是分子分母都很大的有理数的话，那么这样做的时间空间复杂度就无法控制了。我觉得这个题还得用连续分布随机变量而不是离散型的。

http://www.1point3acres.com/bbs/ ... read&tid=200588
概率题有点儿像这个面经里的国家人口那道

2.构建出原数组这道题感觉定义不是很清楚。
例如：[1, 2], [2, 3], 那么结果可能是 [1,2,3], [1,2,2,3], [2,3,1,2].
如果这样定义可以是一个合理的题：给定一个vector<int> a的一些consecutive subarrays vector<vector<int>> subs，求原来array a的最小长度。（注意：即使求最小长度原来array也可能不唯一，但至少这个题就well defined了）.
... 但如果题真的这么出我还没想好怎么做呢，呵呵

dokolo 发表于 2016-10-26 05:22
第一题...
如果是要frequency满足要求，生成满足频率的数组然后洗牌
如果是要possibility满足要求，a = ...

应该是要求original array size最小吧

rowena000 发表于 2016-10-26 07:01
应该是要求original array size最小吧

我也在想这个题应该问可以恢复的原array的最小长度是多少。想了一个这个题好像就很难啊。也无法从sub-array的个数DP, 因为前n-1个sub-arrays可以构造出的最短array未必就是所有n个arrays构造出的最短array的某个sub-array.
没有什么想法。