ออกแบบ Hit Counter ใน C++

สมมติว่าเราต้องการออกแบบ hit counter ที่นับจำนวน hits ที่ได้รับใน 5 นาทีที่ผ่านมา จะมีฟังก์ชันที่รับพารามิเตอร์ timestamp ในหน่วยวินาที และเราสามารถสมมติได้ว่าการเรียกใช้ระบบทำตามลำดับเวลา (timestamp เพิ่มขึ้นอย่างต่อเนื่อง) เรายังสมมติได้ว่า timestamp เริ่มต้นที่ 1

เป็นไปได้ว่า hits หลายครั้งจะมาถึงในเวลาใกล้เคียงกัน

เราจะเรียกฟังก์ชัน hit() เพื่อบันทึก hit และ getHits() เพื่อรับจำนวน hits

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −

• กำหนดอาร์เรย์ time ขนาด 300

• กำหนดอาร์เรย์ hits ขนาด 300

• กำหนดฟังก์ชัน hit() รับ timestamp

• idx := timestamp mod 300

• ถ้า time[idx] ไม่เท่ากับ timestamp แล้ว −

  • time[idx] := timestamp

  • hits[idx] := 1

• มิฉะนั้น

  • hits[idx] := hits[idx] + 1

• กำหนดฟังก์ชัน getHits() รับ timestamp

• ret := 0

• ลูป i := 0 ถึง 299 ทำ −

  • ถ้า timestamp - time[i] < 300 แล้ว −

    • ret := ret + hits[i]

• คืนค่า ret

ตัวอย่าง

ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −

#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