Java code with circular buffer


  • 0
    L

    Complexity would be much less than O(300) if getHits/hit are called frequently. Synchronization is inevitable in concurrent scenarios, by the way, but the optimization used here can help speeding up the time spent in the critical sections.

    public class HitCounter {
    
        int[] cache;
        int last;
        int sum;
        /** Initialize your data structure here. */
        public HitCounter() {
            cache = new int[300];
            last = 1;
            sum = 0;
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int t) {
            updateCache(t);
            cache[t%300] += 1;
            sum+=1;
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int t) {
            updateCache(t);
            return sum;
        }
        
        private void updateCache(int t) {
            int span = t - last;
            if (span>=300) {
                cache = new int[300];
                sum = 0;
            } else {
                for (int i=1; i<=span; i++) {
                    int idx = (last+i)%300;
                    sum -= cache[idx];
                    cache[idx]=0;
                }
            }
            last = t;
        }
    }
    
    /**
     * Your HitCounter object will be instantiated and called as such:
     * HitCounter obj = new HitCounter();
     * obj.hit(timestamp);
     * int param_2 = obj.getHits(timestamp);
     */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.