Cracking the Coding Interview: Heaps – Find the Running Median

Here’s my solution to the challenge: https://www.hackerrank.com/challenges/ctci-find-the-running-median

void addNumber(int num, priority_queue<int, vector, less >* lowers, priority_queue<int, vector, greater >* highers){
    if(lowers->size() ==  0 || num top())
        lowers->push(num);
    else
        highers->push(num);
}

void rebalance(priority_queue<int, vector, less >* lowers, priority_queue<int, vector, greater >* highers){
    if(lowers->size() > highers->size()){
        if(lowers->size() - highers->size() > 1){
            highers->push(lowers->top());
            lowers->pop();
        }
    }
    else {
        if(highers->size() - lowers->size() > 1){
            lowers->push(highers->top());
            highers->pop();
        }
    }
}

double getMedian(priority_queue<int, vector, less >* lowers, priority_queue<int, vector, greater >* highers){
    if(lowers->size() == highers->size()){
        return 0.5 * (lowers->top() + highers->top());
    }
    else {
        if(lowers->size() > highers->size()){
                return 1.0 * lowers->top();
        }
        else if(highers->size() > lowers->size()){
                return 1.0 * highers->top();
        }
    }
    return 0.0;
}

int main(){
    int n;
    cin >> n;
    vector a(n);
    priority_queue<int, vector, less > pqMax;
    priority_queue<int, vector, greater > pqMin;
    for(int a_i = 0;a_i > a[a_i];
        addNumber(a[a_i], &pqMax, &pqMin);
        rebalance(&pqMax, &pqMin);
        cout << fixed << setprecision(1) << getMedian(&pqMax, &pqMin) << endl;
    }
    return 0;
}

All my solutions to HackerRank challenges can be found here: https://github.com/sdulaney/hackerrank

Leave a Comment