50 вопросов и ответов по программированию для подготовки к техническому интервью

Готовясь к собеседованию, многие начинающие программисты понятия не имеют, каких вопросов ожидать от интервьеюров — будь то собеседование в стартап или технологический гигант вроде Amazon, Microsoft или Google. В статье на Hacker Noon разработчик Джавин Пол собрал вопросы, которые любят задавать на таких интервью, а также ответы на них и дополнительные ресурсы для подготовки.

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

Но прежде чем приступить к ним, понадобится хорошо изучить эти темы, или по крайней мере освежить навыки решения задач по ним. Для этого можно пройти курс по алгоритмам и структурам данных Роберта Хорвика: часть 1 и часть 2.

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

1. Массивы

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

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

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

Вот самые частые вопросы:

1. Как найти пропущенное число в заданном массиве целых чисел от 1 до 100? (решение)
2. Как найти повторяющееся число в заданном массиве целых чисел? (решение)
3. Как найти наибольшее и наименьшее число в неотсортированном массиве? (решение)
4. Как найти все пары в массиве целых чисел, сумма которых равна заданному числу? (решение)
5. Как найти повторяющиеся числа в массиве, если их несколько? (решение)
6. Как удалить повторяющиеся элементы из заданного массива в Java? (решение)
7. Как сортировать массив целых чисел без дополнительной памяти при помощи алгоритма быстрой сортировки? (решение)
8. Как удалить повторяющиеся элементы из массива без дополнительной памяти? (решение)
9. Как сделать поменять порядок элементов в массиве на обратный без дополнительной памяти в Java? (решение)
10. Как удалить повторяющиеся элементы из массива без использования коллекций? (решение)

Эти вопросы помогут не только развить навыки решения задач, но и прокачать знания по массивам. Более сложные вопросы по теме можно найти в курсе по алгоритмам The Coding Interview Bootcamp: Algorithms + Data Structures, разработанном специально для подготовки к собеседованиям в таких технологических гигантах, как Google, Microsoft, Apple или Facebook.

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

Записаться на курс Java Programming and Software Engineering Fundamentals от Coursera

2. Связный список:

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

Благодаря такой структуре добавлять и удалять элементы в связном списке достаточно легко, так как нужно просто изменить ссылку без необходимости создавать новый список. При этом искать элементы сложнее; поиск по односвязному списку занимает линейное время O (n). В этой статье можно подробнее прочесть о различиях между массивами и односвязными списками.

Есть разные виды связных списков: односвязный список, который позволяет передвигаться только в одну сторону: в начало или в конец; двусвязный список, дающий возможность перемещения как вперёд, так и назад; кольцевой список, который формирует зацикленную структуру.

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

Вопросы для собеседования:

1. Как найти центральный элемент в односвязном списке за один проход? (решение)
2. Как проверить заданный связный список на цикличность? Как найти исходный узел цикла? (решение)
3. Как сделать реверс связного списка? (решение)
4. Как сделать реверс односвязного списка без рекурсии? (решение)
5. Как удалить повторяющиеся узлы из несортированного связного списка? (решение)
6. Как найти длину односвязного списка? (решение)
7. Как найти 3-й узел с конца в односвязном списке? (решение)
8. Как найти сумму двух связных списков, используя стек? (решение)

Эти вопросы помогут развить умение решать задачи на связные списки и углубить знание этой структуры данных. Если они вызывают трудности, можно обновить свои знания структур данных и алгоритмов, пройдя курс Data Structures and Algorithms: Deep Dive Using Java.

Кроме того, можно потренироваться на этом списке из 30 вопросов.

Записаться на курс Профессия Java-разработчик от Skillfactory

3. Строки

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

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

Вот наиболее частые из них:

1. Как вывести повторяющиеся символы из строки? (решение)
2. Как проверить, являются ли две строки анаграммами? (решение)
3. Как вывести первый неповторяющийся символ из строки? (решение)
4. Как сделать реверс заданной строки с использованием рекурсии? (решение)
5. Как проверить, что строка состоит только из цифр? (решение)
6. Как найти повторяющийся символ в строке? (решение)
7. Как посчитать количество гласных и согласных звуков в заданной строке? (решение)
8. Как посчитать, сколько раз в строке встречается заданный символ? (решение)
9. Как найти все возможные перестановки элементов строки? (решение)
10. Как сделать реверс слов в заданном предложении, не используя классы-коллекции? (решение)
11. Как проверить, является ли одна строка перестановкой другой? (решение)
12. Как проверить, является ли заданная строка палиндромом? (решение)

Способность решить эти вопросы говорит о достаточно хорошем уровне владений строками. Более продвинутые задачи можно найти в книге «Алгоритмы. Руководство по разработке» Стивена Скиены.

Ещё 20 вопросов можно найти здесь.

4. Двоичное дерево поиска

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

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

Секрет успешного прохождения вопросов, связанных с двоичным деревом — основательное знание теории, например, что такое размер или глубина двоичного дерева, что такое лист и узел, а также понимание основных алгоритмов обхода дерева: в прямом, симметричном и обратном порядке.

Наиболее распространённые вопросы по бинарным деревьям:

1. Как реализуется двоичное дерево поиска? (решение)
2. Как выполнить обход в прямом порядке в заданном двоичном дереве? (решение)
3. Как обойти заданное двоичное дерево в прямом порядке без рекурсии? (решение)
4. Как выполнить симметричный обход в заданном двоичном дереве? (решение)
5. Как вывести все узлы заданного двоичного дерева, используя симметричный обход без рекурсии? (решение)
6. Как применяется алгоритм обхода в обратном порядке? (решение)
7. Как обойти заданное двоичное дерево в обратном порядке без рекурсии? (решение)
8. Как вывести на печать все листья двоичного дерева поиска? (решение)
9. Как посчитать количество листьев в заданном двоичном дереве? (решение)
10. Как выполнить двоичный поиск в заданном массиве? (решение)

Если пройти эти вопросы самостоятельно слишком сложно, не помешает пройти какой-нибудь качественный курс по структурам данных и алгоритмам, например From 0 to 1: Data Structures & Algorithms in Java. Вот ещё два списка книг и курсов на эту тему.

5. Прочие алгоритмы и вопросы

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

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

1. Как реализуется сортировка пузырьком? (решение)
2. Как реализуется итеративная быстрая сортировка? (решение)
3. Как реализуется сортировка вставками? (решение)
4. Как реализуется сортировка слиянием? (решение)
5. Как реализуется блочная сортировка? (решение)
6. Как реализуется сортировка подсчётом? (решение)
7. Как реализуется поразрядная сортировка? (решение)
8. Как поменять местами значения двух переменных без использования третьей? (решение)
9. Как определить, пересекаются ли два прямоугольника? (решение)
10. Как спроектировать торговый автомат? (решение)

Свыше 189 вопросов для прохождения собеседования по программированию с ответами можно найти в книге «Карьера программиста» (6-е издание) Гэйл Лакман Макдауэлл.

Здесь можно пройти ещё 50 вопросов по программированию для прохождения собеседований по телефону; закрепить навыки можно с помощью вот этих подборок книг и курсов.

Вот ещё несколько ресурсов и подборок, которые помогут подготовиться к собеседованию:

• 10 книг для подготовки к техническому собеседованию по программированию/разработке
• 10 книг по алгоритмам, которые должен прочитать каждый программист
• 5 лучших книг по структурам данных и алгоритмам для Java-разработчиков
• Онлайн-курс по анализу структур данных и алгоритмов с подготовкой к собеседованию