To the chase

Number of recent requests

Write a RecentCounter class to count the most recent requests within a specific time range.

Please implement RecentCounter class:

  • RecentCounter() initializes the counter with 0 requests.

  • Int ping(int t) adds a new request at time t, where t represents some time in milliseconds, and returns the number of all requests (including new requests) that occurred in the last 3000 milliseconds. Specifically, return the number of requests that occurred within [T-3000, t].

Make sure that each call to ping uses a larger t value than before.

Example:

Input: [" RecentCounter ", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] output: [null, 1, 2, 3, 3] :  RecentCounter recentCounter = new RecentCounter(); recentCounter.ping(1); // requests = [1], range [-2999,1], returns 1 recentCounter.ping(100); // requests = [1], range [-2999,1], returns 1 recentCounter.ping(100); // requests = [1, 100] in the range [-2900,100], returns 2 recentCounter.ping(3001); // requests = [1, 100] in the range [-2900,100], returns 2 recentCounter.ping(3001); // requests = [1, 100, 3001] in range [1,3001], return 3 recentCounter.ping(3002); // requests = [1, 100, 3001] in range [1,3001], return 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002] in the range [2,3002], return 3Copy the code

Resolution:

It looks complicated, but it’s actually quite simple.

Assume that the time node of the first ping is 1, then the range that meets the conditions is >= 1-3000 and less than 1

Similarly, the time node of the NTH ping is M, and the range that meets the conditions is n-3000 <= x <= N

So we just need to save the request time nodes for each time, and then iterate to get the number of satisfying the condition range.

So the constructor should be an array that holds all of the requests, and the ping function should find the number that meets the criteria. The simplest implementation:

var RecentCounter = function() {
    this.requestList = []
};


/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
   let count = 1
   this.requestList.forEach(t1 => {
       t1 >= t - 3000 && count++
   })

   this.requestList.push(t)
    return count
};
Copy the code

The same can be done with the filter function.

var RecentCounter = function() {
    this.requestList = []
};


/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
   this.requestList.push(t)
    return this.requestList.filter(t1 => {
        return t1 >= t - 3000
    }).length
};

Copy the code

The filter function is much cleaner in code volume, but slightly less efficient in performance.

So how to improve performance in the case of large amount of data?

It is not difficult to see that when we calculate the new request that satisfies the condition, the previous request that does not satisfy the condition must not satisfy the condition in the subsequent request

Since time is impossible to go back, you can no longer satisfy >= t-3000 before, then t is strictly increasing, which will cause the previously unsatisfied request to be more unsatisfied later. So we can discard unqualified requests after each ping and form a new requestList.

Final code:

var RecentCounter = function() {
    this.requestList = []
};


/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
  this.requestList.push(t)
   this.requestList = this.requestList.filter(t1 => {
       return t1 >= t - 3000
   })
   return this.requestList.length
};
Copy the code

Although the result is only 400ms, it is a 50% improvement over the original time, and this is especially noticeable when there is a large amount of data.