一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1886|回复: 6
收起左侧

google 比赛夺冠概率题

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

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

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

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

x
一道google的面经题,希望和小伙伴们讨论下~.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%
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
然后由两个胜率表,以及两两之间的胜利概率,得出3的胜率表,然后就知道a的胜率了。
回复 支持 1 反对 0

使用道具 举报

z928czzc 发表于 2016-3-8 12:13:13 | 显示全部楼层
不需要exponential memory usage . Waral 鍗氬鏈夋洿澶氭枃绔,
. From 1point 3acres bbs
对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

对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
。。。胜率表的意思就是只保存胜利的概率,你不需要知道到底是谁赢。。。.1point3acres缃

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

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

使用道具 举报

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

对于位置1的概率 a 20%, b 80% ...
. 1point 3acres 璁哄潧
没怎么看明白。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 14:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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