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

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

Багато технологічних компаній люблять задавати питання про ДП у своїх інтерв’ю. Хоча ми можемо обговорювати, чи ефективно вони оцінюють чиюсь здатність виконувати інженерну роль, DP продовжує залишатися сферою, яка спонукає інженерів на шляху до пошуку роботи, яку вони люблять.

Динамічне програмування - передбачуване та підготовлене

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

Зазвичай ці питання здаються досить складними і можуть скласти враження, що людина, яка їх вирішує, дуже добре володіє алгоритмами. Подібним чином, люди, які можуть бути не в змозі перебороти деякі заплутані концепції ДП, можуть здатися досить слабкими у своїх знаннях алгоритмів.

Реальність інша, і найбільшим фактором їхньої діяльності є готовність. Тож давайте переконаємось, що всі до цього готові. Раз і назавжди.

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

В решті цього допису я розгляну рецепт, за яким ви можете слідувати, щоб зрозуміти, чи є проблема «проблемою ДП», а також знайти рішення такої проблеми. Зокрема, я пройду наступні кроки:

  1. Як розпізнати проблему DP
  2. Визначте змінні проблеми
  3. Чітко висловіть відношення рецидиву
  4. Визначте базові випадки
  5. Вирішіть, чи хочете ви реалізувати це ітеративно або рекурсивно
  6. Додайте мемоїзацію
  7. Визначте складність часу

Зразок проблеми DP

Для того, щоб мати приклад для абстракцій, який я збираюся зробити, дозвольте мені представити зразок проблеми. У кожному з розділів я буду посилатися на проблему, але ви також можете прочитати розділи незалежно від проблеми.

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

У цій проблемі ми на божевільному стрибку, намагаючись зупинитися, уникаючи при цьому шипів.

Ось правила:

1) Вам дають рівну злітно-посадкову смугу з купою шипів. Злітно-посадкова смуга представлена ​​булевим масивом, який вказує, чи не спостерігається певне (дискретне) місце з шипами. Це правда для чіткого і False для ясного.

Приклад подання масиву:

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)

Вуху, здається, у нас є своє відношення до повторень!

Відношення рецидивів: якщо припустити, що ви обчислили підзадачі, як би ви обчислили основну проблему?

Крок 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 Efore S == 0 є достатнім базовим випадком для параметра S.

Крок 5: Вирішіть, чи хочете ви реалізувати це ітеративно або рекурсивно

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

Щоб вирішити, йти ітеративно чи рекурсивно, потрібно ретельно продумати компроміси .

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

У нашій конкретній проблемі я застосував обидві версії. Ось код python для цього:

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

Ітераційне рішення: (оригінальні фрагменти коду можна знайти тут)

Крок 6: Додайте мемоізацію

Мемоізація - це техніка, яка тісно пов’язана з ДП. Він використовується для зберігання результатів дорогих викликів функцій і повернення кешованого результату, коли ті самі входи повторюються знову.

Чому ми додаємо мемоїзацію до нашої рекурсії? Ми стикаємось з тими ж підзадачами, які без мемоїзації обчислюються неодноразово. Ці повторення дуже часто призводять до експоненціальних часових складностей.

У рекурсивних рішеннях додавання мемоїзації повинно бути простим. Подивимось чому. Пам'ятайте, що запам'ятовування - це лише кеш результатів функції. Бувають випадки, коли ви хочете відступити від цього визначення, щоб вижати деякі незначні оптимізації, але розглядати мемоїзацію як кеш результату функції є найбільш інтуїтивним способом її реалізації.

Це означає, що ви повинні:

  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. Попрацюйте над більшою кількістю проблем із ДП, дотримуючись кроків, які ми пройшли. Ви завжди можете знайти їх купу в Інтернеті (наприклад, LeetCode або GeeksForGeeks). Практикуючись, майте на увазі одне: вчіть ідеї, не вчіть проблем. Кількість ідей значно менша, і це простіший простір для перемоги, який також допоможе вам набагато краще.

Коли ви відчуєте, що перемогли ці ідеї, перевірте Refdash, де вас опитує старший інженер, і отримайте детальний відгук про своє кодування, алгоритми та дизайн системи.

Спочатку опубліковано в блозі Refdash. Refdash - це платформа для проведення інтерв’ю, яка допомагає інженерам проводити анонімне інтерв’ю з досвідченими інженерами з провідних компаній, таких як Google, Facebook або Palantir, та отримати детальний відгук. Refdash також допомагає інженерам відкривати дивовижні можливості працевлаштування на основі їхніх навичок та інтересів.