m****r
发帖数: 141 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitcar (mitcar), 信区: JobHunting
标 题: An interview question of finding the median in a moving window.
发信站: BBS 未名空间站 (Thu Mar 22 09:53:07 2012, 美东)
This is an interview question. The interview has been done.
Given a sequence of data (it may have duplicates), a fixed-sized moving
window, move the window at each iteration from the start of the data
sequence, such that
(1) the oldest data element is removed from the window and a new data
element is pushed into the window
(2) find the median of the data inside the window at each moving.
My idea:
Use 2 heaps to hold median. In side the window, sort the data in the window
in the first iteration, the min heap holds the larger part and the max heap
holds the smaller part. If the window has odd number of data, the max heap
returns the median otherwise the arithmetic mean of the top elements of the
two heaps is the median.
When a new data is pushed in to the window, remove the oldest data from one
of the heap and compare the new data with the top of max and min heap so
that to decide which heap the data to be put. Then, find the median just
like in the first iteration.
But, how to find a data element in a heap is a problem. Heap is a binary
tree not a binary search tree.
Any help is really appreciated.
Thanks | a****y
发帖数: 99 | 2
my 2cents,use AVL tree, plus each node store the number of node of the sub-
tree.so that median finding costs log(m). insert, delete also costs log(m).
O(nlog(m) )
I google it and find some reference :
Comparison of algorithms for standard median filtering
Juhola, M. Katajainen, J. Raita, T.
Signal Processing, IEEE Transactions on
Jan. 1991, Volume: 39 , Issue: 1, page(s): 204 - 208
Abstract
On computation of the running median
Astola, J.T. Campbell, T.G.
Acoustics, Speech and Signal Processing, IEEE Transactions on
Apr 1989, Volume: 37, Issue: 4, page(s): 572-574
【在 m****r 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: mitcar (mitcar), 信区: JobHunting
: 标 题: An interview question of finding the median in a moving window.
: 发信站: BBS 未名空间站 (Thu Mar 22 09:53:07 2012, 美东)
: This is an interview question. The interview has been done.
: Given a sequence of data (it may have duplicates), a fixed-sized moving
: window, move the window at each iteration from the start of the data
: sequence, such that
: (1) the oldest data element is removed from the window and a new data
: element is pushed into the window
| m****r
发帖数: 141 | 3 thanks !
But, how to find median on AVL tree ?
thanks
).
【在 a****y 的大作中提到】
:
: my 2cents,use AVL tree, plus each node store the number of node of the sub-
: tree.so that median finding costs log(m). insert, delete also costs log(m).
: O(nlog(m) )
: I google it and find some reference :
: Comparison of algorithms for standard median filtering
: Juhola, M. Katajainen, J. Raita, T.
: Signal Processing, IEEE Transactions on
: Jan. 1991, Volume: 39 , Issue: 1, page(s): 204 - 208
: Abstract
|
|
