Общее замечание о собеседовании по кодированию

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

Пока компании по-прежнему используют эти типы проблем, вам нужно к ним готовиться.

Источник проблемы / Вдохновение

Glassdoor
Автор вопроса: Facebook

описание проблемы

Возвращает список сумм от корня к листу (слева направо) из заданного дерева.

Решение проблемы

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

Теперь давайте изучим код. Во-первых, я создал функцию Node, которая помогает нам многократно строить узлы дерева во время тестирования. Вы можете и должны написать свои собственные тесты, чтобы подтвердить свое решение.

  1. В этом решении мы используем рекурсию для обхода каждого узла дерева. При рекурсии мы находимся на некоторых критериях при каждом последовательном вызове нашей функции. В нашей проблеме, как и во многих проблемах с деревом, нашим критерием завершения является то, есть ли у нас еще узлы, через которые нужно пройти по этой ветви. Этот критерий можно увидеть в строке 2.
  2. Наш рекурсивный случай можно увидеть в операторе else в строках с 4 по 14. Здесь мы перебираем всех дочерних элементов, рекурсивно вызываем getRootToLeafSums с текущим дочерним элементом и добавляем значение текущего узла к сумме дочернего элемента, полученной в результате нашего рекурсивного вызова.
  3. И в базовом, и в рекурсивном случае мы возвращаем массив чисел. При работе с рекурсивными проблемами часто бывает полезно сначала разметить скелет функции и условные операторы. После этого идентификация «типа» JavaScript или возвращаемой структуры данных может быть очень полезной. Вы знаете, что каждый вызов getRootToLeafSums должен возвращать массив чисел, поэтому вы знаете, что и ваш базовый случай, и рекурсивный случай должны возвращать одну и ту же структуру данных.

Вот и все! Основная часть этой проблемы состоит в том, чтобы решить, как пройти по древовидной структуре и как завершить обход каждой ветви. Математическая часть этой задачи довольно тривиальна.

Заключение

Часто эти решения проблем не очень подробны. Ключ состоит в том, чтобы наметить ваш обход и иметь правильное понимание базовых структур данных.

Больше контента на plainenglish.io