百度每天接受用户的搜索查询，总是不停有搜索query进入日志

[问答题]

百度每天接受用户的搜索查询，总是不停有搜索query进入日志。把query看作一个字符串，搜索日志就是一个字符串的数据流。这个字符串永不停止。如何在这个不断增加的字符串流序列中，随机选择一个字符串？如果随机选择10000个字符串呢？

我更牛

一个整数序列（n为多少不知道），要你从中随机取出k个数，每个数被选中的概率一样：

答案是前K个数放入k大小的数组，当前如果是K+1个数用（k/k+1）概率选中并和前K个数组中的元素随机替换。同理当选择K+2。。。。n的情况

证明如下：

数学归纳法

当n=K+1时：

第K+1个数选中的概率是（K/K+1）

第一个数选中的概率为 (1/K+1) + (K/K+1)*(1 - K/K+1) = (K/K+1)

......

假设当n = m是前m个元素被选中的概率都是（K/M）

那么当你= m+1时：

易见第m+1个元素选中的概率为（K/m+1）

那么第一个元素选中的概率是（K/m）*(n+1-k/n+1 + k/n+1 * k-1/k) = （K/m+1）

易见当n = m+1的时候也成立

发表于 2015-03-15 00:57:04 回复(0)

提交观点

问题信息

概率统计百度

上传者：小牧魔法袋

难度：

1条回答 23收藏 11150浏览

扫一扫，把题目装进口袋