A simple java solution that scales, O(1)both time and space! beats 94%


  • 2
    C
    public class HitCounter {
        Deque<Second> q = new LinkedList<Second>();
        int hits = 0;
        /** Initialize your data structure here. */
        public HitCounter() {
            
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            while(!q.isEmpty() && timestamp - q.peek().sec > 299){ //at most 299 cycles, therefore O(1)
                hits -= q.peek().count;
                q.poll();
            }
            if(!q.isEmpty() && q.peekLast().sec == timestamp){
                q.getLast().count++;
                hits++;
            }else{
                q.offer(new Second(timestamp));
                hits++;
            }
        }
        
        /** 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() && timestamp - q.peek().sec > 299){ //at most 299 cycles, therefore O(1)
                hits -= q.peek().count;
                q.poll();
            }
            return hits;
        }
    }
    class Second{
        int sec, count;
        public Second(int sec){
            this.sec = sec;
            count = 1;
        }
    }
    

    Each time we get a new window, we delete old Seconds and subtract counts from total hits.
    this solution also scales on space because we at most have 300 items on the queue. we combine identical hits.


  • 0
    K

    How it will scale if question asked for hit required in past 1000(or any higher value) minutes ?

    Below is my solution Insertion O(1) and query time log(N). Idea is similar to binary search.

    Code Link

    public class HitCounter {
        List<Integer> data;
        /** Initialize your data structure here. */
        public HitCounter() {
            data = new ArrayList();
            data.add(Integer.MIN_VALUE);
            data.add(Integer.MAX_VALUE);
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            data.set(data.size() - 1, timestamp);
            data.add(Integer.MAX_VALUE);
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int timestamp) {
            return getHitsBelow(timestamp + 1) - getHitsBelow(timestamp - 300 + 1);
        }
        
        private int getHitsBelow(int timestamp) {
            int lo = 0;
            int hi = data.size();
            while(lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if(data.get(mid) < timestamp && data.get(mid + 1) >= timestamp) {
                    return mid;
                }
                if(data.get(mid) >= timestamp) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            return hi;
        }
    }
    
    /**
     * Your HitCounter object will be instantiated and called as such:
     * HitCounter obj = new HitCounter();
     * obj.hit(timestamp);
     * int param_2 = obj.getHits(timestamp);
     */
    

  • 0
    T

    Same both O(1) of add and counts except I used a HashMap for scalability. The codes below is much more concise without complicate logic.

    public class HitCounter {
    HashMap<Integer,Integer> hits;  
    /** Initialize your data structure here. */
    public HitCounter() {
        this.hits = new HashMap<>();     
    }  
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        hits.put(timestamp, hits.getOrDefault(timestamp,0)+1);        
    }   
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {//all time stamps older than 5 mins will be removed, so that the total key size<=300
        int sum = 0;
        Iterator<Map.Entry<Integer,Integer>> entryIterator = hits.entrySet().iterator();
        while(entryIterator.hasNext()){
        	Map.Entry<Integer,Integer> entry = entryIterator.next();
        	if(timestamp-entry.getKey()>=300) entryIterator.remove();
        	else sum += entry.getValue();
        }
        return sum;
    }
    }

Log in to reply
 

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