Интервьюеры не отличаются оригинальностью, и один и тот же вопрос можно встретить на 3-5 разных собеседованиях. Но даже опытные программисты, оказываясь в стрессовой ситуации, нередко теряются и не могут найти ответ на довольно простые вопросы. Предлагаем заранее потренироваться, проверить свои знания, а заодно посмотреть на любимые вопросы интервьюеров. Не исключено, что именно на них вам предстоит отвечать на следующем собеседовании.
Структуры данных и вопросы об алгоритмах – основная часть любого собеседования для программистов вне зависимости от их специализации.
Это один из самых популярных вопросов на собеседованиях. Его используют даже в телефонных интервью, чтобы быстро определить общий уровень знаний кандидата и оценить его способность быстро решать нестандартные задачи.
Все программисты знают, что средний элемент в LinkedList несложно найти, определив длину списка, последовательно пройдя все его узлы, пока не дойдёшь до NULL в первом проходе. А затем, пройдя половину из них во втором проходе. Когда же их просят решить эту задачу за один проход, многие теряются.
Большинство задач, поставленных на собеседовании, имеет довольно простое решение, и сидя в спокойной обстановке, Вы без особого труда найдёте его сами.
В этой задаче достаточно ввести два указателя. Первый будет увеличиваться при прохождении одного узла списка, второй – при прохождении двух узлов. В момент, когда второй указатель дойдёт до конца списка (наткнётся на NULL), первый будет указывать на середину списка.
Успешно справились с этим вопросом? Получите следующий.
Исходный код решения
Если в списке есть цикл, то в какой-то момент оба указателя будут показывать на один и тот же узел списка.
Уже знаете ответ?
Можно использовать ту же схему решения. Первый указатель показывает на первый узел в связанном списке, второй на i-тый сначала. Когда второй указатель достигнет конца списка (дойдёт до NULL), первый будет указывать на i-тый элемент с конца.
Это вообще задача на логику для средней школы. Многие программисты стремятся её решить длинным перебором/сравнением элементов, но есть куда более рациональный и эстетичный способ.
- Считаем сумму всех чисел от 1 до 100 любым удобным для Вас методом.
- Считаем сумму элементов массива.
- Вычитаем первое из второго. Получаем… Правильно, получаем значение дублирующегося элемента.
- Если надо, находим номера искомых элементов в массиве.
Один из самых популярных экспресс-вопросов. Есть несколько способов выполнения этого задания, но на собеседовании лучше выбрать самый простой. Не забывайте, что Ваш собеседник далеко не всегда может оценить преимущества длинного, но красивого решения.
Неплохо подойдёт что-то типа этого:
Вопросы по сортировке данных присутствуют почти на каждом собеседовании. Они позволяют нанимателю быстро оценить уровень умений кандидата и определить, соответствует ли этот уровень нужному.
Решить это можно так:
Задавая такие вопросы, ваш собеседник, понятное дело, хочет услышать не заученное определение из учебника или получить ссылку из Википедии, а оценить ваше собственное понимание различия этих двух типов структур данных.
Стек и очередь похожи отсутствием свободного доступа ко всем элементам структуры данных. Главное же отличие заключается в том, что стек – это структура типа LIFO(Last In First Out), где свободный доступ возможен только к последнему добавленному элементу, а при его удалении методом «pop» к элементу, добавленному перед ним. Когда же в стек добавляется новый элемент, доступен становится только он.
Очередь относится к типу FIFO(First In First Out), то есть доступен в ней только первый добавленный элемент. В случае его удаления доступен второй и т.д.
Этот вопрос довольно часто на собеседовании слышат те, кто сумели быстро найти 1 дублирующийся элемент в массиве. Для решения этой задачи можно использовать HashMap. Как Вы, несомненно, знаете, HashMap хранит данные парами – ключ/значение, и создав нужное количество карточек, Вы легко найдёте все повторы и их номера.
Это один из классических вопросов для телефонного собеседования. Любой программист на него ответит, почти не задумываясь.
В обоих списках узлы связаны посредством указателей. Только в односвязном списке указатель от каждого узла ведёт исключительно к следующему, и переход возможен только к нему, то есть исключительно в одном направлении. А в двусвязном от каждого узла, кроме первого и последнего, есть возможность перейти как к следующему, так и к предыдущему узлу, то есть двигаться в обоих направлениях.
Если вдруг кто-то не знает, числа Фибоначчи – это последовательность, где каждое следующее число после 1 является суммой двух ему предшествующих. То есть ряд чисел Фибоначчи выглядит так: 1,1, 2, 3, 5, 8, 13, 21…
Решить эту задачу можно так:
Палиндром – это набор знаков (слово, число, фраза), в котором все знаки при прямом прочтении полностью совпадают со знаками при обратном прочтении.
То есть палиндромами являются числа 66, 13431, 789987 и т.д.
- Для определения значения каждого символа в числе можно использовать оператор /. Например: 66/10 вернёт 6.
- А для нахождения последнего символа в числе оператор %.
66%10=6
123%10=3 - Сравниваем полученные значения и делаем выводы.
Можно пойти другим путём и развернуть число, используя рекурсию.
А после этого дописать этот код так, чтобы он сравнивал полученные цифры.
Задача, в принципе, аналогичная предыдущей, но с существенным отличием — использовать операторы / и % не получится.
Используем рекурсию и получим простое и красивое решение:
Бинарное, или двоичное дерево поиска – это структура данных, каждый узел в которой может иметь от 1 до 2 подузлов (детей) или не иметь их вовсе.
Расположение данных в бинарном дереве имеет ряд ограничений:
- Как и во всех деревьях, любой узел бинарного дерева не может иметь более одного родителя.
- Данные в дереве распределяются в зависимости от их значений. Если значение подузла (ребёнка) меньше, чем значение узла (родителя), этот подузел становиться левым или ребёнком левого подузла, если левый подузел уже существует. Соответственно, если значение подузла больше значения узла, то он становится правым или ребёнком правого.
Применяются бинарные деревья в реализации ассоциативных массивов и множеств, например TreeMap или TreeSet, в некоторых алгоритмах вычислительной геометрии.
Этот вопрос позволяет Вам продемонстрировать свои навыки владения стандартными методами (push и pop) для работы с этой структурой данных. При выполнении этой задачи Вам нужно будет использовать массив или связный список для хранения элементов.
Написать можно, например, программу стандартного калькулятора.
Ещё один пример очень популярного вопроса. Есть много способов изменения порядка элементов в связанном списке. В следующей статье я рассчитываю подробно осветить их все.
Ждите! Или пишите свои варианты этой программы, не заглядывая в «авторскую версию»!
Не забывайте, что решая ту или иную задачу на собеседовании, желательно разъяснять каждый логический шаг интервьюеру. На стартовом собеседовании оценивают не только скорость и правильность решения поставленных задач, но и логику мышления в целом.
Именно поэтому иногда даже неполное решение сложной задачи позволит интервьюеру оценить ваши знания как достаточные для вакантной должности.
Даже если Вы опытный программист с десятками реализованных проектов портфолио, не поленитесь перед собеседованием повторить теорию. Ведь ответ «ну это работает где-то так… и вообще, за последние 3 года я ни разу не пользовался этой структурой данных» вряд ли устроит интервьюера.
Часть материалов переведена из этого источника.