今日面试题:忘我之乘积

给你一个数组A[1..n],请你在O(n)的时间里构造一个新的数组B[1..n],使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法运算。

蓄水池抽样(Reservoir Sampling)问题分析

问题:

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

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

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

分析:

由于N无法确定,数据只能读取一次,并且要求随机,就是每个元素抽出的概率一样,都是k/N

面试的时候,经常会在纸上通过一个小的例子来找到好的解决方案。比如先让你从100个元素中等概率抽取出10个元素。后来又向集合中添加了20个元素,变成了120个元素等概率抽取10个,怎么样才能随着N的动态改变而让N无论等于多少时这N个元素都等概率被抽取呢?

解法一:最小k个指纹

找到一个哈希函数能产生随机数,同时用一个k个元素的堆用来保存最小的k个元素。那么过一遍所有的元素,计算每个的哈希值,通过堆来选择k个元素。

这个算法看起来很精妙,会有什么问题吗?(思考)

解法二:数学计算

先选中前k个, 从第k+1个元素到最后一个元素为止, 以1/i  (i=k+1, k+2,...,N) 的概率选中第i个元素, 并且随机替换掉一个原先选中的元素, 这样遍历一次得到k个元素, 可以保证完全随机选取。

看来简单的算法,怎么能确保每个元素被选中的概率是k/N?

任意元素G在i轮留下来的概率:

P(G留下) = P(G已经存在) * P(G没有被替换)  
         = P(G已经存在) * (1 - P(G被替换))  
         = P(G已经存在) * (1 - P(第i个元素要替换某个元素) * P(某个元素是G))  
         = (k/i) * (1 - (k/(i+1)) * (1/k))  
         = (k/i) * (1 - (1/(i+1)))  
         = (k/i) * (i/(i+1))  
         = (k/(i+1))  

证毕!

这个题有很多的变种,比如,

给你一个长度为N的链表。N很大,但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个,且它们是完全随机的(出现概率均等)。

从一个不知长度的文件中随机抽出k行。

从实时的搜索词中随机抽出k个词。

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