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 | |
