In an API rate-limiting system, each incoming requ...

Below is an example of a concise, optimized C++ solution. The main idea is:

1. Track requests per domain using two deques (or queues) for each domain:

   • A 5-second deque to quickly check the number of requests within the last 5 seconds.
   • A 30-second deque to quickly check the number of requests within the last 30 seconds.

2. For each incoming request at time $t = i$:

   • Clean out entries in the 30-second deque older than $t - 30$.
     • If after cleaning, the deque size $\geq 5$, we reject the new request.
   • Clean out entries in the 5-second deque older than $t - 4$ (so that it covers the interval [$t-4$, $t$]).
     • If after cleaning, the deque size $\geq 2$, we reject the new request.
   • If not rejected, we insert $t$ into both deques and accept the request.

This ensures $O(1)$ amortized checks for each domain, since each request time is pushed and popped at most once from each deque. The solution easily handles up to $10^4$ requests.

cpp
#include <bits/stdc++.h>
using namespace std;

/*
    We define a function getDomainRequestStatus that takes:
      - n: number of requests
      - requests: vector of domain strings (each i-th request arrives at second i)

    Returns a vector of status messages corresponding to each request.

    Rate-limits:
      - At most 2 requests from the same domain in any rolling 5-second window
      - At most 5 requests from the same domain in any rolling 30-second window
*/

vector<string> getDomainRequestStatus(int n, const vector<string>& requests) {
    // We use an unordered_map (hash map) from domain -> pair of deques
    //   first deque  (fiveSec)  to track timestamps within the last 5 seconds
    //   second deque (thirtySec) to track timestamps within the last 30 seconds
    unordered_map<string, pair<deque<int>, deque<int>>> domainMap;
    domainMap.reserve(n);

    vector<string> result(n);

    for(int t = 0; t < n; t++){
        const string& domain = requests[t];
        
        // Retrieve (or create) the deques for this domain
        auto& dqPair = domainMap[domain];
        auto& fiveSec   = dqPair.first;   // holds times in [t-4, t]
        auto& thirtySec = dqPair.second;  // holds times in [t-29, t]

        // 1) Clean out old entries from the 30-second deque
        //    Remove all timestamps <= t-30
        while(!thirtySec.empty() && thirtySec.front() <= t - 30) {
            thirtySec.pop_front();
        }
        // 2) After cleaning, if size >= 5 => block (429)
        if(thirtySec.size() >= 5) {
            result[t] = "{status: 429, message: Too many requests}";
            continue; // do not record this request (do not push into deques)
        }

        // 3) Clean out old entries from the 5-second deque
        //    Remove all timestamps < t-4
        while(!fiveSec.empty() && fiveSec.front() < t - 4) {
            fiveSec.pop_front();
        }
        // 4) After cleaning, if size >= 2 => block (429)
        if(fiveSec.size() >= 2) {
            result[t] = "{status: 429, message: Too many requests}";
            continue; // do not push the new request into the deques
        }

        // If neither limit is exceeded, accept the request
        fiveSec.push_back(t);
        thirtySec.push_back(t);
        result[t] = "{status: 200, message: OK}";
    }

    return result;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;  // number of requests

    vector<string> requests(n);
    for(int i = 0; i < n; i++){
        cin >> requests[i];  // read each domain request
    }

    // Compute the statuses
    vector<string> statuses = getDomainRequestStatus(n, requests);

    // Output the result
    for(const auto &s : statuses){
        cout << s << "\n";
    }

    return 0;
}

Explanation of Key Steps

1. unordered_map<string, pair<deque<int>, deque<int>>> domainMap;
   We keep for each domain two separate deques:

   • fiveSec tracks the timestamps of requests within the last 5 seconds.
   • thirtySec tracks the timestamps of requests within the last 30 seconds.

2. Rolling Window Updates
   For a new request at time $t$:

   • Remove from thirtySec any timestamps $\leq t - 30$. This ensures only requests in the last 30 seconds remain.
   • If after removal, thirtySec.size() $\ge 5$, block this request (rate limit reached).
   • Remove from fiveSec any timestamps $< t - 4$. This ensures only requests in $[t-4, t]$ remain.
   • If after removal, fiveSec.size() $\ge 2$, block this request (rate limit reached).
   • If not blocked, we push the current time $t$ into both deques and mark the request as allowed.

3. Complexities

   • Each request time $t$ is pushed and popped at most once from each deque, so all operations over $n$ requests are $O(n)$ in total.
   • We use unordered_map to look up the deques for a given domain in average $O(1)$ time.

This satisfies the constraints and ensures a clean, efficient rate-limiting mechanism for the 5-second and 30-second windows.