Saltar al contenido

Rate limiter con token bucket

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

La misión

Problema

Un API gateway limita a cada cliente con un token bucket. El bucket guarda como máximo capacity tokens y empieza lleno en el instante 0. Los tokens vuelven a entrar de forma continua a razón de per_second tokens por segundo, nunca por encima de la capacidad, y cada solicitud gasta un token entero o se rechaza. Dados los instantes de las solicitudes en milisegundos, en orden, devuelve para cada una si se permite. Las recargas son fraccionarias, así que un cuarto de segundo a 4 tokens por segundo es exactamente un token; evita el punto flotante para que una solicitud que cae justo en el límite nunca se rechace por un error de redondeo.

Ejemplos

Input:  capacity = 2, per_second = 1, times_ms = [0, 0, 0, 500, 1000, 3000]
Output: [True, True, False, False, True, True]
Por qué: la ráfaga de tres obtiene dos; medio token en 500 no alcanza; después el bucket se recarga
Input:  capacity = 1, per_second = 4, times_ms = [0, 100, 250, 260]
Output: [True, False, True, False]
Por qué: exactamente un token está de vuelta a los 250 ms
Input:  capacity = 3, per_second = 1, times_ms = []
Output: []
Por qué: caso límite: no hay tráfico

Pistas

0 / 3

Tiempo objetivo
O(n)
Espacio objetivo
O(n)

Restricciones

  • request times are in milliseconds, in order

¿Lo que te frena es la idea y no el código? Rate limiting lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio