Вопросы с собеседования. Алгоритмы и структуры данных.

19,5K

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

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

Что же следует знать про структуры данных и алгоритмы?

Сложность алгоритма

Сложность определяется как O(f(n)) («О большое от …») где f(n) — функция сложности. Это обозначение говорит о том, что при увеличении входных параметров (n) время работы алгоритма будет увеличиваться не быстрее чем f(n).

Так как это лишь оценочное представление, то не важны возможные константы, не зависящие от входных параметров т.е. O(n) = O(2*n) = O(n+10) и т.д. При этом возможна ситуация, когда сложность равна O(1). Это значит, что алгоритм работает константное время вне зависимости от размера входных данных. Рассмотрим это все на примерах.

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

Снова рассмотрим массив длиной N. Теперь мы хотим его отсортировать самым простым способом — пузырьком. Этот алгоритм подразумевает, что последовательно, один за одним, самые большие числа «выталкиваются» наверх, как пузырьки в воде. Для этого необходимо N раз пройтись по всем элементам, попарно их сравнить со следующим и поменять местами если один больше другого. Примерное количество операций при этом N*N = N^2. Сложность такого алгоритма квадратичная и выражается как O(N^2).

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

Сложности вставки, поиска и удаления в ArrayList, LinkedList, HasMap

Сложность операций над разными коллекциями зависит от того, какие структуры данных лежат в их основе. Разные действия, такие как добавление, поиск и удаление элемента могут занимать разное время для одного и того же типа коллекции.

• ArrayList основан на массиве.
  • Сложность получение элемента по индексу O(1).
  • Сложность вставки O(1) если не нужно пересоздавать массив (когда закончилось отведенное место для старого). В случае пересоздания сложность становится O(n).
  • Сложность вставки по определенному индексу O(n), т.к. приводит к смещению всех элементов после нового элемента.
  • Сложность удаления элемента O(n), т.к. сначала необходимо будет его найти и потом передвинуть остальные элементы.
• LinkedList основан на связанном списке. Это такой вид структуры, когда каждый элемент содержит ссылку на следующий.
  • Сложность получение элемента по индексу O(n), т.к. у нас нет возможности перепрыгнуть на определенный элемент. Для того, чтобы добраться до искомой позиции придется пройтись по всем элементам до него.
  • Сложность вставки в конец или начало O(1). Ничего не надо передвигать, достаточно лишь поменять указатели.
  • Сложность вставки по определенному индексу в среднем O(n).
  • Сложность удаления элемента O(1), т.к. единственное что потребуется — переписать ссылку на следующий элемент.
  • Сложность удаления элемента по индексу O(n), т.к. сначала придется его найти.
• HashMap, HashSet
  • Сложность всех операций над данными коллекциями будет O(1) в случае нормального распределения функции хэширования. Если же хэш от элемента будет одинаков для всех элементов, то коллекция выродится до случая связанного списка.

Алгоритмы сортировки коллекций

Алгоритмы сортировки — отдельная большая тема. Описание и сложность сортировки пузырьком можно найти в секции сложность алгоритмов. Тут же я приведу ряд наиболее популярных других полезных реализаций:

• Сортировка пузырьков. Сложность O(n^2).
• Быстрая сортировка (Quick sort).  Его сложность зависит от типа входных данных. В среднем она равна O(n*Logn), в худшем падает до O(n^2).
• Сортировка слиянием (Merge sort). Сложность O(n*log(n)).

Логические задачи по алгоритмам

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

Бактерии в стакане или лилии в пруду

Существуют несколько сеттингов для данной задачи — пруд, в котором растут новые лилии или же стакан, в котором размножаются бактерии. Рассмотрим задачу в контексте стакана. В нем каждую секунду каждая бактерия делится пополам. Половина стакана заполняется за 30 секунд. Вопрос: за сколько бактерии заполнят весь стакан?

Высыхающий арбуз

Арбуз на 99% состоит из воды и весит 10кг. Светит солнце, жарко и арбуз теряет влагу. Теперь арбуз состоит из воды на 98%. Сколько теперь весит арбуз?

Поиск цикла в связанном списке

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

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

Если вы хотите еще глубже погрузиться в тему и изучить все на примерах, можно воспользоваться курсом Geekbrains.

Данный пул вопросов будет пополнятся со временем, так что подписывайся на мой канал в Телеграме чтобы ничего не пропустить!