Сегодня на рынке IT трудно представить собеседование без того или иного варианта Live Coding — будь то алгоритмическая задача или рефакторинг уже написанного кода. Цель этого мероприятия — понять, насколько хорошо варит голова кандидата в бою. Ведь теорию, по сути, любой может вызубрить и ответить на все вопросы на ура. А вот как он мыслит и пишет код — простыми вопросами никак не определить.
Часто Live Coding вселяет ужас в кандидата, бывает, что от волнения он просто забывает даже самые простые пути решения той или иной задачи. Мы с вами не будем разбирать конкретные задачи и то, как их можно решить, потому что собеседующие становятся все более изощренными, и предугадать, что для вас подготовили, практически невозможно. Но мы можем исключить самые частые ошибки и получить подсказки к решению задачи, прочитав только требования.
Поэтому сегодня мы с вами разберем самые частые ошибки кандидата, а также в конце видео я дам несколько советов, которые помогут вам в будущем решать любые задачи на раз-два.
Об основных ошибках собеседующихся и советах рассказал lead iOS-разработки — Артур Михайлов.
Для тех, у кого нет времени на чтение материала, рекомендуем посмотреть видеоролик:
Основные ошибки, которые совершают кандидаты на live-coding сессиях
Игнорирование входных данных
Самой распространенной ошибкой можно назвать игнорирование входных данных. Это случай, когда задача или проблема в качестве входного параметра имеет уже готовую (например, отсортированную) структуру данных, которую при решении проблемы или задачи кандидат упускает из виду и меняет структуру под удобную себе. Это ведет к тому, что потенциально линейное решение задачи или проблемы приводится к более сложному.
Пример
Необходимо написать функцию, которая сложит два отсортированных массива в один единый, также отсортированный массив
Самое просто и лаконичное решение может выглядеть следующим образом:
![](https://habrastorage.org/getpro/habr/upload_files/f9a/9a8/e97/f9a9a8e9757f143d7bbe317da808b796.png)
С точки зрения читаемости кода это можно считать эталонным решением, но мы упускаем из виду главное преимущество входных параметров алгоритма — массивы уже отсортированы. Одно только это условие должно натолкнуть в первую очередь на мысль о том, что дальнейшей сортировки в процессе решения задачи стоит избегать, так как сортировка — это процесс с нелинейной сложностью (в лучшем случае O(n log n)).
Решение задачи за линейное время, конечно, потребует больше кода и внимательности, но в этом и заключается, на самом деле, задача — реализовать оптимальный с точки зрения производительности алгоритм. Решение может иметь следующий вид, главным преимуществом которого будет линейная сложность выполнения (O(n)).
![](https://habrastorage.org/getpro/habr/upload_files/917/159/29e/91715929e5105018343db8d8e1f6cf75.png)
Линейная сложность, двойное время выполнения
Зачастую при оценке сложности алгоритма мы можем прийти к результату типа O(n), при том, что время на выполнение алгоритма будет x * n, где x — количество последовательных итераций. Это магическое число x должно быть неявным индикатором и подсказкой для кандидата о том, насколько оптимально реализован его алгоритм. Можно взять себе за правило, что число x не должно превышать 2 или 3. Если в процессе реализации появляется понимание того, что число x уходит далеко за пределы диапазона 2–3, что-то идет не так, и стоит пересмотреть свое решение.
Нет вложенным циклам
Звучит тривиально и просто, но можно легко попасть в ловушку вложенного цикла, сам того не осознавая. Рассмотрим простой пример.
![](https://habrastorage.org/getpro/habr/upload_files/8a2/b20/9af/8a2b209af2939e564698fe1c35081fac.png)
На первый взгляд может показаться, что нас всего один цикл и сложность выполнения будет линейной. Но стоит обратить внимание на функцию 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. Если у вас из опыта есть что добавить, жду ваших случаев в комментариях, с удовольствием почитаю. С вами был Артур, до новых встреч.
Автор: Артур Михайлов, lead iOS-разработки в «Технократии»
Также подписывайтесь на наш телеграм‑канал «Голос Технократии». Каждое утро мы публикуем новостной дайджест из мира ИТ, а по вечерам делимся интересными и полезными статьями.