Quick Overview

A coding question about a rate limiter that receives requests as time bucket and caller pairs, in non-decreasing bucket order, and decides which to allow when each caller may make only a fixed number of requests per bucket. It tests stateful counting, per-key bookkeeping and correct handling of bucket changes.

Per-Caller Request Limiter Over Non-Decreasing Time Buckets

Company: Atlassian

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

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.

Overview: A coding question about a rate limiter that receives requests as time bucket and caller pairs, in non-decreasing bucket order, and decides which to allow when each caller may make only a fixed number of requests per bucket. It tests stateful counting, per-key bookkeeping and correct handling of bucket changes.

Read the full Atlassian Software Engineer interview experience this question came from

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. Implement `check_requests(limit, requests)`. Each element of `requests` is a pair `(time_bucket, caller_id)`. Return a list with one boolean per request, in the same order as `requests`. ### 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. A rate limiter without callers, in which all requests in a time bucket share one limit, is the special case in which every request has the same caller. In JavaScript each request is a two-element array `[time_bucket, caller_id]`; in Java it is a `java.util.List<Object>` holding an integer and then a `String`; in C++ it is a `std::pair<int, std::string>`. Every number in the input fits in a signed 32-bit integer (none exceeds 2^31 - 1). ### 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. ### 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.

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

Input: (2, [(1, 'a'), (1, 'a'), (1, 'a'), (2, 'a')])

Expected Output: [True, True, False, True]

Explanation: Source Example 1: the third request in bucket 1 brings the count to 3 > 2; bucket 2 starts a new count.

Input: (1, [(5, 'alice'), (5, 'bob'), (5, 'alice'), (6, 'alice'), (6, 'bob'), (6, 'bob')])

Expected Output: [True, True, False, True, True, False]

Explanation: Source Example 2: interleaved callers keep separate counts; both restart from zero in bucket 6.

Hints

  1. A request's outcome depends only on how many requests share both its caller and its time bucket up to and including it; rejected requests count too.
  2. Requests from other callers or in other time buckets never change a caller's count, so decide what should identify each count.
  3. Time buckets never decrease and may skip values, and a new bucket starts every caller again from zero.

Loading coding console...

Show the approach

Approach

Algorithm: a request's outcome depends only on how many requests the same caller has made in the same time bucket, rejected ones included, so one counter per (time_bucket, caller_id) pair is enough. Because time buckets never decrease, an earlier bucket can never reappear once the bucket value changes. The implementation therefore keeps a hash map from caller_id to count for the current bucket only, and swaps in a fresh empty map whenever a request's bucket differs from the previous request's. For each request it increments the caller's counter and appends whether the new count is <= limit.

Invariant: before request i is processed, the map holds, for every caller, the number of requests that caller made among requests 0..i-1 in the bucket of request i (a caller missing from the map has count 0). This holds at the start. It is preserved while the bucket stays the same, because only the current caller's counter changes and it changes by exactly 1. It is restored on a bucket change, because buckets are non-decreasing, so no earlier request shares the new bucket.

Correctness: the k-th request of a caller within one bucket is allowed exactly when k <= limit, which is what comparing the incremented counter with limit checks. Counting rejected requests matches the rule that every request adds 1. Callers are compared as whole strings within a single bucket, so ids such as "a" and "a1", or pairs such as (1, "1a") and (11, "a"), never share a counter. Allocating a fresh map instead of clearing a large one keeps each bucket change cheap. Each hash operation costs O(L) for a caller_id of length L <= 20.

Edge cases: a single request is always allowed because limit >= 1. With limit up to 10^9 and at most 10^5 requests, a large limit means no request is ever rejected. Bucket values may skip numbers or jump from 0 to 10^9; only equality with the previous request's bucket matters. Every value fits in a signed 32-bit integer.

Time complexity:
O(n)
Space complexity:
O(n)