目录

• 场景题
• 智力题

场景题

假设有 40 亿 QQ 号，但只有 1G 内存，如何实现去重？

• 布隆过滤器：部分数据可能误判。
• 位数组 （BitMap） ：用 QQ 号为下标的空间存储 0（不存在）和 1（存在），占用空间 4000000000 bit / 1024 / 1024 / 1024 / 8 = 0.465 GB。
   

10 GB 文件找出重复最多的数字
将数字按照区间分块，找出每个区间重复最多的数字及出现次数，再排序各区间的次数。

抢红包如何设计随机？

• 实时分配 / 提前分配
• 保证均值：例如一个 100 的红包十个人抢，第一个人在 0-20 的范围内随机，后续的人根据前面的人抢的红包大小调整上限，这样保证了均值，但后面的方差会变大。
• 设置上、下界限
• ......
   

智力题

1000 个草堆有 1 个有毒，怎么用尽量少的兔子去找出？
2^10 = 1024 ，每一个草堆的编号转换为二进制，让 10 只兔子去对应草堆编号的 10 个位，位为 1 则让对应兔子吃一口，根据 10 只兔子的死亡情况得到二进制编号来唯一确定草堆，最多用掉 9 只兔子。

25 只马每次只能比较 5 只，最少多少次决出前三名？

1. 分为 5 组决出每一组顺序，5 次；
2. 每组的第 1 名比赛一次，决出第一名，1 次；
3. 此时只剩下第 1 名组的 2, 3 名、第 2 名组的 1, 2 名，第 3 名组的第 1 名，这 5 只再比赛一次，决出第二、三名，1 次；
4. 共 7 次比赛决出前三名。
    

8 个小球找出其中 1 个重量比其它重的要几次？

1. 取 6 个小球，天平两端各放 3 个；
2. 如果一样重，剩下的 2 个小球再比较一次；
3. 如果不一样重，在重的 3 个小球里任选 2 个比较；
4. 故 8 个球最多 2 次。
5. N 个球： log3(n) 次。
    

5L 水桶 + 3L 水桶怎么取 4L 水？