2.17 GOOGLE ONSITE 跪经 求分

4, 给的tree node的class是啥样的？

xblwyc 发表于 2016-3-21 16:17
概率那题应该是用二分来解得，因为一般来讲N会给的极大，K应该是个合理的数字。
可以考虑把每一个禁止的数 ...

没看懂，能具体讲讲你的2分是在求什么吗？

把第三轮写了下

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. #define null INT_MAX
   
6. vector<int> nums = {1,2,3,null, null, 4,null,5,null,6,7,8};
   
7. 
   
8. int search(int start, int end, int target) {
   
9.     while(start < end) {
   
10.         int mid = start + (end - start) / 2;
    
11.         if(nums[mid] == null) {
    
12.             int i = search(start, mid-1, target);
    
13.             if(nums[i] == target) return i;
    
14.             i = search(mid+1, end, target);
    
15.             if(nums[i] == target) return i;
    
16.         }
    
17.         else {
    
18.             if(nums[mid] < target) start = mid + 1;
    
19.             else end = mid;
    
20.         }
    
21.     }
    
22.     return start;
    
23. }
    
24. 
    
25. int main(int argc, const char * argv[]) {
    
26.     // insert code here...
    
27.     cout << search(0, nums.size()-1, 5) << endl;
    
28.     return 0;
    
29. }
    

复制代码

第二轮第二题 似乎是reservoir sampling, 和利口 糁就把 比较像

1. 
   
2. int randomSampleNotInList(vector<int>& nums, int N){
   
3.     unordered_set<int> avoid(nums.begin(), nums.end());
   
4.     int ans = 0, cnt_valid = 0;
   
5.     for(int i = 1; i <= N; i++) {
   
6.         if(avoid.count(i)) continue;
   
7.         if(rand() % (++cnt_valid) == 0) ans = i;
   
8.     }
   
9.     return ans;
   
10. }
    
11. 
    
12. int main(int argc, const char * argv[]) {
    
13.     // insert code here...
    
14.     srand(time(NULL));
    
15.     vector<int> avoid = {1,2,6,7,9};
    
16.     int cnt[11] = {0};
    
17.     int rep = 100000;
    
18.     for(int i = 0; i < rep; i++) {
    
19.         cnt[randomSampleNotInList(avoid, 10)]++;
    
20.     }
    
21.     for(int i = 1; i <= 10; i++) {
    
22.         cout << "num:" << i << "   prob:" << (double)cnt[i] / rep << endl;
    
23.     }
    
24.     return 0;
    
25. }
    

复制代码

结果如下

1. num:1   prob:0
   
2. num:2   prob:0
   
3. num:3   prob:0.20183
   
4. num:4   prob:0.20133
   
5. num:5   prob:0.19925
   
6. num:6   prob:0
   
7. num:7   prob:0
   
8. num:8   prob:0.19941
   
9. num:9   prob:0
   
10. num:10   prob:0.19818
    
11. Program ended with exit code: 0

复制代码