SeniorДизайнРедкоЕщё не отвечали
Запросы приходят по времени. Чередуются две операции: пользователь генерирует событие и запрос «сколько пользователей сгенерировали не менее 1000 событий за последние 5 минут». Спроектируйте структуру данных, обрабатывающую обе за амортизированное O(1) на запрос, с константой, не зависящей от порога 1000 и ширины окна в 5 минут. Опишите структуры, почему каждая операция амортизированно O(1) и ловушки с памятью (опустошение окна и не очищаемые устаревшие записи по пользователям).
Держите очередь событий окна, таблицу userId → count и текущий robotCount пользователей на пороге или выше. На операции выкидывайте события старше окна, добавляйте новое и правьте robotCount при пересечении порога. Каждое событие ставится и снимается с очереди раз, поэтому амортизированно O(1).
- ✗Не обрабатывать момент, когда окно становится пустым
- ✗Никогда не удалять пользователей со счётчиком, упавшим до нуля, утекая памятью на длинном потоке
- ✗Позволять константе зависеть от порога 1000 или ширины окна в 5 минут
- →Как удержать память ограниченной, когда долго идут только события (без запросов)?
- →Почему текущий robotCount избавляет от перепросмотра всех пользователей на запрос?
Оглавление
Сценарий
Поток запросов: пользователь жмёт кнопку либо мы хотим число «роботов» (≥1000 событий за 5 минут).
Разбор
Скользящее окно событий + словарь + счётчик:
- Очередь
(timestamp, userId)хранит события последних 5 минут. userId → count— число событий пользователя в окне.robotCount— сколько пользователей сейчас на пороге или выше.
На каждой операции: выкидываем устаревшие события (декремент count, при падении ниже порога — декремент robotCount), добавляем новое (инкремент, при пересечении порога — инкремент robotCount).
Каждое событие проходит очередь один раз — амортизированно O(1). Не забываем чистить записи с count == 0.
Оглавление
