Formatted question description: https://leetcode.ca/all/362.html
362 Design Hit Counter Design a hit counter which counts the number of hits received in the past 5 minutes. Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1. It is possible that several hits arrive roughly at the same time. Example: HitCounter counter = new HitCounter(); // hit at timestamp 1. counter.hit(1); // hit at timestamp 2. counter.hit(2); // hit at timestamp 3. counter.hit(3); // get hits at timestamp 4, should return 3. counter.getHits(4); // hit at timestamp 300. counter.hit(300); // get hits at timestamp 300, should return 4. counter.getHits(300); // get hits at timestamp 301, should return 3. counter.getHits(301); Follow up: What if the number of hits per second could be very large? Does your design scale? @tag-design
Use a queue, add the current timestamp to the queue every time you click, and then when you need to get the number of clicks, we start from the beginning of the queue,
- If the time stamp at the beginning is beyond 5 minutes, delete it until the time stamp at the beginning stops within 5 minutes
- Then the number of elements returned to the queue is the requested number of clicks
Two one-dimensional arrays times and hits with a size of 300 are defined, which are used to store timestamps and hits respectively.
In the click function, take the time stamp to 300, and then check whether the previously saved time stamp in this position is the same as the current time stamp. It also means that it is the same time stamp, then the corresponding number of clicks will increase by 1, if not the same, it means that five minutes have passed, then reset the corresponding number of clicks to 1.
Then when returning the number of hits, we need to traverse the times array to find all the positions within 5 minutes, and then add up the number of clicks in the corresponding positions in hits.
Need further clarify:
- real-time getHits() ?
- batch off-line process, then getHits() ?
1st thought is map reduce, distribute to multiple hosts, so when getHits() need a broadcast to collect all data
options: 1. use a lock 2. equal distribution each machine works independently to count its own users from the past minute. When we request the global number, we just need to add all counters together.