Straight-forward Java Solution using Queue


  • 5
    public class HitCounter {
        
        class Tuple {
            int time;
            int count;
            public Tuple(int time, int count) {
                this.time = time;
                this.count = count;
            }
        }
        
        Queue<Tuple> q;
        int currCount;
    
        public HitCounter() {
            q = new LinkedList<>();
            currCount = 0;
        }
        
        public void hit(int timestamp) {
            advance(timestamp);
            if(!q.isEmpty() && q.peek().time==timestamp) {
                q.peek().count += 1;
            } else {
                q.offer(new Tuple(timestamp, 1));
            }
            currCount += 1;
        }
        
        private void advance(int timestamp) {
            while(!q.isEmpty() && q.peek().time <= timestamp-300) {
                currCount -= q.poll().count;
            }
        }
        
        public int getHits(int timestamp) {
            advance(timestamp);
            return currCount;
        }
    

    }


  • 0
    K
    This post is deleted!

  • 0
    S

    What does this statement mean? What will happen if it were removed?

    if(!q.isEmpty() && q.peek().time==timestamp) {
    q.peek().count += 1;
    }


  • 2
    W

    I don't think you should peek the first element:
    if(!q.isEmpty() && q.peek().time==timestamp) {
    q.peek().count += 1;
    }

    Instead, you should peek the last element, like in a Deque.
    Otherwise, assume you get one hit at time 5, and then you get 1 million hits at time 6.
    Time 5 will remain in the queue because it is only 1 sec away.
    You only peek the first (time 5) and see the timestamp is not 6.
    As a result for the 1 million hits you will add 1 million Tuples to the queue with timestamp 6.

    If you peek the last element, you can keep modifying the last element for the 1 million hits.


  • 0
    A

    @pinkfloyda Is this solution scalable?
    Also what are the running times for the functions hits() and getHits()?


  • 0
    A

    @pinkfloyda If hit() is anyway calling advance() to poll the timestamps above 300 seconds, then why do we need call advance() again in the getHits() function?

    Could you please present an example where such need arises?


  • 0
    C

    @acheiver advance() is necessary in getHit. An example is [hit(1), getHits(301)]. It is optional in hit(). But better to have to keep queue size less than 300.

    wei88 is right. It should be
    if(!q.isEmpty() && q.peekLast().time==timestamp) {
    q.peekLast().count += 1;
    }

    I prefer to add a increase() method into Tuple and change constructor to Tuple(int time)


Log in to reply
 

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