Проблема LCA на собеседовании
Иногда я сталкиваюсь с такими вопросами на собеседовании: "Найти общего родителя любых двух узлов в дереве". Я заметил, что они задают вопросы LCA также в Google, Amazon и т. Д.
Как сказано в википедии, LCA можно найти путем пересечения путей от заданных узлов к корню, и для этого требуется O(H), где H - высота дерева. Кроме того, существуют более продвинутые алгоритмы, которые обрабатывают деревья в O(N) и отвечают на LCA-запросы в O(1).
Интересно, что именно интервьюеры хотят узнать о кандидатах, задающих этот вопрос LCA? Первый алгоритм пересечения путей кажется тривиальным. Ожидают ли они, что кандидаты запомнят алгоритмы предварительной обработки? Ожидают ли они, что кандидаты будут изобретать эти алгоритмы и структуры данных на лету?
2 ответа
Они хотят видеть, из чего ты сделан. Они хотят видеть, как вы думаете, как вы решаете проблемы и справляетесь со стрессом в установленные сроки. Я полагаю, что если вы решите проблему, потому что вы уже знаете решение, то они просто поставят вам другую проблему. Это не решение, которое они хотят, это ваш мозг.
Со многими вопросами об алгоритмах в интервью я не забочусь (или не хочу), чтобы вы помнили ответ. Я хочу, чтобы вы могли получить ответ из основных принципов, которые вы знаете.
Реально: я мог бы дать на две заботы меньше, если вы уже знаете ответ "как сделать X", если вы можете быстро построить ответ на лету. В конечном счете: в реальном мире я не могу предположить, что у вас есть опыт решения проблем домена X, но если вы столкнетесь с проблемой в указанном домене, я, безусловно, надеюсь, что у вас будет аналитическая способность найти разумный ответ на основе общих знаний, которыми вы владеете.
Дерево - это обычная структура данных, которую, как можно предположить, знает большинство людей. Если вы знаете ответ от случая к случаю, вы сможете объяснить его. Если вы не знаете ответ, но понимаете структуру данных, вы сможете легко найти ответ.