Median of a stream of numbers
Given a stream of integers, find the median of the stream of numbers received so far.
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Median of stream of numbers can be queried at multiple times at different point of time. Insertion and median functions can be called in any order. For example:
1 2 3 4 5 |
add(1) add(2) findMedian() -> 1.5 Median of stream of numbers till now add(3) findMedian() -> 2 Median of stream of numbers till now |
First solution be to store the stream received in an unsorted array.
[Read More...]