10k

362. Design Hit Counter

Published on

Question

Design a hit counter that calls hit every time a message comes in and passes in the timestamp; when getCounter is called and the timestamp is passed in, it counts the number of hits within the timestamp -300s.

Implement the HitCounter class:

  • HitCounter() Initializes the object of the hit counter system.
  • void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
  • int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

Example

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1); // hit at timestamp 1.
hitCounter.hit(2); // hit at timestamp 2.
hitCounter.hit(3); // hit at timestamp 3.
hitCounter.getHits(4); // get hits at timestamp 4, return 3.
hitCounter.hit(300); // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

Algorithm

This topic sees the number of waist acid getHit with the previous 300s, then you need to record the timestamp of each hit when it comes in, at first I wanted to use Map to do the record, then I thought about it again, what is the key? It does not seem to be used. So it says that you should only need to store the timestamp.

This question is also the old to be abandoned, only to retain records within 300s, then it is FIFO. with queue can be.

The key point of the implementation process is that when a hit is put in, when taking the number of hits, traversing from the head of the queue, do not meet the conditions of the discard can be (assuming that the topic does not discuss too much whether these outdated data is still needed, you can confirm with the questioner). Until the data is within the current timestamp of -300s.

Code 1

class HitCounter {
    Queue<Integer> queue;

    public HitCounter() {
        this.queue = new LinkedList<>();
    }
    
    public void hit(int timestamp) {
        queue.add(timestamp);
    }
    
    public int getHits(int timestamp) {
        while (!queue.isEmpty() && queue.peek() <= timestamp - 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);
 */

Follow up

The follow up of this topic is that there is a point in time (timestamp) where more than one hit comes at the same time. can your code support scaling.

The above code 1 is supported. But the official solution gives a way to use deque to store a pair, saving each timestamp and the number of hits for that timestamp.

With deque is that he can support the offer and poll at the end of the queue; but I did not use it in the process of implementation; I think queue is still enough.

In addition to store the number of hit timestamp this is really an optimization. Previously, it was to store one for each hit, but now if there are n hits at the same time, under that timestamp, it doesn't need to be O(n), but only O(1).

Code 2

Based on Follow up my implementation

class HitCounter {
    Deque<int[]> queue;

    public HitCounter() {
        this.queue = new LinkedList<>();
    }
    
    public void hit(int timestamp) {
        if (!queue.isEmpty() && queue.peekLast()[0] == timestamp) {
            int[] pair = queue.pollLast();
            queue.offerLast(new int[]{pair[0], pair[1] + 1});
        } else {
            queue.offerLast(new int[]{timestamp, 1});
        }
        // queue.add(timestamp);
    }
    
    public int getHits(int timestamp) {
        while (!queue.isEmpty() && queue.peekFirst()[0] <= timestamp - 300) {
            queue.pollFirst();
        }
        int sum = 0;
        for (int[] pair : queue) {
            sum += pair[1];
        }
        return sum;
    }
}

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

Official Solution

class HitCounter {

    private int total;
    private Deque<Pair<Integer, Integer>> hits; 

    /* Initialize your data structure here. */
    public HitCounter() {
        // Initialize total to 0
        this.total = 0;
        this.hits = new LinkedList<Pair<Integer, Integer>>();
    }
    
    /* Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        if (this.hits.isEmpty() || this.hits.getLast().getKey() ! = timestamp) {
            // Insert the new timestamp with count = 1
            this.hits.add(new Pair<Integer, Integer>(timestamp, 1));
        } else {
            // Update the count of latest timestamp by incrementing the count by 1

            // Obtain the current count of the latest timestamp 
            int prevCount = this.bits.getLast().getValue();
            // Remove the last pair of (timestamp, count) from the deque
            this.hits.removeLast();
            // Insert a new pair of (timestamp, updated count) in the deque
            this.bits.add(new Pair<Integer, Integer>(timestamp, prevCount + 1));
        }
        // Increment total
        this.total++;
    }
    
    /* Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        while (!this.hits.isEmpty()) {
            int diff = timestamp - this.bits.getFirst().getKey();
            if (diff >= 300) {
                // Decrement total by the count of the oldest timestamp
                this.total -= this.bits.getFirst().getValue();
                this.bits.removeFirst();
            }
            else break;
        }
        return this.total;
    }
}

But another point I can learn is that I used a loop to calculate the count at the end, while the official answer used a total to update it at each add and remove, and returned it directly at the end.

The other difference is that the official answer uses an object to store the timestamp and his quantity information, so that the access looks clearer; I used a simple array.

问题

设计一个hit counter，每次有消息来的时候就会调用hit并传入时间戳；当调用getCounter并传入时间戳，计数时间戳-300s之内的hit数量。

Implement the HitCounter class:

  • HitCounter() Initializes the object of the hit counter system.
  • void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
  • int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

例子

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

算法

这个题目看到要算getHit与之前300s内的数量，那么需要记录每个hit进来时的时间戳，一开始想用Map做记录，然后又转念一想，key是什么？似乎用不到。所以就说应该是只需要存时间戳即可。

这个题也是老的要被抛弃，只保留300s内的记录，那么就是FIFO。用queue即可。

实现过程的关键点在于，当一个hit来的时候就放进去，当取这个hit数量的时候，从队头遍历，不满足条件的抛弃即可（假设这个题目没有过多讨论这些过时的数据是否还需要，可以跟出题人确认）。直到数据在当前时间戳-300s范围内。

代码1

class HitCounter {
    Queue<Integer> queue;

    public HitCounter() {
        this.queue = new LinkedList<>();
    }
    
    public void hit(int timestamp) {
        queue.add(timestamp);
    }
    
    public int getHits(int timestamp) {
        while (!queue.isEmpty() && queue.peek() <= timestamp - 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);
 */

Follow up

这个题目的Follow up是说，存在一个时间点（时间戳）同时来了多个hit。你的代码是否可以支持scaling。

上面的代码1是支持的。但是官方的solution给了一个方式说使用deque来存储一个pair，保存每个时间戳以及那个时间戳hit的数量即可。

用deque是说他可以支持队头队尾的offer和poll；但是我在实现的过程中并没有用到；我觉得queue依然够用；

另外存时间戳的hit数量这确实是一个优化。之前是每次hit都要存一个，现在如果同一时间hit了n个，在那个时间戳下，不需要O(n)，只需要O(1)。

代码2

基于Follow up我的实现

class HitCounter {
    Deque<int[]> queue;

    public HitCounter() {
        this.queue = new LinkedList<>();
    }
    
    public void hit(int timestamp) {
        if (!queue.isEmpty() && queue.peekLast()[0] == timestamp) {
            int[] pair = queue.pollLast();
            queue.offerLast(new int[]{pair[0], pair[1] + 1});
        } else {
            queue.offerLast(new int[]{timestamp, 1});
        }
        // queue.add(timestamp);
    }
    
    public int getHits(int timestamp) {
        while (!queue.isEmpty() && queue.peekFirst()[0] <= timestamp - 300) {
            queue.pollFirst();
        }
        int sum = 0;
        for (int[] pair : queue) {
            sum += pair[1];
        }
        return sum;
    }
}

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

Official Solution

class HitCounter {

    private int total;
    private Deque<Pair<Integer, Integer>> hits; 

    /** Initialize your data structure here. */
    public HitCounter() {
        // Initialize total to 0
        this.total = 0;
        this.hits = new LinkedList<Pair<Integer, Integer>>();
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        if (this.hits.isEmpty() || this.hits.getLast().getKey() != timestamp) {
            // Insert the new timestamp with count = 1
            this.hits.add(new Pair<Integer, Integer>(timestamp, 1));
        } else {
            // Update the count of latest timestamp by incrementing the count by 1

            // Obtain the current count of the latest timestamp 
            int prevCount = this.hits.getLast().getValue();
            // Remove the last pair of (timestamp, count) from the deque
            this.hits.removeLast();
            // Insert a new pair of (timestamp, updated count) in the deque
            this.hits.add(new Pair<Integer, Integer>(timestamp, prevCount + 1));
        }
        // Increment total
        this.total++;
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        while (!this.hits.isEmpty()) {
            int diff = timestamp - this.hits.getFirst().getKey();
            if (diff >= 300) {
                // Decrement total by the count of the oldest timestamp
                this.total -= this.hits.getFirst().getValue();
                this.hits.removeFirst();
            }
            else break;
        }
        return this.total;
    }
}

不过我还有一个可以学习的点是，我最后用了一个循环去计算了count，而官方解答多利用了一个total在每次add和remove的时候就做了更新，最后直接返回。

另外区别就是，官方答案用了一个object来存时间戳和他的数量信息，这样存取都看起来更清晰；我用的是一个简单的数组。

Thoughts? Leave a comment