Rolling Median - Amazon Top Interview Questions

                        Solution in C++ :

class RollingMedian {
    public:
    multiset<int> order;
    multiset<int>::iterator it;
    RollingMedian() {
    }

    void add(int val) {
        order.insert(val);
        if (order.size() == 1) {
            it = order.begin();
        } else {
            if (val < *it and order.size() % 2 == 0) {
                --it;
            }
            if (val >= *it and order.size() % 2 != 0) {
                ++it;
            }
        }
    }

    double median() {
        if (order.size() % 2 != 0) {
            return double(*it);
        } else {
            auto one = *it, two = *next(it);
            return double(one + two) / 2.0;
        }
    }
};
                    

                        Solution in Java :

import java.util.*;

class RollingMedian {
    PriorityQueue<Integer> small, great;

    public RollingMedian() {
        this.small = new PriorityQueue<Integer>(Collections.reverseOrder());
        this.great = new PriorityQueue<Integer>();
    }

    public void add(int val) {
        if (this.small.size() == 0 && this.great.size() == 0) {
            this.small.add(val);
        } else if (this.small.size() > this.great.size()) {
            if (this.small.peek() > val) {
                this.great.add(this.small.poll());
                this.small.add(val);
            } else {
                this.great.add(val);
            }

        } else {
            if (this.small.peek() >= val) {
                this.small.add(val);
            } else {
                this.great.add(val);
                this.small.add(this.great.remove());
            }
        }
    }

    public double median() {
        if (this.small.size() > this.great.size()) {
            return this.small.peek();
        } else {
            return (double) (this.small.peek() + this.great.peek()) / 2;
        }
    }
}
                    

                        Solution in Python : 
                            
class RollingMedian:
    def __init__(self):
        self.l = SortedList()

    def add(self, val):
        self.l.add(val)

    def median(self):
        if len(self.l) % 2 == 0:

            return (self.l[len(self.l) // 2] + self.l[(len(self.l) // 2) - 1]) / 2
        else:
            return self.l[len(self.l) // 2]