Несмотря на значительный опыт создания программных продуктов, многие инженеры нервничают при мысли о прохождении собеседования по кодированию, посвященного алгоритмам. Я опросил сотни инженеров в Refdash, Google и стартапах, в которых я участвовал, и некоторые из наиболее частых вопросов, вызывающих беспокойство у инженеров, связаны с динамическим программированием (DP).
Многие технологические компании любят задавать вопросы DP в своих интервью. В то время как мы можем спорить о том, эффективны ли они в оценке способности кого-то выполнять на должности инженера, DP продолжает оставаться областью, которая сбивает инженеров на пути к поиску работы, которая им нравится.
Динамическое программирование - предсказуемое и готовое
Одна из причин, по которой я лично считаю, что вопросы DP могут быть не лучшим способом проверить инженерные способности, заключается в том, что они предсказуемы и легко поддаются сопоставлению с образцом. Они позволяют нам отфильтровать гораздо больше готовности, чем инженерные способности.
Эти вопросы обычно кажутся довольно сложными снаружи и могут создать впечатление, что человек, который их решает, очень хорошо разбирается в алгоритмах. Точно так же люди, которые не могут преодолеть некоторые запутанные концепции DP, могут показаться довольно слабыми в своих знаниях алгоритмов.
Реальность иная, и главный фактор в их исполнении - готовность. Так что давайте удостоверимся, что все к этому готовы. Однажды и на всегда.
7 шагов к решению проблемы динамического программирования
В оставшейся части этого поста я рассмотрю рецепт, которому вы можете следовать, чтобы выяснить, является ли проблема «проблемой DP», а также найти решение такой проблемы. В частности, я проделаю следующие шаги:
- Как распознать проблему DP
- Определите проблемные переменные
- Ясно выразите рекуррентное соотношение
- Определите базовые случаи
- Решите, хотите ли вы реализовать его итеративно или рекурсивно.
- Добавить мемоизацию
- Определить временную сложность
Пример проблемы DP
Чтобы иметь пример абстракции, которую я собираюсь создать, позвольте мне представить пример задачи. В каждом из разделов я буду ссылаться на проблему, но вы также можете прочитать разделы независимо от проблемы.
Постановка задачи:
В этой задаче мы безумно прыгаем с мячом, пытаясь остановиться, избегая при этом шипов.
Вот правила:
1) Вам дается ровная взлетно-посадочная полоса с кучей шипов на ней. Взлетно-посадочная полоса представлена логическим массивом, который указывает, очищено ли конкретное (дискретное) место от шипов. Верно для ясного и ложно для непонятного.
Пример представления массива:
2) Вам дана начальная скорость S. S является целым неотрицательным числом в любой заданной точке и указывает, насколько вы продвинетесь вперед со следующим прыжком.
3) Каждый раз, когда вы приземляетесь на место, вы можете регулировать скорость до 1 единицы перед следующим прыжком.
4) Вы хотите безопасно остановиться в любом месте взлетно-посадочной полосы (не обязательно в конце массива). Вы останавливаетесь, когда ваша скорость становится равной 0. Однако, если вы приземлитесь на шип в любой момент, ваш сумасшедший прыгающий мяч лопнет, и игра будет окончена.
Результат вашей функции должен быть логическим, указывающим, можем ли мы безопасно остановиться где-нибудь на взлетно-посадочной полосе.
Шаг 1. Как распознать проблему динамического программирования
Во-первых, давайте проясним, что DP - это, по сути, просто метод оптимизации. DP - это метод решения проблем путем разбиения их на набор более простых подзадач, решения каждой из этих подзадач только один раз и сохранения их решений. В следующий раз, когда возникнет та же подзадача, вместо повторного вычисления ее решения вы просто посмотрите ранее вычисленное решение. Это экономит время вычислений за счет (надеюсь) скромных затрат на место для хранения.
Признание того, что проблема может быть решена с помощью DP, является первым и часто самым трудным шагом в ее решении. Вы хотите спросить себя, может ли решение вашей проблемы быть выражено как функция решений аналогичных более мелких проблем.
В случае нашего примера проблемы, учитывая точку на взлетно-посадочной полосе, скорость и взлетно-посадочную полосу впереди, мы могли бы определить места, где мы потенциально могли бы прыгнуть в следующий раз. Более того, кажется, что можем ли мы остановиться с текущей точки с текущей скоростью, зависит только от того, сможем ли мы остановиться с точки, которую мы выбрали для перехода к следующей.
Это замечательно, потому что, двигаясь вперед, мы сокращаем полосу впереди и уменьшаем нашу проблему. Мы должны иметь возможность повторять этот процесс до тех пор, пока не дойдем до точки, когда станет очевидным, можем ли мы остановиться.
Распознавание проблемы динамического программирования часто является самым трудным шагом в ее решении. Можно ли выразить решение проблемы как функцию решений аналогичных более мелких проблем?
Шаг 2. Определите проблемные переменные
Теперь мы установили, что между нашими подзадачами существует некоторая рекурсивная структура. Затем нам нужно выразить проблему в терминах параметров функции и посмотреть, какие из этих параметров изменяются.
Обычно на собеседовании у вас будет один или два изменяющихся параметра, но технически это может быть любое число. Классический пример задачи с одним изменяющимся параметром - «определить n-е число Фибоначчи». Таким примером для задачи с двумя изменяющимися параметрами является «Вычислить расстояние редактирования между строками». Если вы не знакомы с этими проблемами, не беспокойтесь об этом.
Чтобы определить количество изменяющихся параметров, нужно перечислить примеры нескольких подзадач и сравнить параметры. Подсчет количества изменяющихся параметров полезен для определения количества подзадач, которые нам нужно решить. Это также важно само по себе, помогая нам лучше понять повторяющуюся связь из шага 1.
В нашем примере два параметра, которые могут измениться для каждой подзадачи:
- Положение массива (P)
- Скорость (S)
Можно сказать, что впереди взлетно-посадочная полоса также меняется, но это было бы излишним, учитывая, что вся неизменяемая взлетно-посадочная полоса и позиция (P) уже несут эту информацию.
Теперь, с этими двумя изменяющимися параметрами и другими статическими параметрами, у нас есть полное описание наших подзадач.
Определите изменяющиеся параметры и определите количество подзадач.
Шаг 3. Четко выразите рекуррентное соотношение
Это важный шаг, через который многие спешат, чтобы приступить к программированию. Как можно более четкое выражение отношения повторяемости укрепит ваше понимание проблемы и значительно упростит все остальное.
Как только вы поймете, что существует рекуррентное отношение, и определите проблемы в терминах параметров, это должно стать естественным шагом. Как проблемы связаны друг с другом? Другими словами, предположим, что вы вычислили подзадачи. Как бы вы вычислили основную проблему?
Вот как мы думаем об этом в нашем примере задачи:
Поскольку вы можете отрегулировать скорость до 1, прежде чем перейти к следующей позиции, есть только 3 возможных скорости и, следовательно, 3 точки, в которых мы могли бы быть следующими.
Более формально, если наша скорость S, позиция P, мы могли бы перейти от (S, P) к:
- (S, P + S); # если не менять скорость
- (S - 1, P + S - 1); # если мы изменим скорость на -1
- (S + 1, P + S + 1); # если мы изменим скорость на +1
Если мы сможем найти способ остановиться в любой из подзадач выше, то мы также можем остановиться на (S, P). Это потому, что мы можем перейти от (S, P) к любому из трех вышеперечисленных вариантов.
Обычно это хороший уровень понимания проблемы (простое объяснение на английском языке), но иногда вы можете захотеть выразить отношение и математически. Давайте вызовем функцию, которую мы пытаемся вычислить, canStop. Потом:
canStop (S, P) = canStop (S, P + S) || canStop (S - 1, P + S - 1) || canStop (S + 1, P + S + 1)
Ууууу, похоже, у нас есть рекуррентная связь!
Отношение повторяемости: если вы вычислили подзадачи, как бы вы вычислили основную проблему?
Шаг 4. Определите базовые варианты
Базовый вариант - это подзадача, не зависящая от других подзадач. Чтобы найти такие подзадачи, вы обычно хотите попробовать несколько примеров, посмотреть, как ваша проблема превращается в более мелкие подзадачи, и определить, в какой момент ее нельзя упростить дальше.
Причина, по которой проблему нельзя упростить, заключается в том, что один из параметров может стать значением, которое невозможно с учетом ограничений проблемы.
В нашем примере задачи у нас есть два изменяющихся параметра, S и P. Давайте подумаем, какие возможные значения S и P могут быть недопустимыми:
- P должен находиться в пределах данной взлетно-посадочной полосы
- P не может быть таким, чтобы взлетно-посадочная полоса [P] была ложной, потому что это означало бы, что мы стоим на шипе
- S не может быть отрицательным, а S == 0 означает, что все готово
Иногда может быть немного сложно преобразовать утверждения, которые мы делаем о параметрах, в программируемые базовые случаи. Это связано с тем, что помимо перечисления утверждений, если вы хотите, чтобы ваш код выглядел лаконично и не проверял наличие ненужных условий, вам также необходимо подумать о том, какие из этих условий вообще возможны.
В нашем примере:
- P ‹0 || P ›= длина взлетно-посадочной полосы кажется правильным решением. Альтернативой может быть рассмотрение использования P == конца взлетно-посадочной полосы в качестве базового варианта. Однако возможно, что проблема разделится на подзадачу, которая выходит за пределы взлетно-посадочной полосы, поэтому нам действительно нужно проверить неравенство.
- Это кажется довольно очевидным. Мы можем просто проверить , является ли ВПП [P] ложным .
- Подобно # 1, мы могли бы просто проверить S ‹0 и S == 0. Однако здесь мы можем предположить, что S не может быть‹ 0, потому что S уменьшается не более чем на 1, поэтому он должен пройти через S == 0 случай заранее. Следовательно, S == 0 является достаточным базовым случаем для параметра S.
Шаг 5. Решите, хотите ли вы реализовать его итеративно или рекурсивно.
То, как мы говорили о шагах до сих пор, может заставить вас подумать, что мы должны реализовать проблему рекурсивно. Однако все, о чем мы говорили до сих пор, полностью не зависит от того, решите ли вы реализовать проблему рекурсивно или итеративно. В обоих подходах вам нужно будет определить отношение повторения и базовые случаи.
Чтобы решить, следует ли идти итеративно или рекурсивно, вы должны тщательно подумать о компромиссах.
Проблемы, связанные с переполнением стека, обычно являются преградой и причиной, по которой вы не хотели бы иметь рекурсию в (серверной) производственной системе. Однако для целей интервью, если вы упоминаете компромиссы, вас обычно устраивает любая из реализаций. Вам должно быть комфортно реализовывать и то, и другое.
В нашей конкретной задаче я реализовал обе версии. Вот код Python для этого:
Рекурсивное решение: (фрагменты исходного кода можно найти здесь)
Итеративное решение: (фрагменты исходного кода можно найти здесь)
Шаг 6. Добавьте мемоизацию
Мемоизация - это техника, которая тесно связана с DP. Он используется для хранения результатов дорогостоящих вызовов функций и возврата кэшированного результата, когда те же входные данные повторяются снова.
Почему мы добавляем мемоизацию к нашей рекурсии? Мы сталкиваемся с теми же подзадачами, которые без запоминания вычисляются повторно. Эти повторения очень часто приводят к экспоненциальным временным сложностям.
В рекурсивных решениях добавление мемоизации должно быть простым. Посмотрим почему. Помните, что мемоизация - это просто кеш результатов функции. Бывают случаи, когда вы хотите отклониться от этого определения, чтобы выжать некоторые незначительные оптимизации, но рассмотрение мемоизации как кеша результатов функции является наиболее интуитивным способом ее реализации.
Это означает, что вам следует:
- Сохраняйте результат своей функции в памяти перед каждым оператором return
- Найдите в памяти результат функции, прежде чем начинать выполнение любых других вычислений.
Вот код сверху с добавленной мемоизацией (добавленные строки выделены): (фрагменты исходного кода можно найти здесь)
Чтобы проиллюстрировать эффективность запоминания и различных подходов, давайте проведем несколько быстрых тестов. Я проведу стресс-тестирование всех трех методов, которые мы видели до сих пор. Вот настройка:
- Я создал взлетно-посадочную полосу длиной 1000 с шипами в случайных местах (я выбрал, чтобы вероятность появления шипа в любом данном месте составляла 20%).
- initSpeed = 30
- Я запустил все функции 10 раз и измерил среднее время выполнения
Вот результаты (в секундах):
Вы можете видеть, что чисто рекурсивный подход занимает примерно в 500 раз больше времени, чем итерационный подход, и примерно в 1300 раз больше времени, чем рекурсивный подход с мемоизацией. Обратите внимание, что это несоответствие будет быстро расти с увеличением длины взлетно-посадочной полосы. Я рекомендую вам попробовать запустить его самостоятельно.
Шаг 7: Определите временную сложность
Есть несколько простых правил, которые могут значительно упростить вычисление временной сложности задачи динамического программирования. Вот два шага, которые вам нужно сделать:
- Подсчитайте количество состояний - это будет зависеть от количества изменяемых параметров в вашей задаче.
- Подумайте о проделанной работе по каждому штату. Другими словами, если все остальное, кроме одного состояния, было вычислено, сколько работы вам нужно сделать, чтобы вычислить это последнее состояние?
В нашем примере задачи количество состояний равно | P | * | S |, где
- P - это набор всех позиций (| P | указывает количество элементов в P)
- S - набор всех скоростей
Работа, проделанная для каждого состояния в этой задаче, составляет O (1), потому что, учитывая все другие состояния, нам просто нужно посмотреть на 3 подзадачи, чтобы определить результирующее состояние.
Как мы уже отмечали в коде ранее, | S | ограничено длиной взлетно-посадочной полосы (| P |), поэтому мы можем сказать, что количество состояний равно | P | ², и поскольку работа, выполняемая для каждого состояния, составляет O (1), то общая временная сложность составляет O (| P | ²).
Однако кажется, что | S | может быть дополнительно ограничен, потому что, если бы это было действительно | P |, совершенно очевидно, что остановка была бы невозможна, потому что вам пришлось бы перепрыгнуть всю взлетно-посадочную полосу на первом ходу.
Итак, давайте посмотрим, как мы можем более жестко ограничить | S |. Назовем максимальную скорость S. Предположим, что мы начинаем с позиции 0. Как быстро мы могли бы остановиться, если бы пытались остановиться как можно скорее, и если бы мы игнорировали возможные всплески?
На первой итерации мы должны были бы дойти, по крайней мере, до точки (S-1), установив нулевую скорость на -1. Оттуда мы продвинемся как минимум на (S-2) шагов вперед и так далее.
Для взлетно-посадочной полосы длины L должны соблюдаться следующие условия:
=> (S-1) + (S-2) + (S-3) + ….+ 1 < L
=> S*(S-1) / 2 < L
=> S² — S — 2L < 0
Если вы найдете корни вышеуказанной функции, они будут:
r1 = 1/2 + sqrt (1/4 + 2L) и r2 = 1/2 - sqrt (1/4 + 2L)
Мы можем записать наше неравенство как:
(S — r1) * (S — r2) < 0
Учитывая, что S - r2 ›0 для любых S› 0 и L ›0, нам понадобится следующее:
S - 1/2 - sqrt (1/4 + 2L) ‹0
= ›S‹ 1/2 + sqrt (1/4 + 2L)
Это максимальная скорость, которую мы могли бы иметь на взлетно-посадочной полосе длиной L. Если бы у нас была скорость выше, мы не смогли бы остановиться даже теоретически, независимо от положения шипов.
Это означает, что общая временная сложность зависит только от длины взлетно-посадочной полосы L в следующем виде:
O (L * sqrt (L)), что лучше, чем O (L²)
O (L * sqrt (L)) - верхняя граница временной сложности
Отлично, вы справились! :)
7 шагов, которые мы прошли, должны дать вам основу для систематического решения любой проблемы динамического программирования. Я настоятельно рекомендую попрактиковаться в этом подходе еще на нескольких задачах, чтобы усовершенствовать свой подход.
Вот несколько следующих шагов, которые вы можете предпринять
- Расширьте пример проблемы, пытаясь найти путь к точке остановки. Мы решили проблему, которая сообщает вам, можете ли вы остановиться, но что, если бы вы также хотели знать, какие шаги нужно предпринять, чтобы в конечном итоге остановиться на взлетно-посадочной полосе? Как бы вы для этого изменили существующую реализацию?
- Если вы хотите укрепить свое понимание мемоизации и понять, что это всего лишь кеш результатов функции, вам следует прочитать о декораторах в Python или аналогичных концепциях на других языках. Подумайте, как они позволят вам реализовать мемоизацию в целом для любой функции, которую вы хотите запомнить.
- Работайте над другими проблемами DP, следуя шагам, которые мы прошли. Вы всегда можете найти их в Интернете (например, LeetCode или GeeksForGeeks). Практикуясь, помните об одном: изучайте идеи, а не изучайте проблемы. Количество идей значительно меньше, и это более легкое пространство для освоения, которое также будет служить вам намного лучше.
Когда вы почувствуете, что овладели этими идеями, посмотрите Refdash, где вы пройдете собеседование со старшим инженером и получите подробные отзывы о вашем коде, алгоритмах и дизайне системы.
Изначально опубликовано в Refdash blog. Refdash - это платформа для собеседований, которая помогает инженерам анонимно проводить собеседования с опытными инженерами из ведущих компаний, таких как Google, Facebook или Palantir, и получать подробные отзывы. Refdash также помогает инженерам открывать удивительные возможности трудоустройства, исходя из их навыков и интересов.
