Moving Stream Average

moving avg，就是一个stream输入，给一个int getNow()API获取当前timestamp， 完成两个函数void record(int value)和double getAvg()，有输入时会自动call record， 然后call getAvg()时返回5分钟内的平均值。用一个queue来存数据，一个sum存当前和， 每次record和getAvg时pop掉过期的数据就好了。

import java.util.LinkedList;
import java.util.Queue;


public class Movingaverage {
    class Event{
        int time;
        int val;

        public Event(int time, int val){
            this.time = time;
            this.val = val;
        }

    }

    Queue<Event> queue = new LinkedList<Event>();
    int sum;
    public int getNow(){
        return 1;
    }

    public void record(int val){
        Event event = new Event(getNow(), val);
        queue.offer(event);
        removeExpireRecord();
    }

    public double getAvg(){
        removeExpireRecord();
        if(queue.isEmpty()) return 0;
        return (double) sum / queue.size();
    }

    public void removeExpireRecord(){
        while(! queue.isEmpty() && Math.abs(queue.peek().time - getNow()) > 5){
            Event cur = queue.poll();
            sum -= cur.val;
        }
    }

}

follow up： 如果还要getMedium呢？我说用two heap， 他说太慢了因为record要o(logN)，说这个getMedium call得很少，可以直接在当前的数据结构上implement， 于是其实就是求unsorted list的medium，用quick select能O(n)时间得到，面试官表示很满意。

    public double Medium(){
        int[] res = new int[queue.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = ((LinkedList<Event>) queue).get(i).val;
        }
        if(res.length % 2 == 0){
            int left = getMedium(res, 0, res.length - 1,  res.length / 2 - 1);
            int right = getMedium(res,0, res.length - 1, res.length / 2 );
            return (left + right) / 2;

        }else{
            int left = getMedium(res, 0, res.length - 1,res.length / 2 );
            return left ;
        }

    }
    public static int getMedium(int[] res, int l, int r,int k){
        if(l == r) return res[l];
        int position = getPartation(res,l,r,k);
        if(position == k){
            return res[k];
        }else if(position < k){
            return getMedium(res, position + 1, r, k);
        }else{
            return getMedium(res, l, position - 1, k);
        }
    }

    public static int getPartation(int[] res, int left, int right, int k){

        int pivot = res[right];
        for(int i = left; i < right; i++){
            if(res[i] <= pivot){
                swap(res, left, i);
                left++;
            }
        }
        swap(res, left, right);
        return left;
    }

    public static void swap(int[]res, int i, int j){
        int temp = res[i];
        res[i] = res[j];
        res[j] = temp;
    }