p*******o 发帖数: 3564 | 1 在careercup上看到,据称是A家题目
Given a dynamic stream of integral numbers, write a function that returns
its median. The numbers may arrive in bursts at any time.
http://www.careercup.com/question?id=12343736
下面有人提出两个heap,但问题在如讨论中提到,stream可能很大,超出storage
limit,版上有没有更好的idea
Thx |
e***s 发帖数: 799 | 2 问题就在不存放整个STREAM,怎么找median |
b*****c 发帖数: 1103 | 3 of course u can use some trick |
t****y 发帖数: 27 | 4 If the stream is infinite, there is no way to get the median with a 100%
accuracy.
I remember there is a paper discussing this problem, and it presents an
algorithm that using a certain amount of memory you can find the median
with a low bound probability. Sorry forgot the paper name though.
returns
【在 p*******o 的大作中提到】 : 在careercup上看到,据称是A家题目 : Given a dynamic stream of integral numbers, write a function that returns : its median. The numbers may arrive in bursts at any time. : http://www.careercup.com/question?id=12343736 : 下面有人提出两个heap,但问题在如讨论中提到,stream可能很大,超出storage : limit,版上有没有更好的idea : Thx
|
w***g 发帖数: 5958 | 5 顶一下。去年去Google貌似被问到了同一个问题。我觉得这个问题更像系统题。
【在 p*******o 的大作中提到】 : 在careercup上看到,据称是A家题目 : Given a dynamic stream of integral numbers, write a function that returns : its median. The numbers may arrive in bursts at any time. : http://www.careercup.com/question?id=12343736 : 下面有人提出两个heap,但问题在如讨论中提到,stream可能很大,超出storage : limit,版上有没有更好的idea : Thx
|
k***t 发帖数: 276 | 6 如果数有范围是否可以计数,甚至分布式计数?
没有上下限的,是否可以考虑近似到一些有限的范围。
【在 p*******o 的大作中提到】 : 在careercup上看到,据称是A家题目 : Given a dynamic stream of integral numbers, write a function that returns : its median. The numbers may arrive in bursts at any time. : http://www.careercup.com/question?id=12343736 : 下面有人提出两个heap,但问题在如讨论中提到,stream可能很大,超出storage : limit,版上有没有更好的idea : Thx
|
p*******o 发帖数: 3564 | 7 有范围的特殊情况当然可以用counting sort找median,不过还是希望有应对一般情况的
方案,期待版上牛人解答
【在 k***t 的大作中提到】 : 如果数有范围是否可以计数,甚至分布式计数? : 没有上下限的,是否可以考虑近似到一些有限的范围。
|
z******t 发帖数: 59 | 8 写了篇博客讨论中位数:
http://codercareer.blogspot.com/2012/01/no-30-median-in-stream.
博客中假设内存中能保存stream中的所有数据。期待大牛指点如何解决海量数据流的解
法。
【在 p*******o 的大作中提到】 : 在careercup上看到,据称是A家题目 : Given a dynamic stream of integral numbers, write a function that returns : its median. The numbers may arrive in bursts at any time. : http://www.careercup.com/question?id=12343736 : 下面有人提出两个heap,但问题在如讨论中提到,stream可能很大,超出storage : limit,版上有没有更好的idea : Thx
|
o******y 发帖数: 446 | 9 在没有任何数据范围限定之前,在任何
时间点,任何前面的历史数据都可能是中位数,
所以任何数据都要能够读取出来如何中位数的话。
这样一看,任何历史数据都要保存,内存
存不了那就存硬盘,没有捷径吧。
面试题不会让你写硬盘存储操作的大程序吧?
所以假设内存能存储就是面试题的假设了。
returns
【在 z******t 的大作中提到】 : 写了篇博客讨论中位数: : http://codercareer.blogspot.com/2012/01/no-30-median-in-stream. : 博客中假设内存中能保存stream中的所有数据。期待大牛指点如何解决海量数据流的解 : 法。
|
b*****c 发帖数: 1103 | 10 必须提前知道数的总数,比如10^12个数,随便多少内存只要O(1), just to increase time complexity |
M********u 发帖数: 42 | |