Design Hit Counter

A website wants to show how busy it is right now: how many visits ("hits") it received in the last 5 minutes. Time is measured in whole seconds. Implement the HitCounter class:

• HitCounter() creates a counter with no hits recorded.
• hit(timestamp) records one hit at second timestamp. Several hits can share the same second.
• getHits(timestamp) returns how many hits were recorded in the 300 seconds ending at timestamp: every hit whose time t satisfies timestamp - 300 < t <= timestamp.

So a hit at second t is counted by getHits up to and including second t + 299, and no longer from second t + 300 on.

Calls arrive in time order: each call's timestamp is at least the previous call's, whichever methods they are.

Each example lists the calls in order, then the arguments of each call, then what each call returns: null for the constructor and for hit, which returns nothing.

Example 1

Input:
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits", "getHits"]
[[], [10], [10], [150], [200], [309], [309], [310], [460]]
Output: [null, null, null, null, 3, null, 4, 2, 1]

At second 309 the window runs from 10 to 309, so all four hits count. One second later it starts at 11, and both hits from second 10 drop out. By second 460 the window starts at 161, leaving only the hit at 309.

Example 2

Input:
["HitCounter", "getHits", "hit", "hit", "getHits", "getHits", "hit", "getHits"]
[[], [4], [5000], [5299], [5299], [5300], [9000], [9000]]
Output: [null, 0, null, null, 2, 1, null, 1]

Before any hit the count is 0. The hit at 5000 is still counted at second 5299 (that is 5000 + 299), but not at 5300. A long quiet gap leaves only the newest hit.

Constraints

• 1 <= timestamp <= 2 * 10⁹
• The timestamp of each call is greater than or equal to the timestamp of the call before it.
• At most 300 calls are made in total to hit and getHits.