《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 3984|回复: 8
收起左侧

google 比赛夺冠概率题

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

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

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

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

x
一道google的面经题,希望和小伙伴们讨论下~
"abc小哥吧,小哥上来很有激情。问了问简历。出的题目说难也不难,说简单没见过也不好答。就是有一堆player,每个人beat 其他人的概率已知。然后已知初始的对阵表,问给定一个player,问他最后夺冠的概率是多少。.1point3acres缃
               ----. 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算概率就行了吧?大神有更好的办法吗?. 鍥磋鎴戜滑@1point 3 acres
z928czzc 发表于 2016-3-8 22:35:42 | 显示全部楼层
。。。胜率表的意思就是只保存胜利的概率,你不需要知道到底是谁赢。。。. Waral 鍗氬鏈夋洿澶氭枃绔,

对于位置1的概率 a 20%, b 80%, c 0%, d 0%. visit 1point3acres.com for more.
对于位置2的概率 a 0%, b 0%, c 60%, d 40%

然后由两个胜率表,以及两两之间的胜利概率,得出3的胜率表,然后就知道a的胜率了。
回复 支持 2 反对 0

使用道具 举报

codemonk 发表于 2017-9-28 05:25:19 | 显示全部楼层
z928czzc 发表于 2016-3-8 12:13
不需要exponential memory usage

对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.     }. 1point3acres.com/bbs
  17.     return wintable;
  18. }

  19. // 对tree的每个节点,都各自保存一个每个人的胜率表。
  20. void run(vector<vector<double>>& winprob) {
  21.     n = winprob.size();
  22.     auto ans = helper(0, n-1, winprob);
  23.     for(double i : ans) cout << i << " ";.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.     cout << endl;
  25. }

  26. int main(int argc, const char * argv[]) {
  27.     // insert code here...
  28.     vector<vector<double>> winprob = {
  29.         {0.0, 0.5, 0.5, 0.5},
  30.         {0.5, 0.0, 0.5, 0.5},
  31.         {0.5, 0.5, 0.0, 0.5},
  32.         {0.5, 0.5, 0.5, 0.0}. 1point3acres.com/bbs
  33.     };
  34.     run(winprob);
  35.    
  36.     cout << endl;
  37.     winprob = vector<vector<double>>({
  38.         {0.0, 0.8, 0.0, 0.5},
  39.         {0.2, 0.0, 0.5, 0.5},. from: 1point3acres.com/bbs
  40.         {0.5, 0.5, 0.0, 0.5},
  41.         {0.5, 1.0, 0.5, 0.0}
  42.     });
  43.     run(winprob);
  44.     return 0;
  45. }
复制代码
  1. 0.25 0.25 0.25 0.25 . visit 1point3acres.com for more.

  2. 0.2 0.1 0.25 0.3
  3. Program ended with exit code: 0
复制代码

补充内容 (2017-9-28 05:32):
如果把第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)个胜率表就可以了。. Waral 鍗氬鏈夋洿澶氭枃绔,

比如对于
      ?-?(3)
  ?-?(1) ?-?(2). Waral 鍗氬鏈夋洿澶氭枃绔,
a-b c-d e-f g-h

先算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
。。。胜率表的意思就是只保存胜利的概率,你不需要知道到底是谁赢。。。
. 1point 3acres 璁哄潧
对于位置1的概率 a 20%, b 80% ...

没怎么看明白。。。
回复 支持 反对

使用道具 举报

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,
  11.     D: 0.4
  12.   }
  13. }
复制代码
通过观察我们发现,想要夺冠的话A必须战胜B,然后在下一轮可能面对C或者D。所以在当前选手组成情况下,A 夺冠的几率就是:
  1. // Let P_ij denote the probability of i beat j
  2. P_ab * (P_ac + P_ad)
复制代码
推而广之,如果有n个选手
  1. P_ab * (P_ac + P_ad + ..... + P_an)
复制代码
至于概率从哪里来我们就可以用传入的Map。

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

Limitation:
  • 用map不及胜率表高效
  • 肯定还有,暂时想不出来。。。
. 鍥磋鎴戜滑@1point 3 acres
欢迎批评指正






. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-18 20:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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