Код Middle Батч и стриминг спрашивают часто обновлено

Окна по минуте с watermark и опоздавшими событиями

Условие

События приходят в порядке поступления: список [event_time, user], время в секундах. Реализуйте tumbling_counts(events, window, lateness):

  • окна фиксированные по window секунд: окно k покрывает [k*window, (k+1)*window);
  • watermark после события = максимальное увиденное event_time минус lateness;
  • окно закрывается, как только watermark стал >= его конца; закрытые окна выдаются в порядке возрастания начала;
  • событие, чьё окно уже закрыто к моменту его прихода, считается опоздавшим и в подсчёт не идёт;
  • после конца потока закрываются все оставшиеся окна.

Верните {"windows": [[начало_окна, число_событий], ...], "late": число_опоздавших}. Окна без событий не выводятся.

Примеры

tumbling_counts([[5, "a"], [20, "b"], [65, "a"], [70, "c"]], 60, 0) // {"windows":[[0,2],[60,2]],"late":0}
tumbling_counts([[5, "a"], [65, "b"], [30, "c"], [70, "d"]], 60, 0) // {"windows":[[0,1],[60,2]],"late":1}
tumbling_counts([[5, "a"], [65, "b"], [30, "c"], [70, "d"]], 60, 10) // {"windows":[[0,2],[60,2]],"late":0}

Как подойти

Подсказки: 2
  1. Храните открытые окна в словаре номер -> счётчик и множество закрытых номеров.
  2. После каждого события закрывайте окна, у которых конец <= watermark.

Решите в тренажёре

Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.