Google的疯狂面试题

zhiqiangSeptember 11, 2007 IT技术科学

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

原文（英文）直接到这里看吧，27floors给出了中文翻译。这里转几个跟概率有关的：

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

最严格的方法是直接计算男孩和女孩数量的期望，都是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个小孩(是不是有点太多了)为止”，这时候如果直接算期望可不是一件容易的事情，但用停时定理一步就能得出结果。

在一条高速公路上，在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$ ，所以...

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

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

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

查看更多关于Google, 概率, 面试题的内容。

15条留言 -> 跳到留言表格

At 2007.09.12 03:02, dribblejj said:

第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1 第二题我不会算，只知道用poisson可以算， $P(t)=1- e^{-t\lambda}$ ,知道P(30) = 0.95,算P(10)......

[Reply]
- At 2007.09.12 18:25, zhiqiang said:
  
  答案最好有直观的意义——就是说不知道poisson分布的人也应该看懂才行
  
  btw: Latex公式左右各写两个$符号可以自动转化为图形，比如 $\alpha=\beta+\gamma$ ，还有你的公式写错了，我替你改了
  
  [Reply]
  - At 2007.09.12 22:39, dribblejj said:
    
    来给俺扫扫盲吧，我不知道怎么才能讲得通俗易懂
    
    [Reply]
At 2007.09.12 07:39, 小一 said:

看来我要是面试的话,肯定通不过了.......

[Reply]
At 2007.09.12 08:04, est said:

在GReader里看到博主的 ol li /li /ol 设置错了，结果已经改过来了，呵呵

[Reply]
At 2007.09.12 09:23, rex said:

记起来了，第一道生男生女的题，我自己也编写过，哈哈。只不过年深日久，原来的记录不知丢到哪里去了。回去翻翻。

[Reply]
- At 2007.09.17 18:30, rex said:
  
  当时的题目是这样的：
  
  一个国家人们只想要男孩，每个家庭都会一直要孩子，只到他们得到一个男孩。如果生的是女孩，他们就会再生一个。如果生了男孩，就不再生了。生男生女事件独立，概论均为0.5，问，这对夫妇最终平均会有多少个孩子？
  
  我的思路：
  
  设生男孩的概率为rate_boy,生女孩的概率为rate_girl,则有rate_boy+rate_gril=1;
  如果不加以限制，对于所生的第n个孩子(n=1,2,3,4,...∞)，只有当其性别为男时，才停止生产，否则继续生出第n+1个孩子。
  第n个孩子是男孩的概率为(在此约定^代表乘方，如2^34代表2的34次方。)
  =rate_girl^(n-1)*rate_boy
  =(1-rate_boy)^(n-1)*rate_boy
  
  当n趋向于∞时，所生孩子的总量是如下序列的总和：
  total number=
  1*(1-rate_boy)^0*rate_boy+2*(1-rate_boy)^1*rate_boy+3*(1-rate_boy)^2*rate_boy+...
  +∞*(1-rate_boy)^(∞-1)*rate_boy.
  ∞不能参加运算，我们用n→∞中的n来参与运算。
  一方面，我们可以用概率论中提供的E(pq)的公式来精确计算，一方面，我们也可以限定一个n值，用计算机累加的方法进行粗略计算。
  计算机方法：
  
  double sum = 0.0;
  int i;
  for(i=1;i＜=n;i++)
  {
  sum+=i*pow(m_girl,i-1)*m_boy;
  }
  只要事先设定了一个n值，我们总可以计算出相应的temp_sum值。
  
  大量计算表明，sum值与rate_boy成反比，乘积为1。比如，当生男孩的概率为0.1时，平均生10个孩子才会得到一个男孩。当然，在所设定的n趋向于∞自然得到此结果。较小的n会得到不合理的解。(只有纯粹的整数运算，计算机的计算才能达到精确。在涉及小数的计算中，其结果只能是无限接近。尤其是在涉及理论推导的计算时，还是用数学的方法比较可信。我的数学不好，如果您感兴趣的话，请用数学的方法将此问题证明出来。)
  如，
  生男的概率为0.5时，理论结果sum是2个，所输入的n为54时，sum→2.
  生男的概率为0.4时，理论结果sum是2.5个，所输入的n为77时，sum→2.5
  生男的概率为0.3时，理论结果sum是3.3个，所输入的n为111时，sum→3.333333333...
  生男的概率为0.2时，理论结果sum是5个，所输入的n为175时，sum→5.
  生男的概率为0.1时，理论结果sum是2.5个，所输入的n为365时，sum→10.(表现形式可能会是9.99999999...，这也是不精确的一种表现。)
  
  [Reply]
  - At 2007.09.17 20:43, zhiqiang said:
    
    只不过计算 $\sum_i i/p^i$ ，可以直接算的，没必要用到计算机来模拟。
    
    [Reply]
At 2007.09.12 16:26, rex said:

生日悖论：

不计特殊的年月，如闰二月。先计算房间里所有人的生日都不相同的概率，那么

第一个人的生日是 365选365
第二个人的生日是 365选364
第三个人的生日是 365选363
:
:
:
第n个人的生日是 365选365-(n-1)

所以所有人生日都不相同的概率是：
(365/365)× (364/365) ×(363/365) ×(362/365)× ... ×(365-n+1/365)

那么，n个人中有至少两个人生日相同的概率就是：
1-(365/365)× (364/365) ×(363/365) ×(362/365)× ... ×(365-n+1/365)

所以当n=10的时候，概率为0.116948178?
不知计算是否正确.

[Reply]
- At 2007.09.12 22:36, zhiqiang said:
  
  公式对了，计算不知道对不对还有题目的意思也不知道是不是指的是生日悖论。
  
  [Reply]
At 2007.09.12 23:09, mathena said:

其实第二题远没有大家想的那么复杂啦.
反过来想抓球问题, 一个篮子里面红色蓝色两种球, 比例是1:1, 抓三次, 至少抓到一次红球的概率是 1-(1/2)^3,
所以, 这一题是 1- [(1-0.95) 开三次方], Google 面试的时候可能会给你一个计算机, 用计算器或者 bc 做一下就知道了, 大致是 63%

[Reply]
- At 2007.09.13 09:18, zhiqiang said:
  
  是的，关键是模型的建立，各个时间段的概率独立性，我一直认为这个概率分布是所有分布里面最美的。由此引出的各种排队模型也非常有趣。
  
  [Reply]
  - At 2007.09.13 09:21, dribblejj said:
    
    还是我太迂腐，学得不够灵活，你的那种分析方式很好。
    
    [Reply]
At 2007.09.13 09:24, dribblejj said:

我最近作的结果出了比较严重的问题，但是deadline就在月底了，所以我最近状态十分不对头.....这就是我在blog上很抓矿的原因，今天不知道几点能睡

[Reply]
At 2008.08.24 23:16, wren said:

第二题的1-0.95，表示的是没有车经过和没有大于一辆车经过的概率。
所以有点不对

[Reply]

« 慕田峪长城

《中国崛起策》正式出版 »

Google的疯狂面试题

查看更多关于Google, 概率, 面试题的内容。

15条留言 -> 跳到留言表格

阅微堂