今日面试题,蓄水池抽样,又称随机抽样问题,表示如下:

要求从N个元素中随机的抽取k个元素,其中N无法确定。

这种应用的场景一般是数据流的情况下,由于数据只能被读取一次,而且数据量很大,并不能全部保存,因此数据量N是无法在抽样开始时确定的;但又要保持随机性,于是有了这个问题。所以搜索网站有时候会问这样的问题。

这里的核心问题就是“随机”,怎么才能是随机的抽取元素呢?我们设想,买彩票的时候,由于所有彩票的中奖概率都是一样的,所以我们才是“随机的”买彩票。那么要使抽取数据也随机,必须使每一个数据被抽样出来的概率都一样。

Google 搜索之星分析

题目:

给你一天的Google搜索日志,你怎么设计算法找出是否有一个搜索词,它出现的频率占所有搜索的一半以上?如果肯定有一个搜索词占大多数,你能怎么提高你的算法找到它?再假定搜索日志就是内存中的一个数组,能否有O(1)空间,O(n)时间的算法?

分析:

首先要看清题目,说的是“一半以上”,“大多数”,"majority",也就是大于50%。

很多情形下,尤其在面试比较紧张的情形下,经常会下意识的很快得出一个如下的方法(这个没有错,能有解决方案胜于完全没想法)。定义一个哈希表,里面存放数组里面的每个元素以及出现的次数。可以通过两个过程来做。

第一步是映射,将每个元素放进去,存在加一,不存在置一。同时统计元素个数。

第二步是遍历整个哈希表,判断是否找到出现次数大于数组长度一半的。如果有,找到。否则没有。

显然,这个要求O(n)的空间在存储哈希表,并不理想。

另外的下意识的方法, 比如说,先将元素排序,然后再进行判断。因为如果有大多数的话,取数组中间点的那个元素即为所要找的那个。不过这种方法首先排序就需要O(NlogN)的时间复杂度,并不是很理想。

题中说到肯定有一个搜索词是大多数,这个条件可能蕴藏着提高的空间。

面试时,我们会经常写下一个例子,手工做些运算,也许能找到好的方案。

比如,1,2,2,3,2,2,3  显然2是多数元素 去除1,2,在2,3,2,2,3 中2仍是多数元素 去除1,3,在2,3,2,2,3 中2更是多数元素

再比如,1,3,2,3,2,2,3  显然没有多数元素 去除1,3,在2,3,2,2,3 中2成了多数

观察结论:在原序列中去除两个不同的元素后,那么在原序列中的多数元素在新序列中还是多数元素。但新序列中的多数元素在原序列不一定是多数,所以需要验证。但原题说是肯定有多数,所以我们可以忽略验证。

基于这个观察,假设我们一开始从数组的开头,碰到某个元素的时候,就设置该元素为当前元素。当前出现的次数为1,后面,如果接着碰到的元素和该元素相同,则当前次数加1,否则减1。如果当前出现的次数为0,则表示当前元素不确定。如果结合我们有大多数元素这个前提的话,必然最后的结果是大于0的,而且最终获取到的值就是大多数元素。

对于这个大多数算法(Majority Algorithm), 国外有教授有研究并发表论文:《MJRTY - A Fast Majority Vote Algorithm》

本文来自微信:待字闺中,7月3日发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。