i********m
发帖数: 332 | 1 刚面完的Yelp skype interview.
题目是这样的：I have a very large text file, many gigabytes. I want a
uniform random sample of exactly k lines. Write a program to read the file
and print the random sample.
We assume we have n lines in the file.
我说假设memory可以handle的话用一个hashmap就解决了， key 是行数，value 就是
string。 她说可以，但是如果memory不能handle怎么办。我说算一下string的
hashCode(). 她说可以 但是你怎么能根据hashCode() 找到String。 我说那就用一个B
+ 数建立index 吧。 然后告诉她怎么build这么一个B+树， 用bulk loading。然后她
说， good，你把她写出来吧。 我顿时就汗颜了，麻痹的1000多行的B+数
implementation 让我写出来不是扯淡么， 我说我用文字描述行不。 她说可以。 真心
蛋疼。 不知道有什么好方法可以不用B+树的 望指点。
开头20分钟问了我的project， 她是做search 的 ，问我的project怎么建的index，用
的什么方法， 怎么做的search， 这些我都high level的跟她说了说 ，她貌似都懂了
，但是问的这个问题实在是蛋疼啊。 大家给点意见。 |
x*******5
发帖数: 152 | 2 It seems fit reservoir sampling problem. Without knowing the total number,
but do want uniform k lines. B+ tree is overkill |
g****y
发帖数: 240 | |
i********m
发帖数: 332 | 4 什么是reservoir sampling 啊 这题要写code 要involve到底层 DB -> read() 和 DB
->write()的东西啊 这不扯淡么 还是说有什么好方法可以做出来的？ |
l*****a
发帖数: 14598 | 5 楼上的不是告诉你这个题目的名称了吗
你怎么还不去喳喳，反而在这里扯到什么DB上
DB
【在 i********m 的大作中提到】
: 什么是reservoir sampling 啊 这题要写code 要involve到底层 DB -> read() 和 DB
: ->write()的东西啊 这不扯淡么 还是说有什么好方法可以做出来的？
|
K*********n
发帖数: 2852 | 6 听说你Skype视频结束以后，一怒之下给对方发了一条消息：wocao
个B
【在 i********m 的大作中提到】
: 刚面完的Yelp skype interview.
: 题目是这样的：I have a very large text file, many gigabytes. I want a
: uniform random sample of exactly k lines. Write a program to read the file
: and print the random sample.
: We assume we have n lines in the file.
: 我说假设memory可以handle的话用一个hashmap就解决了， key 是行数，value 就是
: string。 她说可以，但是如果memory不能handle怎么办。我说算一下string的
: hashCode(). 她说可以 但是你怎么能根据hashCode() 找到String。 我说那就用一个B
: + 数建立index 吧。 然后告诉她怎么build这么一个B+树， 用bulk loading。然后她
: 说， good，你把她写出来吧。 我顿时就汗颜了，麻痹的1000多行的B+数
|
K*********n
发帖数: 2852 | 7 电面考到这个是不是有点过分啊……
【在 g****y 的大作中提到】
: reservoir sampling
|
D**********d
发帖数: 849 | 8 不如先 random sample k 个 在 1...S 里的数，然后直接 取相应的行数。这样只是 O
(K), 用 reservoir sampling 要 O(S). |
i********m
发帖数: 332 | 9 是啊 面完一激动打了一个 wocao 给那个interview的人 然后立马说 sorry it's a
typo |
h****n
发帖数: 2094 | 10 完全不对路。当然让你写B树
哈哈。
个B
【在 i********m 的大作中提到】
: 刚面完的Yelp skype interview.
: 题目是这样的：I have a very large text file, many gigabytes. I want a
: uniform random sample of exactly k lines. Write a program to read the file
: and print the random sample.
: We assume we have n lines in the file.
: 我说假设memory可以handle的话用一个hashmap就解决了， key 是行数，value 就是
: string。 她说可以，但是如果memory不能handle怎么办。我说算一下string的
: hashCode(). 她说可以 但是你怎么能根据hashCode() 找到String。 我说那就用一个B
: + 数建立index 吧。 然后告诉她怎么build这么一个B+树， 用bulk loading。然后她
: 说， good，你把她写出来吧。 我顿时就汗颜了，麻痹的1000多行的B+数
|
|
|
g*****e
发帖数: 282 | 11 +1
O
【在 D**********d 的大作中提到】
: 不如先 random sample k 个 在 1...S 里的数，然后直接 取相应的行数。这样只是 O
: (K), 用 reservoir sampling 要 O(S).
|
i********m
发帖数: 332 | 12 大家说说我最后打了一个wocao过去不会有事吧 她不会去google吧
当时一激动 没来得及看当前的窗口就直接发过去了 后悔啊 |
C***U
发帖数: 2406 | 13 你好逗
哈哈
【在 i********m 的大作中提到】
: 是啊 面完一激动打了一个 wocao 给那个interview的人 然后立马说 sorry it's a
: typo
|
i********m
发帖数: 332 | 14 这题能不能这么做。
用一个random generator每次generate一个0到1的数 say ram
每次用k/n 和 这个 ram 比较， 如果k/n=，throw away
然后去下一行。 |
s******x
发帖数: 417 | |
s**r
发帖数: 390 | 16 这样会出现重复的吧
O
【在 D**********d 的大作中提到】
: 不如先 random sample k 个 在 1...S 里的数，然后直接 取相应的行数。这样只是 O
: (K), 用 reservoir sampling 要 O(S).
|
i********m
发帖数: 332 | 17 这个挂了是肯定的 就怕影响以后啊
【在 s******x 的大作中提到】
: http://www.profanechinese.com/profanechinese.com.test/forums/ch
: 这个是wo cao的google第一搜索答案，如果HR去搜，你肯定挂。
|
c********t
发帖数: 5706 | 18 又学习了，可是看看下面wiki解释的sudo codes，不是uniform啊，i=k+1时候被置换的
概率比 i 极大的时候高很多啊。
array R[k]; // result
integer i, j;
// fill the reservoir array
for each i in 1 to k do
R[i] := S[i]
done;
// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
j := random(1, i); // important: inclusive range
if j <= k then
R[j] := S[i]
fi
done
【在 g****y 的大作中提到】
: reservoir sampling
|
c********t
发帖数: 5706 | 19 好像可以，可是会这么简单吗？
O
【在 D**********d 的大作中提到】
: 不如先 random sample k 个 在 1...S 里的数，然后直接 取相应的行数。这样只是 O
: (K), 用 reservoir sampling 要 O(S).
|
B***i
发帖数: 724 | 20 这个题我也出过。 本来是 要给一个同胞放水的。 sigh.
给总行数n是最简单的一种case. 解法就是先随机生成k个1..n之间的随机数，然后一次
遍历下去，遇到相应的数字就输出。 就是那么简单。这种方法对付sampling with /
without replacement 都管用。
稍微再难点，不知道n. 当然可以先一遍扫描求出n.
其实这些都是垫场热身的。 后面的问题是要用map-reduce的方法在极大的data下
sample. map-reduce 可以求n, 但是不好给每个sample一个序列号。
类似的问题有求中位数， 求99 percentile之类的。 |
|
|
l*****n
发帖数: 577 | 21 what is 99 percentile ? |
e***s
发帖数: 799 | 22 是uniform的，你看wiki有关reservoir sampling 的中文版，有证明。
【在 c********t 的大作中提到】
: 又学习了，可是看看下面wiki解释的sudo codes，不是uniform啊，i=k+1时候被置换的
: 概率比 i 极大的时候高很多啊。
: array R[k]; // result
: integer i, j;
: // fill the reservoir array
: for each i in 1 to k do
: R[i] := S[i]
: done;
: // replace elements with gradually decreasing probability
: for each i in k+1 to length(S) do
|
e***s
发帖数: 799 | 23 这样可以吗？
第一，我们应该是不知道S啊，怎么random（1， S)
第二，有可能出现重复。
O
【在 D**********d 的大作中提到】
: 不如先 random sample k 个 在 1...S 里的数，然后直接 取相应的行数。这样只是 O
: (K), 用 reservoir sampling 要 O(S).
|
m*****k
发帖数: 731 | 24 是这个八
http://blog.csdn.net/wuzhekai1985/article/details/6597351
eg4.12：有一个长度为N的链表，N未知。希望你只遍历一次链表，就从链表中等概率
的挑出K个数。 -- TopLanguage
某博客的解法，非常好 http://blog.csdn.net/potty15/article/details/6221715
a：首先挑出前k个数，保存在pick[1...k]中，然后从第k+1个开始遍历
for i = k+1 to N do //这里N不知道，但是可以用链表->next == null 来判断是否到
达链表末尾。
r = random(1, i);
if (1 <= r <= k);
pick[r] = i;
简单数学证明如下：
归纳法，算法刚开始，对于前k个数被选中的概率都为1，，不失一般性，选择其中的第
j个来讨论，
i = k+1轮：
random(1, i)返回值为j的概率为1/k+1，所以j保留下来的概率为k/k+1
i = k+2轮：
random(1, i)返回值为j的概率为1/k+2，所以j保留下来的概率为(k/k+1) * (k+1/k+2)
= k/k+2
...
i = N轮
random(1, i)返回值为j的概率为1/N，所以j保留下来的概率为(k/k+1) * (k+1/k+2)*.
...* (N-1/N) = k/N
对于第k+1到第N个数，选择其中的数m来讨论，
当i = m时：
random(1, i)返回值在[1, k]内的概率为k/m，所以j保留下来的概率为k/m，设m保存在
第s位
i = m+1轮：
random(1, i)返回值为s的概率为1/(m+1)，所以j保留下来的概率为(k/m) * (m/m+1) =
k/(m+1)
...
i = N轮
random(1, i)返回值为s的概率为1/N，所以j保留下来的概率为(8/m) * (m/m+1) *....
* (N-1/N) = k/N
得证。
个B
【在 i********m 的大作中提到】
: 刚面完的Yelp skype interview.
: 题目是这样的：I have a very large text file, many gigabytes. I want a
: uniform random sample of exactly k lines. Write a program to read the file
: and print the random sample.
: We assume we have n lines in the file.
: 我说假设memory可以handle的话用一个hashmap就解决了， key 是行数，value 就是
: string。 她说可以，但是如果memory不能handle怎么办。我说算一下string的
: hashCode(). 她说可以 但是你怎么能根据hashCode() 找到String。 我说那就用一个B
: + 数建立index 吧。 然后告诉她怎么build这么一个B+树， 用bulk loading。然后她
: 说， good，你把她写出来吧。 我顿时就汗颜了，麻痹的1000多行的B+数
|
i********m
发帖数: 332 | 25 刚面完的Yelp skype interview.
题目是这样的：I have a very large text file, many gigabytes. I want a
uniform random sample of exactly k lines. Write a program to read the file
and print the random sample.
We assume we have n lines in the file.
我说假设memory可以handle的话用一个hashmap就解决了， key 是行数，value 就是
string。 她说可以，但是如果memory不能handle怎么办。我说算一下string的
hashCode(). 她说可以 但是你怎么能根据hashCode() 找到String。 我说那就用一个B
+ 数建立index 吧。 然后告诉她怎么build这么一个B+树， 用bulk loading。然后她
说， good，你把她写出来吧。 我顿时就汗颜了，麻痹的1000多行的B+数
implementation 让我写出来不是扯淡么， 我说我用文字描述行不。 她说可以。 真心
蛋疼。 不知道有什么好方法可以不用B+树的 望指点。
开头20分钟问了我的project， 她是做search 的 ，问我的project怎么建的index，用
的什么方法， 怎么做的search， 这些我都high level的跟她说了说 ，她貌似都懂了
，但是问的这个问题实在是蛋疼啊。 大家给点意见。 |
x*******5
发帖数: 152 | 26 It seems fit reservoir sampling problem. Without knowing the total number,
but do want uniform k lines. B+ tree is overkill |
g****y
发帖数: 240 | |
i********m
发帖数: 332 | 28 什么是reservoir sampling 啊 这题要写code 要involve到底层 DB -> read() 和 DB
->write()的东西啊 这不扯淡么 还是说有什么好方法可以做出来的？ |
l*****a
发帖数: 14598 | 29 楼上的不是告诉你这个题目的名称了吗
你怎么还不去喳喳，反而在这里扯到什么DB上
DB
【在 i********m 的大作中提到】
: 什么是reservoir sampling 啊 这题要写code 要involve到底层 DB -> read() 和 DB
: ->write()的东西啊 这不扯淡么 还是说有什么好方法可以做出来的？
|
K*********n
发帖数: 2852 | 30 听说你Skype视频结束以后，一怒之下给对方发了一条消息：wocao
个B
【在 i********m 的大作中提到】
: 刚面完的Yelp skype interview.
: 题目是这样的：I have a very large text file, many gigabytes. I want a
: uniform random sample of exactly k lines. Write a program to read the file
: and print the random sample.
: We assume we have n lines in the file.
: 我说假设memory可以handle的话用一个hashmap就解决了， key 是行数，value 就是
: string。 她说可以，但是如果memory不能handle怎么办。我说算一下string的
: hashCode(). 她说可以 但是你怎么能根据hashCode() 找到String。 我说那就用一个B
: + 数建立index 吧。 然后告诉她怎么build这么一个B+树， 用bulk loading。然后她
: 说， good，你把她写出来吧。 我顿时就汗颜了，麻痹的1000多行的B+数
|
|
|
K*********n
发帖数: 2852 | 31 电面考到这个是不是有点过分啊……
【在 g****y 的大作中提到】
: reservoir sampling
|
D**********d
发帖数: 849 | 32 不如先 random sample k 个 在 1...S 里的数，然后直接 取相应的行数。这样只是 O
(K), 用 reservoir sampling 要 O(S). |
i********m
发帖数: 332 | 33 是啊 面完一激动打了一个 wocao 给那个interview的人 然后立马说 sorry it's a
typo |
h****n
发帖数: 2094 | 34 完全不对路。当然让你写B树
哈哈。
个B
【在 i********m 的大作中提到】
: 刚面完的Yelp skype interview.
: 题目是这样的：I have a very large text file, many gigabytes. I want a
: uniform random sample of exactly k lines. Write a program to read the file
: and print the random sample.
: We assume we have n lines in the file.
: 我说假设memory可以handle的话用一个hashmap就解决了， key 是行数，value 就是
: string。 她说可以，但是如果memory不能handle怎么办。我说算一下string的
: hashCode(). 她说可以 但是你怎么能根据hashCode() 找到String。 我说那就用一个B
: + 数建立index 吧。 然后告诉她怎么build这么一个B+树， 用bulk loading。然后她
: 说， good，你把她写出来吧。 我顿时就汗颜了，麻痹的1000多行的B+数
|
g*****e
发帖数: 282 | 35 +1
O
【在 D**********d 的大作中提到】
: 不如先 random sample k 个 在 1...S 里的数，然后直接 取相应的行数。这样只是 O
: (K), 用 reservoir sampling 要 O(S).
|
i********m
发帖数: 332 | 36 大家说说我最后打了一个wocao过去不会有事吧 她不会去google吧
当时一激动 没来得及看当前的窗口就直接发过去了 后悔啊 |
C***U
发帖数: 2406 | 37 你好逗
哈哈
【在 i********m 的大作中提到】
: 是啊 面完一激动打了一个 wocao 给那个interview的人 然后立马说 sorry it's a
: typo
|
i********m
发帖数: 332 | 38 这题能不能这么做。
用一个random generator每次generate一个0到1的数 say ram
每次用k/n 和 这个 ram 比较， 如果k/n=，throw away
然后去下一行。 |
s******x
发帖数: 417 | |
s**r
发帖数: 390 | 40 这样会出现重复的吧
O
【在 D**********d 的大作中提到】
: 不如先 random sample k 个 在 1...S 里的数，然后直接 取相应的行数。这样只是 O
: (K), 用 reservoir sampling 要 O(S).
|
|
|
i********m
发帖数: 332 | 41 这个挂了是肯定的 就怕影响以后啊
【在 s******x 的大作中提到】
: http://www.profanechinese.com/profanechinese.com.test/forums/ch
: 这个是wo cao的google第一搜索答案，如果HR去搜，你肯定挂。
|
c********t
发帖数: 5706 | 42 又学习了，可是看看下面wiki解释的sudo codes，不是uniform啊，i=k+1时候被置换的
概率比 i 极大的时候高很多啊。
array R[k]; // result
integer i, j;
// fill the reservoir array
for each i in 1 to k do
R[i] := S[i]
done;
// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
j := random(1, i); // important: inclusive range
if j <= k then
R[j] := S[i]
fi
done
【在 g****y 的大作中提到】
: reservoir sampling
|
c********t
发帖数: 5706 | 43 好像可以，可是会这么简单吗？
O
【在 D**********d 的大作中提到】
: 不如先 random sample k 个 在 1...S 里的数，然后直接 取相应的行数。这样只是 O
: (K), 用 reservoir sampling 要 O(S).
|
B***i
发帖数: 724 | 44 这个题我也出过。 本来是 要给一个同胞放水的。 sigh.
给总行数n是最简单的一种case. 解法就是先随机生成k个1..n之间的随机数，然后一次
遍历下去，遇到相应的数字就输出。 就是那么简单。这种方法对付sampling with /
without replacement 都管用。
稍微再难点，不知道n. 当然可以先一遍扫描求出n.
其实这些都是垫场热身的。 后面的问题是要用map-reduce的方法在极大的data下
sample. map-reduce 可以求n, 但是不好给每个sample一个序列号。
类似的问题有求中位数， 求99 percentile之类的。 |
l*****n
发帖数: 577 | 45 what is 99 percentile ? |
e***s
发帖数: 799 | 46 是uniform的，你看wiki有关reservoir sampling 的中文版，有证明。
【在 c********t 的大作中提到】
: 又学习了，可是看看下面wiki解释的sudo codes，不是uniform啊，i=k+1时候被置换的
: 概率比 i 极大的时候高很多啊。
: array R[k]; // result
: integer i, j;
: // fill the reservoir array
: for each i in 1 to k do
: R[i] := S[i]
: done;
: // replace elements with gradually decreasing probability
: for each i in k+1 to length(S) do
|
e***s
发帖数: 799 | 47 这样可以吗？
第一，我们应该是不知道S啊，怎么random（1， S)
第二，有可能出现重复。
O
【在 D**********d 的大作中提到】
: 不如先 random sample k 个 在 1...S 里的数，然后直接 取相应的行数。这样只是 O
: (K), 用 reservoir sampling 要 O(S).
|
m*****k
发帖数: 731 | 48 是这个八
http://blog.csdn.net/wuzhekai1985/article/details/6597351
eg4.12：有一个长度为N的链表，N未知。希望你只遍历一次链表，就从链表中等概率
的挑出K个数。 -- TopLanguage
某博客的解法，非常好 http://blog.csdn.net/potty15/article/details/6221715
a：首先挑出前k个数，保存在pick[1...k]中，然后从第k+1个开始遍历
for i = k+1 to N do //这里N不知道，但是可以用链表->next == null 来判断是否到
达链表末尾。
r = random(1, i);
if (1 <= r <= k);
pick[r] = i;
简单数学证明如下：
归纳法，算法刚开始，对于前k个数被选中的概率都为1，，不失一般性，选择其中的第
j个来讨论，
i = k+1轮：
random(1, i)返回值为j的概率为1/k+1，所以j保留下来的概率为k/k+1
i = k+2轮：
random(1, i)返回值为j的概率为1/k+2，所以j保留下来的概率为(k/k+1) * (k+1/k+2)
= k/k+2
...
i = N轮
random(1, i)返回值为j的概率为1/N，所以j保留下来的概率为(k/k+1) * (k+1/k+2)*.
...* (N-1/N) = k/N
对于第k+1到第N个数，选择其中的数m来讨论，
当i = m时：
random(1, i)返回值在[1, k]内的概率为k/m，所以j保留下来的概率为k/m，设m保存在
第s位
i = m+1轮：
random(1, i)返回值为s的概率为1/(m+1)，所以j保留下来的概率为(k/m) * (m/m+1) =
k/(m+1)
...
i = N轮
random(1, i)返回值为s的概率为1/N，所以j保留下来的概率为(8/m) * (m/m+1) *....
* (N-1/N) = k/N
得证。
个B
【在 i********m 的大作中提到】
: 刚面完的Yelp skype interview.
: 题目是这样的：I have a very large text file, many gigabytes. I want a
: uniform random sample of exactly k lines. Write a program to read the file
: and print the random sample.
: We assume we have n lines in the file.
: 我说假设memory可以handle的话用一个hashmap就解决了， key 是行数，value 就是
: string。 她说可以，但是如果memory不能handle怎么办。我说算一下string的
: hashCode(). 她说可以 但是你怎么能根据hashCode() 找到String。 我说那就用一个B
: + 数建立index 吧。 然后告诉她怎么build这么一个B+树， 用bulk loading。然后她
: 说， good，你把她写出来吧。 我顿时就汗颜了，麻痹的1000多行的B+数
|
e***s
发帖数: 799 | 49 谢谢你的证明过程，我总算看懂了
【在 m*****k 的大作中提到】
: 是这个八
: http://blog.csdn.net/wuzhekai1985/article/details/6597351
: eg4.12：有一个长度为N的链表，N未知。希望你只遍历一次链表，就从链表中等概率
: 的挑出K个数。 -- TopLanguage
: 某博客的解法，非常好 http://blog.csdn.net/potty15/article/details/6221715
: a：首先挑出前k个数，保存在pick[1...k]中，然后从第k+1个开始遍历
: for i = k+1 to N do //这里N不知道，但是可以用链表->next == null 来判断是否到
: 达链表末尾。
: r = random(1, i);
: if (1 <= r <= k);
|
e***s
发帖数: 799 | 50 谢谢你的证明过程，我总算看懂了
【在 m*****k 的大作中提到】
: 是这个八
: http://blog.csdn.net/wuzhekai1985/article/details/6597351
: eg4.12：有一个长度为N的链表，N未知。希望你只遍历一次链表，就从链表中等概率
: 的挑出K个数。 -- TopLanguage
: 某博客的解法，非常好 http://blog.csdn.net/potty15/article/details/6221715
: a：首先挑出前k个数，保存在pick[1...k]中，然后从第k+1个开始遍历
: for i = k+1 to N do //这里N不知道，但是可以用链表->next == null 来判断是否到
: 达链表末尾。
: r = random(1, i);
: if (1 <= r <= k);
|
|
|
s*********n
发帖数: 191 | 51 这个题目很简单啊，cc150里概率一章的原题啊，怎么可能用B+树呢...扯得太远了吧。
【在 e***s 的大作中提到】
: 谢谢你的证明过程，我总算看懂了
|
f****l
发帖数: 8042 | 52 It's pronounced with two falling tones, so it sounds roughly like the
American English "Fuck me!" Essentially, that's about what it means,
although the "Wo" isn't actually "I" .
你查到的这个解释很有点...把宾主关系搞反了吧。
【在 s******x 的大作中提到】
: http://www.profanechinese.com/profanechinese.com.test/forums/ch
: 这个是wo cao的google第一搜索答案，如果HR去搜，你肯定挂。
|
