Fast scalable Java solution using Hashmap & queue & count


  • 0
    E
    class HitCounter {
        Map<Integer, Integer> map;
        Queue<Integer> q;
        int count;
        /** Initialize your data structure here. */
        public HitCounter() {
            q = new LinkedList<>();
            map = new HashMap<>();
            count = 0;
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            if (map.containsKey(timestamp)) {
                map.put(timestamp, map.get(timestamp) + 1);
                count++;
                return;
            }
            
            while(!q.isEmpty() && q.peek() <= timestamp - 300) {
                count -= map.get(q.peek());
                map.remove(q.poll());
            }
            
            q.offer(timestamp);
            map.put(timestamp, 1);
            count++;
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int timestamp) {
            while(!q.isEmpty() && q.peek() <= timestamp - 300) {
                count -= map.get(q.peek());
                map.remove(q.poll());
            }
            return count;
        }
    }
    

    Use hashMap to make the design scalable.
    Use count to speed up getHits().
    Use Queue to maintain FIFO order of append & remove data.


Log in to reply
 

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