Cost-Based Rate Limiter

Frequency: Reported

Implement a cost-based rate-limiting service between Plaid and banks.

python

def request_api_call(cost: int) -> None:
    ...

def emit_api_calls() -> List[int]:
    ...

request_api_call is called whenever a caller requests an API call. It may be called any number of times during a second.

An automated system calls emit_api_calls exactly once per second, as the final or only call in that second. It returns the costs of the API calls selected for that second, in request order. The selected calls' total cost cannot exceed RATE_LIMIT.

The reported selection behavior scans all pending requests: a request that does not fit remains pending while later, cheaper requests may still be selected. A request whose individual cost exceeds the rate limit is discarded.

Example

python

RATE_LIMIT = 4

request_api_call(2)
request_api_call(2)
request_api_call(1)
request_api_call(1)
emit_api_calls()       # [2, 2]

request_api_call(3)   # pending requests are now [1, 1, 3]
emit_api_calls()       # [1, 1]

emit_api_calls()       # [3]

The source also gives [5, 2, 2] with a limit of 4, for which emit_api_calls() returns [2, 2] and the cost-5 request is removed.

Follow-up: sliding window

Add RATE_LIMIT_WINDOW. Across the previous RATE_LIMIT_WINDOW seconds, emitted requests may have total cost at most RATE_LIMIT.

python

RATE_LIMIT = 5
RATE_LIMIT_WINDOW = 3

request_api_call(2)
emit_api_calls()       # [2]

request_api_call(3)
request_api_call(4)
request_api_call(5)
emit_api_calls()       # [3]
emit_api_calls()       # []
emit_api_calls()       # []
emit_api_calls()       # [4]
emit_api_calls()       # []
emit_api_calls()       # []
emit_api_calls()       # [5]

Submitted Python answers and tests for both parts

The code is preserved as reported and is not presented as a verified reference solution.