美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 涨姿势:剥了柑橘的手不要摸气球 会爆炸!
  • 暴雪成立官方出版社:绝版小说复活
  • 刘嘉玲晒照谢粉丝 竟给自己脸上墨镜打了马赛克
  • 曹骏蓝盈莹宣布恋情 童年男神恋上“浣碧”
  • 技术帝展现神级停车:车身距墙不足一指
  • 她就是撞脸元朝皇后的日本女学生 如今成网红
  • 小鲜肉用倒模当替身传言后续 爆料者又推出廖凡
  • 女大学生裸条不雅照泄露 借钱原因曝光
  • 《超级马里奥跑酷》要求时刻在线
  • NPD数据显示CoD销量腰斩
  • 11月美国大选後房贷利率飙升的现象不但未消失,而且持续攀高-美国房产信息
  • 美国总统特朗普上任後,美国在全球经济发展上将转向保护主义-美国房产信息
  • 战略家:现在是金融类股的反弹消退的时候了
  • 苹果可能在2017年看到一个“惊喜”的反弹
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3197|回复: 10

内推面经 -twitter店面(攒点人品)- 唐人社区|北美华人论坛

[复制链接]
TA在交友中心
0 0 12
  @ME:   

5

主题

17

帖子

29

积分

新手上路

Rank: 1

积分
29
QQ
发表于 2016-9-10 19:24:27 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推面经版-twitter店面(攒点人品)


  JobHunting
标 题: twitter店面(攒点人品)


Given a jar with W white beans and R red beans, randomly pick one bean:
1) if it is white, eat it;
2) if it is red, put it back, and randomly pick one again. Eat it regardless
of color.

Write a program to estimate the probability of the last bean being white.

开始以为是个统计模拟问题,被误导浪费了不少时间。后来明白其实就是一个DP问题,
之后code不难。

--

回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

TA在交友中心
0 0 51
  @ME:   

23

主题

91

帖子

136

积分

注册会员

Rank: 2

积分
136
QQ
发表于 2016-9-10 20:34:39 | 显示全部楼层
JobHunting
标  题: Re: twitter店面(攒点人品)


这确实是概率题啊

Let W, R be the number of white and red beans in the jar

Initial conditions:
P(0, R) = 0 for R = 0,1,2,...
P(W, 0) = 1 for W = 1,2,...
P(1, R) = 1/((R+1)^2) for R = 1,2,...


P(W, R) = 1/2 + P(W-1, R)/2 for W = 2,3,...

我的答案是这样的
--
TA在交友中心
0 0 39
  @ME:   

16

主题

84

帖子

117

积分

注册会员

Rank: 2

积分
117
QQ
发表于 2016-9-10 20:59:59 | 显示全部楼层
JobHunting
标  题: twitter店面(攒点人品)


Given a jar with W white beans and R red beans, randomly pick one bean:
1) if it is white, eat it;
2) if it is red, put it back, and randomly pick one again. Eat it regardless
of color.

Write a program to estimate the probability of the last bean being white.

开始以为是个统计模拟问题,被误导浪费了不少时间。后来明白其实就是一个DP问题,
之后code不难。

--
TA在交友中心
0 0 20
  @ME:   

7

主题

222

帖子

220

积分

中级会员

Rank: 3Rank: 3

积分
220
QQ
发表于 2016-9-10 21:46:02 | 显示全部楼层
JobHunting
标  题: Re: twitter店面(攒点人品)


dp[0][j] = 0, j = 0,1,...,R
dp[i][0] = 1, i = 1,...,W

for i in 1:W+1
    for j in 1:R+1
        probW = i/(i+j)
        probR  = j/(i+j)
        probRandomAndEat = probW * dp[i-1][j] + probR*[i][j-1]
        dp[i][j] = probW * dp[i-1][j]  + probR* probRandomAndEat

return dp[W][R]


【 在 beefcurtain5 (beefcurtain5) 的大作中提到: 】
: 说说怎么做啊
: regardless




--

TA在交友中心
0 0 56
  @ME:   

25

主题

96

帖子

143

积分

注册会员

Rank: 2

积分
143
QQ
发表于 2016-9-10 22:14:01 | 显示全部楼层
JobHunting
标  题: Re: twitter店面(攒点人品)


又想了下我这四种情况的假设不对,不应该是先吃得剩下一白或一红再加,而是在有
w,r以后吃掉一白或一红然后再看w-1,r或w,r-1

【 在 sza (sza) 的大作中提到: 】
: 这四种情况的发生并不是完全都等于1/4




--

TA在交友中心
0 0 64
  @ME:   

29

主题

94

帖子

158

积分

注册会员

Rank: 2

积分
158
QQ
发表于 2016-9-10 23:15:24 | 显示全部楼层
JobHunting
标  题: Re: twitter店面(攒点人品)


p(w, r)代表什么,
如果代表第w+r次抽取时剩余状态,那么应该是由p(w+1, r) p(w, r+1) 得来
如果是代表w+r次消耗的状态,那么概率的计算就变成了(W-w)/(R+W-w-r+1).
求讲解
--
TA在交友中心
0 0 60
  @ME:   

22

主题

98

帖子

148

积分

注册会员

Rank: 2

积分
148
QQ
发表于 2016-9-10 23:30:09 | 显示全部楼层
JobHunting
标  题: Re: twitter店面(攒点人品)


说说怎么做啊
【 在 mengxin (waking up) 的大作中提到: 】
: Given a jar with W white beans and R red beans, randomly pick one bean:
: 1) if it is white, eat it;
: 2) if it is red, put it back, and randomly pick one again. Eat it
regardless
:  of color.
: Write a program to estimate the probability of the last bean being white.
: 开始以为是个统计模拟问题,被误导浪费了不少时间。后来明白其实就是一个DP问题,
: 之后code不难。



--
TA在交友中心
0 0 48
  @ME:   

18

主题

65

帖子

113

积分

注册会员

Rank: 2

积分
113
QQ
发表于 2016-9-10 23:30:19 | 显示全部楼层
JobHunting
标  题: Re: twitter店面(攒点人品)


transfer function:
P(W, R) = (pW + (1-pW)*pW) * P(W-1, R) + (1-pW)*(1-pW) * P(W, R-1)
where pW = W/(W+R)


--
TA在交友中心
0 0 13
  @ME:   

5

主题

237

帖子

225

积分

中级会员

Rank: 3Rank: 3

积分
225
QQ
发表于 2016-9-10 23:42:47 | 显示全部楼层
JobHunting
标  题: Re: twitter店面(攒点人品)


我理解你的公式但pW不就是应该是一白一
红情况下剩白的概率吗?(1/4)

有四种状态
剩白,再加一个白球 p(w-1, r)*1
剩白,再加一个红球 p(w-1, r)*1/4
剩红,再加一个白球 (1-p(w, r-1))*1/4
剩红,再加一个红球 0
全部加起来完事

【 在 mengxin (waking up) 的大作中提到: 】
: transfer function:
: P(W, R) = (pW + (1-pW)*pW) * P(W-1, R) + (1-pW)*(1-pW) * P(W, R-1)
: where pW = W/(W+R)



--
TA在交友中心
0 0 48
  @ME:   

21

主题

70

帖子

116

积分

注册会员

Rank: 2

积分
116
QQ
发表于 2016-9-10 23:48:11 | 显示全部楼层
JobHunting
标  题: Re: twitter店面(攒点人品)


这四种情况的发生并不是完全都等于1/4

【 在 BadassPig (坏屁股猪) 的大作中提到: 】
: 我理解你的公式但pW不就是应该是一白一
: 红情况下剩白的概率吗?(1/4)
: 有四种状态
: 剩白,再加一个白球 p(w-1, r)*1
: 剩白,再加一个红球 p(w-1, r)*1/4
: 剩红,再加一个白球 (1-p(w, r-1))*1/4
: 剩红,再加一个红球 0
: 全部加起来完事



--
您需要登录后才可以回帖 登录 | 立即注册  

本版积分规则

玩美生活FunInUSA.net 华人娱乐论坛发布的内推面经 -twitter店面(攒点人品)- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -twitter店面(攒点人品)- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
1&1 Hosting

Copyright ©2011 FunInUSA.com All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA

安全联盟认证 安全联盟认证

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