Встретиться лицом к лицу с алгоритмами на техническом интервью и выжить – это реально. Держите подробный план спасения из шести шагов.
Бесконечно можно смотреть на три вещи: огонь, воду и как джун пытается решить алгоритмическую задачу.
Если вы ищете работу, будьте готовы столкнуться с алгоритмами. Многие работодатели считают их прекрасным способом выяснить образ мышления кандидата. Эти ребята уже сломали немало амбициозных планов.
[embed]https://giphy.com/gifs/bublywater-fail-neil-patrick-harris-7E8yYUNt0pQSeZNt4Y[/embed]
Как вы решаете подобные задачи? Ныряете с головой, а со всеми тонкостями разбираетесь уже по ходу дела, или у вас есть определенный план действий, анализа проблемы? Первый метод, конечно, тоже может сработать, но второй кажется более правильным.
Когда есть готовый набор шагов, которые теоретически могут решить проблему, это уже половина дела. Конечно, нельзя полностью гарантировать, что решение найдется. Но, по крайней мере, вы сможете преодолеть стресс, побороть панику и начать действовать по плану.
В этой статье мы рассмотрим готовый набор шагов. Он вдохновлен системой PEDAC от LaunchSchool и должен стать вашим спасательным кругом при работе с алгоритмами.
Разберем его шаг за шагом на какой-нибудь общеизвестной проблеме.
Согласно Leetcode, одна из самых распространенных задач средней сложности на интервью – алгоритм String to Integer (извлечение числа из строки). Также это вполне реальная задача разработки, в отличие от многих других (например, задачи Coin Change).
Кодить будем на JavaScript, но подойдет любой другой язык, ведь дело совсем не в синтаксисе, а в идее.
Шаг 1. Перефразируйте проблему своими словами
Самый важный шаг. Это ваш шанс задать интервьюеру вопросы, уточнить требования, проанализировать всю имеющуюся информацию. Перефразировав задачу, вы осознаете ее, начнете формировать модель решения.
Например, для нашей проблемы неплохо было бы уточнить, разрешено ли использовать приведение типов.
Уточненные условия:
- Можно использовать нативный каст (приведение типов) JavaScript для преобразования только одного символа за один раз.
- Для заданной строки нужно вернуть соответствующее ей числовое значение.
- Следует игнорировать все пробелы в начале строки.
- Число может начинаться с отрицательного или положительного знака
(-/+). - Все символы после числа игнорируются.
- Если перед числом стоит любой символ кроме пробела или +/-, строка является недопустимой.
- Если строка не содержит целочисленных значений, она недопустима.
- Для недопустимой строки следует возвращать
0. - Ответ не должен быть больше
(2^31)или меньше-(2^31).
Уже есть идеи? Очевидно, потребуется некоторый цикл, а также много-много условий.
Но подождите, не начинайте кодить прямо сейчас. Еще слишком рано для радикальных действий. Переходим к следующему шагу.
Шаг 2. Входные и выходные данные
На втором шаге работы с алгоритмами необходимо четко определиться с типами данных. Зафиксируйте их хотя бы в виде комментария.
Прежде всего это позволит определить, какое имя дать вашей функции. Leetcode предлагает уже готовую сигнатуру, но на реальном интервью придется делать это самостоятельно.
Кроме того, эта запись послужит напоминанием о тех данных, с которыми вы работаете. Будет обидно провалить тесты, вернув из функции, например, строку вместо массива.
Вот типы данных для нашей задачи:
Input: строка Output: 32-битное целое число со знаком Signature: myAtoi(str)
Шаг 3. Тестовые случаи
Разобравшись в типах, пора переходить к тестовым случаям. Возможно, несколько примеров предоставит сам интервьюер. Обязательно убедитесь, что они покрывают все возможные ситуации, при необходимости добавьте собственные. Создать рабочее решение, но не учесть какую-нибудь мелочь – невероятно обидно.
На Leetcode уже есть несколько достойных тестов:
Input: "4193 with words" Output: 4193 Input: "words and 987" Output: 0 Input: "-91283472332" Output: -2147483648
Но эти примеры не исчерпывают всех возможностей. Вдруг номер начинается с +, или перед числом стоит сразу несколько знаков (-+-50)?
Допишем свои крайние случаи:
Input: "+50.890" Output: 50 Input: " -+100" Output: 0 Input: " !another invalid -10" Output: 0
Шаг 4. Структуры данных
Работа с алгоритмами практически всегда предполагает использование некоторых структур для отслеживания данных. Выбор конкретных структур может сильно повлиять на реализацию решения.
Из описания задачи ясно, что дело придется иметь со строками, а также целыми числами. Потребуются ли для преобразования еще какие-нибудь структуры данных?
Уже сейчас можно предвидеть одну проблему – отслеживание позиции цифры в числе (десятки, сотни, тысячи). Мы не знаем длину итогового числа заранее. Имеет смысл использовать массив, где найденные целочисленные символы будут храниться до преобразования.
Решить эту проблему можно более эффективно (если есть идеи, делитесь в комментариях), однако вы должны понять одну вещь. Лучше создать наивное, но рабочее решение прямо сейчас, чем искать идеальный алгоритм и завалить интервью. В конце концов, оптимизацию с рефакторингом никто не отменял.
Шаг 5. Псевдокод
Теперь все, что вы придумали на предыдущих шагах, необходимо изложить в виде псевдокода.
Это очень полезный прием при работе с алгоритмами. Во-первых, вы сразу увидите слабые места своего решения. Во-вторых, интервьюер поймет, как вы решаете проблемы.
Даже если вы не успеете реализовать вашу задумку непосредственно на языке программирования, этот псевдокод покажет, что вы двигались в верном направлении.
Итак, вот примерный план действий:
- Начать с нулевой позиции в строке;
- До тех пор пока символ на текущей позиции – пробел,
- увеличивать позицию;
- Проверить, является ли следующий символ допустимым;
- если да, вернуть 0;
- Проверить, является ли следующий символ положительным или отрицательным знаком;
- если это отрицательный знак, пометить итоговое число как отрицательное;
- увеличить позицию;
- Запустить цикл по символам строки, начиная с текущей позиции;
- если текущий символ целочисленный,
- добавить его в начало массива,
- увеличить индекс;
- если нет, выйти из цикла.
- Запустить цикл по массиву собранных символов;
- преобразовать строки в числа;
- умножить каждое число на его порядок (10^index), добавить возвращенное значение к итоговому результату;
- Если число помечено как отрицательное, умножить его на -1;
- Если результат меньше минимально допустимого, переназначить его на минимально допустимое значение;
- Или на максимально допустимое, если результат больше его;
- Вернуть результат.
Это самый трудоемкий шаг, ведь именно здесь создается алгоритм.
Проверьте себя еще раз. Соответствует ли ваше решение заявленным требованиям, соблюдает ли форматы данных, проходит ли тесты, включая крайние случаи.
Ищите самое простое решение, какое можете придумать, и начинайте работать с ним.
По сути, именно здесь, на этом шаге, вы решили задачу. Остались только формальности.
Шаг 6. Код!
Если интервьюер выделил вам 45 минут на решение задачи с алгоритмами, потратьте полчаса на ее обдумывание и только 15 минут на сам код, для которого уже все будет готово.
Помните, вашим приоритетом является РЕШЕНИЕ проблемы, а не ИДЕАЛЬНОЕ решение.
Вот, что могло бы получиться:
const WHITESPACE = ' ';
const NEGATIVE_SIGN = '-';
const POSITIVE_SIGN = '+';
const INTEGER_REGEX = /[0-9]/;
const MAX_INTEGER = (2**31) - 1;
const MIN_INTEGER = -(2**31);
function myAtoi(str) {
const strIntArray = [];
let isNegative = false;
let resultVal = 0;
let idx = 0;
while (str[idx] === WHITESPACE) {
idx++;
}
if (invalidChar(str[idx])) {
return 0;
}
if (isSign(str[idx])) {
isNegative = str[idx] === NEGATIVE_SIGN;
idx++;
}
while (isInteger(str[idx])) {
strIntArray.unshift(str[idx]);
idx++;
}
for (let i = 0; i < strIntArray.length; i++) {
let num = Number(strIntArray[i]);
num *= 10**i;
resultVal += num;
}
if (isNegative) {
resultVal = -resultVal;
}
// If result value is less than min, reassign to min
resultVal = Math.max(resultVal, MIN_INTEGER);
// If result value is greater than max, reassign to max.
resultVal = Math.min(resultVal, MAX_INTEGER);
return resultVal;
}
function invalidChar(char) {
return !isInteger(char) && !isSign(char);
}
function isSign(char) {
return char === POSITIVE_SIGN || char === NEGATIVE_SIGN
}
function isInteger(char) {
return INTEGER_REGEX.test(char);
}
Это решение далеко не самое эффективное. Leetcode говорит, что оно превосходит только 25% других решений. Однако с ним вы пройдете большинство технических собеседований по алгоритмам.
План действий
Составление подобного плана и следование ему позволяет вам системно подходить к решению любой задачи – на интервью, в работе, даже в жизни. Заручившись такой поддержкой, вы можете сдерживать свою панику и сосредоточиться на цели, а не на эмоциях.
[embed]https://giphy.com/gifs/CQDmX4bCoJTNK[/embed]
Если у вас еще нет собственного плана, создайте его. Вы можете использовать для вдохновения PEDAC или придумать все с нуля.
Если план уже есть, практикуйте его. Не ждите реального интервью, экспериментируйте прямо сейчас, например, на Pramp или Interviewing.io.
Комментарии