C++의 히트 카운터 디자인

지난 5분 동안 수신된 히트 수를 계산하는 히트 카운터를 설계한다고 가정합니다. 두 번째 단위에서 타임스탬프 매개변수를 받아들이는 함수가 있고 시간 순서대로 시스템에 호출이 이루어지고 있다고 가정할 수 있습니다(따라서 타임스탬프가 단조롭게 증가함). 또한 가장 빠른 타임스탬프가 1에서 시작한다고 가정합니다.

여러 히트가 거의 동시에 도착할 수 있습니다.

따라서 hit() 함수를 호출하여 적중하고 getHits() 함수를 호출하여 적중 횟수를 얻습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 크기가 300인 배열 시간 정의

• 크기가 300인 배열 히트 정의

• hit() 함수를 정의하면 타임스탬프가 필요합니다.

• idx :=타임스탬프 모드 300

• time[idx]가 타임스탬프와 같지 않으면 -

  • 시간[idx] :=타임스탬프

  • 조회수[idx] :=1

• 그렇지 않으면

  • 조회수[idx] :=조회수[idx] + 1

• getHits() 함수를 정의하면 타임스탬프가 필요합니다.

• ret :=0

• initialize i :=0의 경우, i <300일 때 업데이트(i를 1만큼 증가), 수행 -

  • 타임스탬프 - time[i] <300이면 -

    • ret :=ret + 히트[i]

• 리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class HitCounter {
public:
   vector<int< time;
   vector<int< hits;
   HitCounter(){
      time = vector<int<(300);
      hits = vector<int<(300);
   }
   void hit(int timestamp){
      int idx = timestamp % 300;
      if (time[idx] != timestamp) {
         time[idx] = timestamp;
         hits[idx] = 1;
      }
      else {
         hits[idx] += 1;
      }
   }
   int getHits(int timestamp){
      int ret = 0;
      for (int i = 0; i < 300; i++) {
         if (timestamp - time[i] < 300) {
            ret += hits[i];
         }
      }
      return ret;
   }
};
main(){
   HitCounter ob;
   ob.hit(1);
   ob.hit(2);
   ob.hit(3);
   cout << (ob.getHits(4)) << endl;
   ob.hit(300);
   cout << (ob.getHits(300)) << endl;
   cout << (ob.getHits(301));
}

입력

ob.hit(1);
ob.hit(2);
ob.hit(3);
ob.getHits(4);
ob.hit(300);
ob.getHits(300);
ob.getHits(301);

출력

3
4
3