Maintain an Inclusive Three-Second Request Window
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
Implement `RecentCounter()` and `ping(t)`. A ping adds a request at integer millisecond time t and returns the number of recorded requests in the inclusive interval `[t-3000,t]`, including the new request. Ping times are strictly increasing across calls.
```cpp
class RecentCounter {
public:
RecentCounter();
int ping(int t);
};
```
### Examples
**Example 1:**
```text
Input: construct RecentCounter(); call ping(10), ping(3010), ping(3011)
Output: [1,2,2]
Explanation: Time10 is included at3010 exactly on the boundary, then excluded at3011.
```
**Example 2:**
```text
Input: construct RecentCounter(); call ping(100), ping(5000)
Output: [1,1]
Explanation: The first request is older than the second call's window and is removed.
```
### Constraints
- `1 <= t <= 10^9`.
- Ping timestamps are strictly increasing.
- At most `10^4` ping calls occur.
### Contract considerations
This is the original online class, not a newly invented function over an array of timestamps.
```hint Read the boundary condition
With increasing timestamps, expired requests always form a prefix of a queue.
```
### Boundary reminders
This is the original online class, not a newly invented function over an array of timestamps.
Overview: Maintain an Inclusive Three-Second Request Window. Implement RecentCounter() and ping(t). A ping adds a request at integer millisecond time t and returns the number of recorded requests in the inclusive interval [t-3000,t], including the new request.