Следвайте тези стъпки, за да разрешите всеки проблем с интервю за динамично програмиране

Въпреки че имат значителен опит в изграждането на софтуерни продукти, много инженери изпитват нерви при мисълта да преминат през интервю за кодиране, фокусирано върху алгоритмите. Интервюирах стотици инженери в Refdash, Google и в стартиращи компании, в които съм участвал, и някои от най-често срещаните въпроси, които създават неспокойствие на инженерите, са тези, които включват динамично програмиране (DP).

Много технологични компании обичат да задават въпроси на DP в своите интервюта. Въпреки че можем да спорим дали те са ефективни при оценяването на способността на някого да изпълнява инженерна роля, DP продължава да бъде област, която подтиква инженерите да си намерят работа, която обичат.

Динамично програмиране - Предсказуемо и подготвимо

Една от причините, поради които аз лично вярвам, че въпросите за DP може да не са най-добрият начин за тестване на инженерните способности, е, че те са предвидими и лесни за съвпадение. Те ни позволяват да филтрираме много повече за готовност, за разлика от инженерните способности.

Тези въпроси обикновено изглеждат доста сложни отвън и може да ви създадат впечатление, че човек, който ги решава, е много добър в алгоритмите. По подобен начин хората, които може да не успеят да преодолеят някои умопомрачителни концепции на DP, може да изглеждат доста слаби в познанията си за алгоритмите.

Реалността е различна и най-големият фактор за тяхното представяне е готовността. Така че нека се уверим, че всички са подготвени за това. Веднъж завинаги.

7 стъпки за решаване на проблем с динамичното програмиране

В останалата част на тази публикация ще разгледам рецепта, която можете да следвате, за да разберете дали проблемът е „проблем с DP“, както и да намерите решение на такъв проблем. По-конкретно, ще премина през следните стъпки:

  1. Как да разпознаем проблем с DP
  2. Идентифицирайте проблемни променливи
  3. Ясно изразете връзката на рецидивите
  4. Идентифицирайте основните случаи
  5. Решете дали искате да го приложите итеративно или рекурсивно
  6. Добавете запомняне
  7. Определете сложността на времето

Примерен DP проблем

За да имам пример за абстракции, които ще направя, нека въведа примерна задача. Във всеки от разделите ще се позова на проблема, но можете също да прочетете разделите независимо от проблема.

Посочване на проблема:

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

Ето правилата:

1) Дадена ви е равна писта с куп шипове в нея. ПИК е представена от булев масив, който показва дали определено (дискретно) място е без пикове. Вярно е за ясно и невярно за неясно.

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

2) Дадена ви е начална скорост S. S е неотрицателно цяло число във всяка дадена точка и показва колко ще се придвижите напред със следващия скок.

3) Всеки път, когато кацнете на място, можете да регулирате скоростта си с до 1 единица преди следващия скок.

4) Искате безопасно да спрете навсякъде по пистата (не е необходимо да е в края на масива). Спирате, когато скоростта ви стане 0. Ако обаче кацнете на шип във всяка точка, лудата ви подскачаща топка се пука и играта свършва.

Изходът на вашата функция трябва да бъде логическо, показващо дали можем безопасно да спрем навсякъде по пистата.

Стъпка 1: Как да разпознаем проблем с динамичното програмиране

Първо, нека изясним, че DP по същество е просто техника за оптимизация. DP е метод за решаване на проблеми чрез разделянето им в колекция от по-прости подпроблеми, решаването на всяка от тези подпроблеми само веднъж и съхраняване на техните решения. Следващият път, когато се появи същата подпроблема, вместо да преизчислите нейното решение, просто търсите предварително изчисленото решение. Това спестява време за изчисление за сметка на (надявам се) скромни разходи в пространството за съхранение.

Признаването, че проблемът може да бъде решен с помощта на DP, е първата и често най-трудната стъпка при решаването му. Това, което искате да си зададете, е дали вашето решение на проблема може да бъде изразено като функция от решения на подобни по-малки проблеми.

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

Това е страхотно нещо, защото с придвижването напред ние съкращаваме пистата напред и намаляваме проблема си. Трябва да можем да повтаряме този процес докрай, докато стигнем до точка, в която е очевидно дали можем да спрем.

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

Стъпка 2: Идентифицирайте проблемни променливи

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

Обикновено при интервюта ще имате един или два променящи се параметъра, но технически това може да е произволен брой. Класически пример за проблем с променящ се параметър е „определяне на n-то число на Фибоначи“. Такъв пример за проблем с променящи се параметри е „Изчисляване на разстоянието за редактиране между низовете“. Ако не сте запознати с тези проблеми, не се притеснявайте за това.

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

В нашия пример двата параметъра, които могат да се променят за всяка подпроблема, са:

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

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

Сега, с тези 2 променящи се параметъра и други статични параметри, ние имаме пълното описание на нашите подпроблеми.

Идентифицирайте променящите се параметри и определете броя на подпроблемите.

Стъпка 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)

Woohoo, изглежда, че имаме нашата рецидивираща връзка!

Рецидивираща връзка: Ако приемем, че сте изчислили подзадачите, как бихте изчислили основния проблем?

Стъпка 4: Идентифицирайте основните случаи

Основният случай е подпроблема, която не зависи от друга подпроблема. За да намерите такива подпроблеми, обикновено искате да опитате няколко примера, да видите как проблемът ви се опростява на по-малки подпроблеми и да определите в кой момент не може да бъде опростен допълнително.

Причината проблемът да не може да бъде опростен допълнително е, че един от параметрите ще се превърне в стойност, която не е възможна предвид ограниченията на проблема.

В нашия примерен проблем имаме два променящи се параметъра, S и P. Нека помислим какви възможни стойности на S и P може да не са законни:

  1. P трябва да е в рамките на дадената писта
  2. P не може да бъде такова, че пистата [P] да е фалшива, защото това би означавало, че стоим на шип
  3. S не може да бъде отрицателно, а S == 0 показва, че сме готови

Понякога може да бъде малко предизвикателно да преобразуваме твърденията, които правим относно параметрите, в програмируеми базови случаи. Това е така, защото в допълнение към изброяването на твърденията, ако искате да направите кода си кратък и да не проверявате за ненужни условия, трябва да помислите и кои от тези условия са дори възможни.

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

  1. P <0 || P> = дължината на пистата изглежда като правилното нещо. Като алтернатива може да да се разгледа м НАПРАВИМ P == край на пистата база случай. Възможно е обаче проблемът да се раздели на подпроблема, която надхвърля края на пистата, така че наистина трябва да проверим за неравенство.
  2. Това изглежда доста очевидно. Можем просто да проверим дали пистата [P] е невярна .
  3. Подобно на # 1, можем просто да проверим за S <0 и S == 0. Тук обаче можем да разсъждаваме, че е невъзможно S да бъде <0, защото S намалява най-много с 1, така че ще трябва да премине през S == 0 случай предварително. Ther реди S == 0 е достатъчно база случай за параметъра S.

Стъпка 5: Решете дали искате да го приложите итеративно или рекурсивно

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

За да решите дали да отидете итеративно или рекурсивно, искате внимателно да помислите за компромисите .

Проблемите с препълването на стека обикновено са прекъсвач на сделка и причина, поради която не бихте искали да имате рекурсия в (бекенд) производствена система. Въпреки това, за целите на интервюто, стига да споменавате компромисите, обикновено трябва да сте добре с някоя от реализациите. Трябва да се чувствате комфортно да прилагате и двете.

В конкретния ни проблем внедрих и двете версии. Ето кода на python за това:

Рекурсивно решение: (оригинални кодови фрагменти можете да намерите тук)

Итеративно решение: (оригинални кодови фрагменти можете да намерите тук)

Стъпка 6: Добавете запомняне

Мемоизирането е техника, която е тясно свързана с DP. Използва се за съхраняване на резултатите от скъпи извиквания на функции и връщане на кеширания резултат, когато същите входове се появят отново.

Защо добавяме запомняне към нашата рекурсия? Срещаме едни и същи подпроблеми, които, без запомняне, се изчисляват многократно. Тези повторения много често водят до експоненциални времеви сложности.

В рекурсивните решения добавянето на мемоизиране трябва да се чувства лесно. Да видим защо. Не забравяйте, че запомнянето е само кеш на резултатите от функцията. Има моменти, когато искате да се отклоните от тази дефиниция, за да изтласкате някои незначителни оптимизации, но третирането на мемоизирането като кеш на резултатите от функциите е най-интуитивният начин да го приложите.

Това означава, че трябва:

  1. Съхранявайте резултата от вашата функция в паметта си преди всеки оператор return
  2. Потърсете паметта за резултата от функцията, преди да започнете да правите други изчисления

Ето кода отгоре с добавена памет (добавени редове са подчертани): (оригинални кодови фрагменти можете да намерите тук)

За да илюстрираме ефективността на запомнянето и различните подходи, нека направим някои бързи тестове. Ще тествам стрес и на трите метода, които сме виждали досега. Ето настройката:

  1. Създадох писта с дължина 1000 с шипове на произволни места (избрах да има вероятност шип да е на дадено място да бъде 20%)
  2. initSpeed ​​= 30
  3. Изпълних всички функции 10 пъти и измерих средното време за изпълнение

Ето резултатите (за секунди):

Можете да видите, че чистият рекурсивен подход отнема около 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. Колко бързо бихме могли да спрем, ако се опитваме да спрем възможно най-скоро и ако пренебрегнем потенциалните скокове?

В първата итерация ще трябва да стигнем поне до точката (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-те стъпки, които преминахме, трябва да ви дадат рамка за системно решаване на всеки проблем с динамичното програмиране. Силно препоръчвам да практикувате този подход при още няколко проблема, за да усъвършенствате своя подход.

Ето няколко следващи стъпки, които можете да предприемете

  1. Разширете примерния проблем, като се опитате да намерите път до спирка. Решихме проблем, който ви казва дали можете да спрете, но какво, ако искате да знаете и стъпките, които трябва да предприемете, за да спрете в крайна сметка по пистата? Как бихте модифицирали съществуващата реализация, за да направите това?
  2. Ако искате да затвърдите разбирането си за мемоизирането и да разберете, че това е просто кеш за резултат на функция, трябва да прочетете за декоратори в Python или подобни концепции на други езици. Помислете как те биха ви позволили да приложите запомняне като цяло за всяка функция, която искате да запомните.
  3. Работете върху повече проблеми с DP, като следвате стъпките, през които преминахме. Винаги можете да намерите куп от тях онлайн (напр. LeetCode или GeeksForGeeks). Докато практикувате, имайте предвид едно: научете идеи, не научавайте проблеми. Броят на идеите е значително по-малък и това е по-лесно пространство за завладяване, което също ще ви служи много по-добре.

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

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