Как стать лучше на собеседовании по программированию

Стряхните нервы, сделайте глубокий вдох (вы его поняли) и завершите свое следующее интервью!

Итак, вы хотите стать лучше на собеседовании? Все дело в подходе - это руководство представляет собой пошаговое руководство о том, как именно отвечать на вопросы собеседований по кодированию от таких компаний, как Facebook, Amazon, Microsoft, Netflix или Google.

Эта статья расскажет о многом. Он поможет вам ответить на типичный технический вопрос собеседования (доска или не-доска), и вам будут предложены такие вещи, как:

• Менталитет нужен, чтобы побеждать нервы
• Каждый шаг во время собеседования
• Какие выкройки освежить

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

Примечание: изначально это было опубликовано на https://algodaily.com.

Преодоление нервов

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

Почему именно такие интервью вызывают такой ужас?

На самом деле, есть несколько последствий.

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

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

Знание этого, похоже, не помогает, и вот почему.

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

Но на самом деле это не так!

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

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

Если нервы все еще мешают, есть другие решения. Некоторые вещи, которые могут быть полезны, - это ежедневная медитация, здоровая пища, которая питает ваш мозг, и регулярные аэробные упражнения.

Что делать, если вы полностью отключились

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

Так что давайте быстро займемся чем-нибудь - если вы действительно понятия не имеете, вот что делать.

Допустим, вы фронтенд-инженер, у вас за плечами несколько лет разработки одностраничных приложений на JavaScript. В интервью вам задают следующий технический вопрос.

Когда вы примените асинхронную связь между двумя серверными системами?

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

Вот два возможных способа решить эту проблему:

1. Свяжите это с чем-то, что вы сделали.
2. Подчеркните, насколько вы рады учиться и работать над такими вещами.

Первый ответ работает, потому что он все еще позволяет вам продемонстрировать свой опыт:

Я не работал напрямую с серверными системами, но не могли бы вы еще раз напомнить мне, что asynchronous означает? Ах, форма программирования, которая позволяет выполнять работу отдельно от основного потока приложения? Я сделал нечто подобное с React - иногда вставка данных в базу данных через конечную точку REST занимает некоторое время, но мы хотим немедленно сообщить пользователю, что данные сохраняются. Итак, мое обоснованное предположение заключается в том, что это может произойти, когда вы хотите, чтобы процесс что-то делал, ожидая завершения чего-то еще.

В этом случае интервьюер может не на все 100% услышать, но вы проявили некоторую техническую хватку. Вы также смогли обсудить прошлый опыт.

С другой стороны, что, если вам вообще не с чем можно связать этот вопрос? Хорошей альтернативой может быть разговор о том, насколько вы взволнованы и как вы научитесь этому:

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

Насколько хороши собеседования по алгоритму доски?

Остальная часть этого урока будет посвящена подходу к стандартизированным структурам данных и вопросам, основанным на алгоритмах. Это будет по-прежнему актуально, но в меньшей степени, для небольших выборочных задач, таких как «вот базовая настройка, реализуйте REST API с некоторыми каркасами».

Да, интервью по алгоритму доски вызывают споры. Однако есть несколько причин, по которым они все еще сохраняются. Во-первых, они подают интервьюеру несколько сильных сигналов, таких как:

• Может ли кандидат ясно мыслить перед другими (на что направлен этот урок)?
• Похоже, они готовы к собеседованию (сигнал к трудовой этике)?
• Обладают ли они разумными логическими способностями?
• Могут ли они отличить хорошее решение от плохого?
• Как они понимают основы информатики?

Во-вторых, их легко делать в масштабе, что особенно важно, если вы - конгломерат, которому нужно ежегодно нанимать тысячи сотрудников.

Да, есть домашние задания, собеседования с характерными особенностями и недельные «пробные» периоды. Я уверен, что это отличные методы.

Тем не менее, стандартная структура данных и вопросы об алгоритмах «можете ли вы решить эту проблему прямо передо мной?» По-прежнему остаются стандартом для большинства компаний-разработчиков программного обеспечения.

Давайте выясним, как с ними бороться.

Подход хороших собеседников

Прежде чем мы углубимся, сделаем важное замечание. Чтобы все это сработало, вам необходимо отработать свои структуры данных и алгоритмы.

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

Хорошей отправной точкой, конечно же, является Премиум-курс AlgoDaily и проблема ежедневной рассылки. Другие рекомендации можно найти в нашей статье Как подготовиться к техническому собеседованию.

С учетом всего сказанного, вот типичные шаги, которые мы рекомендуем для решения вопросов с доски. Мы потратим много времени на подробное изучение каждого из них.

1. Просмотрите от одного до трех примеров ввода, чтобы понять проблему.
2. Быстро распакуйте решение грубой силы, спросив, как это сделает человек.
3. Свяжите решение методом грубой силы с шаблоном, структурой данных или техникой информатики.
4. Оптимизируйте и снова выполните те же тесты, что и на первом шаге.
5. Если у вас есть время, назовите крайние случаи и способы устранения проблемы.

Общение во время интервью

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

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

Как вы демонстрируете хорошие коммуникативные навыки?

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

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

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

Как собрать требования

Перейдем к практическим советам по техническим вопросам на собеседовании. Можно разобрать проблему Нули до конца. Вот подсказка:

Напишите метод, перемещающий все нули в массиве в его конец.

Первое, что вам следует сделать, это уточнить требования. Пока вы точно не знаете, в чем проблема, вам незачем пытаться найти решение. Вот почему:

Кандидат: Круто, нули сзади, ненулевые спереди. Правильно?

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

Интервьюер: Также обратите внимание, что вы должны поддерживать порядок всех других элементов. О, и это нужно сделать за O (n) раз.

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

Кандидат: Итак, мы хотим переместить все нули назад, оставив ненулевые значения впереди. Мы также хотим сохранить порядок, в котором изначально были ненулевые числа, и алгоритм должен работать в линейном времени.

Интервьюер: Хорошо.

Начните с входов и выходов

Самое следующее, что нужно сделать - это либо попросить несколько образцов массивов, либо придумать свой собственный. Начните создавать свои тестовые примеры. Это поможет вам начать процесс преобразования входных данных для получения выходных данных.

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

Кандидат: Очень интересная проблема. Хорошо, просто чтобы убедиться, что я понимаю трансформацию и результат, которые мы хотим, позвольте мне привести несколько примеров. Значит, если мне дадут [0, 1], мы захотим вернуть [1, 0]?

Интервьюер: Да, именно так. (кандидат начинает думать о том, как переместить одинокий ноль в первом примере)

Кандидат: Хм, для этого нам просто нужно было поменять местами 0 на 1. Теперь, если бы мне дали [1, 0, 2, 0, 4, 0], я бы хотел вернуть [1, 2, 4, 0, 0, 0].

Интервьюер: Верно.

Кандидат: И [0, 0, 4] становится [4, 0, 0]. Хм ...

Как найти решение методом грубой силы

Теперь, когда вы опробовали некоторые входы и выходы, главный вопрос, который нужно задать:

Если бы машины не было, как бы человек вручную решил эту проблему?

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

Кандидат: Хм, да, для этих примеров результат продолжает возвращать массив ненулевых плюс массив нулей в конце. Обдумывая очень простую реализацию, я делал следующее: перебирал, находил ненулевые значения и просто помещал их в другой массив temp. Затем я заполнил оставшуюся часть массива результатов 0s, пока мы не получили исходную длину.

Интервьюер: Интересно. Хотите написать эту реализацию?

Используйте псевдокод, чтобы прояснить свои мысли

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

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

Кроме того, мышление в псевдокоде намного проще изменить, если вы обнаружите вредную ошибку. Вот как это может выглядеть на первый взгляд:

temp = []
zero_count = 0
iterate through array:
  if nonzero, push to new temp
  if zero, increment count
for zero_count times:
  push to temp
return temp

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

Интервьюер: Отлично, теперь вы можете сделать это без создания экземпляра нового массива?

Не теряйте хладнокровия на этом этапе, а также не слишком увлекайтесь прохождением первой части. Пришло время связать наше решение методом грубой силы с техникой его улучшения. Теперь мы рассмотрим несколько способов сделать это.

Как оптимизировать с помощью шаблонов и абстракций

Выполнив примерно 50–100 заданий на собеседовании, вы начнете распознавать шаблоны, которые можете использовать. Вот пример одного из них: If you want speed, you usually need more space/memory. Это особенно актуально для следующего раздела об использовании структуры данных.

Просмотрите каждый шаг в своем решении и подумайте о любых возможных способах его упрощения или разрушения. Есть ли способы уменьшить его сложность?

Один из приемов - думать о том, что вы делаете, с более высокого уровня. Под этим я имею в виду избавиться от сорняков логики и вернуться к переходу от ввода к выводу. В приведенном выше примере да, мы перемещаем нули в конец путем объединения массивов, но что на самом деле нам нужно сделать? Процесс можно представить как:

• Определите ненулевые элементы.
• Поместите элементы в разные индексы.
• Узнайте, сколько там 0.

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

• Например, чтобы идентифицировать ненулевые элементы, вы можете перебирать массив и использовать условное выражение.
• В качестве альтернативы вы можете использовать метод filter.
• А если это не поможет, вы также можете найти несколько zeros подряд и splice новый массив.

Еще кое-что, чтобы спросить себя: What am I trying to do in plain English?

Еще один очень простой способ добиться прогресса - это поиграть с вводом.

• Если это коллекция, помогает ли сортировка или группировка?
• Если это дерево, можем ли мы преобразовать его в массив или связанный список?

Если настройка ввода не повлияла на результат, возможно, пришло время сделать более серьезную трансформацию.

Представьте структуру данных или абстрактный тип данных

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

Возвращаясь к задаче Нули до конца, которую мы сделали ранее, нашим узким местом, вероятно, является шаг putting elements at different indexes. В этом случае мы можем понять, что использование переменной counter полезно.

Обратите внимание, что структура данных не должна быть сложной. В нашем случае мы буквально вводим одну int переменную - , но иногда это все, что вам нужно.

Что должен считать counter? Что ж, как только мы разделим массив на ненулевые ([1, 2, 3]) и нули ([0, 0, 0]), нас действительно волнует только то, где заканчиваются ненулевые числа.

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

Затем мы могли бы написать следующий псевдокод, чтобы использовать эту стратегию:

insert_position = 0
for i in nums
  if i is not 0
    increase insert_position
    keep it in insert_position
  fill the rest in with 0

Несмотря на наличие двух циклов, временная сложность упрощается до O (n). Однако сложность пространства постоянна, поскольку мы используем один и тот же массив, поэтому у нас есть улучшение!

Шпаргалка по тактической структуре данных

Нужен действительно быстрый доступ к элементу в коллекции? У массива уже есть место в памяти.

Нужно быстро вставить данные? Добавьте его в хеш-таблицу или связанный список.

Нужен максимум или минимум за O (1) раз? Звоните в кучу.

Нужно смоделировать связи? Получите график.

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

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

Особое примечание о хеш-таблицах.

Познакомьтесь с этими ребятами как следует! Их можно использовать в удивительном количестве решений.

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

Если дополнительная структура данных не помогает, возможно, пришло время опробовать старый (но надежный) метод.

Знакомство с техникой алгоритмов компьютерных наук

Есть несколько приемов, о которых должен знать каждый. Обычно они охватываются Intro to Algorithms классами для классификации алгоритмов.

Как правило, это инструменты, полезные не только для собеседований, но и для разработки программного обеспечения в целом, так что познакомьтесь с ними!

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

Рекурсия. Посмотрите, можете ли вы использовать функцию, которая вызывает сама себя. Будьте особенно осторожны с рекурсией для деревьев.

Запоминание. Можно ли использовать частичные результаты, полученные с помощью метода грубой силы, для больших или разных входных данных? Если да, используйте какое-то кеширование. Какие данные вы можете хранить в памяти (или создавать и хранить в памяти), чтобы упростить алгоритм?

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

Что делать, если ничего из вышеперечисленного не помогло

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

У вас есть два варианта.

Задайте дополнительные вопросы.

OR

Скажите: «Я застрял. Могу я получить подсказку? »

Продолжайте общаться! Интервьюеры обычно более чем рады намекнуть - собственно, это их работа. Некоторые вопросы собеседования, к сожалению, содержат одну или две «ключевые интуиции», которые вы должны понять, прежде чем сможете найти решение.

После того, как у вас будет рабочее решение

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

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

На этом этапе вы также сможете отсеять неверные предположения или сделать важные выводы («о, подождите, мы должны использовать Map вместо объекта JS»).

Кандидат: начнем с [1, 0, 3]; Я думаю, это хороший кандидат для тестирования. Хорошо, начиная с 1, мы видим, что это не ноль, поэтому он может оставаться на месте. Мы переходим к следующему элементу, поэтому давайте увеличим счетчик последнего индекса массива. Теперь у нас есть 0, давайте пропустим. Хорошо, 3, не ноль, наш счетчик на 1, поэтому мы ставим его после 1, и у нас есть [1, 3]. Большой! Затем мы ставим 0 в конце и получаем желаемый результат.

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

Примечание: если вы собираетесь проводить собеседование на доске, купите Сухую магнитную белую доску и потренируйтесь писать на ней код от руки.

Есть много вещей, которые люди не принимают во внимание при программировании на доске: в основном это управление пространством, но также то, как использовать более короткие переменные и писать по горизонтали.

В любом случае, теперь вы написали этот код:

function zerosToEnd(nums) {
    let insertPos = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[insertPos++] = nums[i];
        }
    }

    for (let j = insertPos; j < nums.length; j++) {
        nums[j] = 0;
    }

    return nums;
}

После того, как вы написали код решения, следует приступить к технической части.

Теперь интервью будет направлено на вопросы интервьюеру. Убедитесь, что у вас есть вопросы, и постарайтесь не думать о своей работе.

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

Надеюсь, вы нашли это руководство полезным. Помните, что любую проблему программирования можно решить с помощью правильного подхода и правильного мышления. Удачи!

Первоначально опубликовано на https://algodaily.com.