Проблема LCA на собеседовании

Question

Иногда я сталкиваюсь с вопросами интервью, такими как this : «Найти общего родителя любых 2 узлов в дереве». Я заметил, что они задают вопросы LCA также в Google, Amazon и т. Д.

Как гласит Википедия LCA можно найти путем пересечения путей от заданных узлов к корню, и требуется O (H), где H - высота дерева. Кроме того, существуют более продвинутые алгоритмы, которые обрабатывают деревья в O (N) и отвечают на LCA-запросы в O (1).

Интересно, что именно интервьюеры хотят узнать о кандидатах, задающих этот вопрос LCA. Первый алгоритм пересечения путей кажется тривиальным. Ожидают ли они, что кандидаты запомнят алгоритмы предварительной обработки? Ожидают ли они, что кандидаты будут изобретать эти алгоритмы и структуры данных на лету?

Answer 1

Они хотят видеть, из чего ты сделан.Они хотят видеть, как вы думаете, как вы решаете проблемы и справляетесь со стрессом в установленные сроки.Я полагаю, что если вы решите проблему, потому что вы уже знаете решение, они просто создадут вам другую проблему.Это не решение, которое они хотят, это ваш мозг.

Answer 2

Со многими вопросами об алгоритмах в интервью мне все равно (или я хочу), чтобы вы запомнили ответ. Я хочу, чтобы вы могли получить ответ из основных принципов, которые вы знаете.

Реально: я мог бы дать на две заботы меньше, если вы уже знаете ответ на вопрос «как сделать Х», если вы можете быстро построить ответ на лету. В конечном счете: в реальном мире я не могу предположить, что у вас есть опыт решения проблем домена X, но если вы столкнетесь с проблемой в указанной области, я, безусловно, надеюсь, что у вас будет аналитическая способность найти разумный ответ на основе общих знаний, которыми вы владеете.

Дерево - это обычная структура данных, которую, как можно предположить, знает большинство, - если вы знаете ответ от случая к случаю, вы сможете объяснить его. Если вы не знаете ответ, но понимаете структуру данных, вы сможете легко найти ответ.