Источник: Nuances of Programming
Во время собеседования на должность в IT-сфере часто касаются вопросов применения алгоритмов. Наиболее популярными являются алгоритмы поиска и сортировки (строковые алгоритмы, бинарный поиск, алгоритм поиска на графах). Несмотря на кажущуюся простоту, они бывают коварны и трудны в реализации под конкретную задачу. Вот почему важно заранее отработать принцип применения каждого алгоритма, а не полагаться на слепую удачу. Чем лучше вы поймёте схему работы, чем подробнее сможете описать решение данных вам задач, тем выше будут шансы на успешное прохождение собеседования.
Будьте готовы к хитрым вопросам и решению проблем альтернативными способами. Например, часто просят вместо рекурсии разобрать задачу через итеративный алгоритм.
Реализуйте алгоритм бинарного поиска
Бинарный поиск — это алгоритм, следующий парадигме «разделяй и властвуй»: задача разбивается на подзадачи. Этот алгоритм поиска удобен, если нужно найти число в массиве простых чисел или элемент в списке. Самый простой способ решения — при помощи рекурсии.
Важно: бинарный поиск возможен, только если массив данных отсортирован.
Реализуйте сортировку пузырьком
Во время сортировки пузырьком сравнивают рядом стоящие числа, выстраивая их в порядке убывания или возрастания.
Временная сложность — O(n²), из-за которого алгоритм подходит только для небольшого объёма данных.
Разница между устойчивой и неустойчивой сортировкой
При устойчивой сортировке не меняется относительный порядок сортируемых элементов, имеющих одинаковые ключи, при неустойчивой — меняется. Например, алгоритм быстрой сортировки — неустойчивый, алгоритм сортировки слиянием — устойчивый.
Как поменять местами два значения переменных без третьей переменной?
Еще один вопрос с подвохом, который на самом деле очень прост. Вы можете поменять местами два числа, не прибегая к временной или третьей переменной, если присвоите одной переменной значение суммы двух чисел, а потом вычтите из этой суммы значение для каждой из переменных. Пример:
Как реализуется поразрядная сортировка?
Алгоритм с временной сложностью О(n). Согласно википедии, поразрядная сортировка это алгоритм сортировки, не требующий сравнения. Он обрабатывает данные с целочисленными ключами путём группирования ключей в соответствии с индивидуальными разрядами, которые разделяют ту же позицию и значение.
Пример реализации на Java сортировки строк по младшему разряду.
Как реализовать алгоритм сортировки вставкой?
Принцип схож с сортированием колоды или одежды в шкафу. Каждая карта ложится на свое место, иначе говоря, каждый последующий элемент добавляется на определенную позицию.
Как реализовать сортировку слиянием?
Как в случае с быстрой сортировкой, этот метод относят к группе «разделяй и властвуй». Например, чтобы отсортировать массив чисел, вы его разделите на небольшие части, пока не останется массив в один или ноль отсортированных элементов. Далее следует объединить малые массивы, чтобы получить финальный результат.
Стоит отметить, что в сравнении с быстрой сортировкой данный алгоритм обрабатывает элементы медленнее.
Реализуйте алгоритм быстрой сортировки на предпочитаемом языке программирования
Алгоритм относится к группе «разделяй и властвуй», что предопределяет разделение задачи на подзадачи. То есть, сначала нужно разбить имеющиеся данные на мельчайшие составляющие, массивы из одного элемента (или с нулевым количеством элементов).
Читайте также:
Читайте нас в телеграмме и vk
Перевод статьи javinpaul: 20+ basic Algorithms Problems from Coding Interviews