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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢分享,第一题是什么意思? : 每个机器都维持一个min heap,最后再把这些heap们merge到一起吗? : : work,
|
b****g 发帖数: 192 | 4 谢谢
第二题:
我看你用了binary search找那个数,耗时O(lg n),但是前面把数组累加已经耗时O
(n)了,
有没有办法耗时O(lg n)?
【在 a******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 嗯,是的
|
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那么多的数累加不会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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题: 对于小的 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是我当场写的,类似的思想是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是我当场写的,类似的思想是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是我当场写的,类似的思想是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么解决阿? 多谢
|
j*****y 发帖数: 1071 | 15 能更仔细点吗?
thanks.
I think keeping track of the average should solve this problem
【在 e******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I think keeping track of the average should solve this problem
|
p*****2 发帖数: 21240 | |
G****A 发帖数: 4160 | 17 第2题应该不是你理解的那个意思。
all
【在 c**m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是我当场写的,类似的思想是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先求总数,返回第一个小于么. : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢分享,第一题是什么意思? : 每个机器都维持一个min heap,最后再把这些heap们merge到一起吗? : : work,
|
t*********h 发帖数: 941 | 30 这个难道不是biased的?favor后面的元素?
【在 a******8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是我当场写的,类似的思想是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题的followup, 我认为每个machine维持一个大小为K的heap, : 然后再合并为一个大小为K的heap,就是所要的结果,没有问题啊。 : : all
|