Problem

You’re on-call for a fintech payments API handling 5M daily active users and bursty traffic during payroll days. A small set of “hot” API keys can suddenly generate huge request spikes, causing CPU thrash and P99 latency regressions. To protect the system, you’re asked to implement an in-memory rate limiter that efficiently rejects requests when a key exceeds its allowed request rate.

Design a function that processes a stream of request events and returns whether each request should be allowed or blocked.

Formal Task

Implement:

• rate_limit(events, limit, window_seconds, ttl_seconds) -> list[bool]

Where:

• events is a list of (timestamp, api_key) pairs sorted by non-decreasing timestamp.
• A request is allowed iff the number of allowed requests for that api_key in the time interval (timestamp - window_seconds, timestamp] is < limit.
• If allowed, the request counts toward the key’s future rate.
• TTL cleanup: If an api_key has had no requests for ttl_seconds, its state must be eligible for removal to prevent memory growth.

Return a boolean list aligned with events indicating allow/block.

Examples

Example 1

Input:

• events = [(1,"A"),(2,"A"),(3,"A"),(4,"A"),(5,"A")]
• limit = 3, window_seconds = 4, ttl_seconds = 10

Output:

• [True, True, True, False, True]

Explanation: At t=4, key A has allowed requests at t=1,2,3 within (0,4] → 3 already, so the 4th is blocked. At t=5, the window is (1,5], so t=1 is out; only t=2,3 remain → allow.

Example 2

Input:

• events = [(1,"A"),(2,"B"),(12,"A"),(13,"A")]
• limit = 2, window_seconds = 10, ttl_seconds = 8

Output:

• [True, True, True, True]

Explanation: Key A is idle from t=1 to t=12 (11 seconds). Since ttl_seconds=8, its state can be dropped and rebuilt at t=12.

Constraints

• 1 <= len(events) <= 2 * 10^5
• 0 <= timestamp <= 10^9
• api_key is a non-empty string, total characters across all keys <= 2 * 10^5
• 1 <= limit <= 10^5
• 1 <= window_seconds <= 10^9
• 1 <= ttl_seconds <= 10^9

Notes / Clarifications

1. events are sorted by time; multiple events may share the same timestamp.
2. Only allowed requests count toward the rate limit.
3. TTL cleanup is about memory safety: you must not keep per-key state forever.