boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - find the median of an infinite data stream of integers
相关主题
请教一道题 median ii
请教一个BST找Median的题目
如何求BST的median
g家面经
Groupon 電面
G 公司的一个面试题
amazon一面面经
问一道题~
How to find median of a stream of integers ?
find medium number in stream 这题怎么作
相关话题的讨论汇总
话题: median话题: integers话题: stream话题: infinite话题: find
进入JobHunting版参与讨论
1 (共1页)
s********r
发帖数: 277
1
昨天遇到的题目,大家有啥好的解答吗,我当时没答上来。每来一个数字之后,我要能
查到开始到当前的median。
j********e
发帖数: 1192
2
你能记录以前所有的数字么?如果不能记录,只能返回estimated median。
如果记录的话,搞个BST,额外记录左右子树的节点数,这样每来个数字,都是
logN的复杂度。

【在 s********r 的大作中提到】
: 昨天遇到的题目,大家有啥好的解答吗,我当时没答上来。每来一个数字之后,我要能
: 查到开始到当前的median。

s********r
发帖数: 277
3
不能记录所有的数字,能记录的话用两个堆就可以了。 estimated median 也行,怎么
算的。
t*****r
发帖数: 324
4
如果不能记录所有的数字的话
我可以
1 1000 1000 1000 ...(100000000个1000)0 0 0 ... (100000000个0)

【在 s********r 的大作中提到】
: 不能记录所有的数字,能记录的话用两个堆就可以了。 estimated median 也行,怎么
: 算的。

j********e
发帖数: 1192
5
有proximation算法,我大概记得的一个算法是:
每来一个数据D,跟当前的median比较,如果D大,那么就增加median,
否则就减少median。那这个增加和减少的step有多种选法,例如
a const small number,或者根据数据的variance,或者density estimation
等。我记得能保证这样的得到的数的expectation是median,而且可以
用于任何quantile (例如75-percentile).

【在 s********r 的大作中提到】
: 不能记录所有的数字,能记录的话用两个堆就可以了。 estimated median 也行,怎么
: 算的。

b*****o
发帖数: 715
6
对于one pass算法,
(1)要求exact median, 可以证明内存需要至少是N/2。
(2)如果允许用随机算法,对于内存量是s,可以先用reservoir sampling采样出s个
sample,然后在对这s个数求median。你可以用概率公式算一下误差。
(3)如果允许approximate median,可以把内存量减少到(log(N))^2。大致想法是把
已经扫描过的数作类似quantization的压缩:对于长度为s的buffer,每个元素不但存一
个value(i),而且还存一个weight(i)。所有的weight加起来就是目前扫描过的数的总数
。算法的关键是要保证:在任何时刻,如果把value(i)重复weight(i)次,然后把所有这
样重复出来的数组成一个stream,用它来计算median,和用原数组计算median,能大致
相当
。细节可参看以下paper:
http://infolab.stanford.edu/~manku/papers/98sigmod-quantiles.pd
1 (共1页)
进入JobHunting版参与讨论
相关主题
find medium number in stream 这题怎么作
google老题:Find kth largest of sum of elements in 2 sorted array
问个题
再来一道简单的bit运算题
两个Amazon面试题
面试题
MS面试题
这个Binary Tree的题来看看
请教一个balanced tree的问题
amazon on-site interview
相关话题的讨论汇总
话题: median话题: integers话题: stream话题: infinite话题: find