CareerCup

My solution:
Time: O(1)
Space: O(1)

public class Statistics {
    private int[] counter;
    private long sum;
    private int n;

    public Statistics() {
        // initial an array for counter number of
        // existed of each value in [0-999]
        counter = new int[1000];

        // sum all insert value
        sum = 0;

        // n is number of value
        n = 0;
    }

    public void insert(int value) {
        // if insert value not in range [0-999], return
        if (value >= 1000 || value < 0) {
            return;
        }

        // increase counter in this value
        counter[value]++;

        // calculate sum
        sum += value;

        // increase number of value
        n++;
    }

    public double getMean() {
        return (double)sum / n;
    }

    // examples we have:
    // value:    3   9   11
    // counter:  1   3   20
    // n = 1 + 3 + 20 = 24
    // so median will be value at position 24 / 2 = 12
    // we will count until meet value at position 12
    // result is 11
    public int getMedian() {
        int medianIndex = (n + 1) / 2;
        // counter variable
        int idx = 0;
        for (int value = 0; value < 1000; value++) {
            idx += counter[value];
            if (idx >= medianIndex) {
                return value;
            }
        }
        return -1;
    }
}

You are not allowed to store the numbers themselves

class NotGreatMath {
	constructor() {
		this.amount = 0;
                this.sum = 0;

		this.median = null;
		this.left = null;
		this.right = null;
        }

	insert(x) {
		this.sum += x;
		this.amount++;

		if (this.amount == 1) {
			this.median = x;
			return;
		}

		const isLeft = x < this.median;
		let next = isLeft ? this.left : this.right;
		const nearest = (isLeft ? x > next : x < next) ? x : next;

		if (this.amount % 2 == 0) {
			this.median = next;
			next = nearest;
		} else {
			this.median = (this.median + next) / 2;
		}


        if (isLeft) {
           this.left = next;
        } {
           this.right = next;
        }
	}

	getMean() {
		return this.sum / this.amount;
	}
	getMedian() {
		return this.median;
	}
}

class NotGreatMath {
	constructor() {
		this.amount = 0;
                this.sum = 0;

		this.median = null;
		this.left = null;
		this.right = null;
        }

	insert(x) {
		this.sum += x;
		this.amount++;

		if (this.amount == 1) {
			this.median = x;
			return;
		}

		const isLeft = x < this.median;
		let next = isLeft ? this.left : this.right;
		const nearest = (isLeft ? x > next : x < next) ? x : next;

		if (this.amount % 2 == 0) {
			this.median = next;
			next = nearest;
		} else {
			this.median = (this.median + next) / 2;
		}


        if (isLeft) {
           this.left = next;
        } {
           this.right = next;
        }
	}

	getMean() {
		return this.sum / this.amount;
	}
	getMedian() {
		return this.median;
	}
}

Even better. Spacetime is o(1) too, but insert is not so fast.

class NotGreatMath {
	constructor() {
		this.amount = 0;
        this.sum = 0;

		this.median = null;
		this.left = null;
		this.right = null;
        }

	insert(x) {
		this.sum += x;
		this.amount++;

		if (this.amount == 1) {
			this.median = x;
			return;
		}

		const isLeft = x < this.median;
		let next = isLeft ? this.left : this.right;
		const nearest = (!next || (isLeft ? x > next : x < next)) ? x : null;

		this.median = (this.amount % 2 == 0) ? next : (this.median + next) / 2;

		if (nearest) {
	        if (isLeft) {
	           this.left = next;
	        } else {
	           this.right = next;
	        }
        }
	}

	getMean() {
		return this.sum / this.amount;
	}
	getMedian() {
		return this.median;
	}
}

The mean should be easy to track by keeping track of count .

While inserting nth number

new_mean =((current_mean)*(count-1) + new_number)/count

Or

we can keep track of the total

.

For median, we can have two heaps, one max-heap and one min-heap. Make sure the difference in the numbers in the 2 heaps is at most one at any point.

For getMedian() - if the difference between the numbers in the 2 heaps is 1, pick up the number on top of the bigger heap

If difference is 0, median is the average of the top of the 2 heaps.