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

vypolnite eti shagi chtoby reshit problemu sobesedovaniya s dinamicheskim programmirovaniem

Никола Отасевич

UmaucoRyPXogpDlwhmgzIWm-yBQ-XAxJ4Xox

Несмотря на значительный опыт создания программных продуктов, многие инженеры испытывают тревогу при мысли о прохождении собеседования с кодировкой, которая сосредоточена на алгоритмах. Я опросил сотни инженеров в Refdash, Google и в стартапах, в которых я был, и некоторые из самых распространенных вопросов, вызывающих у инженеров беспокойство, это вопросы, связанные с динамическим программированием (DP).

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

Динамическое программирование – предполагаемое и подготовленное

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

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

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

7 шагов для решения проблемы динамического программирования

В остальной публикации я расскажу о рецепте, которому вы можете следовать, чтобы выяснить, есть ли проблема «проблемой DP», а также найти решение такой проблемы. В частности, я пройду следующие шаги:

  1. Как распознать проблему DP
  2. Определите переменные проблемы
  3. Четко выразить отношение повторяемости
  4. Определите базовые случаи
  5. Решите, хотите ли вы реализовать его итерационно или рекурсивно
  6. Добавьте запоминание
  7. Определите временную сложность

Образец проблемы DP

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

Постановка проблемы:

YIelQx3b0OSZIaNWVkJEmirqOZRZWXm2fbBk

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

Вот правила:

1) Вы получаете плоскую взлетно-посадочную полосу с кучей шипов. Взлетно-посадочная полоса представлена ​​булевым массивом, указывающим, не содержит ли конкретное (дискретное) место пиков. Это True для ясного и False для непонятного.

Пример представления массива:

c5h0NAmIsaNYEjJfcIZa3uPCiTxO28ew9gPV

2) Вы получаете начальную скорость S. S является целым неотъемлемым числом в любой данной точке, и оно указывает, на сколько вы будете двигаться вперед с последующим прыжком.

3) Каждый раз, когда вы приземляетесь на место, вы можете изменить скорость до 1 единицы перед следующим прыжком.

bCnFU8w6zxjnUpypi0ArUOyON6L20E0EPl0p

4) Вы хотите безопасно остановиться в любом месте вдоль взлетно-посадочной полосы (необязательно быть в конце массива). Вы останавливаетесь, когда ваша скорость становится 0. Однако, если вы в любой момент приземлитесь на шип, ваш подпрыгивающий сумасшедший мяч лопнет, и игра закончена.

Вывод вашей функции должен быть логичным, что указывает, можем ли мы безопасно остановиться в любом месте вдоль взлетно-посадочной полосы.

Шаг 1: Как распознать проблему динамического программирования

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

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

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

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

Распознавание проблемы динамического программирования часто является сложным шагом в ее решении. Можно ли решение задачи выразить как функцию подобных меньших задач?

Шаг 2: Определите проблемные переменные

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

Обычно на собеседовании у вас будет один или два изменяющихся параметра, но технически это может быть любое число. Классическим примером проблемы с одним переменным параметром является «определение n числа Фибоначчи». Таким примером проблемы с двумя переменными параметрами является Вычислите расстояние редактирования между строками. Если вы не знакомы с этими проблемами, не беспокойтесь об этом.

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

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

  1. Позиция массива (P)
  2. Скорость (S)

Можно сказать, что взлетно-посадочная полоса впереди также меняется, но это было бы лишним, учитывая, что вся неизменяемая взлетно-посадочная полоса и позиция (P) уже содержат эту информацию.

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

Определите изменяющиеся параметры и определите количество подзадач.

Шаг 3. Четко выразите соотношение повторяемости

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

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

Вот как мы думаем об этом в нашем примере задачи:

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

Более формально, если наша скорость S, позиция P, мы могли бы перейти от (S, P) к:

  1. (S, P+S); # если мы не изменим скорость
  2. (S – 1, P + S – 1); # если мы изменим скорость на -1
  3. (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 могут быть неприемлемыми:

  1. P должно быть в пределах заданной взлетно-посадочной полосы
  2. P не может быть таким, что взлетно-посадочная полоса[P] ошибочно, потому что это означало бы, что мы стоим на пике
  3. S не может быть отрицательным, а S==0 указывает, что мы закончили

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

В нашем примере:

  1. P < 0 || P >= длина взлетно-посадочная полоса кажется правильным. Альтернативой может быть рассмотрение making P == конец взлетно-посадочная полоса базовый вариант. Однако возможно, что проблема разбивается на подзадачу, выходящую за пределы конца взлетно-посадочной полосы, поэтому нам действительно нужно проверить неравенство.
  2. Это кажется достаточно очевидным. Мы можем просто проверить если взлетно-посадочная полоса[P] является ошибочным.
  3. Подобно №1, мы можем просто проверить, S < 0 и S == 0. Однако здесь мы можем считать, что невозможно, чтобы S было < 0, поскольку S уменьшается максимум на 1, поэтому ему придется пройти через S == 0 случай заранее. Therраньше S==0 является достаточным базовым случаем для параметра S.

Шаг 5: Решите, хотите ли вы реализовать его итерационно или рекурсивно

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

Чтобы решить, идти ли итерационно или рекурсивно, нужно тщательно подумать о компромиссах..

E-2qbrD5g7UtOJIN7ULrdwAdgiL0jAU7uGFH

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

В нашей конкретной задаче я реализовал обе версии. Вот код на python для этого:
Рекурсивное решение: (оригинальные фрагменты кода можно найти здесь)

MmSzAzTeUbtfjiYFSjilQlCBaXRAsOOIesKL

Итерационное решение: (оригинальные фрагменты кода можно найти здесь)

aZgiyRIJ3SAD0Mx6lywCaohZt1BUJ0ZW-1Hm

Шаг 6: Добавьте запоминание

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

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

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

Это означает, что вы должны:

  1. Сохраняйте результат функции в памяти перед каждым вернуться заявление
  2. Найдите в памяти результат функции, прежде чем начать выполнять какие-либо другие вычисления

Вот код сверху с добавленной запоминанием (добавлены строки выделены): (оригинальные фрагменты кода можно найти здесь)

aAgK5alenVTE0zyCTsknv32r-RTjiFOJmMu6

Чтобы проиллюстрировать эффективность запоминания и разных подходов, давайте проведем несколько быстрых тестов. Я проверю все три метода, которые мы видели до сих пор. Вот настройки:

  1. Я создал взлетно-посадочную полосу длиной 1000 с шипами в случайных местах (я решил, чтобы вероятность того, что пик будет в любом месте, составляла 20%)
  2. initSpeed ​​= 30
  3. Я запустил все функции 10 раз и измерил среднее время выполнения

Вот результаты (в секундах):

boxJ2uGkAzVHEakgeFnPJMMe44oFIhLAqGh5

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

Шаг 7: Определите временную сложность

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

  1. Сочтите количество состояний — это будет зависеть от количества изменяемых параметров в вашей задаче
  2. Подумайте о работе, проделанной каждым государством. Другими словами, если все остальное, кроме одного состояния, было вычислено, сколько работы нужно проделать, чтобы вычислить это последнее состояние?

В нашем примере задачи количество состояний равно |P| * |S|, где

  • P — множество всех позиций (|P| указывает количество элементов в P)
  • S — множество всех скоростей

Работа, выполненная для каждого состояния, равна O(1) в этой задаче, так как, учитывая все остальные состояния, мы просто должны рассмотреть 3 подзадачи, чтобы определить результирующее состояние.

Как уже отмечалось в коде ранее, |S| ограничена длиной взлетно-посадочной полосы (|P|), поэтому мы могли бы сказать, что количество состояний равно |P|² и поскольку работа, выполненная для каждого состояния, равна O(1), то общая временная сложность O(|P | ²).

Однако кажется, что |S| можно дополнительно ограничить, потому что если бы это было действительно P, то очень ясно, что остановка была бы невозможна, потому что вам пришлось бы перепрыгнуть всю взлетно-посадочную полосу с первого хода.

Так что давайте посмотрим, как мы можем поставить более жесткое ограничение для |S|. Назовем максимальную скорость S. Предположим, что мы начинаем с позиции 0. Как быстро мы могли бы остановиться, если бы пытались как можно быстрее остановиться и проигнорировать потенциальные прыжки?

tnzdVcGH4Npix6BcaJu1vGVlOkcvJo89NYgv

На первой итерации мы должны были бы подойти по крайней мере к точке (S-1), регулируя нашу скорость до нуля на -1. Оттуда мы как минимум проходили бы (S-2) шаги вперед и так далее.

Для взлетно-посадочной полосы длина Lдолжно соблюдать следующее:

=> (S-1) + (S-2) + (S-3) + ….+ 1

=> S*(S-1) / 2

=> S² — S — 2 л < 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 + 2 л)

Это максимальная скорость, которую мы могли бы иметь взлетно-посадочной полосе длиной L. Если бы у нас была скорость выше этой, мы не могли бы остановиться даже теоретически, независимо от положения шипов.

Это означает, что общая временная сложность зависит только от длины взлетно-посадочной полосы L в следующем виде:

O(L * sqrt(L)), что лучше, чем O(L²)

O(L * sqrt(L)) — это верхний предел временной сложности

Прекрасно, ты выдержал! 🙂

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

Вот несколько следующих шагов, которые вы можете сделать

  1. Расширьте образец задачи, попытавшись найти путь к точке остановки. Мы решили проблему, указывающую вам, можете ли вы остановиться, но что делать, если вы также хотите знать шаги, которые нужно предпринять, чтобы наконец остановиться вдоль взлетно-посадочной полосы? Как вы изменили бы существующую реализацию для этого?
  2. Если вы хотите закрепить свое понимание мемоизации и понять, что это просто кэш результатов функций, вам следует прочитать о декораторах в Python или подобных концепциях на других языках. Подумайте, как они позволят вам воплотить запоминание в целом для любой функции, которую вы хотите запомнить.
  3. Поработайте над другими проблемами DP, следуя прошедшим шагам. Вы всегда можете найти их в Интернете (например, LeetCode или GeeksForGeeks). Упражняясь, помните одну вещь: изучайте идеи, а не изучайте проблемы. Количество идей значительно меньше, и это легче завоевать пространство, которое также будет служить вам гораздо лучше.

Когда вы почувствуете, что преодолели эти идеи, проверьте Refdash где вас проводит собеседование со старшим инженером и получаете подробный отзыв о вашей кодировке, алгоритмах и дизайне системы.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *