Hit counter
Build a class HitCounter that records events, called hits, and answers one question: how many hits happened in the 300 seconds (5 minutes) up to a given second?
HitCounter()starts with no hits.hit(timestamp)records one hit at secondtimestamp.get_hits(timestamp)returns how many recorded hits have a timetwithtimestamp - 300 < t ≤ timestamp. So a hit exactly 300 seconds old no longer counts. Asking records nothing.
Calls arrive in time order: each call's timestamp is at least the previous call's. Many hits can arrive in the same second. (LeetCode spells the second method getHits.)
hit(5), hit(9), hit(9), get_hits(10), hit(120), get_hits(304), get_hits(305), get_hits(309)Outputthe four get_hits calls return 3, 4, 3, 1At second 305 the hit from second 5 is 300 seconds old and drops out. At 309 both hits from second 9 drop out too.
hit(10), hit(20), get_hits(309), get_hits(310), get_hits(1000)Outputthe three get_hits calls return 2, 1, 0At 310 the hit from second 10 is exactly 300 seconds old. By 1000 every hit is too old.
1 ≤ timestamp ≤ 2 × 109
Timestamps never decrease from one call to the next.
Up to 105 calls in total; many hits can share one second.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.