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.