Как проходить DSA-собеседования. Объяснение для людей, ненавидящих это дело

Перевод статьи «Get Hired: Data Structure and Algorithm Interviews For People Who Hate Them».

Скажу честно: я сама ненавижу собеседования, где проверяют знания структур данных и алгоритмов (data structure and algorithm, DSA). В ходе последнего поиска работы я прошла больше 30 таких собеседований — в качестве промежуточной стадии между общением с рекрутером по телефону и собеседованием «вживую». И каждый раз эта процедура вызывает рвотный рефлекс.

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

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

В этом процессе мне помогло одно обстоятельство: мой опыт нахождения по другую сторону стола. Работая в Salesforce, я сама проводила DSA-собеседования. Пожалуй, их у меня было 15-20 за последние 3 года.

Теперь я хочу поделиться с вами тем, что узнала при проведении и прохождении собеседований. Безусловно, я не смогу изложить в статье всю тему структур данных и алгоритмов, так что и пытаться не буду. Я хочу провести вас через процесс DSA-собеседования, осветив его как со стороны кандидата, так и со стороны интервьюера. А затем я расскажу, что помогло мне в учебе, и поделюсь ресурсами. Также я выскажу свои соображения относительно всего этого процесса и поведаю о «красных флагах», сигнализирующих о больших проблемах в компании.

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

Формат собеседования

Прежде всего, давайте оговорим, что я подразумеваю под выражением «DSA-собеседование». Я имею в виду формат собеседования, когда кандидату предлагают решить задачу по программированию, а для решения требуется использовать структуры данных (например, массивы, деревья) и/или распространенные алгоритмы (сортировки или поиска). Например, для решения задачи вам может понадобиться повернуть массив или вывести двоичное дерево в восходящем порядке.

Задачи для таких собеседований самодостаточны, это не часть какого-то проекта. Их цель — проверить ваше умение решать проблемы (т. е., проверяется наличие этого отдельного навыка).

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

DSA-собеседования могут проводиться в телефонном режиме — тогда вы печатаете код в браузерной IDE, разделяемой с интервьюером. Или же это может быть личное собеседование, где вы решаете задачу на белой доске.

На таких интервью вам обычно выдают 2-3 задания, на решение каждого отводится 20-30 минут.

Зачем вообще проводят DSA-собеседования? Во многих компаниях уверены, что разработчик, хорошо знающий «основы», будет хорош на любой должности. Одно из преимуществ этих собеседований — ваш результат не будет зависеть от команды, к которой вы присоединитесь. Многие крупные компании не подбирают кандидатов под конкретную команду до самых последних стадий собеседований. А на более ранних стадиях проверяются навыки, которые пригодятся кандидату при работе в любой команде.

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

Анатомия собеседования

Сторона интервьюера

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

Задача. Дан несортированный массив целых чисел. Найдите все уникальные пары чисел, которые при сложении дают значение k.

Почему я выбрала такое задание? Мне нравится, что здесь возможны несколько вариантов решения, с разной временной сложностью. Есть брутфорс-решение (O(N²)), решение с сортировкой (O(NlogN)), хэш-таблица (O(N)). Таким образом, кандидат может справиться с задачей, даже если его решение не будет лучшим из возможных. Мне также нравится, что оптимальное решение подразумевает использование хэш-таблицы, а этой структурой данный мы пользуемся ежедневно.

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

Шаги наилучшего решения будут следующими:

• Инициализируем таблицу целых чисел и список пар целых чисел.
• Перебираем массив input-а и помещаем каждое число в таблицу в качестве ключа, а число вхождений — в качестве значения. Каждый раз при нахождении числа в массиве мы увеличиваем значение количества вхождений в таблице.
• Перебираем таблицу. Для каждого значения v проверяем, содержит ли таблица число k -v. Если да, помещаем эту пару чисел (v, k-v) в список пар и удаляем оба значения из таблицы. Особый случай: если k = 2v, проверяем, что в таблице есть как минимум два экземпляра v (например, map.get(v) >= 2).
• Возвращаем список пар.

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

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

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

Сторона кандидата

Теперь давайте посмотрим, что должен делать кандидат.

После того как я прочитаю вам задачу, вы должны на минутку притормозить и собраться с мыслями. Не чувствуйте себя обязанным выдать ответ сразу. Когда будете готовы, задайте мне уточняющие вопросы. Например, по этой задаче можно спросить, насколько велик массив, а также — считать ли пары (4,6) и (6,4) разными или одной парой. Вы должны убедиться, что точно уловили суть задачи и знаете, что вас просят сделать.

Далее, еще до того как подумать о каком-либо коде, пройдитесь по вариантам input-а. Если это телефонное собеседование, напечатайте несколько примеров, а если пользуетесь белой доской, — запишите их. Предположим, для решения нашей задачи вы выбрали массив [1, 2, 3, 0, 1] и значение k = 2. Уникальными парами, в сумме дающими 2, будут (1, 1) и (2, 0). Разбирая этот пример, вы увидите, что вам нужен способ сопоставлять комбинации чисел в массиве.

Теперь можно перейти к брутфорс-решению. Это вложенный цикл for, где внешний цикл выбирает элемент массива, а внутренний перебирает остаток чисел в массиве в поисках соответствия. Я бы посоветовала вначале проговорить брутфорс-решение интервьюеру. Оно должно стать отправной точкой для нахождения верного решения и одновременно — точкой, до которой вы сможете откатиться, если другие решения не сработают. Ваш интервьюер может попросить вас обдумать другие варианты, прежде чем писать что-либо.

Далее вы оптимизируете свое решение. Это ключ к прохождению DSA-собеседований. Спросите себя, могут ли вам помочь какие-нибудь структуры данных. «Могу ли я использовать массив, набор, список, таблицу, стек, очередь, дерево, граф?» Затем подумайте, могут ли вам помочь какие-нибудь распространенные алгоритмы. «Поможет ли здесь сортировка, поиск, использование рекурсии или динамическое программирование?» Чаще всего ответ будет в каком-то из этих двух списков.

При поиске оптимального решения для этой задачи главное — оптимизировать время, необходимое для определения, есть ли в массиве совпадение с заданным числом. Хэш-таблицы имеют время поиска O(1); это подсказывает нам, что они могут помочь в решении задачи.

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

Но просто записать свое решение недостаточно. Вы должны проверить, является ли оно рабочим. Я бы посоветовала взять несколько негативных тестовых случаев (нулевой input, пустой массив в качестве input) и несколько позитивных (input — [1, 1], [1, 2, 3], [-1, 1]). Таким образом вы можете найти баги в своем решении до того, как это сделает интервьюер.

Теперь у вас есть хорошо протестированное, производительное решение. Прекрасно! Интервьюер может задать вам пару дополнительных вопросов, а затем вы перейдете к следующей задаче.

Красные флаги

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

1. Интервьюер не вовлечен в процесс.

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

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

2. Интервьюер относится к вам снисходительно.

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

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

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

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

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

Подготовка к собеседованию

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

Мой главный совет всем, кто готовится к DSA-собеседованию: практикуйтесь в написании кода не в IDE. Канонический совет — приобретите книгу Гейла Лакмана Макдауэлла «Cracking the Coding Interview» и пишите решения ручкой на бумаге. Ниже вы найдете также несколько веб-ресурсов, где можно найти задачи на программирование.

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

Для меня самое сложное в прохождении таких собеседований то, что из головы внезапно выпадают все знания. Здесь мне помогает наличие заготовленных вопросов со списками: «Могу ли я использовать массив, набор, список, таблицу, стек, очередь, дерево, граф?», «Поможет ли здесь сортировка, поиск, использование рекурсии или динамическое программирование?». Весьма вероятно, что хоть что-нибудь из этих списков пригодится.

Вот несколько ресурсов, которые я использовала для подготовки к DSA-собеседованиям:

• js.checkio.org — задачи на программирование (JavaScript), уровень — от абсолютного новичка до эксперта.
• CodingBat — задачи на программирование (Java и Python), уровень — от начального до среднего.
• HackerRank — задачи для написания кода на многих языках программирования, уровень — от среднего и до эксперта.
• LeetCode — задачи для написания кода на многих языках программирования, уровень — от среднего и до эксперта.

Некоторые компании даже проводят свои DSA-собеседования на HackerRank и LeetCode, так что я советую познакомиться с этими платформами поближе.

Итоги

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

[customscript]techrocks_custom_after_post_html[/customscript]

[customscript]techrocks_custom_script[/customscript]