Design Hit Counter
Count how many hits arrived in the last five minutes. hit(t) records one hit at second t. getHits(t) returns how many hits landed in the 300 seconds that end at t: seconds t-299 through t, both included. A hit exactly 300 seconds old no longer counts. Every call carries a second, and it is never smaller than the second on the call before it. Several hits can share the same second. The script driver below replays a list of calls and collects what each getHits returned. Limits: at most 500000 calls, 1 <= t <= 2000000000. Example: HitCounter() hit(10), hit(20), hit(20), getHits(25) -> 3 hit(305), getHits(309) -> 4 (the hit at 10 is 299 seconds old) getHits(310) -> 3 (now it is 300 seconds old and gone) getHits(605) -> 0
You're counting hits on a page, but only the ones from the last five minutes. The window is exact: a hit 299 seconds old still counts, and one 300 seconds old does not. Keeping every hit and rescanning them all works until the traffic shows up. Expect up to 500,000 calls, most of them hits.
Examples
You write
HitCounter: hit(timestamp: int), get_hits(timestamp: int)
Example 1
- Input
- HitCounter(), hit(10), hit(20), hit(20), getHits(25) => 3, hit(305), getHits(309) => 4, getHits(310) => 3, getHits(605) => 0
- returns
- [3, 4, 3, 0]
Example 2
- Input
- HitCounter(), getHits(1) => 0, hit(1), getHits(1) => 1
- returns
- [0, 1]
Save this for your laptop
The editor and Run need a bigger screen. The link opens Design Hit Counter ready to code. It is free, and the editor needs no account.
The pattern behind it
Design
I reach for it when
- The statement describes a class with methods, not one function.
- Each method needs to be fast, and the structure decides how fast.
Say this before you type. Say each method, the cost you want from it, and the structure that earns that cost.
All 28 Design problemsArrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 126 Arrays & Hashing problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.