Читать книгу Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию - Гейл Макдауэлл - Страница 38

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

Предположим, что вас попросили выполнить следующее задание: провести сортировку очень большого массива Person, упорядочив его элементы в соответствии со значением возраста человека (в возрастающем порядке).

Нам известно два факта:

• Массив имеет большие размеры, значит, эффективность алгоритма очень важна.

• Сортировка выполняется по возрасту, то есть значения имеют ограниченный

диапазон. Рассмотрев различные алгоритмы, мы понимаем, что нам идеально подходит блочная сортировка. Если блоки будут достаточно маленькими (например, 1 год), то время выполнения составит O(n).

Общие алгоритмы сортировки

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

Пузырьковая сортировка | Время выполнения в худшем и среднем случае: O(n²). Память: O(1).

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

Сортировка выбором | Время выполнения в худшем и среднем случае: O(n²). Память: O(1).

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

Сортировка слиянием | Время выполнения в худшем и среднем случае: O(n log(n)).

Память: зависит от задачи.

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

Метод слияния копирует все элементы из целевого массива во вспомогательные, разделяя левую и правую половины (helperLeft и helperRight). Мы «двигаемся» по вспомогательному массиву helper, копируя наименьший элемент каждой половины в массив. В итоге мы копируем оставшиеся элементы в целевой массив.

1 void mergesort(int[] array, int low, int high) {

2 if (low < high) {

3 int middle = (low + high) / 2;

4 mergesort(array, low, middle); // Сортируем левую половину

5 mergesort(array, middle + 1, high); // Сортируем правую половину

6 merge(array, low, middle, high); // Объединяем их

7 }

8 }

9

10 void merge(int[] array, int low, int middle, int high) {

11 int[] helper = new int[array.length];

12

13 /* Копируем обе половины во вспомогательный массив */

14 for (int i = low; i <= high; i++) {

15 helper[i] = array[i];

16 }

17

18 int helperLeft = low;

19 int helperRight = middle + 1;

20 int current = low;

21

22 /* Проходимся по вспомогательному массиву. Сравниваем левую и правую

23 * половины, копируем обратно наименьший элемент из двух половин

24 * в исходный массив. */

25 while (helperLeft <= middle && helperRight <= high) {

26 if (helper[helperLeft] <= helper[helperRight]) {

27 array[current] = helper[helperLeft];

28 helperLeft++;

29 } else { // Если правый элемент меньше, чем левый

30 array[current] = helper[helperRight];

31 helperRight++;

32 }

33 current++;

34 }

35

36 /* Копируем оставшуюся часть левой стороны массива

37 * в целевой массив */

38 int remaining = middle – helperLeft;

39 for (int i = 0; i <= remaining; i++) {

40 array[current + i] = helper[helperLeft + i];

41 }

42 }

Обратите внимание, что в целевой массив скопированы только оставшиеся элементы левой половины вспомогательного массива. Почему не правой половины? Правая половина и не должна копироваться, потому что она уже там.

Рассмотрим для примера массив [1, 4, 5 || 2, 8, 9] (знак || указывает точку раздела).

До момента слияния половин оба массива – вспомогательный и целевой – заканчиваются элементами [8, 9]. Когда мы копируем в целевой массив больше четырех элементов (1, 4, 5, и 2), элементы [8, 9] продолжают оставаться в обоих массивах. Нет никакой необходимости копировать их.

Быстрая сортировка | Время выполнения в среднем случае: O(n log(n)), в худшем случае: O(n²). Память: O(log(n)).

При быстрой сортировке из массива выбирается случайный (опорный) элемент, и все элементы массива располагаются по принципу: меньшие – равные – большие относительно выбранного элемента. Такую декомпозицию эффективнее всего осуществлять через перестановки (см. далее).

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

1 void quickSort(int arr[], int left, int right) {

2 int index = partition(arr, left, right);

3 if (left < index – 1) { // Сортируем левую половину

4 quickSort(arr, left, index – 1);

5 }

6 if (index < right) { // Сортируем правую половину

7 quickSort(arr, index, right);

8 }

9 }

10

11 int partition(int arr[], int left, int right) {

12 int pivot = arr[(left + right) / 2]; // Выбираем центральную точку

13 while (left <= right) {

14 // Находим элемент слева, который должен быть справа

15 while (arr[left] < pivot) left++;

16

17 // Находим элемент справа, который должен быть слева

18 while (arr[right] > pivot) right-;

19

20 // Меняем местами элементы и перемещаем левые и правые индексы

21 if (left <= right) {

22 swap(arr, left, right); // Меняем местами элементы

23 left++;

24 right-;

25 }

26 }

27 return left;

28 }

Поразрядная сортировка | Время выполнения в среднем случае: O(n log(n)), в худшем случае: O(kn).

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

Мы группируем числа по каждому разряду. Например, массив целых чисел сначала сортируется по первому разряду (чтобы все 0 собрались в группу). Затем каждая из групп сортируется по следующему разряду. Процесс повторяется, пока весь массив не будет отсортирован.

В отличие от алгоритмов сортировки с использованием сравнения, которые в большинстве случаев не могут выполняться быстрее, чем за O(log(n)), данный алгоритм в худшем случае дает результат O(kn), где n – количество элементов в массиве, а k – количество проходов алгоритма сортировки.

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

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

1 int binarySearch(int[] a, int x) {

2 int low = 0;

3 int high = a.length – 1;

4 int mid; 5

6 while (low <= high) {

7 mid = (low + high) / 2;

8 if (a[mid] < x) {

9 low = mid + 1;

10 } else if (a[mid] > x) { 11 high = mid – 1; 12 } else {

13 return mid;

14 } 15 } 16 return -1; // Ошибка 17 }

18

19 int binarySearchRecursive(int[] a, int x, int low, int high) { 20 if (low > high) return -1; // Ошибка

21 22 int mid = (low + high) / 2;

23 if (a[mid] < x) { 24 return binarySearchRecursive(a, x, mid + 1, high); 25 } else if (a[mid] > x) { 26 return binarySearchRecursive(a, x, low, mid – 1); 27 } else {

28 return mid;

29 } 30 }

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

Вопросы собеседования

10.1. Дано: два отсортированных массива A и B. Размер массива A (свободное место в конце) позволяет поместить в него массив B. Напишите метод слияния массивов B и A, сохраняющий сортировку.

10.2. Напишите метод сортировки массива строк, при котором анаграммы группируются друг за другом.

10.3. Дано: отсортированный массив из n целых чисел, который был циклически сдвинут произвольное число раз. Напишите код для поиска элемента в массиве. Исходите из предположения, что массив изначально был отсортирован по возрастанию.

Пример:

Ввод: найдите индекс элемента со значением 5в {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14} Вывод: 8.

10.4. Дано: файл размером 20 Гбайт, содержащий строки. Как выполнить сортировку такого файла?

10.5. Дано: отсортированный массив, состоящий из строк, разделенных пустыми строками. Напишите метод для обнаружения позиции заданной строки.

Пример:

Ввод: найдите индекс элемента "ball" в массиве {"at", " ", " ", " ","ball", " ", " ","car", " "," ","dad", " "," "}

Вывод: 4

10.6. Дано: матрица размером M×N, строки и колонки которой отсортированы. Напишите метод нахождения элемента.

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

Пример:

Ввод (ht, wt): (65, 100) (70, 150)(56, 90)(75, 190)(60, 95) (68, 110)

Вывод: максимальная высота пирамиды – 6 человек, сверху вниз: (56, 90)(60, 95) (65, 100)(68, 110)(70, 150)(75, 190)

10.8. Вы обрабатываете поток целых чисел. Периодически вам нужно находить ранг числа x (количество значений <= x). Какие структуры данных и алгоритмы необходимы для поддержки этих операций? Реализуйте метод track(int x), вызываемый при генерировании каждого символа, и метод getRankOfNumber(int x), возвращающий количество значений <=x (не включая x).

Пример:

Поток (в порядке появления): 5, 1, 4, 4, 5, 9, 7, 13, 3

getRankOfNumber(1)= 0

getRankOfNumber(3)= 1

getRankOfNumber(4)= 3

Дополнительные вопросы: массивы и строки (1.3), рекурсия (8.3), модерирование (17.6, 17.12), вопросы повышенной сложности (18.5).