Per-Caller Request Limiter Over Non-Decreasing Time Buckets

You are implementing a simple rate limiter that counts requests in discrete time buckets. Each request belongs to a time bucket, given as an integer, and comes from a caller, identified by a string. A caller may make at most `limit` requests in any one time bucket. Given the requests in the order they arrive, decide for each one whether it is allowed. The interview built this in two steps, with a few happy-path test cases after each: first a version without callers, in which all requests in a time bucket share one limit, and then the per-caller version below. The first version is the special case in which every request has the same caller. ### Function Signature ```python def check_requests(limit: int, requests: list[tuple[int, str]]) -> list[bool]: ``` Each request is `(time_bucket, caller_id)`. ### Rules - Process the requests in the given order. Every request adds 1 to the number of requests its caller has made in its time bucket, whether or not the request is allowed. - A request is allowed (`True`) if, after it is counted, its caller's number of requests in that time bucket is at most `limit`. Otherwise it is rejected (`False`). - Counts are kept per caller and per time bucket. Requests from other callers, and requests in other time buckets, never change a caller's count. - Time buckets never decrease from one request to the next. Consecutive requests may share a bucket, and bucket values may skip numbers. - Return one boolean per request, in the same order as `requests`. ### Constraints - `1 <= limit <= 10^9` - `1 <= len(requests) <= 10^5` - `0 <= time_bucket <= 10^9` for every request, and the time buckets are non-decreasing in input order - Every `caller_id` is a nonempty string of at most 20 lowercase English letters and digits. - All inputs are valid. ### Examples **Example 1** ```text Input: limit = 2, requests = [(1, "a"), (1, "a"), (1, "a"), (2, "a")] Output: [True, True, False, True] ``` Caller `"a"` makes three requests in bucket 1. The third brings the count to 3, which exceeds 2. Bucket 2 starts a new count. **Example 2** ```text Input: limit = 1, requests = [(5, "alice"), (5, "bob"), (5, "alice"), (6, "alice"), (6, "bob"), (6, "bob")] Output: [True, True, False, True, True, False] ``` In bucket 5, `"alice"` and `"bob"` each get one request through, and the second request from `"alice"` is rejected. In bucket 6 both callers start again from zero, and the second request from `"bob"` is rejected. **Example 3** ```text Input: limit = 3, requests = [(0, "x"), (0, "x"), (0, "x"), (0, "x"), (0, "x"), (3, "x")] Output: [True, True, True, False, False, True] ``` This is the single-caller case from the first step. Once the count in bucket 0 exceeds the limit, every further request in that bucket is rejected. Bucket 3 comes directly after bucket 0 in the input, and its count starts from zero.