2.17 GOOGLE ONSITE 跪经 求分

EE转专业狗刷了N久的题准备google, 还是跪在Onsite了，来贡献一下面经
提早一天飞到san jose，给安排的房间那个床so fancy，左右两边独立调软硬，然并卵，几乎失眠的一夜第二天来到CL1300, 也就是google infrastructure部门, 没啥warm up，直接上题，题也都很裸

第一轮：
1. 实现一个class

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

应该先写个O(N)的理一下思路。这一轮一定被给了低分。


第四轮：
多叉树序列化反序列化，写的磕磕绊绊。。这道刷题刷漏了，结果偏偏考到，真是验证墨菲定律




祝小伙伴们好运 拿下google offer多多 求分求分~~~      

adiggo 发表于 2016-3-25 14:58
第三题 array是空 需要跳过去， 如果mid 的value的空， 那么该往左移动index， 直到找到第一个不是空的， ...

感觉这道题，就是讨论，最后复杂度还是O(n)

http://stackoverflow.com/questions/6979276/select-random-value-not-in-array

第二轮第二题 似乎是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

复制代码

不是在白板上写吗？

stony0408 发表于 2016-2-27 11:36
不是在白板上写吗？

是白板写~

概率其实挺简单 如果我理解正确。 就是随机从N里选一个数直到不在那个list里。

lz有送hc吗

那个binary search题目 是求从左向右还是从右向左数第一个比target小的index 啊?
从左向右数
int getPosition(int a[], int n, int target) {
   int left = 0, right = n - 1, middle, result = -1;

   while (left <= right) {
       middle = left + (right - left) / 2;
      
       if (a[middle] >= target)
            right = middle - 1;
      else {
            result = middle;
            right = middle - 1;
      }
   }

   return result;
}

从 右向左数
int getPosition(int a[], int n, int target) {
   int left = 0, right = n - 1, middle, result = -1;

   while (left <= right) {
       middle = left + (right - left) / 2;
      
       if (a[middle] >= target)
            right = middle - 1;
      else {
            result = middle;
            left = middle + 1;
      }
   }

   return result;
}

duduhaha 发表于 2016-2-27 14:57
那个binary search题目 是求从左向右还是从右向左数第一个比target小的index 啊?
从左向右数
int getPosi ...

从小到大排序的 所以是从左边第一个咯 然后array里空的index记得要跳过去

kinggarden2001 发表于 2016-2-27 12:22
概率其实挺简单 如果我理解正确。 就是随机从N里选一个数直到不在那个list里。

是的 后来就想到了 当时不知怎么脑子就跟浆糊一样

请问楼主面完以后多就知道HC的消息啊，祝楼主找工顺利！！！

求教概率那题还有二分查找包含空的那题有什么好办法嘛？