Rate limiter

Questions 1 to 5 of 7

1. 1. The rate limiter stores a std::deque of request times for each user, not a single counter. Why?

   A deque sorts the times by itself, so the limiter never has to compare themA counter cannot be stored in an unordered_map, so the limiter needs a containerA single count tells how many requests happened, but not which ones have left the window; a queue keeps each time, so the old ones can be removedA deque uses less memory than a counter for the same user
2. 2. What does this program print? ``cpp #include <deque> #include <iostream> #include <initializer_list> int main() { const int limit = 2; const long long window = 5; std::deque<long long> times; int allowed = 0; for (long long now : {0LL, 1LL, 2LL, 5LL, 6LL}) { while (!times.empty() && now - times.front() >= window) { times.pop_front(); } if (static_cast<int>(times.size()) < limit) { times.push_back(now); ++allowed; } } std::cout << allowed << "\n"; } ``

   2435
3. 3. Put these steps in the order that allow runs for one request in the RateLimiter class.

   Use the arrows to put the steps in order.

   1. 1.Check whether the queue holds fewer than limit_ times↑↓
   2. 2.When the check passes, push now onto the back and return true↑↓
   3. 3.Drop times at the front that are at least window_ old↑↓
   4. 4.Read or create the user's queue with history_[user]↑↓
4. 4. In the RateLimiter class from worked example 1, with window 10, does the request made at second 0 still count at second 10?

   Yes, the window covers seconds 0 through 10 and includes both endsYes, it counts until second 11 because the test uses >No, because the window holds only the last 5 secondsNo, because its age at second 10 is 10, which is at least the window, so it is removed
5. 5. What does this program print? ``cpp #include <algorithm> #include <deque> #include <iostream> int main() { std::deque<long long> times = {0, 1}; const long long window = 4; auto pending = [&](long long now) { return std::count_if(times.begin(), times.end(), [&](long long t) { return now - t < window; }); }; std::cout << pending(4) << " " << pending(5) << "\n"; } ``

   1 00 02 11 1