ধরুন আমরা একটি হিট কাউন্টার ডিজাইন করতে চাই যা গত 5 মিনিটে প্রাপ্ত হিটের সংখ্যা গণনা করে। একটি ফাংশন থাকবে এবং এটি দ্বিতীয় ইউনিটে একটি টাইমস্ট্যাম্প প্যারামিটার গ্রহণ করে এবং আমরা ধরে নিতে পারি যে সিস্টেমে কলগুলি কালানুক্রমিক ক্রমে করা হচ্ছে (তাই, টাইমস্ট্যাম্প একঘেয়েভাবে বাড়ছে)। আমরাও অনুমান করি যে প্রথম দিকের টাইমস্ট্যাম্প 1 এ শুরু হয়।
এটা সম্ভব যে একই সময়ে মোটামুটিভাবে একাধিক হিট আসে।
তাই আমরা হিট করার জন্য hit() ফাংশনকে কল করব এবং হিটের গণনা পেতে getHits() ফাংশনকে কল করব।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
300 আকারের একটি অ্যারে সময় নির্ধারণ করুন
-
300 আকারের একটি অ্যারে হিট সংজ্ঞায়িত করুন
-
একটি ফাংশন হিট(), এটি টাইমস্ট্যাম্প নিতে হবে,
-
idx :=টাইমস্ট্যাম্প মোড 300
-
যদি সময়[idx] টাইমস্ট্যাম্পের সমান না হয়, তাহলে -
-
time[idx] :=টাইমস্ট্যাম্প
-
হিট[idx] :=1
-
-
অন্যথায়
-
হিট[idx] :=হিট[idx] + 1
-
-
একটি ফাংশন সংজ্ঞায়িত করুন getHits(), এতে টাইমস্ট্যাম্প লাগবে,
-
ret :=0
-
আরম্ভ করার জন্য i :=0, যখন i <300, আপডেট করুন (i 1 দ্বারা বাড়ান), −
-
যদি টাইমস্ট্যাম্প - সময়[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
