Без паники! Разбираемся с алгоритмами в 6 шагов

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

Без паники! Разбираемся с алгоритмами за 6 шагов

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

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

Frustrated Over It GIF by bubly - Find & Share on GIPHY

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

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

В этой статье мы рассмотрим готовый набор шагов. Он вдохновлен системой PEDAC от LaunchSchool и должен стать вашим спасательным кругом при работе с алгоритмами.

Разберем его шаг за шагом на какой-нибудь общеизвестной проблеме.

Согласно Leetcode, одна из самых распространенных задач средней сложности на интервью – алгоритм String to Integer (извлечение числа из строки). Также это вполне реальная задача разработки, в отличие от многих других (например, задачи Coin Change).

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

Шаг 1. Перефразируйте проблему своими словами

Без паники! Разбираемся с алгоритмами в 6 шагов

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

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

Уточненные условия:

  • Можно использовать нативный каст (приведение типов) JavaScript для преобразования только одного символа за один раз.
  • Для заданной строки нужно вернуть соответствующее ей числовое значение.
  • Следует игнорировать все пробелы в начале строки.
  • Число может начинаться с отрицательного или положительного знака (-/+).
  • Все символы после числа игнорируются.
  • Если перед числом стоит любой символ кроме пробела или +/-, строка является недопустимой.
  • Если строка не содержит целочисленных значений, она недопустима.
  • Для недопустимой строки следует возвращать 0.
  • Ответ не должен быть больше (2^31) или меньше -(2^31).

Уже есть идеи? Очевидно, потребуется некоторый цикл, а также много-много условий.

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

Шаг 2. Входные и выходные данные

На втором шаге работы с алгоритмами необходимо четко определиться с типами данных. Зафиксируйте их хотя бы в виде комментария.

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

Кроме того, эта запись послужит напоминанием о тех данных, с которыми вы работаете. Будет обидно провалить тесты, вернув из функции, например, строку вместо массива.

Вот типы данных для нашей задачи:

Шаг 3. Тестовые случаи

Без паники! Разбираемся с алгоритмами в 6 шагов

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

На Leetcode уже есть несколько достойных тестов:

Но эти примеры не исчерпывают всех возможностей. Вдруг номер начинается с +, или перед числом стоит сразу несколько знаков (-+-50)?

Допишем свои крайние случаи:

Шаг 4. Структуры данных

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

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

Уже сейчас можно предвидеть одну проблему – отслеживание позиции цифры в числе (десятки, сотни, тысячи). Мы не знаем длину итогового числа заранее. Имеет смысл использовать массив, где найденные целочисленные символы будут храниться до преобразования.

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

Шаг 5. Псевдокод

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

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

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

Итак, вот примерный план действий:

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

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

Ищите самое простое решение, какое можете придумать, и начинайте работать с ним.

По сути, именно здесь, на этом шаге, вы решили задачу. Остались только формальности.

Шаг 6. Код!

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

Помните, вашим приоритетом является РЕШЕНИЕ проблемы, а не ИДЕАЛЬНОЕ решение.

Вот, что могло бы получиться:

Это решение далеко не самое эффективное. Leetcode говорит, что оно превосходит только 25% других решений. Однако с ним вы пройдете большинство технических собеседований по алгоритмам.

Без паники! Разбираемся с алгоритмами в 6 шагов

План действий

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

Flexible Yoga GIF - Find & Share on GIPHY

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

Если план уже есть, практикуйте его. Не ждите реального интервью, экспериментируйте прямо сейчас, например, на Pramp или Interviewing.io.

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

Еще много полезных материалов по алгоритмам:

proglib.io

Добавить комментарий

Ваш e-mail не будет опубликован.

19 − десять =