一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 2511|回复: 6
收起左侧

houzz店面

[复制链接] |试试Instant~ |码农类general, 美国面经, 面试经验, houzz
我的人缘0

分享帖子到朋友圈
seakid | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎

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

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
周一刚跪完,至今没收到HR电话,估计的挂了。
问了两题,第一题是检查一个graph是不是bipartite的,bfs解完了,接下来问时间复杂度,可不可以优化。
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
ocess可以返回同样几率的0和1.

评分

参与人数 1大米 +3 收起 理由
edyyy + 3 感谢分享!

查看全部评分


上一篇:Yelp OA
下一篇:piu 电面

本帖被以下淘专辑推荐:

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

使用道具 举报

我的人缘0
bearicc 2017-7-14 00:34:27 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   94% (33)
 
 
5% (2)    👎
  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
回复

使用道具 举报

我的人缘0
edyyy 2017-7-13 21:53:36 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (312)
 
 
5% (19)    👎
谢谢楼主分享,bipartitie都考??第二题是用non-uniform概率来调整吗?
回复

使用道具 举报

我的人缘0
saklyn 2017-7-13 23:24:09 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (168)
 
 
5% (10)    👎
第一个只是看是不是bipartite,O(N)解决,所有点都查过了总该知道。
第二个是样本数量的问题,假如一种uniform coin样本数量是N1,生成0的概率是0.8,生成1的概率是0.2,那是否可以找到另外一种uniform coin,样本数量为N2,生成0的概率为x,生成1的概率是1-x。求解出N1和N2的关系就行。
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的硬币。
回复

使用道具 举报

我的人缘0
cawe 2017-7-18 04:51:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   86% (19)
 
 
13% (3)    👎
楼主面的哪个组的呢
回复

使用道具 举报

我的人缘0
linlin1990 2017-9-8 12:51:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   72% (37)
 
 
27% (14)    👎
bipartite 这题 求问O(V+E)这个难道还能优化吗。。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-2-20 00:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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