在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4331|回复: 8
收起左侧

google 比赛夺冠概率题

[复制链接] |试试Instant~ |关注本帖
bobzhang2004 发表于 2016-3-8 11:49:30 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类General 硕士 全职@Google - 内推 - HR筛选  | Other | 其他

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

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

x
一道google的面经题,希望和小伙伴们讨论下~. from: 1point3acres
"abc小哥吧,小哥上来很有激情。问了问简历。出的题目说难也不难,说简单没见过也不好答。就是有一堆player,每个人beat 其他人的概率已知。然后已知初始的对阵表,问给定一个player,问他最后夺冠的概率是多少。
               ----. From 1point 3acres bbs.留学论坛-一亩-三分地
    ---                  ----
a--b   c---d    e---f  g---h

输入的format你自己决定。楼主当时真心也不知道啥好做法,很想用tree,但觉得用tree吧,从leaf node开始遍历到root 又很奇怪,而且很难找到一个node 的siblings。所以给了一个暴力解法,最后被证明是exponential memory usage。code也不是很好写,而且有些case也没处理。基本idea就是列出所有的对阵可能性,然后每一个可能性都有一个probability,最后结果相加。有点类似bfs。"
我觉的直接brute force算概率就行了吧?大神有更好的办法吗?
z928czzc 发表于 2016-3-8 22:35:42 | 显示全部楼层
。。。胜率表的意思就是只保存胜利的概率,你不需要知道到底是谁赢。。。

对于位置1的概率 a 20%, b 80%, c 0%, d 0%
对于位置2的概率 a 0%, b 0%, c 60%, d 40%
. 1point 3acres 论坛
然后由两个胜率表,以及两两之间的胜利概率,得出3的胜率表,然后就知道a的胜率了。
回复 支持 2 反对 0

使用道具 举报

codemonk 发表于 2017-9-28 05:25:19 | 显示全部楼层
z928czzc 发表于 2016-3-8 12:13
不需要exponential memory usage
.本文原创自1point3acres论坛
对tree的每个节点,都各自保存一个每个人的胜率表。然后bottom up即可 ...

按照楼上大神的思路,搞了个分治的解。函数递归画成树的话 有 N个leaf,因为树是平衡的,所以内部点也是 O(N) 个,每个点要计算一次 wintable, 需要O(N^2). 所以总时间O(N^3)。
  1. int n;
  2. vector<double> helper(int start, int end, vector<vector<double>>& winprob) {
  3.     vector<double> wintable(n, 0.0);
  4.     if(start == end) {
  5.         wintable[start] = 1.0;
  6.         return wintable;
  7.     }
  8.     int mid = start + (end - start) / 2;
  9.     auto left = helper(start, mid, winprob);
  10.     auto right = helper(mid+1, end, winprob);
  11.     for(int i = 0; i < n; i++) {
  12.         for(int j = 0; j < n; j++) {
  13.             wintable[i] += left[i] * right[j] * winprob[i][j];
  14.             wintable[j] += left[i] * right[j] * winprob[j][i];
  15.         }
  16.     }
  17.     return wintable;
  18. }

  19. // 对tree的每个节点,都各自保存一个每个人的胜率表。
  20. void run(vector<vector<double>>& winprob) {.1point3acres网
  21.     n = winprob.size();
  22.     auto ans = helper(0, n-1, winprob); 来源一亩.三分地论坛.
  23.     for(double i : ans) cout << i << " ";
  24.     cout << endl;. more info on 1point3acres
  25. }
  26. . from: 1point3acres
  27. int main(int argc, const char * argv[]) {
  28.     // insert code here...
  29.     vector<vector<double>> winprob = {. 留学申请论坛-一亩三分地
  30.         {0.0, 0.5, 0.5, 0.5},
  31.         {0.5, 0.0, 0.5, 0.5},
  32.         {0.5, 0.5, 0.0, 0.5},.本文原创自1point3acres论坛
  33.         {0.5, 0.5, 0.5, 0.0}
  34.     };
  35.     run(winprob);
  36.    
  37.     cout << endl;
  38.     winprob = vector<vector<double>>({
  39.         {0.0, 0.8, 0.0, 0.5},
    来源一亩.三分地论坛.
  40.         {0.2, 0.0, 0.5, 0.5},
  41.         {0.5, 0.5, 0.0, 0.5},. 1point 3acres 论坛
  42.         {0.5, 1.0, 0.5, 0.0}
  43.     });. 牛人云集,一亩三分地
  44.     run(winprob);
  45.     return 0;
  46. }
复制代码
  1. 0.25 0.25 0.25 0.25
  2. . more info on 1point3acres
  3. 0.2 0.1 0.25 0.3
  4. Program ended with exit code: 0
复制代码

补充内容 (2017-9-28 05:32):.1point3acres网
如果把第3行放到 递归的后面(第10行),空间复杂度可以做到 O(logN + N) 。。。 不对请指正
回复 支持 1 反对 0

使用道具 举报

z928czzc 发表于 2016-3-8 12:13:13 | 显示全部楼层
不需要exponential memory usage

对tree的每个节点,都各自保存一个每个人的胜率表。然后bottom up即可。如果总共n个人,由两个child的胜率表算它的parent胜率表只要n^2复杂度。总共算O(n)个胜率表就可以了。
-google 1point3acres
比如对于
      ?-?(3)
  ?-?(1) ?-?(2)
a-b c-d e-f g-h-google 1point3acres

先算1 2的胜率表,再算3的胜率表就可以了
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-8 12:40:02 | 显示全部楼层
z928czzc 发表于 2016-3-8 12:13
不需要exponential memory usage

对tree的每个节点,都各自保存一个每个人的胜率表。然后bottom up即可 ...

谢谢,但是要算1和2的胜率也得从leaf开始向上算吧,但是1到底是哪个赢呢?a-b还是c-d?可以写下code吗?
回复 支持 反对

使用道具 举报

youdidut 发表于 2016-3-8 23:11:23 | 显示全部楼层
用Queue,每次取出队列中的两组概率(比如:{a:0.5,b:0.5}{c:0.1,d:0.9})算出最新的概率,放回队列。取出的最后两组数据代表决赛。
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-8 23:12:51 | 显示全部楼层
z928czzc 发表于 2016-3-8 22:35
。。。胜率表的意思就是只保存胜利的概率,你不需要知道到底是谁赢。。。

对于位置1的概率 a 20%, b 80% ...

我觉得这个应该是对的
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-17 10:00:06 | 显示全部楼层
z928czzc 发表于 2016-3-8 22:35
。。。胜率表的意思就是只保存胜利的概率,你不需要知道到底是谁赢。。。

对于位置1的概率 a 20%, b 80% ...

没怎么看明白。。。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

sh.holmes 发表于 2017-10-21 19:39:02 | 显示全部楼层
不知道是不是我理解的有问题,我觉得这个题可以很简单地解:

根据楼主的回忆,input 是概率以及初始的对阵情况,可以要求概率表为一个map,对阵情况为一个二维矩阵,&#127792;:
  1. // 胜率 map
  2. win = {
  3.   A: {
  4.     B: 0.5,
  5.     C: 0.1,
  6.     D: 0.6
  7.   },
  8.   B: {
  9.     A: 0.5,
  10.     C: 0.7,. visit 1point3acres for more.
  11.     D: 0.4
  12.   }
  13. }
复制代码
通过观察我们发现,想要夺冠的话A必须战胜B,然后在下一轮可能面对C或者D。所以在当前选手组成情况下,A 夺冠的几率就是:
  1. // Let P_ij denote the probability of i beat j. 1point3acres
  2. P_ab * (P_ac + P_ad)
复制代码
推而广之,如果有n个选手
  1. P_ab * (P_ac + P_ad + ..... + P_an)
复制代码
至于概率从哪里来我们就可以用传入的Map。

时间复杂度: O(n), n 为选手数
空间复杂度: O(1) 因为除了需要不断更新概率之外,没有什么需要保存的

Limitation:
  • 用map不及胜率表高效
  • 肯定还有,暂时想不出来。。。

欢迎批评指正.1point3acres网

. 围观我们@1point 3 acres


. 1point3acres


回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-23 17:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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