G面经prepare: Data Stream Average

给一个datastream和一个fixed window size, 让我design一个class可以完成add number还有find average in the window. 就是不能用vector得用array.

当然用queue是最好的

package DataStreamAverage;

import java.util.*;

public class Solution {
    int count;
    int sum;
    Queue<Integer> q;
    
    public Solution() {
        this.count = 0;
        this.sum = 0;
        this.q = new LinkedList<Integer>();
    }
    
    
    public ArrayList<Double> average (HashSet<Integer> set, int L) {
        ArrayList<Double> result = new ArrayList<Double>();
        Iterator<Integer> iter = set.iterator();
        while (iter.hasNext()) {
            int cur = iter.next();
            q.offer(cur);
            count++;
            sum += cur;
            if (q.size()>L) {
                int front = q.peek();
                sum -= front;
                count--;
                q.poll();
            }
            double aver = (double)sum/count;
            result.add(aver);
        }
        return result;
        
    }
    

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i=1; i<=10; i++) {
            set.add(i);
        }
        Solution sol = new Solution();
        ArrayList<Double> res = sol.average(set, 2);
        System.out.println(res);
    }

}

当然用fixed size array也可以，但是要小心，一个是要折回，二个是要删除数组元素之前存在的数

 1 package DataStreamAverage;
 2 
 3 import java.util.*;
 4 
 5 public class Solution2 {
 6     int count;
 7     int sum;
 8     int[] arr;
 9     int pos;
10     
11     public Solution2(int size) {
12         this.count = 0;
13         this.sum = 0;
14         this.arr = new int[size];
15         Arrays.fill(arr, Integer.MIN_VALUE);
16         this.pos = 0;
17     }
18     
19     
20     public ArrayList<Double> average (HashSet<Integer> set, int L) {
21         ArrayList<Double> result = new ArrayList<Double>();
22         Iterator<Integer> iter = set.iterator();
23         while (iter.hasNext()) {
24             int cur = iter.next();
25             if (pos == arr.length) {
26                 pos = 0;
27             }
28             if (arr[pos] != Integer.MIN_VALUE) {
29                 sum -= arr[pos];
30                 count--;
31             }
32             arr[pos] = cur;
33             sum += arr[pos];
34             pos++;
35             count++;
36             double aver = (double)sum/count;
37             result.add(aver);
38         }
39         return result;
40     }
41     
42 
43     /**
44      * @param args
45      */
46     public static void main(String[] args) {
47         // TODO Auto-generated method stub
48         HashSet<Integer> set = new HashSet<Integer>();
49         for (int i=1; i<=10; i++) {
50             set.add(i);
51         }
52         Solution2 sol = new Solution2(2);
53         ArrayList<Double> res = sol.average(set, 2);
54         System.out.println(res);
55     }
56 
57 }