Читать книгу Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию - Гейл Макдауэлл - Страница 24

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

1. Задайте интервьюеру вопросы, чтобы снять неоднозначности.

2. Разработайте алгоритм.

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

4. В умеренном темпе начните писать программный код.

5. Проверьте написанную программу и внимательно исправьте ошибки. Остановимся на каждом шаге поподробнее.

Шаг 1. Задайте вопросы

Технические задачи более неоднозначны, чем может показаться на первый взгляд, убедитесь, что вам ясна суть вопроса. Задача может оказаться намного проще, чем казалась в начале. Некоторые интервьюеры (в частности, в Microsoft) специально проверяют, поняли ли вы задачу.

Вот несколько примеров хороших вопросов: какие типы данных используются? Какие объемы данных будут использоваться? Какие исходные предположения нужны для решения? Кто будет пользователем?

Задача: «Разработайте алгоритм сортировки списка»

Вопрос: Какой список нужно сортировать? Массив? Связный список?

Ответ: Массив.

Вопрос: Что будет в массиве? Числа? Символы? Строки?

Ответ: Числа.

Вопрос: Числа будут целыми?

Ответ: Да.

Вопрос: Что представляют собой эти числа? Это идентификаторы? Значение чего-либо?

Ответ: Это возраст клиентов.

Вопрос: Сколько будет клиентов?

Ответ: Миллион.

Теперь постановка задачи изменилась: нужно отсортировать массив из миллиона целых чисел в диапазоне от 0 до 130 (максимально возможный возраст). Как ее решить?

Достаточно создать массив из 130 элементов и посчитать количество значений для каждого возраста.

Шаг 2. Разработайте алгоритм

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

• Сколько памяти и времени понадобится для реализации этого алгоритма?

• Что произойдет, если данных будет больше, чем запланировано?

• Какие проблемы могут возникнуть в процессе работы вашего алгоритма? Например, если вы создаете модификацию бинарного дерева поиска, как ваш алгоритм повлияет на время вставки, поиска и удаления?

• Какие компромиссные решения возможны с учетом существующих ограничений? Для каких сценариев компромиссное решение будет наименее оптимальным?

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

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

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

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

Шаг 4. Код

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

• Используйте структуры данных везде, где это возможно; выберите подходящую структуру данных или разработайте собственную. Например, если вас просят определить минимальный возраст группы людей, можно создать специальную структуру данных – Person. Этим вы покажете интервьюеру, что способны создать хороший объектно-ориентированный проект.

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

Шаг 5. Проверка

Вам нужно протестировать код. В первую очередь обратите внимание на следующие моменты:

• экстремальные случаи – 0, отрицательное значение, null, максимумы, минимумы;

• ошибки пользователя – что случится, если пользователь передаст null или отрицательное значение;

• общие случаи – протестируйте типовое поведение программы.

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

Если вы находите ошибки (а они будут), не торопитесь их исправлять – попытайтесь найти причину их возникновения. Вы же не хотите стать одним из кандидатов, который, обнаруживая, что функция возвращает trueвместо false, просто инвертирует ее значение. Это устранит ошибку в конкретном случае, но неизбежно породит новые.

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