Question

Formatted question description: https://leetcode.ca/all/362.html

 362	Design Hit Counter

 Design a hit counter which counts the number of hits received in the past 5 minutes.

 Each function accepts a timestamp parameter (in seconds granularity)
 and you may assume that calls are being made to the system in chronological order
 (ie, the timestamp is monotonically increasing).
 You may assume that the earliest timestamp starts at 1.

 It is possible that several hits arrive roughly at the same time.

 Example:

 HitCounter counter = new HitCounter();

 // hit at timestamp 1.
 counter.hit(1);

 // hit at timestamp 2.
 counter.hit(2);

 // hit at timestamp 3.
 counter.hit(3);

 // get hits at timestamp 4, should return 3.
 counter.getHits(4);

 // hit at timestamp 300.
 counter.hit(300);

 // get hits at timestamp 300, should return 4.
 counter.getHits(300);

 // get hits at timestamp 301, should return 3.
 counter.getHits(301);

 Follow up:
 What if the number of hits per second could be very large? Does your design scale?

 @tag-design

Algorithm

Use a queue, add the current timestamp to the queue every time you click, and then when you need to get the number of clicks, we start from the beginning of the queue,

  • If the time stamp at the beginning is beyond 5 minutes, delete it until the time stamp at the beginning stops within 5 minutes
  • Then the number of elements returned to the queue is the requested number of clicks

Follow-up question

Two one-dimensional arrays times and hits with a size of 300 are defined, which are used to store timestamps and hits respectively.

In the click function, take the time stamp to 300, and then check whether the previously saved time stamp in this position is the same as the current time stamp. It also means that it is the same time stamp, then the corresponding number of clicks will increase by 1, if not the same, it means that five minutes have passed, then reset the corresponding number of clicks to 1.

Then when returning the number of hits, we need to traverse the times array to find all the positions within 5 minutes, and then add up the number of clicks in the corresponding positions in hits.

Need further clarify:
  • real-time getHits() ?
  • batch off-line process, then getHits() ?

1st thought is map reduce, distribute to multiple hosts, so when getHits() need a broadcast to collect all data

options: 1. use a lock 2. equal distribution each machine works independently to count its own users from the past minute. When we request the global number, we just need to add all counters together.

Code

Java

import java.util.ArrayDeque;

public class Design_Hit_Counter {

    public class HitCounter {
        private ArrayDeque<Integer> queue; // @note: ArrayDeque has no capacity restrictions

        // Why is ArrayDeque better than LinkedList?
        // If you need add/remove of the both ends, ArrayDeque is significantly better than a linked list
        // https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist

        /** 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). */

        // Time Complexity : O(n)
        public int getHits(int timestamp) {
            int startTime = timestamp - 300;

            // remove all hits over 300 seconds old
            while(!queue.isEmpty() && queue.peek() <= startTime) {
                queue.poll();
            }
            return queue.size();
        }
    }

    public class HitCounterFollowUp {
        private int[] times;
        private int[] hits;

        /** Initialize your data structure here. */
        public HitCounterFollowUp() {
            int[] times = new int[300];
            int[] hits = new int[300];
        }

        /** Record a hit.
         @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            int idx = timestamp % 300;
            if (times[idx] != timestamp) {
                times[idx] = timestamp; // update with most recent timestamp
                hits[idx] = 1;
            } else {
                ++hits[idx];
            }
        }

        /** Return the number of hits in the past 5 minutes.
         @param timestamp - The current timestamp (in seconds granularity). */

        // Time Complexity : O(n)
        public int getHits(int timestamp) {
            int res = 0;
            for (int i = 0; i < 300; ++i) {
                if (timestamp - times[i] < 300) {
                    res += hits[i];
                }
            }
            return res;
        }
    }

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

All Problems

All Solutions