Java scalable solution using HashMap and LinkedList


  • 1
    M
    public class HitCounter {
    
        // Stores the number of hits per timestamp
        private Map<Integer, Integer> map;
        
        // Stores the last 300 seconds timestamp records
        private LinkedList<Integer> list;
        
        /** Initialize your data structure here. */
        public HitCounter() {
            map = new HashMap();
            list = new LinkedList<Integer>();
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            // If new hit, add to map and
            // increment the hit count
            if(!map.containsKey(timestamp)) {
                map.put(timestamp, 1);
                list.add(timestamp);
            } else {
                // If previously hit, just
                // increment the hit count
                // No need to add it to list
                map.put(timestamp, map.get(timestamp) + 1);    
            }
            // On each hit, do a repair
            // so that we do not grow the
            // list and map indefinitely
            // untill a getHits is called.
            repair(timestamp);
        }
        
        // This will ensure on any hit or getHit,
        // we store data in the last 300 seconds
        private void repair(int timestamp) {
            while(!list.isEmpty()) {
                if(list.getFirst() > timestamp - 300) {
                    break;
                } else {
                    map.remove(list.removeFirst());
                }
            }
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int timestamp) {
            repair(timestamp);
            
            int ret = 0;
            for(int i : list) {
                ret += map.get(i);
            }
            return ret;
        }
    }
    

Log in to reply
 

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