C++-এ Design Hit Counter: গত ৫ মিনিটের হিট কাউন্টার ডিজাইন করা

একটি হিট কাউন্টার ডিজাইন করতে হবে যা গত ৫ মিনিট (৩০০ সেকেন্ড) এ প্রাপ্ত হিটের সংখ্যা গণনা করতে পারে। hit(timestamp) ফাংশন দিয়ে হিট রেকর্ড করব এবং getHits(timestamp) দিয়ে গত ৩০০ সেকেন্ডের হিট কাউন্ট পাব। টাইমস্ট্যাম্প ক্রোনোলজিক্যালি বেড়ে যাবে (মনোটোনিক্যালি ইনক্রিজিং)।

সমাধানের পদ্ধতি (Circular Array / Ring Buffer)

সাইজ ৩০০ এর দুটি অ্যারে ব্যবহার করা হয়: time[] (টাইমস্ট্যাম্প সংরক্ষণ) এবং hits[] (কাউন্ট সংরক্ষণ)। সূচক হবে timestamp % 300।

1. hit(timestamp):
   • idx = timestamp % 300
   • যদি time[idx] != timestamp হয় (পুরানো ডেটা), তবে time[idx] = timestamp এবং hits[idx] = 1 সেট করুন।
   • অন্যথায় hits[idx]++ করুন।
2. getHits(timestamp):
   • ret = 0 আরম্ভ করুন।
   • ০ থেকে ২৯৯ পর্যন্ত লুপ চালান।
   • যদি timestamp - time[i] < 300 হয় (গত ৩০০ সেকেন্ডের মধ্যে), তবে 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;  // 3
    ob.hit(300);
    cout << (ob.getHits(300)) << endl; // 4
    cout << (ob.getHits(301));         // 3
    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