16G黑的白的都没了 - 未名空间MITBBS历史存档

a*82013-10-31 07:10

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)，当时面试就是有点一根
筋。最后问了问组的情况，听口音感觉是同胞里的一个大牛，希望能水过。（突然想起
来介绍的时候他的名字不像是同胞的）

h*r2013-10-31 07:10

2 楼

请问大家，一个30万左右的房子的Escrow费用应该大概是多少钱？我是说要给Escrow公
司让他们工作服务的费用。是不是一定都是Seller和buyer各付各的，有没有可能
Seller都付呢？

m*d2013-10-31 07:10

3 楼

偶尔白的还能出来一下

b*g2013-10-31 07:10

4 楼

谢谢分享，第一题是什么意思？
每个机器都维持一个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），边想边写边测弄了快半小时才弄出来，最后也解释了半天，其实也

J*S2013-10-31 07:10

5 楼

看当地CITY的规定，可以SELLER全付。

【在 h*********r 的大作中提到】

: 请问大家，一个30万左右的房子的Escrow费用应该大概是多少钱？我是说要给Escrow公
: 司让他们工作服务的费用。是不是一定都是Seller和buyer各付各的，有没有可能
: Seller都付呢？

i*c2013-10-31 07:10

6 楼

这次nexus第一次出白色的，我还以为白的能先没呢。

【在 m*d 的大作中提到】

: 偶尔白的还能出来一下

a*82013-10-31 07:10

7 楼

嗯，是的

【在 b****g 的大作中提到】

: 谢谢分享，第一题是什么意思？
: 每个机器都维持一个min heap，最后再把这些heap们merge到一起吗？
:
: work,

b*d2013-10-31 07:10

8 楼

你可以在合同里面写都让seller来付,就看seller答应不答应了.

【在 h*********r 的大作中提到】

: 请问大家，一个30万左右的房子的Escrow费用应该大概是多少钱？我是说要给Escrow公
: 司让他们工作服务的费用。是不是一定都是Seller和buyer各付各的，有没有可能
: Seller都付呢？

d*32013-10-31 07:10

9 楼

应该还会慢慢放货的。。。

b*g2013-10-31 07:10

10 楼

谢谢
第二题：
我看你用了binary search找那个数，耗时O（lg n），但是前面把数组累加已经耗时O
（n）了，
有没有办法耗时O（lg n）？

【在 a******8 的大作中提到】

: 嗯，是的

b*22013-10-31 07:10

11 楼

在加州, 每个county/city对seller/buyer付什么都有不同的规定. 但是最终还是要看
contract上是怎么写的.

i*n2013-10-31 07:10

12 楼

由于不是纯白，买者表示比较纠结。。。

【在 i******c 的大作中提到】

: 这次nexus第一次出白色的，我还以为白的能先没呢。

j*y2013-10-31 07:10

13 楼

第二题: 对于小的 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*o2013-10-31 07:10

14 楼

那么多的数累加不会overflow 么？

j*y2013-10-31 07:10

15 楼

怎么解决阿？多谢

【在 e******o 的大作中提到】

: 那么多的数累加不会overflow 么？

a*82013-10-31 07:10

16 楼

这是我当场写的，类似的思想是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*p2013-10-31 07:10

17 楼

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*m2013-10-31 07:10

18 楼

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*m2013-10-31 07:10

19 楼

恩，你这个跟我想的一样。

【在 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*y2013-10-31 07:10

20 楼

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*y2013-10-31 07:10

21 楼

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*o2013-10-31 07:10

22 楼

I think keeping track of the average should solve this problem

【在 j*****y 的大作中提到】

: 怎么解决阿？多谢

j*y2013-10-31 07:10

23 楼

能更仔细点吗？
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*22013-10-31 07:10

24 楼

第二题纪录一个总数就可以了吧？

G*A2013-10-31 07:10

25 楼

第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*n2013-10-31 07:10

26 楼

第一题的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*Y2013-10-31 07:10

27 楼

第一题同一个页面可能在多个机器里吗？
比如说，一个页面在机器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*Y2013-10-31 07:10

28 楼

找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*Y2013-10-31 07:10

29 楼

这个要求每个页面只在一个机器里，不知原题有这个条件没有。

【在 r*******n 的大作中提到】

: 第一题的followup，我认为每个machine维持一个大小为K的heap，
: 然后再合并为一个大小为K的heap，就是所要的结果，没有问题啊。
:
: all

e*o2013-10-31 07:10

30 楼

有问题，比如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*k2013-10-31 07:10

31 楼

this only works when a certain key stays on a certain machine 吧。

【在 r*******n 的大作中提到】

: 第一题的followup，我认为每个machine维持一个大小为K的heap，
: 然后再合并为一个大小为K的heap，就是所要的结果，没有问题啊。
:
: all

c*u2013-10-31 07:10

32 楼

先求总数，返回第一个小于么.
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*h2013-10-31 07:10

33 楼

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*y2013-10-31 07:10

34 楼

See this paper "Weighted random sampling with a reservoir":
http://dl.acm.org/citation.cfm?id=1138834

a*82013-10-31 07:10

35 楼

版上的大牛真多啊，paper都能被翻出来，顺便update下，电面过了，onsite了。。

【在 Y*****y 的大作中提到】

: See this paper "Weighted random sampling with a reservoir":
: http://dl.acm.org/citation.cfm?id=1138834

c*r2013-10-31 07:10

36 楼

第一题要当场写代码吗？比如写一个build min heap and merge several min heap?

s*n2013-10-31 07:10

37 楼

it is about map-reduce.

【在 b****g 的大作中提到】

: 谢谢分享，第一题是什么意思？
: 每个机器都维持一个min heap，最后再把这些heap们merge到一起吗？
:
: work,

t*h2013-10-31 07:10

38 楼

这个难道不是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*f2013-10-31 07:10

39 楼

为什么很多人认为merge heap呢，不对啊，应该merge hash map啊

【在 r*******n 的大作中提到】

: 第一题的followup，我认为每个machine维持一个大小为K的heap，
: 然后再合并为一个大小为K的heap，就是所要的结果，没有问题啊。
:
: all