title: Finding mean and median in constant time
body: <p>This is a common interview question. 
  You have a stream of numbers coming in (let's say more than a million). The numbers are between [0-999]). </p>
  
  <pre><code>Implement a class which supports three methods in O(1) 
  
  * insert(int i); 
  * getMean(); 
  * getMedian(); 
  </code></pre>
  
  <p>This is my code.</p>
  
  <pre><code>public class FindAverage {
  
    private int[] store;
    private long size;
    private long total;
    private int highestIndex;
    private int lowestIndex;
  
    public FindAverage() {
      store  = new int[1000];
      size = 0;
      total = 0;
      highestIndex = Integer.MIN_VALUE;
      lowestIndex = Integer.MAX_VALUE;
  
    }
  
    public void insert(int item) throws OutOfRangeException {
      if(item &lt; 0 || item &gt; 999){
        throw new OutOfRangeException();
      }
      store[item] ++;
      size ++;
      total += item;
      highestIndex = Integer.max(highestIndex, item);
      lowestIndex = Integer.min(lowestIndex, item);
    }
  
    public float getMean(){
      return (float)total/size;
    }
  
    public float getMedian(){
  
    }
  }
  </code></pre>
  
  <p>I can't seem to think of a way to get the median in O(1) time.
  Any help appreciated.</p>