面试遇到的智力/概率题整理

1 - 10000瓶水，其中一瓶有毒，小白鼠喝后12小时才会有反应，问在12小时内需要多少只小白鼠能知道哪瓶水有毒。

• log2(10000) = 14
• 10000需要14位的2进制数
• 每一位对应一只老鼠，对于每一位取1的水，喂给该位的老鼠
• 根据14只老鼠的状态，确定毒水各位的取值，合并在一起就是编号的2进制

2 - 10个人里每个人在10分钟内的任何一个分钟到达的概率是均匀分布的，问所有人都到达的时刻在几分钟时概率最大。

• 假设最后一个人在第n分钟到达，概率是(n/10)^9*(1/10)，n取10最大

3 - 2.5亿个整数找不重复的整数，内存无法一下存下这2.5亿个数。

• 位图法：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。扫描后，查看bitmap，把对应位是01的整数输出即可。

4 - 1000盏灯关着，1000个人标号1~1000依次进入，每个人进去按一下自己标号倍数的开关，问最后哪些灯亮着。

• 亮着的灯的编号为1000以内的平方数
• 开关按过的次数为其编号的所有因数的个数
• 由关到开，按过的次数为奇数次，说明有奇数个因子
• 所有因数的个数为奇数的自然数只有完全平方数

5 - 给一个01二项分布的随机器，参数为p，用它设计一个0-1的均匀分布的随机器（连续的）

• 使用两次随机器，结果是00,01,10,11，概率分别为（1-p)(1-p), (1-p)p, p(1-p), pp，把01和10两种情况保留，其他两种情况抛弃，将01作为0, 10作为1

6 - 100人坐飞机，第一个乘客在座位中随便选一个坐下，第100人正确坐到自己坐位的概率是？

• 0.5
• 可以推广到任意k个乘客
• 等价描述：2 - k号乘客登机后如果发现1号坐在本属于自己的位置上，就会请1号离开，然后1号随机再找空位，当k号乘客登机时，2 - k-1号都在自己位置上，1号在自己位置与在k号位置的概率相同，所以0.5

7 - 一根绳子分成三段，围成三角形的概率

• 假设绳子长度为1，三段分别为x，y，1-x-y，满足三角形三边关系：两边之和大于第三边，得到x+y>0.5，y<0.5，x<0.5，通过面积比例求得概率

8 - 25匹马，5个赛道，最快几次求出前三名

• 5+1+1=7
• 分成五组A-E，假设每组赛后成绩降序排列为1-5：5次
• 将每组的第一名A1-E1，五个跑一次，假设成绩降序为A1、B1、C1、D1、E1：1次
• 已知D组与E组第一名都进不了前三，所以这两组不再考虑，同理C组只有C1可能前三，B组只有B1、B2有可能前三
• A1确定是最快的那匹马，问题变成求出第二名与第三名