[Google Interview] No. 30 - Median in Stream

Question: How to get the median from a stream of numbers at any time? The median is middle value of numbers. If the count of numbers is even, the median is defined as the average value of the two numbers in middle.


$ cat template.h
#include <vector>

using namespace std;

template <class T>
class Median
{
public:
        Median(){};
        Median(T *val, int num);
        ~Median(){};

        void push(T val);
        void pop();
        T front(){return flist.front();};
        float median();

        void print();

private:
        vector<T> flist;
};

template <class T>
Median<T>::Median(T *val, int num)
{
        if ( (!val) || (num<=0) )
        {
                return;
        }

        for (int i=0; i<num; i++)
        {
                push(val[i]);
        }
}

template <class T>
void Median<T>::push(T val)
{
        flist.push_back(val);
        // use standard sort
        sort(flist.begin(), flist.end());
}

template <class T>
void Median<T>::pop()
{
        flist.pop_back();
}

template <class T>
float Median<T>::median()
{
        float median=0;
        int num = flist.size();
        if (num < 0)
        {
                return 0;
        }

        if (num & 1)
        {
                median=(float)flist.at(num/2);
        }
        else
        {
                median=(float)(flist.at((num/2)-1) + flist.at(num/2))/2;
        }

        return median;
}

template <class T>
void Median<T>::print()
{
        T *pval = flist.data();

        for (int i=0; i<flist.size(); i++)
        {
                cout << pval[i] << " ";
        }
        cout << endl;
}

$ cat median.cpp

#include <iostream>

#include "template.h"

int main (int argc, char **argv)

{

        int intArr[]={77, 26, 1, 5, 8, 10, 20, 33, 66, 4, 3, 2, 100};

        int intNum = sizeof(intArr)/sizeof(intArr[0]);

        Median<int> myvector(intArr, intNum);

        myvector.print();

        cout << "median=" << myvector.median() << endl;

        return 0;

}

Result:

1 2 3 4 5 8 10 20 26 33 66 77 100 

median=10

ref: http://codercareer.blogspot.tw/2012/01/no-30-median-in-stream.html