Implement a rule-based rate limiter

## Problem Design and implement a **rule-based rate limiter** that decides whether each incoming request should be **allowed** or **rejected**. You are given: - A stream of incoming **requests**. - A list of **rate limit rules**. Each rule contains: - A **filter policy** that may match on any subset of the following request attributes: - `first_name` - `last_name` - `ip` - `country` - A rate limit: **at most `limit` requests per `window_seconds`** for the matching key. A request **matches** a rule if all attributes specified in the rule's filter equal the request's corresponding attributes. (Attributes not present in the filter are treated as wildcards.) ### Rule application semantics - A request can match **multiple rules**. - The request should be **rejected** if it would violate **any** matched rule (i.e., all matched rules must remain within their limits). - If a request is rejected, it must **not** consume quota for any rule. ### Input/Output (one possible interface) Implement a class/function with an API similar to: - `bool allow(Request r, int timestamp_seconds)` Where `timestamp_seconds` is non-decreasing across calls. ### Constraints / expectations - Number of rules: up to `R`. - Number of requests: up to `N`. - Aim for efficient per-request processing (better than scanning all historical requests). - Handle large cardinality of keys (e.g., many unique IPs). ### Clarifications to confirm with interviewer (if needed) - Whether `timestamp_seconds` is strictly increasing or may have ties. - Whether rules can be added/removed dynamically or are static. - Whether windows are **sliding** windows or **fixed** aligned windows. ## Example (illustrative) A rule: filter `{ip="1.2.3.4"}`, limit `5`, window `60` means: for that IP, allow at most 5 requests in any 60-second window (or in the last 60 seconds, depending on window type you confirm). Return `true` for allowed, `false` for rejected.