Google的疯狂面试题

作者:, 发表于

有一些是火星题,比如最后一个海盗分金,不太可能还用来作为面试题,估计是被拉过来凑数的。

原文(英文)直接到这里看吧,27floors给出了中文翻译 。这里转几个跟概率有关的:

  1. 一个国家人们只想要男孩,每个家庭都会一直要孩子,只到他们得到一个男孩。如果生的是女孩,他们就会再生一个。如果生了男孩,就不再生了。那么,这个国家里男女比例如何?

最严格的方法是直接计算男孩和女孩数量的期望,都是1,所以男女比例平衡。另一种说法是每个孩子的概率都是1:1,所以总的来看,最终的比例也将是1:1。这种说法可以用概率里面的"停时"的概念严格化,其实也不简单。比如,如果每个家庭一直要孩子,直到男孩比女孩数多一个,这时候如何分析?

停时: \(\tau\) 称为独立同分布随机变量 \(X_1, X_2, \cdots\) 的停时,若 \(\{\tau=n\}\)\(\{X_{n+1}, X_{n+2}, \cdots\}\) 独立。

停时定理: \(EX_i<\infty\Rightarrow E\sum_{i=1}^\tau X_i=E\tau EX\)

"停时"是一个很深刻的概念,也非常有用。比如如果题目改成「如果每个家庭一直都要孩子,直到男孩比女孩数多一个,或者生到了100个小孩(是不是有点太多了)为止」,这时候如果直接算期望可不是一件容易的事情,但用停时定理一步就能得出结果。

  1. 在一条高速公路上,在30分钟内看到一辆汽车的可能性是0.95,那么在10分钟内看到一辆车的概率是多少(假设过车的概率是恒定的)?

这个题目我觉得是所有题目里面最有意思的一个(海岛分金更有意思,但2old)。会做得举手...

只需注意一个事实:下一辆车来的时间和已经等待多久无关(等公交车不算)。这种概率分布称为Poisson分布...记事件A:0-10分钟无车,B:10-20分钟无车,C:20-30分钟无车,则A,B,C互相独立,而 \(0.05 = P(A\wedge B\wedge C)=P(A)^3\) ,所以...

  1. 你和朋友去参加一个晚会,带你和朋友在内,共有10人。你的朋友和你打赌,你找到一位和你同一天生日的,你就得到1美元,他找到的任何一个和你生日不同的人,他得到2美元。你会打这个赌吗?

这里似乎有些问题,原以为是翻译错误,但读原文才发现,原文就不清楚。不知道是不是想考"生日悖论"(birthday paradox),关于存在两个人同一天生日的概率。

另外提一下下,我在阅微客栈里发过很多算法的面试题。

[tags]Google,面试题,概率[/tags]

Q.E.D.


上一篇:帽子游戏二2007年6月25日
这个题目听说是MSRA的面试题。 在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参

下一篇:用Web Picasa API搭建站内相册2007年11月10日
在flickr时代,为了专门把站内嵌入相册,还专门写了一篇文章把Flickr相册搬回家。flickr被墙之后,我就把个人相册转到了Web Picasa上。用Picasa Web就简单


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。