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

Часть VIII. Вопросы собеседования
Концепции и алгоритмы. Вопросы и советы
9. Рекурсия и динамическое программирование

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

Когда вы получаете задание «Разработайте алгоритм для вычисления N-го…», или «Напишите код для вывода первых n…», или «Реализуйте метод для вычисления всех…» – скорее всего, речь пойдет о рекурсии.

Практика – путь к совершенству! Чем больше задач вы решите, тем легче будет распознавать рекурсивные задачи.

С чего начать

Рекурсивные решения, по определению, основываются на решении подзадач. Очень часто придется вычислять f(n), добавляя, вычитая или еще как-либо изменяя f(n-1). Следует принимать во внимание оба типа рекурсии: восходящую и нисходящую.

Восходящая рекурсия

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

Нисходящая рекурсия

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

Динамическое программирование

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

Если вам не повезло и вы получили задачу по ДП, подход будет аналогичен подходу к решению рекурсивной задачи. Различие заключается в том, что промежуточные результаты «кэшируются» для будущих вызовов.

Простой пример динамического программирования: числа Фибоначчи

В качестве очень простого примера динамического программирования рассмотрим программу, генерирующую N-е число Фибоначчи. Просто, не так ли?

1 int fibonacci(int i) {

2 if (i == 0) return 0;

3 if (i == 1) return 1;

4 return fibonacci(i – 1) + fibonacci(i – 2);

5 }

Каково время выполнения этой функции? Вычисление N-го числа Фибоначчи зависит от предыдущих n–1 чисел. Но каждый вызов делает два рекурсивных вызова. Это означает, что время выполнения составит O(2ⁿ). График, приведенный ниже, показывает это экспоненциальное увеличение.

Время, потраченное на вычисление N-го числа Фибоначчи в секундах

Всего одно небольшое изменение – и время, необходимое на выполнение этой функции, уменьшится до O(N). Нужно всего лишь «кэшировать» результаты функции fibonacci(i) между вызовами:

1 int[] fib = new int[max];

2 int fibonacci(int i) {

3 if (i == 0) return 0;

4 if (i == 1) return 1;

5 if (fib[i]!= 0) return fib[i]; // Возвращаем кэшированный результат.

6 fib[i] = fibonacci(i – 1) + fibonacci(i – 2); // Кэшируем результат

7 return fib[i];

8 }

Генерирование 50-го числа Фибоначчи на стандартном компьютере с помощью рекурсивной функции займет более одной минуты. Метод динамического программирования позволит сгенерировать 10 000-е число Фибоначчи за доли миллисекунды (но не забывайте, что размера типа int может оказаться недостаточно).

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

Рекурсивные и итерационные решения

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

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

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

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

9.2. Представьте робота, сидящего в левом верхнем углу сетки с координатами X, Y. Робот может перемещаться в двух направлениях: вправо и вниз. Сколько существует маршрутов, проходящих от точки (0,0) до точки (X,Y).

Дополнительно

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

9.3. В массиве A[0…n-1] задан «волшебный» индекс – A[i]=i. Учитывая, что массив отсортирован, напишите метод, чтобы найти этот «волшебный» индекс, если он существует в массиве A.

Дополнительно

Что произойдет, если значения окажутся одинаковыми?

9.4. Напишите метод, возвращающий все подмножества одного множества.

9.5. Напишите метод, возвращающий все перестановки строки.

9.6. Реализуйте алгоритм, выводящий все корректные (правильно открытые и закрытые) комбинации пар круглых скобок.

Пример:

Ввод: 3

Вывод: ((())), (()()), (())(), ()(()), ()()()

9.7. Реализуйте функцию заливки краской, которая используется во многих графических редакторах. Дана плоскость (двумерный массив цветов), точка и цвет, которым нужно заполнить все окружающее пространство, окрашенное в другой цвет.

9.8. Дано неограниченное количество монет достоинством 25, 10, 5 и 1 цент. Напишите код, определяющий количество способов представления n центов.

9.9. Дана шахматная доска размером 8×8. Напишите алгоритм, находящий все варианты расстановки восьми ферзей так, чтобы никакие две фигуры не попадали на одну горизонталь, вертикаль или диагональ. Учитываются не только главные, но и все остальные диагонали.

9.10. Дан штабель из n ящиков шириной w_i, высотой h_i и глубиной d_i. Ящики нельзя поворачивать, добавлять ящики можно только наверх штабеля. Каждый нижний ящик в стопке по высоте, ширине и глубине больше ящика, который находится на нем. Реализуйте метод, позволяющий построить самый высокий штабель (высота штабеля равна сумме высот всех ящиков).

9.11. Дано логическое выражение, построенное из символов θ, 1, &, | и ^, и имеющее значение result. Напишите функцию, подсчитывающую количество вариантов логических выражений, дающих значение result.

Пример:

Выражение: 1^θ|θ|1

Результат: result=false(θ)

Вывод: 2 способа: 1^((θ|θ)|1) и 1^(θ|(θ|1))

Дополнительные вопросы: связные списки (2.2, 2.5, 2.7), стеки и очереди (3.3), деревья и графы (4.1, 4.3, 4.4, 4.5, 4.7, 4.8, 4.9), головоломки (6.4), сортировка и поиск (9.5, 9.6, 9.7, 9.8), C++ (13.7), модерирование (17.13, 17.14), задачи повышенной сложности (18.4, 18.7, 18.12, 18.13).

Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию

Подняться наверх