Number of Recent Calls – Queue Data Structure Exercise

Write a class RecentCounter to count recent requests. It has only one method: ping(int t), where t represents some time in milliseconds. Return the number of pings that have been made from 3000 milliseconds ago until now. Any ping with time in [t – 3000, t] will count, including the current ping. It is guaranteed that every call to ping uses a strictly larger value of t than before.

Example 1:
Input: inputs = [“RecentCounter”,”ping”,”ping”,”ping”,”ping”], inputs = [[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]

Note:
Each test case will have at most 10000 calls to ping.
Each test case will call ping with strictly increasing values of t.
Each call to ping will have 1 <= t <= 10^9.

The Queue is a First In First Out Data Structure that is commonly used to solve problems. The above puzzle is actually quite similar to the one asked by one Google Interviewer e.g. Print Message Problem. The Queue is very useful in purging out old messages/calls.

In the following Java solution, we declare a queue using LinkedList, every call to the Ping, we add the call to the queue and purge out old calls (poping out the queue using the poll method).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class RecentCounter {
    public RecentCounter() {
         time = new LinkedList<Integer>();
    }
    
    public int ping(int t) {
        time.add(t);
        while (time.peek() < t - 3000) {
            time.poll();
        }
        return time.size();
    }
    
    private Queue<Integer> time;
}
/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

class RecentCounter {
    public RecentCounter() {
         time = new LinkedList<Integer>();
    }
    
    public int ping(int t) {
        time.add(t);
        while (time.peek() < t - 3000) {
            time.poll();
        }
        return time.size();
    }
    
    private Queue<Integer> time;
}
/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

The C++ solution is quite the same, except that the name of the pop method is pop and the peek method is front.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class RecentCounter {
public:
    RecentCounter() {
    }
 
    int ping(int t) {
        time.push(t);
        while (time.front() < t - 3000) {
            time.pop();
        }
        return time.size();
    }
private:
    queue<int> time;
};
 
/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter obj = new RecentCounter();
 * int param_1 = obj.ping(t);
 */

class RecentCounter {
public:
    RecentCounter() {
    }

    int ping(int t) {
        time.push(t);
        while (time.front() < t - 3000) {
            time.pop();
        }
        return time.size();
    }
private:
    queue<int> time;
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter obj = new RecentCounter();
 * int param_1 = obj.ping(t);
 */

–EOF (The Ultimate Computing & Technology Blog) —