java - Finding mean and median in constant time -

this common interview question. have stream of numbers coming in (let's more million). numbers between [0-999]).

implement class supports 3 methods in o(1)   * insert(int i);  * getmean();  * getmedian();  

this 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 < 0 || item > 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(){    } } 

i can't seem think of way median in o(1) time. appreciated.

you have done heavy lifting, building store counters. size value, it's easy enough.

you start iterating store, summing counts until reach half of size. median value, if size odd. size, you'll grab 2 surrounding values , average.

performance o(1000/2) on average, means o(1), since doesn't depend on n, i.e. performance unchanged if n reaches billions.

remember, o(1) doesn't mean instant, or fast. wikipedia says it:

an algorithm said constant time (also written o(1) time) if value of t(n) bounded value not depend on size of input.

in case, bound 1000.