Leetcode #362. Design Hit Counter

[yokostan]

class HitCounter {
    public Queue<Integer> queue;

    /** Initialize your data structure here. */
    public HitCounter() {
        queue = new ArrayDeque<Integer>();
    }

    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        queue.offer(timestamp);
    }

    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        while (!queue.isEmpty() && timestamp - queue.peek() >= 300) {
            queue.poll();
        }
        return queue.size();
    }
}

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */

Changing ArrayDeque to LinkedList works as well. The difference between ArrayDeque and LinkedList(from Stack Overflow): Linked structures are possibly the worst structure to iterate with a cache miss on each element. On top of it they consume way more memory.

If you need add/remove of the both ends, ArrayDeque is significantly better than a linked list. Random access each element is also O(1) for a cyclic queue.

The only better operation of a linked list is removing the current element during iteration.

Methods: ArrayDeque: add, addFirst, addLast, clear, size, clone, contains, Iterator(), offer, offerFirst, offerLast, peek, peekFirst, peekLast, poll, pollFirst, pollLast, pop (for stack), push (for stack).

LinkedList: add, addAll, addFirst, addLast, clear. size, clone, contains, descendingIterator, getFirst, getLast, indexOf, offer, offerFirst, offerLast, peek..., poll..., pop..., push...