G面经prepare: Data Stream Average-白红宇

G面经prepare: Data Stream Average

阅读量：5061 次

发布时间：2019-06-12

本文共 2694 字，大约阅读时间需要 8 分钟。

给一个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
     
       q;        public Solution() {        this.count = 0;        this.sum = 0;        this.q = new LinkedList
      
       ();    }            public ArrayList
       
         average (HashSet
        
          set, int L) {        ArrayList
         
           result = new ArrayList
          
           (); Iterator
           
             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
            
              set = new HashSet
             
              (); for (int i=1; i<=10; i++) { set.add(i); } Solution sol = new Solution(); ArrayList
              
                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
     
       average (HashSet
      
        set, int L) {21         ArrayList
       
         result = new ArrayList
        
         ();22         Iterator
         
           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 args45      */46     public static void main(String[] args) {47         // TODO Auto-generated method stub48         HashSet
          
            set = new HashSet
           
            ();49 for (int i=1; i<=10; i++) {50 set.add(i);51 }52 Solution2 sol = new Solution2(2);53 ArrayList
            
              res = sol.average(set, 2);54 System.out.println(res);55 }56 57 }