Count Blocked Rate-Limited Requests

You are given an in-memory request log for a web platform. Each log entry has: - `timestamp`: an ISO-8601 UTC timestamp - `request_ip`: the client IPv4 address - `host`: the hostname being requested The log is already sorted by time in ascending order, and you may assume it fits in memory. A request is evaluated against a **sliding window** of `T` seconds. For a request at time `t`, only earlier requests with timestamps in the interval **`(t - T, t)`** are counted. A request that happened **exactly** `T` seconds earlier is **not** in the window. Important rules: - A request that gets **blocked** must still be counted in the history for future requests. - If multiple requests have the same timestamp, process them in input order. - In part 2, if a request violates both rules, it should be counted as **one** blocked request, not two. ## Part 1: Per-IP rate limiting Implement logic to count how many requests would be blocked by this rule: - A request from IP `x` is blocked if there have already been at least `IPReqMax` requests from the same IP in the previous `T` seconds. In other words, the current request is blocked when: - `count(previous requests from same IP in (t - T, t)) >= IPReqMax` ### Example Input log: ```text timestamp,request_ip,host 2024-01-01T00:00:00+00:00,127.0.0.1,example1.com 2024-01-01T00:00:01+00:00,127.0.0.1,example2.com 2024-01-01T00:01:02+00:00,127.0.0.1,example1.com 2024-01-01T00:01:03+00:00,127.0.0.1,example2.com 2024-01-01T00:01:04+00:00,127.0.0.1,example1.com 2024-01-01T00:02:04+00:00,127.0.0.1,example1.com ``` With `IPReqMax = 1` and `T = 60`: - Request 1 -> succeed - Request 2 -> blocked - Request 3 -> succeed - Request 4 -> blocked - Request 5 -> blocked - Request 6 -> succeed So the answer is `3` blocked requests. ## Part 2: Per-IP and per-(IP, host) rate limiting Now add a second rule: - A request from IP `x` to host `h` is also blocked if there have already been at least `IPHostReqMax` requests from the same IP to the same host in the previous `T` seconds. A request is blocked if **either** of these is true: 1. `count(previous requests from same IP in (t - T, t)) >= IPReqMax` 2. `count(previous requests from same IP and same host in (t - T, t)) >= IPHostReqMax` Again, blocked requests still contribute to both counters for future requests. ### Example Input log: ```text timestamp,request_ip,host 2024-01-01T00:00:00+00:00,127.0.0.1,example1.com 2024-01-01T00:00:01+00:00,127.0.0.1,example2.com 2024-01-01T00:00:10+00:00,127.0.0.1,example1.com 2024-01-01T00:00:11+00:00,127.0.0.1,example3.com 2024-01-01T00:01:04+00:00,127.0.0.1,example3.com 2024-01-01T00:01:11+00:00,127.0.0.1,example1.com ``` With `IPReqMax = 3`, `IPHostReqMax = 1`, and `T = 60`: - Request 1 -> succeed - Request 2 -> succeed - Request 3 -> blocked by per-(IP, host) rule - Request 4 -> blocked by per-IP rule - Request 5 -> blocked by per-(IP, host) rule - Request 6 -> succeed So the answer is `3` blocked requests. ## Task Write an efficient function or program that, given the sorted request log and the parameters: - `T` - `IPReqMax` - optionally `IPHostReqMax` returns: 1. the number of blocked requests under the per-IP rule only, and 2. the number of blocked requests under the combined per-IP and per-(IP, host) rules. Aim for an approach that is efficient for large logs loaded into memory.