362. Design Hit Counter

For this design problem, I was thinking of use an 300-size array to keep the counts. However, this solution doesn't provide any information about if the hits in the array are expired. For example, we have a hit at 1s and we have another hit at 302s. Then when we count the hits in the last 300s, we'll get 2 because we don't know when to expire the hit at 1s. Therefore, we need to another array to record the timestamp for each count in last 300s. When we hit the counter, we'll wrap around the timestamp to 300s, say i, and then we check in the time[] array if time[i] matches the input timestamp. If so, we increase the hits[i] counter for that hit. If hits[i] is more than 1, it means there are multiple hits happening in the same second. On the other hand, if time[i] doesn't match the input timestamp, it means the time[i] has expired, we need to give it new time stamp and reset the hits[i] counter to 1. When counting the hits in last 300s, we just need to sum up all the hits in last 300s.

1:  class HitCounter {  
2:  private:  
3:    vector<int> time;  
4:    vector<int> hits;  
5:  public:  
6:    /** Initialize your data structure here. */  
7:    HitCounter() {  
8:      time = vector<int>(300, 0);  
9:      hits = vector<int>(300, 0);  
10:    }  
11:    /** Record a hit.  
12:      @param timestamp - The current timestamp (in seconds granularity). */  
13:    void hit(int timestamp) {  
14:      int i = timestamp % 300;  
15:      if (time[i] != timestamp) {  
16:        time[i] = timestamp;  
17:        hits[i] = 1;  
18:      } else {  
19:        hits[i]++;  
20:      }  
21:    }  
22:    /** Return the number of hits in the past 5 minutes.  
23:      @param timestamp - The current timestamp (in seconds granularity). */  
24:    int getHits(int timestamp) {  
25:      int count = 0;  
26:      for (int i = 0 ; i < 300; i++) {  
27:        if (timestamp - time[i] < 300) {  
28:          count += hits[i];  
29:        }  
30:      }  
31:      return count;  
32:    }  
33:  };  
34:  /**  
35:   * Your HitCounter object will be instantiated and called as such:  
36:   * HitCounter obj = new HitCounter();  
37:   * obj.hit(timestamp);  
38:   * int param_2 = obj.getHits(timestamp);  
39:   */