You are given a very long stream and you need to compute the running median for each group of 1k numbers. Same question for the running median. What is the complexity?
Suppose you know a priori the number of elements in the stream.
Solution:
given a running average, you can update the group by adding a new element and removing the oldest one. This will give you a solution that is linear in the number of elements in the stream
Similar intuition is for the median, you can use a balanced BST where every node has the number of nodes contained in the subtree rooted at it.
Posts
Best paper awards at ICALP 2012
-
The preliminary version of the detailed programme for ICALP 2012 is now
available here. While skimming through the programme, I learnt that the
best paper ...
34 minutes ago
BST would be costly to consider due to balancing.
ReplyDeleteRather we can make use of one median element and two heaps, a MinHeap and a MaxHeap. As the elements from stream are read, push the median to appropriate heap and update the median with balanced element.
We published a sample implementation of above approach http://www.geeksforgeeks.org/archives/14873
ReplyDelete