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

 找回密码
 立即注册
  • 男生“换心”后秒变学霸!这才是真相
  • 18万元!日本无印良品推9平单间小屋:海边山脚都能建
  • 大疆发飙!举报干扰成都机场无人机奖100万
  • 把猫头鹰羽毛一撩 网友惊呼:竟是大长腿
  • 夸张!科学家揭开人类大秘密:《魔戒》小矮人成真
  • 捡回一条命!男子深海垂钓巨大鲨鱼上钩:结果意外
  • 胖子有救!利用大脑电磁刺激技术进行减肥:效果不错
  • 男子和机器人手臂玩刀戳手指缝:这结果没想到
  • 催眠是真的吗?其实 你被骗很多年了!
  • 担任戛纳主竞赛评委 范冰冰:深感荣幸 很有压力
  • 100天了,特朗普的“三驾马车”还能走多远
  • 对于IBM,巴菲特到底是怎么想的?
  • 法国大选是否能点燃美国市场?
  • 对于石油,投资者难得保持一致意见:看跌
  • 福特汽车销量“遇冷”
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3224|回复: 10

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

[复制链接]

5

主题

18

帖子

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不难。

--
【中国海淘拼单总群】36382164
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

26

主题

101

帖子

157

积分

注册会员

Rank: 2

积分
157
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,...

我的答案是这样的
--

19

主题

95

帖子

136

积分

注册会员

Rank: 2

积分
136
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不难。

--

7

主题

234

帖子

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




--

27

主题

106

帖子

164

积分

注册会员

Rank: 2

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


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

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




--

30

主题

100

帖子

166

积分

注册会员

Rank: 2

积分
166
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).
求讲解
--

24

主题

103

帖子

172

积分

注册会员

Rank: 2

积分
172
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不难。



--

21

主题

73

帖子

131

积分

注册会员

Rank: 2

积分
131
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)


--

5

主题

251

帖子

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)



--

22

主题

74

帖子

122

积分

注册会员

Rank: 2

积分
122
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店面(攒点人品)- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
Sasa.com

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

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

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

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