houzz店面

周一刚跪完，至今没收到HR电话，估计的挂了。
问了两题，第一题是检查一个gra

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

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

ocess可以返回同样几率的0和1.

第一题要看是不是bipartite， 查所有点还不够，要查每条edge是不是连不同类型的点。时间复杂度得是O（V+E）。
第二题我没解出来，后来google的。 如果那个coin出0的几率是p（p为止），甩两次出现01和10的几率都是p*（1-p），把01当0，10当1，00和11都不要，就是50%的fair coin了。

1. int seed = chrono::system_clock::now().time_since_epoch().count();                  
   
2. default_random_engine gen(seed);                                                   
   
3.                                                                                     
   
4. int flip_unfair_coin() {                                                            
   
5.     // p(0) = 0.1                                                                  
   
6.     if (gen() % 100 < 10) {                                                         
   
7.         return 0;                                                                  
   
8.     } else {                                                                        
   
9.         return 1;                                                                  
   
10.     }                                                                              
    
11. }                                                                                   
    
12.                                                                                     
    
13. int flip_unfair_coin2() {                                                           
    
14.     int a = 0, b = 0;                                                               
    
15.     while (a == b) {                                                               
    
16.         a = flip_unfair_coin();                                                     
    
17.         b = flip_unfair_coin();                                                     
    
18.     }                                                                              
    
19.     return a;                                                                       
    
20. }                                                                                   
    
21.                                                                                     
    
22. void test(int(*f)()) {                                                              
    
23.     int n, count = 0, total = 1e6;                                                  
    
24.     for (int i = 0; i < total; ++i) {                                               
    
25.         n = f();                                                                    
    
26.         if (n == 0) {                                                               
    
27.             ++count;                                                               
    
28.         }                                                                           
    
29.     }                                                                              
    
30.     cout << "total = " << total << " count(0) == " << count <<                     
    
31.         " ratio = " << double(count) / total << endl;                              
    
32. }
    
33.                                                                                                          
    
34. int main() {                                                                     
    
35.     test(flip_unfair_coin);                                                         
    
36.     test(flip_unfair_coin2);                                                     
    
37.     return 0;                                                                    
    
38. }

复制代码

补充内容 (2017-7-14 00:35):
result:
total = 1000000 count(0) == 99973 ratio = 0.099973
total = 1000000 count(0) == 499450 ratio = 0.49945

谢谢楼主分享，bipartitie都考？？第二题是用non-uniform概率来调整吗？

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

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

楼主面的哪个组的呢

bipartite 这题 求问O（V+E）这个难道还能优化吗。。。