一亩三分地论坛

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

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

twitter sde 电面~~~

[复制链接] |试试Instant~ |关注本帖
肥霸 发表于 2015-2-24 09:39:54 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@twitter - 内推 - 技术电面 |Fail

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

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

x
Suppose I have a jar containing red and white beans. I proceed to eat the beans according to the following process:
On each "turn" I draw a bean from the jar.
1. If the bean is white I eat it.
2. If the bean is red I throw it back in the jar. Then I draw another bean and eat it, regardless of its color.
I repeat this process until I've eaten all the beans.
What is the probability that the last bean will be white, given some starting point of R red beans and W white beans.
. from: 1point3acres.com/bbs
一开始和面试官聊了下模拟算法,然后用动归,结果时间不够递推式没搞出来,第二天就收到拒信了。。。不过是不是最近TWITTER不怎么招人?



补充内容 (2015-2-24 09:43):
加分。。。。怎么我今天不能搜索论坛帖子了?/???

评分

4

查看全部评分

eshenxian 发表于 2016-7-19 08:23:56 | 显示全部楼层
在任意时刻,吃红豆概率=连续两次抓到红豆概率: (r/(r+w))^2, 吃白豆概率=1-吃红豆概率。
P(last=w| W, R) = P(吃红豆|W, R)*P(last=w|W, R-1) + P(吃白豆|W, R)*P(last=w|W-1, R)
DP公式,
p[w][r] = (r/(r+w))**2 p[w][r-1] + (1-(r/(r+w))**2) * p[w-1][r]. visit 1point3acres.com for more.
起始:
p[0][1] = 1, p[1][0] = 0.

好像只能迭代,不能直接数学表达式算出来,因为每步的r/(r+w)是不确定的。

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

NdrZmansN 发表于 2015-2-24 09:52:34 | 显示全部楼层
楼主面的啥组?
回复 支持 反对

使用道具 举报

 楼主| 肥霸 发表于 2015-2-25 04:48:05 | 显示全部楼层
general的。。。面我的是个DATA SCIENTIST
回复 支持 反对

使用道具 举报

yabay91 发表于 2015-2-25 05:05:29 | 显示全部楼层
lz你之前内推的时候有木有收到确认信啊。。。

我之前找人内推了。。一直没有消息。。不知道什么情况。。
回复 支持 反对

使用道具 举报

 楼主| 肥霸 发表于 2015-2-25 14:15:08 | 显示全部楼层
yabay91 发表于 2015-2-25 05:05
lz你之前内推的时候有木有收到确认信啊。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦

我之前找人内推了。。一直没有消息。。不知道什么情况。。

收到了呀~~
回复 支持 反对

使用道具 举报

zhiyiting 发表于 2015-2-26 02:14:54 | 显示全部楼层
肥霸面吃豆子

补充内容 (2015-2-26 06:21):
是不是P[j] = i/(i+j)*P[j-1] + i/(i+j)*(i/(i+j) * P[i-1][j] + j/(i+j)*P[j-1])

补充内容 (2015-2-26 06:22):
= =他怎么把我的吃掉了,明明打了

补充内容 (2015-2-26 06:23):
因为把[ i ]当做italic了
回复 支持 反对

使用道具 举报

llxujiji 发表于 2015-2-27 11:57:45 | 显示全部楼层
LZ加油!搭车问下twitter是不是不咋找人了
回复 支持 反对

使用道具 举报

tyr034 发表于 2015-3-3 02:21:57 | 显示全部楼层
这题咋做啊
回复 支持 反对

使用道具 举报

tyr034 发表于 2015-3-3 10:46:18 | 显示全部楼层
楼主能不能分享下思路啊
回复 支持 反对

使用道具 举报

douya 发表于 2015-3-3 12:20:12 | 显示全部楼层
应该怎么做呢?
回复 支持 反对

使用道具 举报

douya 发表于 2015-3-3 12:28:43 | 显示全部楼层
zhiyiting 发表于 2015-2-26 02:14
肥霸面吃豆子. 1point 3acres 璁哄潧

补充内容 (2015-2-26 06:21):

这是1d还是2d dp么? 能详细讲下?
回复 支持 反对

使用道具 举报

 楼主| 肥霸 发表于 2015-3-3 12:46:52 | 显示全部楼层
zhiyiting 发表于 2015-2-26 02:14
肥霸面吃豆子

补充内容 (2015-2-26 06:21):

你这是一维DP,  P【j】定义的是啥?
回复 支持 反对

使用道具 举报

 楼主| 肥霸 发表于 2015-3-3 12:47:37 | 显示全部楼层
tyr034 发表于 2015-3-3 10:46
楼主能不能分享下思路啊

我当时也挂了。。。弄个二维DP P[W][R]
回复 支持 反对

使用道具 举报

zhiyiting 发表于 2015-3-3 12:49:02 | 显示全部楼层
肥霸 发表于 2015-3-3 12:46 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你这是一维DP,  P【j】定义的是啥?

我这是二维DP,系统把我的[ i ]当成italic吃掉了
肥霸求光环啊,我也要面试了~~当年拿了你的托福书就考得很好。。
回复 支持 反对

使用道具 举报

zhiyiting 发表于 2015-3-3 12:59:45 | 显示全部楼层
douya 发表于 2015-3-3 12:28.鐣欏璁哄潧-涓浜-涓夊垎鍦
这是1d还是2d dp么? 能详细讲下?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Pi,j = j/(i+j)*Pi,j-1 + i/(i+j)*(i/(i+j) * Pi-1,j + j/(i+j)*Pi,j-1)
当前这一轮,有i个红色豆子,j个白色豆子
如果拿了白色豆子,就吃掉,所以最后一轮是白色豆子就是i红豆j-1白豆概率,两件事情同时发生,j/(i+j)*Pi,j-1
如果拿到红色豆子,就放回去,再拿一个吃掉,如果再拿到红色豆子,就是i-1,j豆子概率,如果再拿到白色豆子,就是i,j-1概率.鐣欏璁哄潧-涓浜-涓夊垎鍦
不知道对不对。。
回复 支持 反对

使用道具 举报

zhiyiting 发表于 2015-3-3 13:44:02 | 显示全部楼层
zhiyiting 发表于 2015-3-3 12:59
Pi,j = j/(i+j)*Pi,j-1 + i/(i+j)*(i/(i+j) * Pi-1,j + j/(i+j)*Pi,j-1)
当前这一轮,有i个红色豆子,j ...

算了一下,是不对的
回复 支持 反对

使用道具 举报

 楼主| 肥霸 发表于 2015-3-3 13:51:44 | 显示全部楼层
zhiyiting 发表于 2015-3-3 12:49
我这是二维DP,系统把我的[ i ]当成italic吃掉了
肥霸求光环啊,我也要面试了~~当年拿了你的托福书就 ...

同求光环~~~~~~~~~~~~那感觉你做的差不多了,就是要么吃掉一个白球,要么吃掉一个红球,所以P[R][W] = P[R-1][W] *XX + P[R][W-1] *XX
XX是一些转移概率
回复 支持 反对

使用道具 举报

 楼主| 肥霸 发表于 2015-3-3 13:52:28 | 显示全部楼层
你的系数还有一些问题估计,如果错了的话
回复 支持 反对

使用道具 举报

douya 发表于 2015-3-4 00:40:25 | 显示全部楼层
zhiyiting 发表于 2015-3-3 13:44
算了一下,是不对的

我感觉是这样:换个定义方法,pi,j不是吃了i+j个,而是还剩i red, j white。
pi,j = pi+1,j *(i+1)/(i+1+j) * (i+1)/(i+1+j)
      + pi,j+1 * ((j+1)/(i+1+j) + (1-(j+1)/(i+1+j))*(j+1)/(i+1+j) )

最后求的是p0,1
回复 支持 反对

使用道具 举报

 楼主| 肥霸 发表于 2015-3-4 16:25:18 | 显示全部楼层
楼上貌似不太对~~~最好反过来想
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 15:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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