Алгоритмы нужны программистам, или cамая быстрая и простая реализация RMQ
Недавно встретилась по работе интересная задача, прямо на те самые презираемые на интервью алгоритмы. Очередное доказательство, что, по крайней мере, в Гугле алгоритмы нужны. А значит и интервью у них вообще-то не оторваны от реальности. Итак, задача: есть лог видео конференции, состоящий из событий - в такое-то время такой-то пользователь подключился или отключился. Надо посчитать статистику. Среди прочего скучного надо для каждого пользователя найти, сколько максимально пользователей было вместе с ним в какой-то момент времени. В статье описано как эту задачу решать действительно быстро - за линейную сложность.
https://habr.com/ru/articles/962688/
#непересекающиеся_множества #интервью #lca #наименьший_общий_предок #максимум_на_отрезке #минимум_на_отрезке #dsu #rmq