Оптимизация часто включает компромиссы;в некоторых случаях один алгоритм однозначно лучше другого, но в других случаях один алгоритм лучше в одном отношении (например, время), а другой алгоритм лучше в другом отношении (например, использование памяти).
В вашемВ этом случае, я предполагаю, что ваш интервьюер искал подход, который оптимизировал бы объем обработки, который должен быть выполнен после того, как вы начнете получать запросы, , даже если это означает, что вам нужно сделать больше предварительной обработки дляграф.Моя причина сказать, что это термин «запрос»;довольно часто оптимизируют источник данных для «онлайновых» запросов.(Конечно, он (а), вероятно, не ожидал, что вы сами решите, что этот компромисс был в порядке; скорее, он (а), вероятно, надеялся на разговор о разного рода компромиссах.)
Итак, учитывая это.,.
- Я вижу, что вы уже пометили свой вопрос с помощью [tree] и [наименьшего общего ответа], поэтому вы, вероятно, уже сделали самые большие наблюдения, а именно:
- График - это дерево.Мы можем произвольно выбрать «корень», так что каждый другой узел имеет «родителя», ненулевую «глубину», одного или нескольких «предков» и т. Д.
- Как только мы это сделаем, самый короткийпуть от узла a к узлу b состоит из узла a , узла b , всех предков a , которыене являются предками b , все предки b , которые не являются предками a , и их "наименее общий предок".(Это остается верным, если a является предком b или наоборот: если a является предком b , то этонаименьший общий предок a и b , и наоборот. Это даже остается верным, если a и b одинаковы.)
- Итак, мы можем выполнить следующую предварительную обработку:
- Представить граф как отображение от каждого узла в список его соседей.(Так как узлы пронумерованы от 1 до N , это сопоставление представляет собой массив списков N .)
- Выберите корневой узел.
- Рассчитайте и сохраните «родителя» и «глубины» каждого узла.(Мы можем сделать это за O ( N ), используя поиск по глубине или поиск по ширине.)
- Для каждой пары узлов рассчитайте и сохранитеих "наименее общий предок".(Мы можем сделать это за общее время O ( N 2 ), используя результаты предыдущего шага и памятки, потому что памятка обеспечивает амортизацию.)
- Инициализируйте сопоставление от каждого узла числу раз, которое является конечной точкой пути, и сопоставление от каждого узла количеству раз, когда он является наименьшим общим предком конечных точек пути.(Примечание: если данный путь от одного узла к самому себе, то мы будем считать как , дважды , что это конечная точка пути, а также один раз, когда он является последним общим предком конечных точек.)
- Для каждого запроса обновите два сопоставления.Мы можем сделать это за O (1) раз за запрос, всего O ( Q ).
- Наконец:
- Выполните обход графа по порядку, вычисляя количество путей, которые посетили этот узел.Логика для этого заключается в следующем: общее количество путей, которые посетили узел a , равно сумме числа путей, которые посетили каждый из его дочерних элементов, минус сумма количества раз, которое каждыйего потомков был последним общим предком конечной точки пути, плюс число раз, когда a сам был конечной точкой, минус количество раз, когда a сам был последним общим предкомконечной точки пути (для отмены двойного счета).
- Возвращает узел, для которого предыдущий шаг вернул наибольшее число.Если несколько узлов связаны для наибольшего, то.,,Я не знаю, формулировка проблемы была неопределенной по этому поводу, вам нужно спросить о требованиях.
В целом, это требует O (N 2 ) предварительная обработка, O ( Q ) обработка в реальном времени для каждого запроса и O ( N * 1116)*) постобработка.
Если N достаточно велик, и мы ожидаем, что возможно, что хотя бы один раз было посещено только небольшое подмножество узлов, тогда мы можем ускорить постобработку, игнорируянепосещенные части дерева.Это включает в себя поддержание набора узлов, которые были конечными точками путей, а затем выполнение постобработки «снизу вверх», запуск с самых глубоких таких узлов и перемещение «родительских» от данного узла, только если число посещенных путейэтот узел меньше, чем количество раз, когда он был наименьшим общим предком.Если мы обозначим число различных конечных точек как P , а число различных посещенных узлов - M , то это можно сделать как-то вроде O ( P log P + M ).