Недавно встретилась по работе интересная задача, прямо на те самые презираемые на интервью алгоритмы. Очередное доказательство, что, по крайней мере, в Гугле алгоритмы нужны. А значит и интервью по ним вообще-то не оторваны от реальности.
Итак, задача: есть лог видео конференции, состоящий из событий - в такое-то время такой-то пользователь подключился или отключился. И надо посчитать всякую разную статистику. Среди прочего скучного надо для каждого пользователя найти, сколько максимально пользователей было вместе с ним в какой-то момент времени.
Похоже, на интервью спрашивают слишком простые задачки, потому что тут другой программист впендюрил наивное решение за квадрат: перебираем события в порядке возрастания времени, поддерживаем хеш-сет активных пользователей, обновляем значение метрики для всех активных пользователей текущим размером хэш-сета. А квадратичное решение тут действительно плохо, ибо бывают конференции и на тысячи пользователей.
Набросок кода
std::unordered_set<UserID> active_users;
for (auto &event: events) {
if (event.type == Event::kJoin) {
active_users.insert(event.user_id);
for (auto &user_id : active_users) {
stats[user_id].max_concurrent_users =
max(stats[user_id].max_concurrent_users,
active_users.size());
}
} else {
active_users.erase(event.user_id);
}
}Обратите внимание, тут даже оптимизация есть - максимальное количество пользователей считается только при событии типа join. Примерно в 2 раза быстрее. Но это все еще решение за квадрат потому что тут n промежутков времени и в каждом из них может быть активно O(n) пользователей. Тут и далее n - количество событий.
Как всегда, программист просто не понял, что тут вообще есть какие-то эти ваши алгоритмы. У него есть задача - подсчитать метрики. Он эту задачу и решил, переведя требования на язык программирования. То, что тут вообще-то стандартнейшая алгоритмическая задача из книжек и не видно по постановке. Именно это свойство алгоритмических задач и создает у многих ошибочное ощущение, что алгоритмы им в работе вообще не нужны, и кроме литкода и интервью нигде не встречаются.
Задача Range Maximum Query
Эта задача на самом деле - стандартная задача Range Maximum Query: если рассмотреть, сколько пользователей было между двумя соседними событиями, то у нас получается массив из чисел, и для каждого пользователя надо найти максимум на отрезке от его события подключения до его события отключения. Правда, в литературе ставят задачу на минимум (Range Minimum Query), но это вообще не принципиально - абсолютно те же самые алгоритмы можно заставить искать максимум, лишь поменяв пару знаков в сравнениях. Или в худшем случае умножить все числа на -1, найти из них минимум неизмененным алгоритмом, а потом поменять у ответа знак назад.
Вот иллюстрация:
Выше фактически реализовано наивное решение задачи RMQ за 
, только порядок циклов вывернут, чтобы не хранить все значения в массиве. В наивном решении внешний цикл по запросам, а внутри цикл по всем числам отрезке. А тут, наоборот - происходит проход по всем числам и обновление ответа для всех запросов, включающих это число.
У этой задачи есть множество решений разной степени сложности кода и эффективности. На хабре уже есть множество статей:
https://habr.com/ru/articles/114980/
предподсчет + 
на запрос благодаря предподсчету на всех отрезках длины, равной какой-то степени двойки.https://habr.com/ru/articles/115026/
предпосдчет + 
на запрос благодаря использованию структуры данных "дерево отрезков".https://habr.com/ru/articles/138946/
предподсчет + 
на запрос через разбиение на блоки размером 
.На хабре так и не написали об алгоритме Фараха-Колтона и Бендера c пердподсчтетом
и 
на запрос. Но этот алгоритм весьма сложен в реализации и состоит из кучи шагов: Сначала RMQ сводится к задаче Lowest Common Ancestor (LCA) через построение Декартового дерева, потом LCA сводится к задаче +-1 RMQ (тот же RMQ, только числа в массиве отличаются на +1 или -1), и уже эта задача решается за линейную сложность через предподсчет и разбиение на блоки размера 
.
Тут я приведу другой алгоритм с 
пердподсчетом и 
на запрос, который даже проще многих перечисленных выше в реализации. Правда, в отличии от некоторых из них, этот алгоритм offline, т.е. он может обработать все запросы только вместе группой. Этот алгоритм в интернете иногда называют "Arpa's trick".
В итоге этот алгоритм дает решение исходной задачи за 
, при условии уже отсортированности событий по времени. Но даже с сортировкой он все еще быстрее и проще перечисленных выше алгоритмов.
Линейное решение задачи
Итак, основная идея: давайте для каждого числа найдем следующее большее-равное его справа и сохраним на него указатель. Тогда при запросе на максимум нам надо пройтись по этим ссылкам от левого края запроса, пока мы не выйдем из отрезка. Последний элемент в цепочке будет максимумом на отрезке. Но тут сложно быстро понять, где остановиться.
Тогда давайте обрабатывать запросы слева направо по концам и поддерживать ссылки только среди чисел левее границы. Т.е. мы будем дорисовывать стрелочки ведущие в текущее число, а потом находить все максимумы на запросы, кончающиеся в текущем числе. Тогда задача становится проще: надо просто идти до конца всегда. Мы не выйдем за границу отрезка, потому что ссылки за нее еще не созданы:
Итак, у нас есть структура, где мы от каждого элемента можем провести максимум одну стрелочку к какому-то другому элементу и нам надо уметь проходиться по стрелочкам до конца. Знакомые со структурами данных читатели заметят, что эта структура очень похожа на структуру данных Disjoint Set Union (или Union-Find, или "система непересекающихся множеств"). С той лишь разницей, что в DSU числа куда-то ссылаются всегда, но некоторые ссылаются сами на себя и итерация идет пока не зациклится в таких числах. Давайте тогда проводить ссылку от числа на само себя, если правее нет ничего больше-равного. И вот мы решили задачу стандартной структурой DSU. Прелесть этой структуры данных в том, что она позволяет искать конец цепочки за
, где 
- это обратная функция Аккермана, которая меньше 5 для всех мыслимых объемов данных (
), поэтому ее можно считать константой. Об этом свойстве уже есть замечательная статья на хабре.
Вот и алгоритм получается такой: идем слева направо по массиву и объединяем все значения в непересекающиеся множества - элементы принадлежат одному и тому же множеству, если в отрезке, начинающемся с них, максимумом будет один и тот же элемент. Этот элемент будет корнем множества. Чтобы найти максимум на отрезке, заканчивающимся в последнем обработанном числе, надо взять корень множества, которому принадлежит начало отрезка.
Остается вопрос о том, как эти множества поддерживать при добавлении нового элемента. Можно заметить, что множества эти образуют непрерывные отрезки, а сами максимумы будут на концах отрезков и идут в массиве в порядке убывания значений. Действительно, самый большой элемент в массиве будет корнем для всех чисел левее его. Это будет первое множество. Далее можно рассмотреть оставшиеся числа правее, там тоже есть какой-то глобальный максимум и он тоже откусит от этих чисел свое множество и так далее. Когда мы добавляем новый элемент, он "вытеснит" все корни множеств, которые меньше-равны ему, и поглотит их множества. Так что, если хранить эти корни множеств в порядке увеличения индексов, то они будут и в порядке уменьшения значений. И при добавлении нового элемента надо будет убрать все меньшие с конца. Т.е. хранить их надо в стеке и убирать с конца меньшие нового элемента.
Вот и код с "алгоритмами". Несмотря на то, что он работает в тысячи раз быстрее на больших объемах, он не сильно сложнее. Он даже работает не медленнее на маленьких конференциях, так что он всегда лучше наивного решения за квадрат:
Набросок кода
// Структура непересекающихся множеств, всегда указывает на больший элемент
// правее данного.
std::vector<int> dsu(events.size());
// Количество акивных пользователей после каждого события.
std::vector<int> user_counts(events.size());
// Индексы максимальных элементов, для которых нет большего правее.
// Они же корни в системе непересекающихся множеств.
// Всегда в порядке возрастания индексов и убывания значений.
std::deque<int> maximums_stack;
// запоминаем для каждого пользователя, когда он подключился
std::unordered_map<UserID, int> join_event_idx;
int active_user_count = 0;
// Основной цикл.
for (int event_idx = 0; event_idx < events.size(); ++event_idx) {
Event &event = events[event_idx];
if (event.type == Event::kJoin) {
++active_user_count;
// Запоминаем начало отрезка на будущее.
join_event_idx[event.user_id] = event_idx;
} else {
--active_user_count;
// Берем известное начало отрезка-запроса.
int join_idx = join_event_idx[event.user_id];
// Проходимся до корня от самого левого элемента в отрезке.
int max_users_count = user_counts[DsuRoot(join_idx, dsu)];
// Сохраняем ответ.
stats[event.user_id].max_concurrent_users = max(user_stats.max_concurrent_users,
max_users_count);
}
// Добавляем новый элемент в структуру.
user_counts[event_idx] = active_user_count;
// Правее него пока вообще ничего нет - он сам себе максимум.
dsu[event_idx] = event_idx;
// Какие-то из существующих максимумов меньше нового элемента.
// Но они хранятся в стеке, по убыванию, поэтому все они лежат на верхушке.
while (!maximums_stack.empty() &&
user_counts[stack.back()] <= active_user_count) {
// Новый элемент теперь следующий больший для вытесненного максимума.
dsu[maximums_stack.back()] = event_idx;
maximums_stack.pop_back();
}
// Новый элемент - максимум, и он должен быть в стеке.
stack.push_back(event_idx);
}
// Функция для работы с системой непересекающихся множеств.
// Находит корень множества, которому принадлежит idx.
int DsuRoot(int idx, vector<int> &dsu) {
int root = idx;
while (dsu[root] != root) {
root = dsu[root];
}
// Эвристика сжатия путей.
while (idx != root) {
int nxt = dsu[idx];
dsu[idx] = root;
idx = nxt;
}
return cur;
}Тут, опять же, лишь набросок кода для примера. На самом деле для читабельности среди кучи метрик вся хитрая логика прячется в своем классе за методами AddSample() и FindMaxAmongLastK() и комментариев сильно меньше.
Замечание по оценке времени работы
Очень продвинутые в алгоритмах читатели возразят, что тут используется DSU лишь с эвристикой сжатия путей, без ранговой эвристики. И вообще DSU работает за 
а не за 
Хоть это и можно считать константой на практике. И действительно, если бы у нас была произвольная задача RMQ так все и было бы. И этот код в итоге работал бы за O(n + m log n), где m количество запросов. А чтобы код работал хотя бы за 
надо было бы реализовывать ранговую эвристику при слиянии множеств, и еще пришлось бы дополнительно хранить значение максимума для каждого множества (ведь максимум уже не обязательно был бы корнем).
Но у нас ведь задача немного ограниченная: числа в массиве не любые, они изменяются только на +-1 от соседних. Плюс, в каждом элементе может начинаться или заканчиваться максимум один запрос. И начало этого запроса всегда выпадает на элемент, который больше предыдущего. Все эти ограничения позволяют доказать строгую оценку O(n) для времени работы этого алгоритма и без ранговой эвристики. А без нее код получается чуть проще и работает чуть быстрее. Но у меня не получилось вывести достаточно простое и короткое доказательство. Так что оно, может быть, появится в следующей статье, если кому-то интересно.
Альтернативные объясниения алгоритма
Можно рассматривать этот алгоритм как смесь алгоритма Фараха-Колтона-Бендера, упомянутого в начале статьи, и алгоритма Тарьяна для LCA. Сначала точно такое же сведение RMQ к LCA в декартовом дереве, но потом применяем алгоритм Тарьяна с DSU для поиска LCA вместо сведения задачи к +-1 RMQ. Если упрощать код и смешивать выполнение LCA вместе с построением декартового дерева, то в итоге получится вот этот алгоритм.
Еще его можно вывести из другой логики, именно так я к нему и пришел. Давайте обрабатывать запросы слева направо в концах. Тогда нам надо уметь выполнять 2 операции: добавить элемент и взять максимум из скольки-то последних. Эта задача чем-то похожа на известную задачу о максимуме в sliding window. И тут применима такая же логика: какие-то элементы никогда не будут ответом ни для какого запроса. Это те, правее котрых есть что-то больше-равное их. Давайте их называть "плохими", а все остальные - "хорошими". Действительно, любой запрос, включающий такой плохой элемент, включает и больший его правее, а значит ответом будет вот тот другой элемент (или что-то еще большее), но точно не сам плохой элемент.
Поэтому плохие элементы можно вообще выкинуть из рассмотрения, тогда оставшиеся хорошие элементы образуют строго убывающую подпоследовательность. Действительно, если где-то они идут по возрастанию, то левый элемент не может быть хорошим, ведь правее его есть что-то большее. При добавлении нового элемента какие-то хорошие с конца станут плохими и будут выкинуты. А новый элемент всегда хороший, ведь правее его вообще ничего нет, не говоря уже о больших элементах. Эти хорошие элементы - это и есть те самые корни множеств и числа в стеке в алгоритме.
При запросе надо найти самый левый хороший элемент, который еще попадает в отрезок-запрос. Ведь в качестве ответа можно взять все хорошие элементы, но самый больший из них - самый левый, они же убывают. Тут можно было бы воспользоваться бинарным поиском по индексу, но можно пойти дальше. Давайте для всех возможных начал запросов следить, где бы они находились в стеке, если бы они там были. Можно их как бы повесить на элемент в стеке, который ближайший к ним справа. При удалении элемента из стека, повешенные на него начала будут перевешаны на новый элемент. Вот и получилось, что нам надо поддерживать непересекающиеся множества и объединять их, а максимум для каждого множества - это какой-то элемент в стеке, соответствующий какому-то множеству. Это можно быстро делать с помощью структуры данных DSU.
Комментарии (56)
malkovsky
27.11.2025 13:51Это же классический Accidently quadratic! Давно уже есть идея написать по статью на обозрение всем, кто считает, что алгоритмы не нужны.
Мне кажется, что сбор статистики -- это то, что возникает всегда и везде. У меня возникла как-то задача, которую в целом можно описать как "нужно быстро считать какую-то статистику за недавний промежуток времени переменной длины в онлайн". Подсчет суммы/среднего/минимума мы сделали довольно легко с
на запрос, был даже довольно экзотичный случай подсчета среднеквадратиченого отклонения, который тоже считается и тут у меня тоже есть ссылочка на квадрат. Но вот у нас дело дошло до квантиля и тут мы поняли, что задаче резко стала сложнее -- внезапно в какой-то момент научились тоже делать за логарфим с помощью wavelet tree. 
wataru Автор
27.11.2025 13:51был даже довольно экзотичный случай подсчета среднеквадратиченого отклонения, который тоже считается и тут у меня тоже есть ссылочка на квадрат.
Спасибо за ссылочку, надо бы там пофиксить. Это отклонение же элементарно считается.
Про квантили интересно: не могли бы вы поточнее описать задачу? Длина окон прямо от зароса к запросу меняется? Было бы интересно почитать, как вы там делали с wavelet tree. Если окна совсем произвольные, то пока вижу как сделать за O(log^3(n)) каким-нибудь деревом отрезков декартовых деревьев и бинпоиском по ответу.
malkovsky
27.11.2025 13:51Окна не совсем произвольные. В целом понятно, что если например окно фиксированного размера по времени или скажем по количеству событий, то можно обойтись любым бинарным деревом поиска с поддержкой размера поддеревьев для поиска.
Решение за log^3 -- там есть несколько вариантов, но в целом это что-то в духе декартого дерево по времени, в каждой вершине что-то что умеет считать порядковую статистику. Есть вариации, но все они log^3 запрос + nlogn памяти. По поводу wavelet tree на 100% не уверен, но кажется в этой статье описан алгоритм, который мы использовали. Уточню, что там не logn, а log U в предположении, что все величины -- это целые числа из диапазона [1..U]
wataru Автор
27.11.2025 13:51Так какие у вас там окна? Размер от запроса к запросу меняется? Окно всегда кончается в текущем элементе? Формализуйте, если вам не сложно, задачу, пожалуйста.
malkovsky
27.11.2025 13:51Размер окна от запроса к запросу меняется, да. Окно всегда кончается в текущем элементе, да. Возможно поможет контекст: дело происходило на транспортном уровне передачи данных, где мы хотим посчитать актуальную статистику за последний RTT - round trip time, время от отправки пакета до получения фидбека по нему - это величина ведят себя достаточно предсказуема большую часть времени, но в критические моменты начинает изменяться и на это нужно реагировать.
wataru Автор
27.11.2025 13:51Кстати,
"нужно быстро считать какую-то статистику за недавний промежуток времени переменной длины в онлайн". Подсчет суммы/среднего/минимума мы сделали довольно легко с
на запрос Если у вас запросы именно "за недавний промежуток", т.е. идут в порядке увеличения правых концов, то вам как раз подходит алгоритм из статьи для реализации минимума за O(1).
malkovsky
27.11.2025 13:51А для такого случая есть еще проще алгоритм со стеком, он есть на e-maxx, едиинственное -- для случая когда длина не фиксирована, то мы делали бинарный поиск. Еще я до конца не понял, можно ли алгоритм из статьи делать онлайн
wataru Автор
27.11.2025 13:51Алгоритм со стеком с e-maxx не работает, если начала окон произвольно меняются. Про бинарный поиск по стеку я как раз и написал в конце статьи про альтернативный вывод.
Алгоритм в статье как раз реализует два метода: AddSample, GetMaxFromNLast. Он оффлайн в смысле, что ему надо запросы обрабатывать в строгом порядке увеличения концов. Но это как раз ваш случай.
nick758
27.11.2025 13:51Но ведь человек, написавший изначальный код, тоже прошёл через алгоритмическое собеседование.
Кстати, интересно насколько быстрее работает ваш вариант. Предположим, на 10000 элементах.
wataru Автор
27.11.2025 13:51К сожалению, идеальных тестов не бывает. Плюс со временем народ начинает тренироваться проходить тест, а не делать то, что тест сделан проверять, что еще больше повышает ложно-положительные результаты.
mynameco
27.11.2025 13:51надо еще по ресурсам компании смотреть, по срокам. этот код еще поддерживать нужно. возможно менять и добавлять. и тут, возможно, придется искать того специалиста, которому пригодились его знания, либо переписывать на квадрат, чтобы можно было недорого, поддерживать этот код.
wataru Автор
27.11.2025 13:51Зачем его менять и добавлять? Решатель для RMQ лежит в директории с универсальными общими библиотеками, менять его вряд ли когда-то придется. Если кому-то надо будет его доработать под их нужды (например, под минимум), то у них какая-то похожая алгоритмическая задача и без знаний они ее все-равно не решат. Сам код обработчика событий лишь вызывает 2 функции у решателя в библиотеке, поддерживать его сможет даже формошлеп. Ну и, в конце-концов, интервью с алгоритмами проходили все, так что считается, что любой программист должен уметь хотя бы разобраться в таком коде.
malkovsky
27.11.2025 13:51Решатель для RMQ лежит в директории с универсальными общими библиотеками, менять его вряд ли когда-то придется.
Не, ну почему не придётся, как раз таки допилить ради ускорение всех компонент, которые его использует -- здравое дело. С другой стороны, чаще всего у опытных разработчиков не должно быть проблем сделать улучшение без изменения интерфейса.
ohrenet
27.11.2025 13:51С другой стороны, чаще всего у опытных разработчиков не должно быть проблем сделать улучшение без изменения интерфейса.
Любой опытный разработчик понимает что любое внесение изменений чревато проблемами. И чем заумней код, тем выше шансы что-то там незаметно для юнит-тестов поломать.
malkovsky
27.11.2025 13:51Вы гиперболизируете, как-будто из вашего сообщения стоит сделать вывод, что писать новый код не выгодно, потому что это чревато проблемами.
Да, я прекрасно понимаю есть например ситуации когда есть код, не меняющийся десятилетиями и прекрасно работающий, использующийся всеми. Делать изменения в таком коде ради выигрыша 0,1% нецелесоообразно из-за надёжности. Но если подобные проекты забрасываются, то рано или поздно оказываются на свалке истории.
ohrenet
27.11.2025 13:51Вы гиперболизируете, как-будто из вашего сообщения стоит сделать вывод, что писать новый код не выгодно, потому что это чревато проблемами.
В этом и состоит работа инженера-программиста: находить компромис между выгодой и издержками, рисками, последствиями.
heartdevil
27.11.2025 13:51Вообще говоря, в "хороших" компаниях, людей не мыслящих категориями алгоритмов и структур данных, вообще не пустят к такого рода задачам. Просто из-за профнепригодности.
В конкретном примере, я думаю, разработчик был даже знаком с алгоритмами и структурами данных и все равно написал квадратичное решение. Что может только подчеркивать насколько эти знания и умения не просто освоить и применить.То есть для тех, кто считает, что, мол, ну когда время прижмет, тогда и разберусь, хочу сказать что -- нет. Скорее всего, не разберетесь.
Это не те знания которые вы, там, прочитав умные книжки по чистой архитектруре, получили и сразу стали применять как по лекалу. Люди годами изучают и не могут изучить нормально.
А то, что на интревью, бывает, что лотерея, типа, учил, учил и не попалось -- ну да, бывает. Не без изъянов эти интервью. Это как раз точка улучшения - сделать так, чтобы не конкретные алгоитмы спрашивали, а скорее проверяли алгоритмическое мышление.
Ну и вообще, если вы начнете копать глубже, то тот софт, на котором вы уже и не "должны" понимать алгоритмы и структуры данных, он , скоре всего, и написан при помощи этих алгоритмов и структур данных. Вот начните даже с операционных систем и идите выше. До ваших веб серверов, где вы там что-то "архитектурите".
Zara6502
27.11.2025 13:51Итак, задача: есть лог видео конференции, состоящий из событий - в такое-то время такой-то пользователь подключился или отключился. И надо посчитать всякую разную статистику. Среди прочего скучного надо для каждого пользователя найти, сколько максимально пользователей было вместе с ним в какой-то момент времени.
вероятно я тот самый кто ничего не понял из статьи, но вопросы у меня вызывает вот что. В задаче у вас есть работающее уже решение, то есть логи пишутся. А вам нужно не переписать систему логирования, а разобрать лог. А это сразу - парсер, который съест всё время, а только потом уже ваш алгоритм. И тут вопрос к производительности и памяти. А будет ли квадратичное решение медленнее вашей городушки парсер+алгоритм? В статье я про это ничего не вижу, а значит и разговоры про что там нужно пока преждевременны. В своих скромных статьях всё же я провожу сравнение по скорости и доказываю что алгоритмы полезны, но и там встаёт затронутый вопрос - а кто потом всё это будет поддерживать???
wataru Автор
27.11.2025 13:51Логи собираются с пользователей, их потом надо аггрегировать и обработать. Это и есть то место, где решается задача. Тут разговор не об одной программе, где можно сразу что-то подсчитать и потом записать в лог, или о базе данных, где можно соптимизировать sql запрос вместо обработки потом - тут распределенная система из пользователей, подключенных к серверам в разных частях света.
Да, перекачка всего это объема данных и аггрегация по конференциям занимют дольше времени, чем даже квадратичный алгоритм, но это не значит, что из-за одного медленного этапа можно забить на оптимизацию всех других.
Я написал, что решение быстрее даже для 2 пользователей, а значит оно во всем лучше. Думал этого достаточно.
Реальные боевые данные я показать не могу, но в бенчмарке это решение соптимзировало обработку с 3300мс до 18мс для небольшого набота тестовых данных. И то, что раньше работало на ~600 серверах от 20 до 150 минут (в зависимости от размеров коференций), стало отрабатывать за меньше минуты на тех же серверах. Да, это всего 5-20% от всего пайплайна. Но это несколько часов процессорного времени, на 600 серверах, несколько раз в день. Т.е. этот код сохранил 1000-7500 часов процессорного времени каждый день.
У гугла, конечно, очень много серверов, но это не значит, что можно их бездумно жрать.
Zara6502
27.11.2025 13:51я не сомневаюсь в ваших компетенциях, я скорее о полноте самой статьи (в данном случае о недостатке компетенции читателя).
но это не значит, что можно их бездумно жрать
о нет, я как раз за алгоритмы и оптимизации везде и всюду, особенно что касается экономии ресурсов.
Вот например:
Всего-то чатик на ПК, а вес как у приличной игры, как-то не уверен я что кто-то что-то тут оптимизирует. Кстати это обновление я не могу поставить уже неделю, обрывается скачивание, видимо товарищ майор дёргает рубильник )
У смартфонов та же проблема, как только средний смарт стал 4-8 гигов оперативки и 256 диска - понеслась, даже простейший софт весит гигабайты.
ohrenet
27.11.2025 13:51Вот что получается когда нанимают алгоритмистов, которые выдрачивают аж 2мс ускорения, а просто нормально софт писать некому.
sergey-gornostaev
27.11.2025 13:51Один мой друг™ однажды встретил похожую задачу в системе крупной медицинской сети. Масштаб не гугловый, конечно, но объёмы данных и частота операций с ними тоже нехилая. Местные кулибины наворотили в java-коде сложных алгоритмов, которыми очень гордились, и даже расстроились, когда все они были заменены на довольно простые, но на много более эффективные sql-запросы с использованием диапазонных типов.
romanov9889
27.11.2025 13:51просто тут есть два конца спектра: алгодрочеры и отрицатели и обе категории странные.
ohrenet
27.11.2025 13:51Каждый должен заниматься своим делом. Парочка (условно) алгоритмистов в команде конечно не помешает. Парочка других специалистов. Каждый посмотрит на задачу под своим углом. Тогда есть шанс получить действительно грамотное решение.
wataru Автор
27.11.2025 13:51Это так не работает. Вы должны заметить, что тут у вас задача на алгоритмы, чтобы к алгоритмисту обратиться. Поэтому алгоритмист должен ревьювить весь код в команде вообще, чтобы искать там косяки. Гуглу легче нанимать только алгоритмистов.
ohrenet
27.11.2025 13:51Ну вот когда профайлер запикает красным, тогда и обратимся.
Гугл делать может что угодно, потому что вы - не гугл.
Гугл кстати не алгоритмистов нанимает, а преданных.
wataru Автор
27.11.2025 13:51Да, иногда бывает лучше оптимизировать сразу работу с базой данных, чем пост-процессинг. Это если у вас навороченная база данных, где это уже сделать можно. В моем случае - это распределенное хранилище и map-reduce чтобы его обрабатывать. Там нет "более эффективных" sql запросов.
ALexKud
27.11.2025 13:51Да, именно так. Если логи закинуть в БД то без всяких математических алгоритмов можно эту задачу решить элементарными SQL запросами c оконными функциями. При наличии индексов по датам все будет летать.
wataru Автор
27.11.2025 13:51Эм... ответьте мне на несколько вопросов, пожалуйста:
1) Какая СУБД может использоваться вот тут? Учтите, ей надо поглотить несколько террабайт данных.
2) Составьте-ка, пожалуйста, эффективный запрос, который по таблице с событиями подключения/отключения посчитает указанную в статье статистику. Хотя бы найдите мне индекс, который позволит быстро искать `select max(active_count) where id >= A and id <= B` у базы данных из первого вопроса.
3) Что, по вашему, происходит внутри базы данных, отвечающей на этот запрос? Действительно ли загрузка террабайт данных в БД, чтобы обработать их там, будет эффективнее просто обработки их хорошим алгоритмом сразу в кластере Map-reduce прямо на месте их аггрегации?
NihilPersonalis
27.11.2025 13:51Практически любая.
В нашем мире данные всего и вся лежат в БД. Поэтому логично адаптироваться именно под такой способ хранения. Тем более что внутри современных БД лежат реально мощные механизмы для обработки данных. Решить же задачу можно разными путями. От простого "в лоб" через умный SQL запрос и до предварительного расчёта, а то и вообще учёта количества активных пользователей для каждого подключения. Затраты практически нулевые и результат уже готов.
Как уже написал. Обычно агрегация подобных данных и так уже лежит в БД.
wataru Автор
27.11.2025 13:51От простого "в лоб" через умный SQL запрос и до предварительного расчёта, а то и вообще учёта количества активных пользователей для каждого подключения. Затраты практически нулевые и результат уже готов.
Простой в лоб - это будет тот же самый квадратичный алгорим, только крутящийся в движке БД. Что за предварительный расчет вы предалагаете? Что за умный SQL запрос? Давайте, вот есть конкретная задача, покажите, как ее классно решать с БД.
В лучшем случае внутри БД будет примерно такой же по производительности алгоритм, в худжем - гораздо медленнее. Я думаю там где-то точно должно быть решение за логарифм с использованием деревьев отрезков или чего-то подобного в индексе, но это все-равно медленнее.
ohrenet
27.11.2025 13:51В нашем мире данные всего и вся лежат в БД.
Если они действительно лежат в БД и не подразуменевается их срочная оперативная обработка и выдача результата, то может проще эту обработку просто зашедулить с низким приоритетом. Сколько эти "тысячи часов процессорного времени" в денежных единицах? Стоит ли овчинка выделки этими алгоритмами?
NihilPersonalis
27.11.2025 13:51Как разраб и архитектор информационных систем с математическим образованием и строчкой в дипломе математик-инженер скажу так. Вышка и алгоритмы нужны чтобы изначально правильно откалибровать мозг. Но ни разу в работе не нужны были алгоритмы в математическом понимании.
То что привела автор это обычная работа разработчика, не кодера. Т.е. мы и так постоянно применяем алгоритмы в работе. Даже правильный порядок действий это тоже ведь алгоритм. И сделать то, что приведено в статье математическое образование не требуется, как и какое-то особенное алгоритмическое. На таком уровне соображать должен любой, кто называет себя разработчиком. Мы ведь постоянно сталкиваемся с подобными оптимизациями. Это фактически просто здравый смысл.
wataru Автор
27.11.2025 13:51это обычная работа разработчика
Это фактически и есть основная мысль моей статьи, спасибо.
Но ни разу в работе не нужны были алгоритмы в математическом понимании.
Это просто уже народный термин. Любая не совсем тривиальная и наивная работа с данными - это уже "алгоритм". А программирование - это написать обработчик клика по кнопке и прочее перекладывание джейсонов. И когда их такие спрашивают на интервью в фаанг - это, редиски такие, валят оторванными от реальности задачами.
И сделать то, что приведено в статье математическое образование не требуется
Ну вообще, не рассуждая математически или не зная про классическую задачу RMQ, это решение вывести или найти практически невозможно. Так что надо именно теоретическую базу хотя бы один раз в жизни почитать.
sobeskiller
Ну т.е. встретилась задача, и разобраться, сделать research - не судьба? Обязательно алгоритмы нужны на собесе? А если какой-то алгоритма в памяти такого нанятого кандидата не оказалось, то всё, "у него лапки"?
lightln2
Я часто вижу такую точку зрения, что эти задачки на литкоде и собеседованиях - это такая лотерея, что человек их заучивает, и потом либо ему повезло, и он похожую задачу решал, либо не повезло.
Мне кажется, эти задачи скорее простые примеры из базового курса по Computer Science - то есть, если вы этот курс прошли, и прорешали эти задачи, то вероятность встретить задачу уровня easy/medium, к которой вообще непонятно, как подступиться, мала. Даже если в вузе такого курса не было, их на ютубе много, от MIT или МФТИ, например.
Другое дело, что многим быстрее рискнуть и бессистемно запомнить принцип решения пары сотен задач, чем проходить годовой курс и разбираться в теории, но я не знаю, насколько это проблема собеседований.
По поводу сделать research - далеко не всегда его можно делать, если вы не знаете основы computer science (А если знаете - то решение задачек на собеседовании не будет проблемой). В гугле часто возникают задачи, для которых надо придумать новый, прежде несуществующий, алгоритм, а не просто применить новый, они публикуют научные статьи каждый год.
ohrenet
Упаси господь сувать в это программистов. Разработка алгоритмов это работа математиков. Это действительно уровень науки.
cpud47
А математики тут как помогут? Всё же довольно много алгоритмов на практике используют различные шорткаты и особенности задачи. Поэтому их сначала внедряют в прод, а потом, через годы приходят математики и оформляют их в какой-то общий алгоритм.
Alexandroppolus
У "другого программиста" из статьи не возникло беспокойства по поводу O(N^2) и как следствие повода этот самый ресерч делать. Он запилил простой вариант за 10-15 минут и закрыл таск
ohrenet
Почему вы решили что не возникло? Может очень даже возникло. И проведя комплексный анализ что N не настолько велико, а сопровождаемость кода сильно упадёт, было принято верное решение "не умничать".
wataru Автор
Повторю: N до 10000. Это для вас "не велико"?
ohrenet
В зависимости от задачи, да, это могут быть совсем копейки.
wataru Автор
В другом комменте написал: Сэкономлеты тысячи часов процессорного времени в день.
cpud47
Как известно, алгоритмы за
это алгоритмы, которые падают только на проде (падают в смысле "выходят за все мыслимые пределы по времени").
Аналогичный пример: если не знать про FullScan vs IndexScan, то заметить наличие проблемного FullScan во время разработки — крайне маловероятно. И я видел примеры, когда делали таблицу с историческими данными без индексов...
ohrenet
Внедрить нагрузочное тестирование не пробовали?
wataru Автор
Без обширного знания алгортмов и навыков их применения вы этот research не сделаете.
Во-первых, вы скорее всего и не заметите, что тут вообще какие-то алгоритмы нужны. Но, допустим, вы профайлером нашли место где самый долгий цикл и даже подумали почему-то, а вдруг тут алгоритмами что-то можно сделать.
Вторая загвоздка: вы не найдете решение задачи, не зная ни про какие RMQ. В интернете вот такая постановка задачи не встречается. Там числа и отрезки, а у вас какие-то пользователи и события.
Ну, допустим, вам дико повезло. И вы нашли заветное описание алгоритма в интернете. Без понимания и знаний вы его заставить работать в вашей (напоминаю - измененной задаче) скорее всего не сможете.
Но, даже если вам необычайно повезет и вы все найдете в интернете, вы потратите на это дело во много раз больше времени, чем подготовленный человек, из-за преодоления упомянутых выше преград.
Если кандидат проходит собеседования и решает случайные задачи, то это значит, что или он выучил их очень много (что маловероятно и очень сложно), или он в них разбирается и способен выводить решения сам. Так что и новую неизвестную задачу сможет свести к известным алгоритмам или хотя бы понять, из какой области алгоритмы нужны и искать их по правильным ключевым словам в реальной работе.
А что касается интервью - там не дают каких-то особо заумных алгоритмов. Плюс для прохождения интервью не обязательно решать задачу именно тем методом, что имел ввиду автор задачи. Даже решать ее целиком и правильно не обязательно. Достаточно грамотно рассуждать, свести задачу к чему-то осмысленному и перечислить хоть какие-то вменяемые альтернативы, да выдать немного хорошего кода для самых инетересных частей предложенного решения. Не нужно знать все наизусть, надо знать базу и уметь ее применять.
ohrenet
Да, конечно!
Это вы теоретизируете. Ваш код тупо скопипастят и прогонят через тесты. Хоть один не прошёл - досвидос.
wataru Автор
Нет, не теоретизирую. Я эти интервью в гугле провожу. Я знаю, как они, по крайней мере, дложны работать. Нет, код никуда в падавляющем большинстве случаев не копируют и не прогоняют. Он в 60% случаев вообще не скомпилировался бы по моим ощущениям, но кандидаты интервью проходят.
Я, конечно, не могу полностью исключать существование отдельных странных кадров, которые вопреки инструктажу интервью проводят имено так, как вы говорите, а для отчета выдумывают что-то вменяемое, и поэтому им никто еще не надавал по рукам. Но это должно быть ничтожное меньшинство ситуаций.
Asterris
Вы в Гугле работаете? Получали согласование с руководством на такие комментарии?
Надеюсь вы понимаете, что из этого комментария легко написать статью "СОТРУДНИК ГУГЛ ПРИЗНАЛСЯ, ЧТО НАНИМАЕТ НА РАБОТУ ЛЮДЕЙ, НЕ УМЕЮЩИХ ПРОГРАММИРОВАТЬ" - и опровергать это придется на сильно высоком уровне.
Чота там подраспустил вас нынче ваш комплаенс, в наши времена за такие комменты по шапкам прилетало сразу.
sobeskiller
Я про research более общего генезиса: как вообще подобного рода задачи решаются. Изучить весь опыт и best practices. Может тут вообще алгоритмы не нужны и задача решает другими подходами. Либо эффективно применяются довольно специфичные алгоритмы, учитывающие природу domain knowledge.
Это вообще более глобальная проблема. У нас же чуть что, каждый тут же бежит изобретать свой 5 колёсный велосипед из
говна и палоктого что лучше всего умеет.wataru Автор
Эта задача в такой формулировке вообще нигде не встречается. Вы буквально ничего по ней нигде не найдете, если только уже не обладаете достаточным набором знаний, чтобы переформулировать/свести ее к чему-то более стандартному.
sobeskiller
В такой - конечно не встречается. Было бы странно если бы встречалась.Да, надо обладать некоторым объёмом знаний предметной области чтобы смочь переформулировать или найти что-то более-менее близкое. Да и вообще понимать что на самом деле делаешь. В любом случае, это в первую очередь domain knowledge, research, а алгоритмы тут уже постольку-поскольку.
wataru Автор
И какие же знания "предметной области" тут помогут? Единственное знание, что тут нужно, это что можно быстро искать максимум на отрезке в массиве и это не "предметная область", это алгоритмы. Или, по-вашему, обработка логов и вычисление статистики - это такая особая предметная область?