Войти Регистрация
Алгоритмы

46. Корзина токенов

Средняя

Корзина вмещает capacity токенов и пополняется на rate токенов в секунду, но не выше ёмкости. В момент 0 корзина полная.

Дан список вызовов calls, каждый — [n, t]: в момент t (секунды, не убывают) запрос просит n токенов. Если токенов хватает — списываем и отвечаем True, иначе False без списания. Верните список ответов.

В работе: Не больше 100 запросов в секунду к платёжному API с запасом на всплески.

Пример 1

Ввод
capacity = 5
rate = 1
calls = [[3, 0], [3, 0], [3, 1]]
Вывод
[True, False, True]

После первого вызова остаётся 2, через секунду — 3.

Ограничения

  • 1 ≤ capacity, rate ≤ 10⁶
  • 0 ≤ число вызовов ≤ 10⁵
  • Время — целые секунды
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def token_bucket(capacity, rate, calls):
МоделированиеПроектирование структурыцельO(n)

Источник: МТС, KION, Go, 2025. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.