Готовясь к собеседованию, многие начинающие программисты понятия не имеют, каких вопросов ожидать от интервьеюров — будь то собеседование в стартап или технологический гигант вроде Amazon, Microsoft или Google. В статье на Hacker Noon разработчик Джавин Пол собрал вопросы, которые любят задавать на таких интервью, а также ответы на них и дополнительные ресурсы для подготовки.
Все задания, которые с большой вероятностью предложат кодеру на техническом собеседовании, можно условно разделить на две группы: общие логические задачи типа «поменять значения переменных, не используя временную переменную», а также вопросы по структурам данных и алгоритмам. Наиболее частые из последних: массивы, связные списки, строки, двоичные деревья, а также различные вопросы по алгоритмам — именно они будут рассмотрены ниже.
Но прежде чем приступить к ним, понадобится хорошо изучить эти темы, или по крайней мере освежить навыки решения задач по ним. Для этого можно пройти курс по алгоритмам и структурам данных Роберта Хорвика: часть 1 и часть 2.
Список наиболее часто задаваемых вопросов для собеседований по программированию.
1. Массивы
Массив — это важнейшая структура данных, хранящая набор элементов в непрерывном участке памяти. Это излюбленная тема интервьюеров, и много вопросов по ней можно ожидать в любом собеседовании, например на реверс, сортировку или поиск элементов массива.
Главный плюс такой структуры данных, как массив — он обеспечивает быстрый поиск сложностью О(1) при знании индексов, но добавление и удаление элементов из него происходит медленно, потому что нельзя менять размер массива после создания. Чтобы увеличить или уменьшить массив, нужно создать новый и скопировать в него все элементы из старого.
Чтобы с лёгкостью отвечать на вопросы, связанным с массивами, нужно хорошо разбираться как с самими массивами, так и с базовыми конструкторами, такие как рекурсия и основные операторы.
Вот самые частые вопросы:
- Как сортировать массив целых чисел без дополнительной памяти при помощи алгоритма быстрой сортировки? (решение)
- Как сделать поменять порядок элементов в массиве на обратный без дополнительной памяти в Java? (решение)
Эти вопросы помогут не только развить навыки решения задач, но и прокачать знания по массивам. Более сложные вопросы по теме можно найти в курсе по алгоритмам The Coding Interview Bootcamp: Algorithms + Data Structures, разработанном специально для подготовки к собеседованиям в таких технологических гигантах, как Google, Microsoft, Apple или Facebook.
Дополнительно можно поупражняться на этой подборке из 30 вопросов.
2. Связный список:
Ещё одна базовая структура данных — связный список. Как и массив, это линейная структура данных, и элементы в нём хранятся линейно, но в отличие от массива — не в непрерывных областях. Они разбросаны в памяти и соединяются с помощью узлов. Связный список — ничто иное, как список узлов, каждый из которых содержит собственно данные и ссылку на следующий узел.
Благодаря такой структуре добавлять и удалять элементы в связном списке достаточно легко, так как нужно просто изменить ссылку без необходимости создавать новый список. При этом искать элементы сложнее; поиск по односвязному списку занимает линейное время O(n). В этой статье можно подробнее прочесть о различиях между массивами и односвязными списками.
Есть разные виды связных списков: односвязный список, который позволяет передвигаться только в одну сторону: в начало или в конец; двусвязный список, дающий возможность перемещения как вперёд, так и назад; кольцевой список, который формирует зацикленную структуру.
Чтобы успешно справляться с вопросами по линейным спискам, важно хорошо знать рекурсию. Если извлечь из связного списка один узел, оставшаяся структура по-прежнему будет связным списком, и поэтому для многих задач в этой теме более простыми являются рекурсивные решения, чем итеративные.
Вопросы для собеседования:
Эти вопросы помогут развить умение решать задачи на связные списки и углубить знание этой структуры данных. Если они вызывают трудности, можно обновить свои знания структур данных и алгоритмов, пройдя курс Data Structures and Algorithms: Deep Dive Using Java.
Кроме того, можно потренироваться на этом списке из 30 вопросов.
3. Строки
Помимо массивов и связных списков, ещё одной популярной темой являются строки: вопросы по ним неизменно звучат на каждом собеседовании на должности в программировании.
Плюсом здесь можно считать то, что зная массивы, очень легко решать задачи на строки, потому что строка представляет собой массив символов. Следовательно, все методы, усвоенные при решении вопросов на массивы, можно использовать и для решения вопросов на строки.
Вот наиболее частые из них:
Способность решить эти вопросы говорит о достаточно хорошем уровне владений строками. Более продвинутые задачи можно найти в книге «Алгоритмы. Руководство по разработке» Стивена Скиены.
Ещё 20 вопросов можно найти здесь.
4. Двоичное дерево поиска
Все рассмотренные выше структуры — линейные, однако в действительности представить всю информацию таким образом невозможно, и здесь помогает такая структура данных, как дерево.
Дерево позволяет хранить данные в виде иерархии. В зависимости от способа хранения информации, существуют различные типы деревьев, например двоичное дерево, в котором каждый узел имеет не более двух дочерних элементов. Наряду с двоичным деревом поиска, это одна из самых широко распространённых древовидных структур данных, а значит, по нему обязательно попадётся множество вопросов, включая их обход, подсчёт узлов, определение глубины и сбалансированности дерева.
Секрет успешного прохождения вопросов, связанных с двоичным деревом — основательное знание теории, например, что такое размер или глубина двоичного дерева, что такое лист и узел, а также понимание основных алгоритмов обхода дерева: в прямом, симметричном и обратном порядке.
Наиболее распространённые вопросы по бинарным деревьям:
- Как вывести все узлы заданного двоичного дерева, используя симметричный обход без рекурсии? (решение)
Если пройти эти вопросы самостоятельно слишком сложно, не помешает пройти какой-нибудь качественный курс по структурам данных и алгоритмам, например From 0 to 1: Data Structures & Algorithms in Java. Вот ещё два списка книг и курсов на эту тему.
5. Прочие алгоритмы и вопросы
Помимо вопросов, касающихся структур данных, в большинстве собеседований на должность программиста задают вопросы по алгоритмам, проектированию, поразрядным операциям, а также общие логические задачи.
Очень важно хорошо подготовиться по этим темам, потому что на реальных собеседованиях по ним часто попадаются неожиданные каверзные вопросы. Если прорешать их заранее, они не вызовут проблем, а это придаст уверенности в себе при объяснении решения интервьюеру.
Свыше 189 вопросов для прохождения собеседования по программированию с ответами можно найти в книге «Карьера программиста» (6-е издание) Гэйл Лакман Макдауэлл.
Здесь можно пройти ещё 50 вопросов по программированию для прохождения собеседований по телефону; закрепить навыки можно с помощью вот этих подборок книг и курсов.
Вот ещё несколько ресурсов и подборок, которые помогут подготовиться к собеседованию:
