Google SETI 店面面经

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

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

感受：感觉是简单题==以前project里好像写过类似的。

talk is cheap, show me the code:

1. #include <iostream>
   
2. 
   
3. class CCountry
   
4. {
   
5.     public:
   
6.     int total;
   
7.     vector<int>sum;
   
8.     vector<string>countries;   
   
9.     CCountry(vector<string>countries, vector<int>populations)
   
10.     {
    
11.         this->countries = countries;
    
12.         total = 0;
    
13.         sum.push_back(-1);
    
14.         for (int a:populations)
    
15.         {
    
16.             total+=a;
    
17.             sum.push_back(total);
    
18.         }
    
19.     }   
    
20.     string get()
    
21.     {
    
22.         int n = rand()%total;
    
23.         int idx = lower_bound(sum.begin(),sum.end(),n)-sum.begin();        
    
24.         return countries[idx-1];
    
25.     }
    
26. };
    
27. 
    
28. int main()
    
29. {
    
30.     vector<string>countries({"China","USA","Russia"});
    
31.     vector<int>populations({70,20,10});
    
32.     CCountry mCountry(countries,populations);
    
33.     for (int i=0; i<20; i++)
    
34.         cout<<mCountry.get()<<endl;
    
35. }

复制代码

我只想到了用bst log(n)的复杂度，楼主怎么看？最后祝楼主好运连连

张大虾不吃鸡 发表于 2018-9-12 05:43
我只想到了用bst log(n)的复杂度，楼主怎么看？最后祝楼主好运连连

我就先存到array，之后binary search. O(logN)。没想过用bst。复杂度一样

请问楼主SETI会比SWE面试简单一些吗？

求问楼主，为啥要binary search tree，就是一个random？？？求问，不知道哪里理解的不对

嬉皮笑脸 发表于 2018-10-4 18:05
求问楼主，为啥要binary search tree，就是一个random？？？求问，不知道哪里理解的不对

528. Random Pick with Weight