今天百度的一道笔试题
由于存储空间有限，每天只能存储m个请求，每天的请求数量远大于m,请求数量不到最后时刻不会知道。
求一算法实现随机存储m个请求，每个请求被存储的概率都一样
[解决办法]
先存储m个,
当第N(N>m)个请求来时,m/N概率存储该请求,随机替换m个存储好的请求中的一个.
[解决办法]
我今天也参加了百度的笔试题目，我的思路是这样的。。
如果用户查询的数量小于m，那么直接就存起来。如果用户查询的数量大于m，假设为m+i，那么在1-----m+i之间随机产生一个数，如果选择的是前面m条查询进行存取，那么概率为m/（m+i），如果选择的是后面i条记录中的查询，那么用这个记录来替换前面m条查询记录的概率为m/（m+i）*（1-1/m）=(m-1)/(m+i)，当查询记录量很大的时候，m/（m+i）== (m-1)/(m+i)，所以每个query被抽中的概率是相等的。
[解决办法]
设f(x)是保留下来的概率，按照1L的方法推导公式如下：
f(i) = 1 when i belongs to [1,m]
so， f(m) = 1 = m/m
f(i) = m/(i-1) * ( 1 - ( (m/i) / m ) ) = m/i , when i > m
[解决办法]
假设存储空间是m个，当前处理到n个。
当n=m时，把所有n都放入m中
当n=m+1时，生成1到m+1的随机数，若是1则，用新数替换m里随机位置的一个的数。
从n到n+1时，生成1到n+1的随机数，若是1则，用新数替换m里随机位置的一个的数。
