Recent calls counter
A server wants to know how busy it has been lately. Write a class RecentCounter with one method, ping(t). A call ping(t) means one request reached the server at time t, measured in milliseconds (ms). It returns the number of requests, this one included, that reached the server no more than 3,000 ms before t.
So count the requests with a time from t - 3000 to t, both ends included. A request exactly 3,000 ms old still counts; one 3,001 ms old does not.
Times only go up: each call's t is larger than the previous call's. In the examples, the calls run in order on one new RecentCounter(), and the output lists what each call returns.
ping(100), ping(2000), ping(2500), ping(4000), ping(7000)Output1, 2, 3, 3, 2At 4000 the window is 1000 to 4000, so the request at 100 no longer counts. At 7000 the window is 4000 to 7000: 2000 and 2500 drop out, and 4000 is exactly 3,000 ms old, so it stays.
ping(1), ping(2), ping(3), ping(9000)Output1, 2, 3, 1At 9000 all three earlier requests are too old, so three drop out at once.
ping(10), ping(3010), ping(3011)Output1, 2, 2At 3010 the request at 10 is exactly 3,000 ms old and counts. At 3011 it is 3,001 ms old and does not.
1 ≤ t ≤ 109, a whole number of milliseconds.
Every call's
tis larger than the one before.At most 105 calls to
ping.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.