Сегодня на рынке IT трудно представить собеседование без того или иного варианта Live Coding — будь то алгоритмическая задача или рефакторинг уже написанного кода. Цель этого мероприятия — понять, насколько хорошо варит голова кандидата в бою. Ведь теорию, по сути, любой может вызубрить и ответить на все вопросы на ура. А вот как он мыслит и пишет код — простыми вопросами никак не определить.

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

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

Об основных ошибках собеседующихся и советах рассказал lead iOS-разработки — Артур Михайлов.

Для тех, у кого нет времени на чтение материала, рекомендуем посмотреть видеоролик:

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

Пример

Необходимо написать функцию, которая сложит два отсортированных массива в один единый, также отсортированный массив

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

С точки зрения читаемости кода это можно считать эталонным решением, но мы упускаем из виду главное преимущество входных параметров алгоритма — массивы уже отсортированы. Одно только это условие должно натолкнуть в первую очередь на мысль о том, что дальнейшей сортировки в процессе решения задачи стоит избегать, так как сортировка — это процесс с нелинейной сложностью (в лучшем случае O(n log n)).

Решение задачи за линейное время, конечно, потребует больше кода и внимательности, но в этом и заключается, на самом деле, задача — реализовать оптимальный с точки зрения производительности алгоритм. Решение может иметь следующий вид, главным преимуществом которого будет линейная сложность выполнения (O(n)).

Зачастую при оценке сложности алгоритма мы можем прийти к результату типа O(n), при том, что время на выполнение алгоритма будет x * n, где x — количество последовательных итераций. Это магическое число x должно быть неявным индикатором и подсказкой для кандидата о том, насколько оптимально реализован его алгоритм. Можно взять себе за правило, что число x не должно превышать 2 или 3. Если в процессе реализации появляется понимание того, что число x уходит далеко за пределы диапазона 2–3, что-то идет не так, и стоит пересмотреть свое решение.

Звучит тривиально и просто, но можно легко попасть в ловушку вложенного цикла, сам того не осознавая. Рассмотрим простой пример.

На первый взгляд может показаться, что нас всего один цикл и сложность выполнения будет линейной. Но стоит обратить внимание на функцию contains(:), как тут же становится понятно, что мы получили цикл в цикле, а это, в свою очередь, дает сложность O(n2).

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

Это принцип, описанный в одноименной книге Даниэля Канемана, который хорошо применим к решению задач на live coding. Как только задали все уточняющие вопросы, стоит собрать ответы на них воедино и проанализировать в голове свое решение, проговаривая каждый шаг ВСЛУХ. Это поможет наладить контакт с собеседующим и сразу позволит понять, в правильном ли направлении идет ход мыслей

Самое главное в задаче или проблеме — это то, что решение должно быть РАБОЧИМ. Решить задачу или проблему не всегда получится решить лаконично и красиво с точки зрения кода. Все примеры «идеального» решения на LeetCode и Codewars не были написаны сходу без правок — они итеративно рефакторились до того момента, когда решение приобретет лаконичный вид. Учитывая этот факт, хорошим подходом будет в первую очередь написать РАБОЧЕЕ решение задачи, а уже потом, по договоренности с собеседующим, отрефакторить код. 

Единственное, о чем стоит помнить, — это то, что «грязное» решение будет по сложности выполнения приближенным к оптимальному. Если «грязное» решение имело сложность O(n2), а рефакторинг привел к уменьшению сложности, то это уже не рефакторинг, а новый подход к решению задачи.

Вне зависимости от языка программирования в решении задачи может выглядеть разумным использование функций высшего порядка с нелинейной сложностью выполнения. Примерами таких функций могут быть sort, сложность которого является O(n log n).

Собеседующий описывает задачу и обязательно говорит время, за которое задача должна быть решена. Это само по себе должно послужить сигналом о том, с какой сложностью выполнения мы столкнулись. Если это время 10–15 минут, то, скорее всего, ожидаемая сложность — O(n). Если времени дается больше, например 30 минут, то, скорее всего, решение не будет таким уж простым, и сложность выполнения может выходить за рамки O(n). Но чаще всего все же алгоритмические задачи будут сводиться к линейной сложности, если вы, конечно, не собеседетесь в «Желтую компанию» с красной буквой Я или в сеть компаний FAANG (Facebook, Apple, Amazon, Netflix, Google) на сеньорскую позицию.

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