समस्या विवरण
मान लीजिए हम एक हिट काउंटर डिजाइन करना चाहते हैं जो पिछले 5 मिनट में प्राप्त हिट्स की संख्या गिनता है। एक फ़ंक्शन होगा जो सेकंड इकाई में टाइमस्टैम्प पैरामीटर स्वीकार करता है और हम मान सकते हैं कि सिस्टम को कॉल कालानुक्रमिक क्रम में की जा रही हैं (इसलिए, टाइमस्टैम्प नीरस रूप से बढ़ रहा है)। हम यह भी मानते हैं कि सबसे पहला टाइमस्टैम्प 1 से शुरू होता है।
यह संभव है कि कई हिट लगभग एक ही समय पर आएं।
तो हम हिट करने के लिए hit() फ़ंक्शन को कॉल करेंगे और हिट्स की संख्या प्राप्त करने के लिए getHits() फ़ंक्शन को।
समाधान दृष्टिकोण
सर्कुलर बफर (आकार 300 = 5 मिनट × 60 सेकंड) का उपयोग करके:
- आकार 300 की दो सरणियां परिभाषित करें: time और hits
- 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 लौटाएं
C++ कार्यान्वयन
#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;
}
};
int 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));
return 0;
}
इनपुट
ob.hit(1); ob.hit(2); ob.hit(3); ob.getHits(4); ob.hit(300); ob.getHits(300); ob.getHits(301);
आउटपुट
3 4 3
