Как реализовать логику автоотклонения звонков при более чем 10 звонках за 15 минут от пользователя

Что проверяют

Узнаёте ли вы в задаче скользящее окно (rate limiting) и умеете ли выбрать структуру данных под него. Следом спрашивают, что делать с миллионом абонентов и несколькими серверами и как посчитать то же самое по историческим данным.

Как отвечать

Сначала зафиксируйте условия: отклоняется 11-й звонок в окне или 10-й, учитываются ли уже отклонённые звонки, окно скользящее или привязано к четвертям часа. Это сразу показывает, что вы думаете о граничных случаях.

• онлайн-решение: словарь user_id -> deque с временами принятых звонков. На новом звонке выталкиваем слева всё старше 15 минут; если в очереди уже 10 элементов, отклоняем, иначе добавляем текущее время. Амортизированно O(1) на звонок, не больше 10 меток на абонента;
• время: в одном процессе time.monotonic(), чтобы перевод часов не ломал окно. Функция принимает время параметром, так её легко тестировать;
• чистка: абоненты, не звонившие дольше окна, удаляются, иначе словарь растёт бесконечно;
• фиксированное окно: счётчик на интервал дешевле, но на стыке двух интервалов пропускает до 20 звонков подряд. Объясните, почему он не подходит под формулировку;
• распределённо: Redis, sorted set на абонента, ZREMRANGEBYSCORE для старых меток, ZCARD и ZADD атомарно в Lua-скрипте, EXPIRE на ключ;
• потоковая обработка: в Flink или Spark Structured Streaming это состояние по ключу user_id с таймерами очистки.

Для аналитической части покажите SQL: count(*) over (partition by user_id order by ts range between interval '15 minutes' preceding and current row) находит все моменты, где порог был превышен.

Где спотыкаются

Хранят все звонки всех пользователей в одном списке и фильтруют его целиком на каждый вызов. На реальном трафике это O(N) и глобальное состояние без блокировок.

Путают «больше 10» и «10 и больше» и не проговаривают, входит ли в окно звонок ровно 15 минут назад.

Измеряют интервал системными часами. Перевод времени или синхронизация NTP сдвигают окно, и абонента блокирует или отпускает раньше срока.