Вопросы для интервью по алгоритмам

Опыт интервью и руководство — часть 6

Вопросы для интервью по алгоритмам

Подготовка к интервью по алгоритмам разработки программного обеспечения

Здравствуйте, друзья😊! Сегодня я поделюсь с вами вопросами для собеседования, связанными с алгоритмами в рамках моей серии подготовки к собеседованию для инженеров-программистов. Это шестая часть серии. Если вы пропустили предыдущие сессии, вы можете прочитать первую часть здесь, ООП и Java, База данных, Структуры данных,и Параллельное программирование. Давайте без промедления перейдем к сегодняшней теме Алгоритмы.

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

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

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

1. Что подразумевается под алгоритмами сортировки?

• Алгоритм сортировки переупорядочивает элементы массива или списка на основе оператора сравнения элементов. В соответствующей структуре данных оператор сравнения используется для определения нового порядка элементов.

2. Какие алгоритмы сортировки вы знаете?

• "Сортировка слиянием"
• Сортировка вставками
• Пузырьковая сортировка
• Быстрая сортировка
• Сортировка кучей
• Сортировка подсчетом

3. Что подразумевается под стабильным и нестабильным алгоритмом сортировки?

• Стабильность алгоритма сортировки определяется тем, как он обрабатывает одинаковые (или повторяющиеся) элементы. В отличие от устойчивых алгоритмов сортировки нестабильные алгоритмы сортировки не сохраняют относительный порядок одинаковых элементов. Другими словами, стабильная сортировка сохраняет относительные положения двух равных компонентов.
• Это очень заметно при сортировке объектов.
• Как вы можете видеть на изображении ниже, A — это входная числовая последовательность, а B — выходная последовательность алгоритма сортировки. Вы можете четко наблюдать разницу между стабильной и нестабильной сортировкой.

• Пузырьковая сортировка, Сортировка вставками и Сортировка слиянием — естественно стабильные алгоритмы сортировки.

4. Что подразумевается под алгоритмом сортировки на месте?

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

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

• Лучший вариант. В лучшем случае функция выполняет минимально возможное количество шагов для n-элементных входных данных. С точки зрения алгоритмов сортировки это можно рассматривать как данный массив для сортировки уже в отсортированном виде. Таким образом, шаги, необходимые для получения результата, очень минимальны. Рассмотрим приведенный ниже входной массив для алгоритма сортировки [1,2,3,4,5,6,7]. Он уже отсортирован. Таким образом, для выполнения сортировки потребуется лучший случай временной сложности.
• Наихудший случай. Функция, которая выполняет наибольшее количество шагов для входных данных размера n, является наихудшим случаем. С точки зрения алгоритмов сортировки это можно рассматривать как данный массив для сортировки уже в обратно отсортированном виде. Таким образом, шаги, необходимые для получения результата, очень высоки. Давайте рассмотрим приведенный ниже входной массив для алгоритма сортировки [7,6,5,4,3,2,1]. Он отсортирован в обратном порядке. Так что на сортировку уйдёт больше времени. Это худший случай временной сложности.
• Средний случай. Средний случай — это функция, которая выполняет среднее количество шагов для n элементов входных данных. Это можно рассматривать как данный массив для сортировки, который не отсортирован ни в какой форме (по возрастанию или по убыванию). Таким образом, шаги, необходимые для получения результата, являются средними. Давайте рассмотрим приведенный ниже входной массив для алгоритма сортировки [4,6,2,1,3,5,7]. Он не отсортирован ни в каком порядке. Это Средний Случай сложности времени. Это наиболее часто встречающийся случай для любого алгоритма сортировки. У лучших алгоритмов сортировки должна быть лучшая временная сложность среднего случая.

7. Объясните, как работает сортировка вставками?

• Сортировка вставками — один из основных алгоритмов сортировки.
• Алгоритм очень похож на заказ карт в карточных играх. Алгоритм сортировки на месте и алгоритм стабильной сортировки.

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

• Хорошо работает в почти отсортированных массивах. Эффективен для сортировки небольшого массива элементов.

Временная сложность в лучшем случае: O(n)

Средняя сложность рассмотрения дела: O(n*n)

Сложность в наихудшем случае: O(n*n)

Сложность пространства: O(1), дополнительное пространство не требуется для хранения элементов при выполнении сортировки.

8. Объясните, как работает пузырьковая сортировка?

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

• Это требует большего сравнения и замены элементов. Не лучший выбор для сортировки длинных массивов. Его нельзя использовать в ситуациях, когда замена элементов является очень затратной операцией.
• Неэффективный алгоритм сортировки во многих ситуациях.

Временная сложность в лучшем случае: O(n)

Средняя сложность рассмотрения дела: O(n*n)

Временная сложность в худшем случае: O(n*n)

Пространственная сложность: O(1), дополнительное пространство не требуется для хранения элементов при выполнении сортировки.

6. Объясните, как работает сортировка слиянием?

• Алгоритм сортировки слиянием — это алгоритм типа разделяй и властвуй.
• Он многократно сортирует каждый небольшой фрагмент данного массива, чтобы отсортировать данный большой массив элементов.
• После того, как каждый небольшой фрагмент отсортирован, они правильно объединяются для окончательного решения в заданном массиве. Ниже вы можете увидеть анимацию сортировки слиянием. Все точки данных сортируются как небольшие фрагменты и позже объединяются. Код алгоритма сортировки слиянием можно найти здесь. Сортировка слиянием Может быть реализована как рекурсивный, так и итеративный подход.

• Вы также можете просмотреть изображение ниже для дальнейшего разъяснения алгоритма. Исходный массив [6,5,12,10,9,1]разделяется на два небольших массива[6,5,12]и [10 ,9,1]. Затем оба массива также дополнительно делятся на несколько еще меньших массивов. Это продолжается до тех пор, пока весь массив не будет разделен на каждый элемент. Затем каждый элемент сравнивается и объединяется в массив, как и раньше. Изображение правильно прояснит ваши сомнения.

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

Временная сложность в лучшем случае: O(nlogn)

Средняя сложность рассмотрения дела: O(nlogn)

Временная сложность в наихудшем случае: O(nlogn)

Сложность пространства: O(n), требуется дополнительное пространство для хранения элементов при выполнении сортировки.

9. Объясните, как работает быстрая сортировка?

• Алгоритм быстрой сортировки также является алгоритмом типа разделяй и властвуй.
• В быстрой сортировке сортировка выполняется в самом разделе разделить, но когда мы рассматриваем сортировку слиянием, основная работа по сортировке выполняется на этапе завоевать алгоритма.
• При быстрой сортировке он выбирает опорный элемент и разбивает указанный массив вокруг этого опорного элемента. QuickSort поставляется в различных вариантах, каждый из которых выбирает поворот уникальным способом. В качестве опорного элемента выбирается первый, последний, медианный или случайный элемент.
• Разбиение на разделы — самая важная операция в quickSort(). При заданном массиве и опорном элементе x цель разбиения состоит в том, чтобы поместить x в правильное положение в отсортированном массиве, при этом все меньшие элементы (меньше x) помещаются перед x, а все более крупные элементы (больше x) помещаются после x. . Все это должно быть выполнено линейным способом.
• Анимация ниже научит точному процессу сортировки в Quick Sort.

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

Временная сложность в лучшем случае: O(nlogn)

Средняя сложность рассмотрения дела: O(nlogn)

Сложность в наихудшем случае: O(n*n)

Сложность пространства: O(1), дополнительное пространство не требуется для хранения элементов при выполнении сортировки.

10. Объясните, как работает сортировка выбором?

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

• Количество свопов в сортировке выбором всегда меньше, чем количество элементов, необходимых для сортировки, что делает его удобным, когда запись в память требует больших затрат.

Временная сложность в лучшем случае: O(n*n)

Средняя сложность рассмотрения дела: O(n*n)

Сложность в наихудшем случае: O(n*n)

Сложность пространства: O(1), дополнительное пространство не требуется для хранения элементов при выполнении сортировки.

11. Каковы преимущества и недостатки пузырьковой сортировки?

• Преимущество: просто для понимания. Лучший алгоритм для лучших случаев.
• Недостаток: средний случай, наихудший случай – высокая временная сложность.

12. по каким критериям можно сравнивать алгоритмы сортировки?

• На основе количества сравнений
• На основе рекурсии или нерекурсии
• На основе стабильности.
• В зависимости от потребности в дополнительном пространстве.
• На основе количества свопов

13. Что такое алгоритм сортировки подсчетом?

• Алгоритм сортировки целых чисел и алгоритм несравнительной сортировки.
• Сортировка подсчетом — это тип алгоритма сортировки, который можно использовать для сортировки значений в известном диапазоне.
• Он может сортировать значения за время O(n). Вы можете пойти сюда для лучшего понимания. Нет более эффективного ресурса, чем указанное выше место для сортировки подсчетом.

14. В чем разница между алгоритмами сравнительной и несравнительной сортировки?

• Как следует из названия, алгоритмы сортировки на основе сравнения, такие как быстрая сортировка, требуют сравнения элементов для сортировки, в то время как алгоритмы сортировки без сравнения, такие как сортировка подсчетом, позволяют сортировать элементы, не сравнивая их. Удивлен?

Алгоритмы поиска

1. Что такое линейный поиск и как он работает?

• Самый простой способ поиска в наборе данных — это линейный поиск.
• Каждая часть данных просматривается одна за другой, с начала сбора данных до тех пор, пока не будет найдено совпадение.
• Поиск заканчивается, как только объект найден. Если вы не можете найти совпадение, Object отсутствует в коллекции.
• Нет необходимости в отсортированной коллекции для выполнения поиска.
• В приведенном ниже примере мы выполняем поиск, чтобы найти число 20. Изображение очень легко объясняет процедуру.

• Код Python для линейного поиска приведен ниже. это само собой объяснимо.

def linear_search(arr, length, k):
    for j in range(0, length):
       if (arr[j] == k):
          return j
    return -1

Временная сложность в наихудшем случае: O(n)

2. Что такое бинарный поиск и как он работает?

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

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

• После всего лишь одного сравнения мы фактически игнорируем половину элементов.
• Пример одного из примеров поиска показан ниже. Картина объяснима сама собой. Вы можете комментировать с любыми уточнениями.

def bSearch(arr, l, r, x):
    if r >= l:
        mid = l + (r - l) // 2
        if arr[mid] == x:
          return mid
       elif arr[mid] > x:
          return bSearch(arr, l, mid-1, x)
       else:
          return bSearch(arr, mid + 1, r, x)
   else:
       return -1

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

Временная сложность в наихудшем случае: O(log n)

3. Как использовать двоичный поиск, чтобы найти число в массиве, в котором содержится миллион чисел?

• Поскольку массив отсортирован, первое, что приходит на ум, — это бинарный поиск.
• Однако сложность в том, что мы не знаем размер массива.
  Если массив бесконечен, мы не можем использовать бинарный поиск, так как у нас нет подходящих границ.
• Таким образом, чтобы найти положение ключа, мы должны сначала определить границы, а затем использовать технику бинарного поиска.
• Пусть low указывает на первый элемент массива, а high указывает на второй.
• Теперь сравните ключ с элементом с высоким индексом, и если он больше, чем элемент с высоким индексом, продублируйте высокий индекс с низким индексом и удвойте высокий индекс. Если он меньше, выполните бинарный поиск по найденным высоким и низким индексам.
• Пусть k обозначает расположение искомого элемента. Количество шагов, необходимых для обнаружения высокого индекса h, равно O (log k). Значение h должно быть меньше 2*k. Между h/2 и h число компонентов должно быть O(k). В результате временная сложность шага бинарного поиска составляет O(log k), а общая временная сложность составляет 2*O(Log k), что означает O(log k).

Я полагаю, вы поняли все вопросы, обсуждавшиеся выше, связанные с алгоритмами для интервью. Если у вас есть какие-либо вопросы или какие-либо разъяснения, не стесняйтесь обращаться ко мне через раздел ответов. Спасибо, что потратили свое драгоценное время на чтение этого блога, и я верю, что это вдохновит вас на продолжение чтения других блогов об интервью. Предыдущие части подготовки к интервью можно найти здесь. Это будет очень полезно для вашей подготовки к интервью. До следующего раза, пока! 👋

Понравилась статья? Станьте Medium Member, чтобы продолжить обучение без каких-либо ограничений. Если вы воспользуетесь приведенной выше ссылкой, я получу часть вашего членского взноса без каких-либо дополнительных затрат для вас. Заранее спасибо.