j******2 发帖数: 362 | 1 Write a function that gets a billion integers. How can you find the median
in most efficient way (time)?
Follow-up: If the input is an endless stream of integers, and we want to
find the current median.
第一个是不是用partition based selection, expected time O(n)
第二个用min and max heaps, expected time O(nlogn)
困惑的是:一个函数装得下a billion integers吗?要不要分几个phase啥的? |
p*****p 发帖数: 379 | 2 1 billion = 2^9
1 int = 4 bytes
total 2^11 bytes = 2^2 G = 4G
还好,压力不是很大
【在 j******2 的大作中提到】 : Write a function that gets a billion integers. How can you find the median : in most efficient way (time)? : Follow-up: If the input is an endless stream of integers, and we want to : find the current median. : 第一个是不是用partition based selection, expected time O(n) : 第二个用min and max heaps, expected time O(nlogn) : 困惑的是:一个函数装得下a billion integers吗?要不要分几个phase啥的?
|
l***i 发帖数: 1309 | 3 the follow-up seems to require partition the interval 0 to MAXINT into
buckets and count each bucket? |
b*****o 发帖数: 715 | 4 这道题并不常见,因为很难。
one-pass median和mapreduce median是一个research问题,和in-memory median是完
全不同的问题,至今也没有公认最优的算法,有兴趣你可以看看这篇paper:
http://infolab.stanford.edu/~manku/papers/98sigmod-quantiles.pd
你是真的遇到了这道题,还是自己想的?
我曾经想过用这道题做面试题的,后来仔细想想觉得太难,如果没有看paper研究过这
个问题,是根本不可能写出实际可以用的code的。
【在 j******2 的大作中提到】 : Write a function that gets a billion integers. How can you find the median : in most efficient way (time)? : Follow-up: If the input is an endless stream of integers, and we want to : find the current median. : 第一个是不是用partition based selection, expected time O(n) : 第二个用min and max heaps, expected time O(nlogn) : 困惑的是:一个函数装得下a billion integers吗?要不要分几个phase啥的?
|
j******2 发帖数: 362 | 5 谢谢指点。是在careercup上看到的g家面试题。
【在 b*****o 的大作中提到】 : 这道题并不常见,因为很难。 : one-pass median和mapreduce median是一个research问题,和in-memory median是完 : 全不同的问题,至今也没有公认最优的算法,有兴趣你可以看看这篇paper: : http://infolab.stanford.edu/~manku/papers/98sigmod-quantiles.pd : 你是真的遇到了这道题,还是自己想的? : 我曾经想过用这道题做面试题的,后来仔细想想觉得太难,如果没有看paper研究过这 : 个问题,是根本不可能写出实际可以用的code的。
|
b*****o 发帖数: 715 | 6 第一问可以做面试题。做bucket count一点点缩小范围就是了。
但是第二问one-pass median我觉得不适合做面试题。
【在 j******2 的大作中提到】 : 谢谢指点。是在careercup上看到的g家面试题。
|
j******2 发帖数: 362 | 7 哦。
第一问具体是不是这样:
用3个phase:
1. 确定在哪个million——O(n)
2. 确定在哪个thousand,并根据前面和后面的数,确定要找thousand里的第k个数——
O(n/1000)
3. 用partition的方法找出一千个数的第k个数——O(n/1000000)
总的时间复杂度还是O(n)
1B的数还不到整数范围,所以每个phase只要一千个int的counter就行了, partition又
是in-place的,所以总的空间就要1k*4byte=4kb。
第二问我觉得好象挺常见着的,用两个heap做,cc150书里的18.9的原题。不过没说
stream能有多长就是了。
谢谢大师指点哦~~
【在 b*****o 的大作中提到】 : 第一问可以做面试题。做bucket count一点点缩小范围就是了。 : 但是第二问one-pass median我觉得不适合做面试题。
|
x******a 发帖数: 6336 | 8 isn't 1b= 10^9?
【在 p*****p 的大作中提到】 : 1 billion = 2^9 : 1 int = 4 bytes : total 2^11 bytes = 2^2 G = 4G : 还好,压力不是很大
|
|