推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 578|回复: 5
收起左侧

houzz店面

[复制链接] |试试Instant~ |关注本帖
seakid 发表于 2017-7-13 07:26:03 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@houzz - 内推 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
周一刚跪完,至今没收到HR电话,估计的挂了。
问了两题,第一题是检查一个graph是不是bipartite的,bfs解完了,接下来问时间复杂度,可不可以优化。
第二题问一个unfair coin,怎么disign一个process可以返回同样几率的0和1.

评分

1

查看全部评分

edyyy 发表于 2017-7-13 21:53:36 | 显示全部楼层
谢谢楼主分享,bipartitie都考??第二题是用non-uniform概率来调整吗?
回复 支持 反对

使用道具 举报

saklyn 发表于 2017-7-13 23:24:09 | 显示全部楼层
第一个只是看是不是bipartite,O(N)解决,所有点都查过了总该知道。. visit 1point3acres.com for more.
第二个是样本数量的问题,假如一种uniform coin样本数量是N1,生成0的概率是0.8,生成1的概率是0.2,那是否可以找到另外一种uniform coin,样本数量为N2,生成0的概率为x,生成1的概率是1-x。求解出N1和N2的关系就行。. From 1point 3acres bbs
N1*0.8+N2*x=0.5*(N1+N2)
N1*0.2+N2*(1-x)=0.5*(N1+N2)

然后造一个大小为N1+N2的list。x也可以是0.8,看面试官要求,0也行,也就是N2个样本只产生数值为1的硬币。
回复 支持 反对

使用道具 举报

 楼主| seakid 发表于 2017-7-13 23:46:05 | 显示全部楼层
第一题要看是不是bipartite, 查所有点还不够,要查每条edge是不是连不同类型的点。时间复杂度得是O(V+E)。
第二题我没解出来,后来google的。 如果那个coin出0的几率是p(p为止),甩两次出现01和10的几率都是p*(1-p),把01当0,10当1,00和11都不要,就是50%的fair coin了。
回复 支持 反对

使用道具 举报

bearicc 发表于 2017-7-14 00:34:27 | 显示全部楼层
  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 {                                                                        . more info on 1point3acres.com
  9.         return 1;                                                                   . from: 1point3acres.com/bbs
  10.     }                                                                              
  11. }                                                                                   
  12.                                                                                     
  13. int flip_unfair_coin2() {                                                           
  14.     int a = 0, b = 0;                                                               
  15.     while (a == b) {                                                               
  16.         a = flip_unfair_coin();                                                     . from: 1point3acres.com/bbs
  17.         b = flip_unfair_coin();                                                     
  18.     }                                                                              
  19.     return a;                                                                       -google 1point3acres
  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;                                                                . 1point3acres.com/bbs
  28.         }                                                                           
  29.     }                                                                              
  30.     cout << "total = " << total << " count(0) == " << count <<                     
  31.         " ratio = " << double(count) / total << endl;                               . From 1point 3acres bbs
  32. }
  33.                                                                                                           鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  34. int main() {                                                                     
  35.     test(flip_unfair_coin);                                                         -google 1point3acres
  36.     test(flip_unfair_coin2);                                                     
  37.     return 0;                                                                    . 1point3acres.com/bbs
  38. }
复制代码

补充内容 (2017-7-14 00:35):. Waral 鍗氬鏈夋洿澶氭枃绔,
result:
total = 1000000 count(0) == 99973 ratio = 0.099973. 鍥磋鎴戜滑@1point 3 acres
total = 1000000 count(0) == 499450 ratio = 0.49945
回复 支持 反对

使用道具 举报

cawe 发表于 2017-7-18 04:51:19 | 显示全部楼层
楼主面的哪个组的呢
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-23 06:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表