Pular para o conteúdo

Rate limiter com token bucket

Fácil#token-bucket#integer-math~15 min

A missão

Problema

Um API gateway limita cada cliente com um token bucket. O bucket guarda no máximo capacity tokens e começa cheio no instante 0. Os tokens voltam a pingar continuamente, a per_second tokens por segundo, nunca além da capacidade, e cada requisição gasta um token inteiro ou é rejeitada. Dados os instantes das requisições em milissegundos, em ordem, retorne para cada uma se ela é permitida. As recargas são fracionárias, então um quarto de segundo a 4 tokens por segundo é exatamente um token; evite ponto flutuante para que uma requisição exatamente no limite nunca seja rejeitada por um erro de arredondamento.

Exemplos

Input:  capacity = 2, per_second = 1, times_ms = [0, 0, 0, 500, 1000, 3000]
Output: [True, True, False, False, True, True]
Por quê: a rajada de três recebe dois; meio token em 500 não basta; depois, o bucket se recarrega
Input:  capacity = 1, per_second = 4, times_ms = [0, 100, 250, 260]
Output: [True, False, True, False]
Por quê: exatamente um token está de volta em 250 ms
Input:  capacity = 3, per_second = 1, times_ms = []
Output: []
Por quê: edge case: sem tráfego

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(n)

Restrições

  • request times are in milliseconds, in order

Travou na ideia, e não no código? Rate limiting explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado