Контест Middle Безопасность бэкенда обновлено
Кто превысил лимит запросов: скользящее окно
Условие
По логу запросов найди IP, которые хоть раз превысили лимит. Первая строка: n W L. Дальше n строк <время в секундах> <ip>, время не убывает.
IP нарушил лимит, если в какой-то момент t (время одного из его запросов) число его запросов со временем в полуинтервале (t - W, t] стало больше L.
Выведи нарушителей по одному в строке в порядке возрастания кодов символов, или OK, если нарушителей нет.
n ≤ 2·10⁵.
Пример
6 10 2
1 1.1.1.1
2 2.2.2.2
5 1.1.1.1
9 1.1.1.1
11 1.1.1.1
30 2.2.2.2
1.1.1.1
В момент 9 у 1.1.1.1 три запроса в окне (-1, 9]: 1, 5 и 9.
Как подойти
Подсказки: 3
- Для каждого IP держи очередь времён его запросов в текущем окне.
- Перед проверкой выкидывай из головы очереди времена
<= t - W. Array.shift()в цикле это O(n) на вызов: используй индекс головы.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Предыдущий вопрос
Rate limiter на token bucket
Следующий вопрос
Код-ревью: регистрация, вход и сброс пароля