Tuesday, October 18, 2011

Compute the running median and the running average

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.

2 comments:

  1. BST would be costly to consider due to balancing.

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

    ReplyDelete
  2. We published a sample implementation of above approach http://www.geeksforgeeks.org/archives/14873

    ReplyDelete