362. Design Hit Counter

1. if we need to keep all the historical data

1. if we need to keep all the historical data
use treemap<time, count>

hit: O(logn)
getHits: O(logn)

class HitCounter {
    
    TreeMap<Integer, Integer> map;
    int count = 0;
    public HitCounter() {
        map = new TreeMap<>();
    }
    
    public void hit(int timestamp) {
        count++;
        map.put(timestamp, count);
    }
    
    public int getHits(int timestamp) {
        Integer cur = map.floorKey(timestamp);
        int curCount = cur != null ? map.get(cur) : 0;
        
        int start = timestamp - 300;
        if (start >= 0) {
            Integer before = map.floorKey(start);
            return curCount - (before != null ? map.get(before) : 0);
        }
        return curCount;
    }
}

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 
 the past 300 seconds).
 
 timestamp parameter (in seconds granularity),
 timestamp is monotonically increasing
 
 Several hits may arrive roughly at the same time.
 
 Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
 
 Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).
 
 nput
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[],            [1],    [2],   [3],    [4],     [300], [300],      [301]]  => time
Output
[null, null, null, null, 3, null, 4, 3]

hits depends on time

1. if we need to keep all the historical data
use treemap<time, count>


2. no need to keep the historical data
but!

All the calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing).

this means getHits(time), the time is incresing, we dont need to look up old data

so the idea is queue, FIFO

 */

2. no need to keep the historical data

use queue, FIFO

T:
hit(): O(1)

getHits(): O(m)
最好的狀況, 直接拿到, 不用 poll, O(1)
最差的狀況是, 像是在 time = 1時 hit了 m 次, 到 301 秒 才 get, 這樣要 poll() m 次 => O(m)

S: O(n), 如果在 300秒內有 n 次 hits

class HitCounter {

    Queue<Integer> queue;
    public HitCounter() {
        queue = new LinkedList<>();
    }
    
    public void hit(int timestamp) {
        queue.offer(timestamp);
    }
    
    public int getHits(int timestamp) {
        // so if not meets the 300 seconds range's data, just abadon it
        while (!queue.isEmpty() && timestamp - queue.peek() >= 300) {
            queue.poll();
        }
        return queue.size();
    }
}

/**
ex:
     hit    getHits
[[], [1],  [301]], so abadon queue's peek

T:
hit(): O(1)

getHits(): O(m)
最好的狀況, 直接拿到, 不用 poll, O(1)
最差的狀況是, 像是在 time = 1時 hit了 m 次, 到 301 秒 才 get, 這樣要 poll() m 次 => O(m)

S: O(n), 如果在 300秒內有 n 次 hits
 */

but for huge data at the same time, queue is easy out of memory

# circular buffer idea

so just maintain two arrays (size 300) to keep data

T:

hit: O(1)

getHits: O(300)

S: O(600)

class HitCounter {

    int[] times;
    int[] hits;
    public HitCounter() {
        times = new int[300];
        hits = new int[300];
    }
    
    public void hit(int timestamp) {
        int idx = timestamp%300;
        if (times[idx] != timestamp) {
            times[idx] = timestamp;
            hits[idx] = 1;
        } else {
            hits[idx]++;
        }
    }
    
    public int getHits(int timestamp) {
        int result = 0;
        for (int i = 0; i < 300; i++) {
            // 301秒getHits,不需要 1秒的 data, so 301-i < 300, so i >= 2
            if (timestamp - times[i] < 300) { 
                result += hits[i];
            }
        }
        return result;
    }
}

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */

more comment

```java
class HitCounter {

    int[] hits = new int[300];
    int[] times = new int[300];
    public HitCounter() {
        this.hits = new int[300];
        this.times = new int[300];
    }
    
    public void hit(int timestamp) { 
        int i = timestamp%300;
        if (times[i] != timestamp) { // new timestamp, so override it, and count = 1
            times[i] = timestamp;
            hits[i] = 1;
        } else {
            hits[i]++; // same timestamp, so add count
        }
    }
    
    public int getHits(int timestamp) {
        int result = 0;
        for (int i = 0; i < 300; i++) {
            if (timestamp - times[i] < 300) { // only need past 300 secs
                result += hits[i];
            }
        }
        return result;
    }
}

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);

 hitTime % 300
  |           301
          300
 |----------|         
              
 1 2 3 4. 300 301. hits
                                 1     store in 1
                                 when 
 hit [300] -> store with t%300, 301 -> store in 1 

 this way only is suitable for hit and getHits by time order

This is very similar to the circular buffer I used in my senior design, very common practice I believe


use queue -> o(n)
301 300 4  3  2  1
 */
```