面试题

1. 引言
问题：有1000瓶药，但是其中有一瓶是有毒的，小白鼠吃了24小时后就会死掉，请问，在24小时找出有毒的药物，最少需要多少只小白鼠？
答案是：10只，一只小白鼠可以表示2种状态，2^10可以表示1024种状态
分析可参考：http://lzj0470.iteye.com/blog/657579
通过二进制向量组来扩展描述的状态，Bloom Filter(BF)算法也是利用这个思想，其本质是上是一个很长的二进制向量和一系列随机映射函数

2. 概述
问题：快速判断一个元素是否在一个集合中
解决方法：一般来说，我们会用HASH表来存储集合中的数据，好处是快速准确，缺点是存储效率低，在海量数据时一般服务器无法存储。
BF是针对哈希表存储效率低的问题，而衍生出来的一种算法。
其通过利用二进制数组来描述一个集合，来判断一个元素是否属于这个集合
优点是：快速查找，并具有非常高的存储效率
缺点是：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合

3. 算法描述
BF包含：
1)一个m位的二进位数组，每一位初始化时置为0
2)k个相互独立的hash函数
算法：
针对一个n个元素的集合，通过k个hash函数，将集合中的每个元素都映射到二进位数组中，映射到的位置置为1
例如：对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1
在判断某个元素P是否在这个集合时，通过对P应用k次hash函数，判断其对应所有的位置都是1，如果是则认为P是集合中的元素，否则不是。

4. 最优位数组m大小及hash函数个数
在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合。因此，如何根据输入元素个数n，确定位数组m的大小及hash函数个数是一个非常重要的问题。
经过一些复杂的证明（可参考相关文档），可以得到：
1）当hash函数个数k=(ln2)*(m/n)时错误率最小
2）在错误率不大于E的情况 下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合，但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)的1.44倍

5. 应用
有10亿个url，如何判断一个新的url是否在这个url的集合中？
一个url平均长度为52，如果用Hash表解决的话，由于Hash表的存储效率一般只有50%，因此10个url大概需要100G内存，一般服务器无法存储。
使用BF，要求错误率小于万分之一。
此时，输入元素n=10亿，最大错误率E=0.0001
可计算出：m=nlg(1/E)*1.44=57.6亿，大概需要7.2亿（57.6亿/8）个字节，即720M内存。
Hash函数个数：k=(ln2)*(m/n)  大概4个Hash函数

6.总结
BF通过牺牲一定的错误率来保证时间和空间（鱼与熊掌，不可兼得），目前被广泛应用于海量数据处理及数据库系统中。
例如，在Big table和Cassandra中，都使用BF作为索引结构。
P.S 针对BF的错误识别问题，可以通过建立白名单的方式解决。

参考文献：
paper：Network Applications of Bloom Filters: A Survey
http://blog.csdn.net/jiaomeng/article/details/1495500

 

迅雷面试题

1.给你10台机器，每个机器2个cpu，2g内存，现在已知在10亿条记录的数据库里执行一次查询需要5秒，问用什么方法能让90%的查询能在100毫秒以内返回结果。
2.一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca,结果是bc。最后就做出这一道题目，时间复杂度为O(n!), 空间复杂度为O(n)。

算法题：
1.连接两个单向链表，返回排序后的结果。
2.一个保存有10000个URL的文本文件，删除其中相同的URL。
3.将9个石子放在9×9的方格中，要求同行、同列、45度上无两个石子。

智力题：
1.一笔画四条直线穿过3×3的9个点。
2.国王给三个囚犯每人戴了一顶帽子，帽子不是黑色就是白色，并且告诉囚犯们谁看到其它两个人都是白帽子或者知道自己戴的是黑帽子，谁就能被释放。囚犯们能看到其它的人帽子颜色，但是看不到自己的帽子颜色。过了一段时间，三个囚犯都没有说话，其中一个聪明的囚犯立刻肯定自己戴的是黑帽子，你知道为什么吗？
3.有16个硬币，A和B轮流拿，每次拿的个数只能是1，2，4之一，谁最后拿谁就输。问可以保证赢吗？?