Algorithms

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

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

Реализуйте алгоритм бинарного поиска

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

Важно: бинарный поиск возможен, только если массив данных отсортирован.

Пример реализации на Java.

Реализуйте сортировку пузырьком

Во время сортировки пузырьком сравнивают рядом стоящие числа, выстраивая их в порядке убывания или возрастания.

Временная сложность — O(n²), из-за которого алгоритм подходит только для небольшого объёма данных.

Пример реализации на Java.

Разница между устойчивой и неустойчивой сортировкой

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

Как поменять местами два значения переменных без третьей переменной?

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

a = 3; b = 5;

a = a + b; // 8
b = a - b; // 3
a = a - b; // 5

Как реализуется поразрядная сортировка?

Алгоритм с временной сложностью О(n). Согласно википедии, поразрядная сортировка это алгоритм сортировки, не требующий сравнения. Он обрабатывает данные с целочисленными ключами путём группирования ключей в соответствии с индивидуальными разрядами, которые разделяют ту же позицию и значение.

Пример реализации на Java сортировки строк по младшему разряду.

Как реализовать алгоритм сортировки вставкой?

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

Пример реализации на Java.

Как реализовать сортировку слиянием?

Как в случае с быстрой сортировкой, этот метод относят к группе «разделяй и властвуй». Например, чтобы отсортировать массив чисел, вы его разделите на небольшие части, пока не останется массив в один или ноль отсортированных элементов. Далее следует объединить малые массивы, чтобы получить финальный результат.

Стоит отметить, что в сравнении с быстрой сортировкой данный алгоритм обрабатывает элементы медленнее.

Пример реализации на Java.

Реализуйте алгоритм быстрой сортировки на предпочитаемом языке программирования

Алгоритм относится к группе «разделяй и властвуй», что предопределяет разделение задачи на подзадачи. То есть, сначала нужно разбить имеющиеся данные на мельчайшие составляющие, массивы из одного элемента (или с нулевым количеством элементов).

Пример на Java.

Читайте также:


Перевод статьи javinpaul: 20+ basic Algorithms Problems from Coding Interviews