Java 108ms Queue solution with getHits() without counting the queue size.


  • 0

    Key points:
    (1) Keep a counter running and record the count at each hit.
    (2) Find the last count of the last 300 secs by dequeue.
    (3) The hit count is (the current counter - the last count).
    (4) Need to reset the counter when close to the limit.

    public class HitCounter {
        class Hit{
            int t;
            long c;
            Hit(int time, long count){
                t = time;
                c = count;
            }
        }
        LinkedList<Hit> hits;
        long counts = 0;
        long lastcount = 0;
        long BUFFER = Integer.MAX_VALUE-10;
        int range = 300;
        /** Initialize your data structure here. */
        public HitCounter() {
            hits = new LinkedList<Hit>();
            hits.offer( new Hit(0,0) );
        }
        
        public void removeTail(int time){
            while ( ! hits.isEmpty() &&  hits.peek().t <= time) {
                lastcount = hits.poll().c;
            }
        }
        
        public void reset(){
            for (Hit hit: hits) hit.c -= counts;
            lastcount -= counts;
            counts = 0;
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            ++counts;
            if (! hits.isEmpty() && hits.peekLast().t == timestamp ) {
                hits.getLast().c = counts;
            } else hits.offer( new Hit(timestamp, counts ) );
            if (counts >= BUFFER) reset();
            removeTail(timestamp - range);
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int timestamp) {
            removeTail(timestamp - range);
            return (int) (counts - lastcount);
        }
    }

  • 0
    K

    Actually, jdk's LinkedList implementation maintained the list size for you.


Log in to reply
 

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