由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 请教一道题目
相关主题
问一个面试题An interview question about probability. (转载)
一道概率题Pick k lines from a large file randomly uniformly distributed
[合集] 微软面试题一道What is the best way to choose a random value in a stream?
Amazon onsite 面试形式变了?[合集] 那个Google random generate 1-7的题怎么做啊?
random(5) generate random(7)randomized quick sort的最坏情况时间复杂度
一道概率题目问一下shuffle card问题
在线等一道面试probability题的答案,谢谢~前段时间整理的随机算法
问一道Amazon的老题问个题
相关话题的讨论汇总
话题: given话题: num话题: 160话题: 一道话题: line
进入JobHunting版参与讨论
1 (共1页)
c*****o
发帖数: 178
1
在glassdoor上看到一道题目:
Given a file of unknown size, devise an algorithm to give equal probability
randomization to choosing a single line given a one line buffer space.
请教思路?
r**u
发帖数: 1567
2
这个刚有人总结过,我copy&paste。
要求从N个元素中随机的抽取1个元素, 其中N无法确定(数据流)。
int Num;
int i = 0;
int choose = 0;
while(scanf("%d", &Num)&& Num != 0){
   if (((double)rand()/(double)RANDOM_MAX) < (1.0 / (double)++i))
      choose = Num;
}
cout << choose < 总是选择第一行, 二分之一几率选择第二行, 以此类推, K分之一机率选择第K行,
当while 执行完毕,假设N个数字,则每个数字被选择的机率均为1/N
第一行被选择的机率为:
1 * 1/2 * 2/3 * 3/4 *.... (N-1)/N = 1/N
第K行被选择的机率为:
1/K * K/(K+1) * .... (N-1)/N = 1/N

probability

【在 c*****o 的大作中提到】
: 在glassdoor上看到一道题目:
: Given a file of unknown size, devise an algorithm to give equal probability
: randomization to choosing a single line given a one line buffer space.
: 请教思路?

1 (共1页)
进入JobHunting版参与讨论
相关主题
问个题random(5) generate random(7)
求问一个题一道概率题目
问一道google面试题在线等一道面试probability题的答案,谢谢~
Now can anyone have the idea about the chance of ADV?问一道Amazon的老题
问一个面试题An interview question about probability. (转载)
一道概率题Pick k lines from a large file randomly uniformly distributed
[合集] 微软面试题一道What is the best way to choose a random value in a stream?
Amazon onsite 面试形式变了?[合集] 那个Google random generate 1-7的题怎么做啊?
相关话题的讨论汇总
话题: given话题: num话题: 160话题: 一道话题: line