a******8
发帖数: 90 | 1 1. 一个log里有页面的访问记录，如何获得前1000popular的（hash_map + heap）
followup,log里存在多个machine里，我原先说每个maintain heap,后来经提醒不work,
改用每个存heap，然后merge，再提了些优化的方案.面试官基本满意。
2.一个很大的table存了query -> occurrence,如何随机获得1个query,概率是基于每个
query的occurrence,
1 2 3
20 10 30
获得第一个数的概率是 20/60.
这题我很纠结，我上来就想到因为大数据量，用resevior sampling的变版做（
constant space），边想边写边测弄了快半小时才弄出来，最后也解释了半天，其实也
有很直接的方法，把累加做个数组就行了，用bst搜素log(n)，当时面试就是有点一根
筋。最后问了问组的情况，听口音感觉是同胞里的一个大牛，希望能水过。（突然想起
来介绍的时候他的名字不像是同胞的） |
b****g
发帖数: 192 | 2 谢谢分享，第一题是什么意思？
每个机器都维持一个min heap，最后再把这些heap们merge到一起吗？
work,
【在 a******8 的大作中提到】
: 1. 一个log里有页面的访问记录，如何获得前1000popular的（hash_map + heap）
: followup,log里存在多个machine里，我原先说每个maintain heap,后来经提醒不work,
: 改用每个存heap，然后merge，再提了些优化的方案.面试官基本满意。
: 2.一个很大的table存了query -> occurrence,如何随机获得1个query,概率是基于每个
: query的occurrence,
: 1 2 3
: 20 10 30
: 获得第一个数的概率是 20/60.
: 这题我很纠结，我上来就想到因为大数据量，用resevior sampling的变版做（
: constant space），边想边写边测弄了快半小时才弄出来，最后也解释了半天，其实也
|
a******8
发帖数: 90 | 3 嗯，是的
【在 b****g 的大作中提到】
: 谢谢分享，第一题是什么意思？
: 每个机器都维持一个min heap，最后再把这些heap们merge到一起吗？
:
: work,
|
b****g
发帖数: 192 | 4 谢谢
第二题：
我看你用了binary search找那个数，耗时O（lg n），但是前面把数组累加已经耗时O
（n）了，
有没有办法耗时O（lg n）？
【在 a******8 的大作中提到】
: 嗯，是的
|
j*****y
发帖数: 1071 | 5 第二题: 对于小的 case怎么做阿
比如
1 2 3
20 10 30
那么 frequence 的sum 是 60
那么产生一个 [1 60] 之间的随机数 r
如果 r <= 20 , 返回 1
否则如果 r <=30 ， 返回 2
否则 返回 3
问题是出来一个随机数 r, 怎么有效判断它所在的区间呢？
work,
【在 a******8 的大作中提到】
: 1. 一个log里有页面的访问记录，如何获得前1000popular的（hash_map + heap）
: followup,log里存在多个machine里，我原先说每个maintain heap,后来经提醒不work,
: 改用每个存heap，然后merge，再提了些优化的方案.面试官基本满意。
: 2.一个很大的table存了query -> occurrence,如何随机获得1个query,概率是基于每个
: query的occurrence,
: 1 2 3
: 20 10 30
: 获得第一个数的概率是 20/60.
: 这题我很纠结，我上来就想到因为大数据量，用resevior sampling的变版做（
: constant space），边想边写边测弄了快半小时才弄出来，最后也解释了半天，其实也
|
e******o
发帖数: 757 | |
j*****y
发帖数: 1071 | 7 怎么解决阿？ 多谢
【在 e******o 的大作中提到】
: 那么多的数累加不会overflow 么？
|
a******8
发帖数: 90 | 8 这是我当场写的，类似的思想是resevior sampling
1 2 3 4
40 30 20 10
int getO(int A[], int n)
{
//check n <= 1
int ret = 0;
int totalweight = A[0];
for(int i = 1; i < n; i++)
{
totalwieght += A[i];
int p = rand()%totalweight;
if(p <= A[i]) ret = i;//
}
return A[ret];
}
这个方法好处是不需要O（n)的空间，如果是支持多次查询，可以做一个array存累加值
，比如：
1 2 3 4
40 30 20 10
new array: 40 70 90 100
这样直接rand()%100,判断数落的空间，新建这个array要O(n),后面用binary search查
询,时间复杂度log(n).
大数据确实存在累加over flow,假如total weight远超过int size,而有一个weight就
是1，没法用正常方法取到。有个优化的方法就是对所有weight平均分下，先随机取出
期中一个，然后再进行上面的算法。在计算weight总值的时候要用到大数加减。不过面
试时间有限，这些都是后来想的。。。
【在 j*****y 的大作中提到】
: 第二题: 对于小的 case怎么做阿
: 比如
: 1 2 3
: 20 10 30
: 那么 frequence 的sum 是 60
: 那么产生一个 [1 60] 之间的随机数 r
: 如果 r <= 20 , 返回 1
: 否则如果 r <=30 ， 返回 2
: 否则 返回 3
: 问题是出来一个随机数 r, 怎么有效判断它所在的区间呢？
|
p*****p
发帖数: 379 | 9 for循环里每次rand一下和for外面rand一次应该概率不同吧？感觉p应该放到外面？
【在 a******8 的大作中提到】
: 这是我当场写的，类似的思想是resevior sampling
: 1 2 3 4
: 40 30 20 10
: int getO(int A[], int n)
: {
: //check n <= 1
: int ret = 0;
: int totalweight = A[0];
: for(int i = 1; i < n; i++)
: {
|
c**m
发帖数: 535 | 10 1. Find 1000 popular URLs in a log.
对于这种log里找popular URL的题目，首先肯定是要用hash去保存每一个URL的
frequency。然后对于返回top k：option 1， sort， O(nlogn)；option2，用一个
size为k的min_heap，O（nlogk）。
Follow up，如果log存在多个machine里，那么肯定是要merge result了。这个时候每
个machine如果只是存一个size为k的heap显然是不够的了。所以我们可以对于每个
machine：opt 1，sort the URL frequency；opt 2， use a min_heap to store all
URL frequency。这里个人感觉opt 1好一些。
2. Return a query based on the occurrence from a big table。
首先这个很大的table，也就是一个很大file，然后不能完全放入main memory里面，是
吧？那个这个其实跟“从一个大文件里随机取出一行”是一样道理的，只不过是加了
occurrence这个条件。思路就是依次从头开始取，然后统计，并且同时计算当前概率，
然后继续下一行。只需要扫描一遍即可。Pseudocode:
all_occur = 0;
chosen = “”;
for (query in table) {
this_occur = query.occurence;
all_occur += this_occur;
if (random(0, all_occur) <= this_occur) chosen = query;
}
return chosen;
还望大家指点～～ |
|
|
c**m
发帖数: 535 | 11 恩，你这个跟我想的一样。
【在 a******8 的大作中提到】
: 这是我当场写的，类似的思想是resevior sampling
: 1 2 3 4
: 40 30 20 10
: int getO(int A[], int n)
: {
: //check n <= 1
: int ret = 0;
: int totalweight = A[0];
: for(int i = 1; i < n; i++)
: {
|
j*****y
发帖数: 1071 | 12 thanks
all
【在 c**m 的大作中提到】
: 1. Find 1000 popular URLs in a log.
: 对于这种log里找popular URL的题目，首先肯定是要用hash去保存每一个URL的
: frequency。然后对于返回top k：option 1， sort， O(nlogn)；option2，用一个
: size为k的min_heap，O（nlogk）。
: Follow up，如果log存在多个machine里，那么肯定是要merge result了。这个时候每
: 个machine如果只是存一个size为k的heap显然是不够的了。所以我们可以对于每个
: machine：opt 1，sort the URL frequency；opt 2， use a min_heap to store all
: URL frequency。这里个人感觉opt 1好一些。
: 2. Return a query based on the occurrence from a big table。
: 首先这个很大的table，也就是一个很大file，然后不能完全放入main memory里面，是
|
j*****y
发帖数: 1071 | 13 thanks.
【在 a******8 的大作中提到】
: 这是我当场写的，类似的思想是resevior sampling
: 1 2 3 4
: 40 30 20 10
: int getO(int A[], int n)
: {
: //check n <= 1
: int ret = 0;
: int totalweight = A[0];
: for(int i = 1; i < n; i++)
: {
|
e******o
发帖数: 757 | 14 I think keeping track of the average should solve this problem
【在 j*****y 的大作中提到】
: 怎么解决阿？ 多谢
|
j*****y
发帖数: 1071 | 15 能更仔细点吗？
thanks.
I think keeping track of the average should solve this problem
【在 e******o 的大作中提到】
: I think keeping track of the average should solve this problem
|
p*****2
发帖数: 21240 | |
G****A
发帖数: 4160 | 17 第2题应该不是你理解的那个意思。
all
【在 c**m 的大作中提到】
: 1. Find 1000 popular URLs in a log.
: 对于这种log里找popular URL的题目，首先肯定是要用hash去保存每一个URL的
: frequency。然后对于返回top k：option 1， sort， O(nlogn)；option2，用一个
: size为k的min_heap，O（nlogk）。
: Follow up，如果log存在多个machine里，那么肯定是要merge result了。这个时候每
: 个machine如果只是存一个size为k的heap显然是不够的了。所以我们可以对于每个
: machine：opt 1，sort the URL frequency；opt 2， use a min_heap to store all
: URL frequency。这里个人感觉opt 1好一些。
: 2. Return a query based on the occurrence from a big table。
: 首先这个很大的table，也就是一个很大file，然后不能完全放入main memory里面，是
|
r*******n
发帖数: 3020 | 18 第一题的followup， 我认为每个machine维持一个大小为K的heap，
然后再合并为一个大小为K的heap，就是所要的结果，没有问题啊。
all
【在 c**m 的大作中提到】
: 1. Find 1000 popular URLs in a log.
: 对于这种log里找popular URL的题目，首先肯定是要用hash去保存每一个URL的
: frequency。然后对于返回top k：option 1， sort， O(nlogn)；option2，用一个
: size为k的min_heap，O（nlogk）。
: Follow up，如果log存在多个machine里，那么肯定是要merge result了。这个时候每
: 个machine如果只是存一个size为k的heap显然是不够的了。所以我们可以对于每个
: machine：opt 1，sort the URL frequency；opt 2， use a min_heap to store all
: URL frequency。这里个人感觉opt 1好一些。
: 2. Return a query based on the occurrence from a big table。
: 首先这个很大的table，也就是一个很大file，然后不能完全放入main memory里面，是
|
Y**Y
发帖数: 66 | 19 第一题同一个页面可能在多个机器里吗？
比如说，一个页面在机器1里有1000个，在机器2里有2000个。所以这个页面的访问数是
3000.
work,
【在 a******8 的大作中提到】
: 1. 一个log里有页面的访问记录，如何获得前1000popular的（hash_map + heap）
: followup,log里存在多个machine里，我原先说每个maintain heap,后来经提醒不work,
: 改用每个存heap，然后merge，再提了些优化的方案.面试官基本满意。
: 2.一个很大的table存了query -> occurrence,如何随机获得1个query,概率是基于每个
: query的occurrence,
: 1 2 3
: 20 10 30
: 获得第一个数的概率是 20/60.
: 这题我很纠结，我上来就想到因为大数据量，用resevior sampling的变版做（
: constant space），边想边写边测弄了快半小时才弄出来，最后也解释了半天，其实也
|
Y**Y
发帖数: 66 | 20 找top K可以用randomized partition, 可以average O(n)吧？
all
【在 c**m 的大作中提到】
: 1. Find 1000 popular URLs in a log.
: 对于这种log里找popular URL的题目，首先肯定是要用hash去保存每一个URL的
: frequency。然后对于返回top k：option 1， sort， O(nlogn)；option2，用一个
: size为k的min_heap，O（nlogk）。
: Follow up，如果log存在多个machine里，那么肯定是要merge result了。这个时候每
: 个machine如果只是存一个size为k的heap显然是不够的了。所以我们可以对于每个
: machine：opt 1，sort the URL frequency；opt 2， use a min_heap to store all
: URL frequency。这里个人感觉opt 1好一些。
: 2. Return a query based on the occurrence from a big table。
: 首先这个很大的table，也就是一个很大file，然后不能完全放入main memory里面，是
|
|
|
Y**Y
发帖数: 66 | 21 这个要求每个页面只在一个机器里，不知原题有这个条件没有。
【在 r*******n 的大作中提到】
: 第一题的followup， 我认为每个machine维持一个大小为K的heap，
: 然后再合并为一个大小为K的heap，就是所要的结果，没有问题啊。
:
: all
|
e******o
发帖数: 757 | 22 有问题，比如top 3
machine 1 A 50 B 40 C 37
machine 2 E 50 F 20 G 10 C 8 B2
如果只存 3 个的话，结果是AEB， 而正确答案是AEC
【在 r*******n 的大作中提到】
: 第一题的followup， 我认为每个machine维持一个大小为K的heap，
: 然后再合并为一个大小为K的heap，就是所要的结果，没有问题啊。
:
: all
|
m*****k
发帖数: 731 | 23 this only works when a certain key stays on a certain machine 吧。
【在 r*******n 的大作中提到】
: 第一题的followup， 我认为每个machine维持一个大小为K的heap，
: 然后再合并为一个大小为K的heap，就是所要的结果，没有问题啊。
:
: all
|
c*u
发帖数: 22 | 24 先求总数，返回第一个小于么.
for 1..n
sum += weight[n]
if(rand()*totalWeight < sum)
return query[n];
【在 a******8 的大作中提到】
: 这是我当场写的，类似的思想是resevior sampling
: 1 2 3 4
: 40 30 20 10
: int getO(int A[], int n)
: {
: //check n <= 1
: int ret = 0;
: int totalweight = A[0];
: for(int i = 1; i < n; i++)
: {
|
l**h
发帖数: 893 | 25 it's a variant to this one:
http://www.geeksforgeeks.org/select-a-random-number-from-stream
【在 c*u 的大作中提到】
: 先求总数，返回第一个小于么.
: for 1..n
: sum += weight[n]
: if(rand()*totalWeight < sum)
: return query[n];
|
Y*****y
发帖数: 361 | 26 See this paper "Weighted random sampling with a reservoir":
http://dl.acm.org/citation.cfm?id=1138834 |
a******8
发帖数: 90 | 27 版上的大牛真多啊，paper都能被翻出来，顺便update下，电面过了，onsite了。。
【在 Y*****y 的大作中提到】
: See this paper "Weighted random sampling with a reservoir":
: http://dl.acm.org/citation.cfm?id=1138834
|
c***r
发帖数: 35 | 28 第一题要当场写代码吗？比如写一个build min heap and merge several min heap? |
s*****n
发帖数: 5488 | 29 it is about map-reduce.
【在 b****g 的大作中提到】
: 谢谢分享，第一题是什么意思？
: 每个机器都维持一个min heap，最后再把这些heap们merge到一起吗？
:
: work,
|
t*********h
发帖数: 941 | 30 这个难道不是biased的？favor后面的元素？
【在 a******8 的大作中提到】
: 这是我当场写的，类似的思想是resevior sampling
: 1 2 3 4
: 40 30 20 10
: int getO(int A[], int n)
: {
: //check n <= 1
: int ret = 0;
: int totalweight = A[0];
: for(int i = 1; i < n; i++)
: {
|
|
|
Y********f
发帖数: 410 | 31 为什么很多人认为merge heap呢，不对啊，应该merge hash map啊
【在 r*******n 的大作中提到】
: 第一题的followup， 我认为每个machine维持一个大小为K的heap，
: 然后再合并为一个大小为K的heap，就是所要的结果，没有问题啊。
:
: all
|
