一道巨常见的题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道巨常见的题

一道巨常见的题# JobHunting - 待字闺中

j*22013-02-20 08:02

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*p2013-02-20 08:02

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*i2013-02-20 08:02

3 楼

the follow-up seems to require partition the interval 0 to MAXINT into
buckets and count each bucket?

b*o2013-02-20 08:02

4 楼

这道题并不常见，因为很难。
one-pass median和mapreduce median是一个research问题，和in-memory median是完
全不同的问题，至今也没有公认最优的算法，有兴趣你可以看看这篇paper：
http://infolab.stanford.edu/~manku/papers/98sigmod-quantiles.pd
你是真的遇到了这道题，还是自己想的？
我曾经想过用这道题做面试题的，后来仔细想想觉得太难，如果没有看paper研究过这
个问题，是根本不可能写出实际可以用的code的。

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

j*22013-02-20 08:02

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*o2013-02-20 08:02

6 楼

第一问可以做面试题。做bucket count一点点缩小范围就是了。
但是第二问one-pass median我觉得不适合做面试题。

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

: 谢谢指点。是在careercup上看到的g家面试题。

j*22013-02-20 08:02

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我觉得不适合做面试题。