Ошибки при самостоятельной подготовке к решению алгоритмических задач на интервью

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

• Введение
• Ошибка 1. Начинать подготовку со сложных задач
• Ошибка 2. Пропускать этапы решения задач
• Ошибка 3. Подгонять задачу под известный подход
• Ошибка 4. Я должен решить сам
• Ошибка 5. Зависать на возникших вопросах
• Ошибка 6. Забить на качество кода
• Ошибка 7. Проверять алгоритм на простых входных данных
• Ошибка 8. Игнорировать допущенные ошибки
• Заключение

Введение

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

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

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

«Что вы думаете о таких собеседованиях с алгоритмами? Они вообще показательны?»

«Нет, я думаю что это смешно. В результате вы лишь найдете людей, которые умеют решать такие задачи», — известный разработчик Дуглас Крокфорд.

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

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

Итак, рассмотрим выявленные ошибки.

Ошибка 1. Начинать подготовку со сложных задач

«Я же сеньор-помидор, начинать с лёгких задач для слабаков»

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

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

Ниже представлены автопортреты участников тренинга, проведенного его автором Бетти Эдвардс. Один — нарисованный учеником в начале курса, второй — по окончании учебы, пять дней спустя.

«Они изумительны, не правда ли? Авторов первых рисунков никак нельзя заподозрить в наличии способностей к рисованию. Большинство этих творений напоминают мне мою сову. Но лишь несколько дней спустя все до единого уже умели рисовать! Эдвардс клянется, что это совершенно типичная группа и типичная ситуация. Кажется, такого просто быть не может. Эдвардс считает также, что большинство людей смотрят на умение рисовать как на сверхъестественную способность, обладать которой дано лишь избранным. Но это только потому, что люди не понимают слагаемых — вполне доступных для усвоения слагаемых — умения рисовать. В действительности, по словам Эдвардс, это не столько умение рисовать, сколько умение видеть, то есть воспринимать линии, пространства, взаимоотношения элементов, свет и тень, а также все это вместе взятое. Рисование требует от нас усвоить каждое из этих отдельных умений, а затем объединить их в одном процессе. Некоторые люди приобретают такие навыки походя, а другим приходится работать над их освоением. Но, как легко убедиться по автопортретам "после", на это способен каждый», — Кэрол Дуэк из книги «Гибкое сознание: новый взгляд на психологию».

Ошибка 2. Пропускать этапы решения задач

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

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

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

«Советы должны быть простыми и естественными, иначе они не будут ненавязчивыми. Советы должны быть общими, применимыми не только к данной задаче, но ко всевозможным задачам, если они имеют целью развить способности учащегося, а не просто какой-нибудь частный технический навык. Таблица должна быть короткой, чтобы вопросы из нее повторялись достаточно часто; применяться они должны естественно и в разнообразных ситуациях. Тогда, вероятно, они будут в конце концов усвоены учащимся и обратятся в привычную функцию его ума», — Пойа в книге «Как решать задачу».

Благодарю за рекомендацию книги «Математика и правдоподобные рассуждения. Д. Пойа» Романа Зайруллина, автора «LEGACY SOFTWARE: Как заставить чужой код работать», которая позволит глубже понять этапы этого процесса.

Или специализированным под нашу задачу, представленными как «Схема решения задачи» в книге «*Карьера программиста» Лакмана Гэйла.

Ошибка 3. Подгонять задачу под известный подход

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

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

Простой пример для иллюстрации:

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

interface Dict {
  [key: string]: number;
}

function alternatingCharacters(s: string): number {
  let countToDelete: Dict = {};

  for (let i = 0;  i < (s.length - 1); i++) {
    const current = s[i], next = s[i + 1];

    if (current === next) {
      countToDelete[current] = countToDelete[current] ? countToDelete[current] += 1 : 1;
    }
  }

  return Object.values(countToDelete).reduce((acc, item) => acc + item, 0);
}

Зачем здесь хэш-таблица?

Ошибка 4. Я должен решить сам

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

Я использую такой подход: если за 2-3 сессии по 1-2 часа не удалось сформулировать решение, то я пытаюсь понять логику эталонного решения. Выявленную логику выражаю в коде самостоятельно. Если решение задачи не представлено концептуально, а представлено только в коде без пояснений, то можно воспользоваться поиском разбора решения конкретной задачи в интернете. Иначе придется выстраивать логику решения по исходному коду, что сложнее. Задача не в том, чтобы улучшить навык работы с чужим кодом, а в том чтобы подготовиться к решению алгоритмических задач. Пример такого разбора.

Ошибка 5. Зависать на возникших вопросах

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

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

Второй метод вычисления чисел Фибоначчи представляет собой линейную итерацию. Разница в числе шагов, требуемых двумя этими методами — один пропорционален n, другой растет так же быстро, как и само Fib(n), — огромна, даже для небольших значений аргумента. Не нужно из этого делать вывод, что древовидно-рекурсивные процессы бесполезны.

Когда мы будем рассматривать процессы, работающие не с числами, а с иерархически структурированными данными, мы увидим, что древовидная рекурсия является естественным и мощным инструментом. Но даже при работе с числами древовидно-рекурсивные процессы могут быть полезны — они помогают нам понимать и проектировать программы. Например, хотя первая процедура fib и намного менее эффективна, чем вторая, зато она проще, поскольку это немногим более, чем перевод определения последовательности чисел Фибоначчи на Лисп. Чтобы сформулировать итеративный алгоритм, нам пришлось заметить, что вычисление можно перестроить в виде итерации с тремя переменными состояния.

Структура и интерпретация компьютерных программ, Харольд Абельсон, Джеральд Джей Сассман, Джулия Сассман.

Забавное наблюдение: на интервью меня просили реализовать функцию flatten не используя рекурсивную процедуру (здесь речь о синтаксисе), однако в lodash эта функция представлена рекурсивной процедурой и это не ограничивает пользователей.

Ошибка 6. Забить на качество кода

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

Пишите в том стиле, в котором привыкли, чтобы не добавлять лишней сложности. Если писали в декларативном, не стоит начинать писать в императивном стиле, и наоборот.

Ошибка 7. Проверять алгоритм на простых входных данных

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

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

Этот пример плох по нескольким причинам. Во-первых, он слишком мал; в таком примере трудно найти закономерность. Во-вторых, он не конкретен. Бинарное дерево поиска содержит значения. Что, если числа сообщат что-то полезное о том, как решать задачу? В-третьих, нарисованное дерево является особым случаем: мало того, что оно сбалансировано; это идеальное дерево, в котором каждый узел, кроме листовых, имеет два дочерних узла. Особые случаи часто вводят в заблуждение», — «Карьера программиста», Лакман Гэйл.

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

• Конкретным. В нем должны использоваться реальные числа или строки (если это относится к вашей задаче)
• Достаточно большим. Многие примеры слишком малы (вдвое меньше необходимого)
• Не относящимся к особым случаям. Будьте осторожны: очень легко непреднамеренно нарисовать особый случай. Если ваш пример в каком-то отношении может рассматриваться как частный случай (даже если вам кажется, что это ни на что не повлияет), исправьте этот недостаток.
• Постарайтесь создать самый лучший пример, который у вас получится. Если позднее окажется, что ваш пример недостаточно хорош, обязательно исправьте его.

Ошибка 8. Игнорировать допущенные ошибки

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

Заключение

По моей оценке, если ежедневно уделять подготовке 1-2 часа в день, можно подготовиться примерно за 2-4 недели. Чтобы сделать точную оценку, учитывайте, как давно вы решали подобные задачи и в каком объеме.

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

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

Благодарю за помощь в подготовке статьи Динару Рустамовну Хаматову, Петра Анатольевича Капишева, Александра Сергеевича Панфилова.