c*e
发帖数: 15 | 1 因为没见过这个题，所以想了好半天才答上来
面试感觉一般，答得不顺利，move on了
一个很长的text文档，怎样遍历一边，随机输出其中的一行
限制：
1.只能遍历一边
2.随机均匀分配
================
我的答案是：
保存已经遍历的行中的一个preLine
每读入第n行，在line_n和preLine中选一个，update preLine.
line_n的概率是1/n, preLine的概率是(n-1)/n
读到文件尾return preLine. | l*x
发帖数: 14021 | 2 I can think of two possible solutions, in both solutions we calculated the
random number first.
1. Since it is a text file, can we get the size of the file? As we read
through the file, we can calculate the size of all the lines have been read.
Once the size read / size all = the random number, the current line is the
line to return.
2. If the random number is X out of 100, save the lines from (x/100) *
current total to the current line. e.g is X is 50 out of 100, current total
line number is 20, save lines 10 to 20. Once we reach the end of the file,
the first line being saved is the line to be returned. This way, we can only
need to save up to half of the whole file.
If the X is less than 50/100, assume we can read the file backward. | c*******t
发帖数: 1095 | 3 LZ right answer
LS complicated and may not be allowed | l*x
发帖数: 14021 | 4 汗，读贴不仔细。以为LZ保存读过的每条line。 | k*******a
发帖数: 772 | 5 这个不是老题目了吗
用一个cache
读第一行，保存
第二行，1/2概率 replace
第三行，1/3概率 replace
。。。
第n行， 1/n概率 replace |
|
