近期论坛无法登录的解决方案


一亩三分地论坛

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

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

google 比赛夺冠概率题

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

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

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

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

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

输入的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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
。。。胜率表的意思就是只保存胜利的概率,你不需要知道到底是谁赢。。。

对于位置1的概率 a 20%, b 80%, c 0%, d 0%.鏈枃鍘熷垱鑷1point3acres璁哄潧
对于位置2的概率 a 0%, b 0%, c 60%, d 40%

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

使用道具 举报

z928czzc 发表于 2016-3-8 12:13:13 | 显示全部楼层
关注一亩三分地微博:
Warald
不需要exponential memory usage

对tree的每个节点,都各自保存一个每个人的胜率表。然后bottom up即可。如果总共n个人,由两个child的胜率表算它的parent胜率表只要n^2复杂度。总共算O(n)个胜率表就可以了。

比如对于
      ?-?(3)
  ?-?(1) ?-?(2) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
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 .1point3acres缃

对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
。。。胜率表的意思就是只保存胜利的概率,你不需要知道到底是谁赢。。。. From 1point 3acres bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
对于位置1的概率 a 20%, b 80% ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
没怎么看明白。。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-26 12:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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