Slijedite ove korake da biste riješili bilo koji problem razgovora s dinamičkim programiranjem

Iako imaju značajno iskustvo u gradnji softverskih proizvoda, mnogi inženjeri osjećaju se nervozno kad pomisle da prolaze kroz kodiranje intervjua koji se fokusira na algoritme. Ispitao sam stotine inženjera u Refdashu, Googleu i kod startupa čiji sam dio bio, a neka od najčešćih pitanja koja inženjere čine nelagodnima su ona koja uključuju dinamičko programiranje (DP).

Mnoge tehnološke tvrtke vole postavljati pitanja DP-u u svojim intervjuima. Iako možemo raspravljati o tome jesu li učinkoviti u procjeni nečije sposobnosti za obavljanje inženjerske uloge, DP je i dalje područje koje inženjere izvodi na put da pronađu posao koji vole.

Dinamičko programiranje - predvidljivo i pripremljivo

Jedan od razloga zašto osobno vjerujem da DP pitanja možda nisu najbolji način za testiranje inženjerske sposobnosti jest taj što su predvidljiva i jednostavna za podudaranje. Omogućuju nam da filtriramo mnogo više za spremnost za razliku od inženjerskih sposobnosti.

Ta se pitanja obično izvana čine prilično složenima i mogu stvoriti dojam da je osoba koja ih rješava vrlo dobra u algoritmima. Slično tome, ljudi koji možda neće moći preboljeti neke koncepte DP-a koji zamahuju, mogu izgledati prilično slabo u svom znanju algoritama.

Stvarnost je drugačija, a najveći faktor u njihovom nastupu je spremnost. Stoga pobrinimo se da su svi spremni za to. Jednom zauvijek.

7 koraka za rješavanje problema s dinamičkim programiranjem

U ostatku ovog posta pregledat ću recept koji možete slijediti da biste utvrdili je li problem "problem s DP-om", kao i da biste pronašli rješenje za takav problem. Konkretno, proći ću sljedeće korake:

  1. Kako prepoznati problem s DP-om
  2. Prepoznajte varijable problema
  3. Jasno izrazite odnos ponavljanja
  4. Utvrdite osnovne slučajeve
  5. Odlučite želite li ga primijeniti iterativno ili rekurzivno
  6. Dodajte memoizaciju
  7. Odredite vremensku složenost

Uzorak DP problema

U svrhu davanja primjera za apstrakcije koje ću izvesti, dopustite mi da predstavim problem s uzorkom. U svakom od odjeljaka pozvat ću se na problem, ali odjeljke biste mogli pročitati i neovisno o problemu.

Izjava o problemu:

U ovom smo problemu na ludoj skakačkoj lopti, pokušavajući se zaustaviti, a usput izbjegavamo šiljke.

Evo pravila:

1) Dobili ste ravnu pistu s gomilom šiljaka. Pista je predstavljena logičkim nizom koji pokazuje je li određeno (diskretno) mjesto bez šiljaka. Točno je za jasno, a Lažno za nejasno.

Primjer predstavljanja niza:

2) Dobivate početnu brzinu S. S je negativan cijeli broj u bilo kojoj danoj točki i pokazuje koliko ćete se pomicati naprijed sljedećim skokom.

3) Svaki put kad sletite na mjesto, možete prilagoditi brzinu do 1 jedinice prije sljedećeg skoka.

4) Želite se sigurno zaustaviti bilo gdje uz pistu (ne mora biti na kraju niza). Zaustavljate se kada vaša brzina postane 0. Međutim, ako u bilo kojem trenutku sletite na šiljak, vaša luda odskočna kugla pukne i igra je gotova.

Izlaz vaše funkcije trebao bi biti logička vrijednost koja pokazuje možemo li se sigurno zaustaviti bilo gdje uz pistu.

Korak 1: Kako prepoznati problem dinamičkog programiranja

Prvo, razjasnimo da je DP u osnovi samo tehnika optimizacije. DP je metoda za rješavanje problema raščlanjivanjem na skup jednostavnijih podproblema, rješavanjem svakog od tih podproblema samo jednom i pohranjivanjem njihovih rješenja. Sljedeći put kad se dogodi isti podproblem, umjesto ponovnog izračunavanja njegovog rješenja, jednostavno potražite prethodno izračunato rješenje. To štedi vrijeme računanja na štetu (nadam se) skromnih izdataka u skladišnom prostoru.

Prepoznavanje da se problem može riješiti DP-om prvi je i često najteži korak u njegovom rješavanju. Ono što se želite zapitati jest može li se vaše rješenje problema izraziti u funkciji rješenja sličnih manjih problema.

U slučaju našeg primjera problema, s obzirom na točku na pisti, brzinu i pistu ispred, mogli bismo odrediti mjesta na kojima bismo mogli sljedeći skok. Nadalje, čini se da možemo li se zaustaviti s trenutne točke trenutnom brzinom ovisi samo o tome možemo li se zaustaviti od točke koju odaberemo da pređemo na sljedeću.

To je sjajna stvar, jer kretanjem naprijed skraćujemo pistu naprijed i smanjujemo svoj problem. Morali bismo biti u mogućnosti ponavljati ovaj postupak sve dok ne dođemo do točke u kojoj je očito možemo li se zaustaviti.

Prepoznavanje problema s dinamičkim programiranjem često je najteži korak u njegovom rješavanju. Može li se rješenje problema izraziti u funkciji rješenja sličnih manjih problema?

Korak 2: Utvrdite varijable problema

Sada smo ustanovili da postoji neka rekurzivna struktura između naših podproblema. Dalje, problem moramo izraziti u smislu parametara funkcije i vidjeti koji se od tih parametara mijenja.

Tipično u intervjuima imat ćete jedan ili dva parametra koji se mijenjaju, ali tehnički to može biti bilo koji broj. Klasični primjer problema s jednim parametrom koji se mijenja je "odrediti n-ti Fibonaccijev broj". Takav primjer za problem s dva parametra koji se mijenjaju je "Izračunaj udaljenost udaljenosti između nizova". Ako niste upoznati s tim problemima, ne brinite zbog toga.

Način da se utvrdi broj promjenjivih parametara je navođenje primjera nekoliko potproblema i usporedba parametara. Brojanje broja promjena parametara dragocjeno je za određivanje broja potproblema koje moramo riješiti. To je također važno samo po sebi, pomažući nam da ojačamo razumijevanje odnosa ponavljanja iz koraka 1.

U našem primjeru, dva parametra koja se mogu promijeniti za svaki potproblem su:

  1. Položaj niza (P)
  2. Brzina (S)

Moglo bi se reći da se i pista naprijed mijenja, ali to bi bilo suvišno s obzirom na to da cijela pista koja se ne mijenja i položaj (P) već nose te informacije.

Sada, s ova dva parametra koja se mijenjaju i ostalim statičkim parametrima, imamo cjelovit opis naših pod-problema.

Utvrdite parametre koji se mijenjaju i odredite broj potproblema.

Korak 3: Jasno izrazite odnos ponavljanja

Ovo je važan korak kroz koji mnogi žure kako bi ušli u kodiranje. Što jasnije izražavanje relacija recidiva ojačat će razumijevanje vašeg problema i sve ostalo znatno olakšati.

Jednom kada shvatite da relacija ponavljanja postoji i odredite probleme u smislu parametara, to bi trebao doći kao prirodni korak. Kako se problemi međusobno povezuju? Drugim riječima, pretpostavimo da ste izračunali potprobleme. Kako biste izračunali glavni problem?

Evo kako o tome razmišljamo u našem primjeru problema:

Budući da možete prilagoditi brzinu do 1 prije skoka u sljedeći položaj, postoje samo 3 moguće brzine, a time i 3 mjesta u kojima bismo mogli biti sljedeći.

Formalnije, ako je naša brzina S, položaj P, mogli bismo prijeći iz (S, P) u:

  1. (S, P + S) ; # ako ne promijenimo brzinu
  2. (S - 1, P + S - 1) ; # ako promijenimo brzinu za -1
  3. (S + 1, P + S + 1) ; # ako promijenimo brzinu za +1

Ako možemo pronaći način da se zaustavimo u bilo kojem od gore navedenih potproblema, onda možemo zaustaviti i od (S, P). To je zato što možemo prijeći iz (S, P) u bilo koju od gornje tri mogućnosti.

Ovo je obično dobra razina razumijevanja problema (objašnjenje na engleskom jeziku), ali ponekad biste možda željeli izraziti odnos i matematički. Nazovimo funkciju koju pokušavamo izračunati canStop. Zatim:

canStop (S, P) = canStop (S, P + S) || canStop (S - 1, P + S - 1) || canStop (S + 1, P + S + 1)

Woohoo, čini se da imamo svoj odnos ponavljanja!

Odnos ponavljanja: Pod pretpostavkom da ste izračunali podprobleme, kako biste izračunali glavni problem?

Korak 4: Utvrdite osnovne slučajeve

Osnovni slučaj je potproblem koji ne ovisi o bilo kojem drugom podproblemu. Da biste pronašli takve potprobleme, obično želite isprobati nekoliko primjera, vidjeti kako se vaš problem pojednostavljuje u manje potprobleme i prepoznati u kojem se trenutku ne može dodatno pojednostaviti.

Razlog zbog kojeg se problem ne može dodatno pojednostaviti je taj što bi jedan od parametara postao vrijednost koja nije moguća s obzirom na ograničenja problema.

U našem primjeru problema imamo dva parametra koji se mijenjaju, S i P. Razmislimo o tome koje moguće vrijednosti S i P možda nisu legalne:

  1. P bi trebao biti u granicama zadane piste
  2. P ne može biti takav da je pista [P] lažna jer bi to značilo da stojimo na šiljku
  3. S ne može biti negativan, a S == 0 znači da smo završili

Ponekad može biti malo izazovno pretvoriti tvrdnje koje iznosimo o parametrima u programabilne osnovne slučajeve. To je zato što, osim navođenja tvrdnji ako želite da vaš kod izgleda sažeto i ne provjerava nepotrebne uvjete, morate razmisliti i koji su od tih uvjeta uopće mogući.

U našem primjeru:

  1. P <0 || P> = duljina piste čini se ispravnom stvari. Alternativa bi mogla biti uzeti u obzir m aking p == kraj piste baza slučaj. Međutim, moguće je da se problem podijeli na potproblem koji prelazi kraj piste, pa stvarno moramo provjeriti nejednakost.
  2. To se čini prilično očitim. Jednostavno možemo provjeriti je li pista lažna .
  3. Slično # 1, mogli bismo jednostavno provjeriti je li S <0 i S == 0. Međutim, ovdje možemo zaključiti da je nemoguće da S bude <0, jer se S smanjuje za najviše 1, pa bi to trebalo proći S == 0 slučaj unaprijed. Ther efore S == 0 dovoljan baza slučaj za parametar.

Korak 5: Odlučite želite li ga primijeniti iterativno ili rekurzivno

Način na koji smo razgovarali o dosadašnjim koracima mogao bi vas navesti na pomisao da bismo problem trebali primijeniti rekurzivno. Međutim, sve o čemu smo do sada razgovarali potpuno je agnostično odlučujete li problem primijeniti rekurzivno ili iterativno. U oba pristupa morali biste odrediti odnos ponavljanja i osnovne slučajeve.

Da biste odlučili želite li ići iterativno ili rekurzivno, želite pažljivo razmisliti o kompromisima .

Problemi s preljevom steka obično su prekid dogovora i razlog zašto ne biste željeli imati rekurziju u (pozadinskom) proizvodnom sustavu. Međutim, za potrebe intervjua, sve dok spominjete kompromise, obično biste trebali biti u redu s bilo kojom primjenom. Trebali biste se osjećati ugodno provodeći oboje.

U našem konkretnom problemu implementirao sam obje verzije. Evo python koda za to:

Rekurzivno rješenje: (originalne isječke koda možete pronaći ovdje)

Iterativno rješenje: (izvorne isječke koda možete pronaći ovdje)

Korak 6: Dodajte memoizaciju

Memoizacija je tehnika koja je usko povezana s DP-om. Koristi se za spremanje rezultata skupih poziva funkcije i vraćanje predmemoriranog rezultata kada se ponove isti ulazi.

Zašto svojoj rekurziji dodajemo memoizaciju? Nailazimo na iste podprobleme koji se bez pamćenja ponavljaju više puta. Ta ponavljanja vrlo često dovode do eksponencijalnih vremenskih složenosti.

U rekurzivnim rješenjima dodavanje pamćenja trebalo bi se osjećati jednostavno. Da vidimo zašto. Imajte na umu da je pamćenje samo predmemorija rezultata funkcije. Postoje slučajevi kada želite odstupiti od ove definicije kako biste iscijedili neke manje optimizacije, ali tretiranje memoizacije kao predmemorije rezultata funkcije najintuitivniji je način za njezinu primjenu.

To znači da biste trebali:

  1. Rezultat funkcije pohranite u svoju memoriju prije svake naredbe return
  2. Potražite memoriju za rezultat funkcije prije nego što počnete raditi bilo koje drugo izračunavanje

Evo koda odozgo s dodanom memorizacijom (istaknuti su dodani redovi): (originalne isječke koda možete pronaći ovdje)

Kako bismo prikazali učinkovitost pamćenja i različitih pristupa, napravimo nekoliko brzih testova. Testirat ću stres sve tri metode koje smo do sada vidjeli. Evo postavljanja:

  1. Napravio sam pistu duljine 1000 s šiljcima na slučajnim mjestima (odabrao sam da vjerojatnost da se šiljak nalazi na bilo kojem mjestu bude 20%)
  2. initSpeed ​​= 30
  3. Sve sam funkcije pokrenuo 10 puta i izmjerio prosječno vrijeme izvršavanja

Evo rezultata (u sekundama):

Možete vidjeti da čisti rekurzivni pristup traje oko 500x više vremena od iterativnog pristupa i oko 1300x više vremena od rekurzivnog pristupa s memoizacijom. Imajte na umu da bi ovo odstupanje brzo raslo s duljinom piste. Potičem vas da ga sami pokušate pokrenuti.

Korak 7: Odredite vremensku složenost

Postoje nekoliko jednostavnih pravila koja mogu znatno olakšati vremensku složenost problema dinamičkog programiranja. Evo dva koraka koja trebate učiniti:

  1. Prebrojite broj stanja - to će ovisiti o broju promjena parametara u vašem problemu
  2. Razmislite o obavljenom poslu u svakoj državi. Drugim riječima, ako je izračunato sve drugo, osim jednog stanja, koliko posla morate napraviti da biste izračunali to posljednje stanje?

U našem primjeru problema, broj stanja je | P | * | S |, gdje

  • P je skup svih položaja (| P | označava broj elemenata u P)
  • S je skup svih brzina

Rad po svakom stanju u ovom je problemu O (1), jer, s obzirom na sva ostala stanja, jednostavno moramo pogledati 3 potproblema kako bismo odredili rezultirajuće stanje.

Kao što smo već primijetili u kodu, | S | je ograničena duljinom piste (| P |), pa bismo mogli reći da je broj stanja | P | ², a budući da je rad po svakoj državi O (1), tada je ukupna vremenska složenost O (| P | ²).

Međutim, čini se da je | S | može se dodatno ograničiti, jer da je to stvarno | P |, vrlo je jasno da zaustavljanje ne bi bilo moguće jer biste u prvom potezu morali preskočiti duljinu cijele piste.

Pa da vidimo kako možemo strože vezati | S |. Nazovimo maksimalnu brzinu S. Pretpostavimo da krećemo s položaja 0. Koliko brzo bismo se mogli zaustaviti ako se pokušavamo zaustaviti što prije i ako zanemarimo potencijalne skokove?

U prvoj iteraciji morali bismo doći barem do točke (S-1), podešavanjem brzine na nuli za -1. Odatle bismo barem prošli (S-2) korake naprijed i tako dalje.

Za pistu duljine L mora biti sljedeće:

=> (S-1) + (S-2) + (S-3) + .... + 1 <L

=> S * (S-1) / 2 <L

=> S² - S - 2L <0

Ako pronađete korijene gornje funkcije, oni će biti:

r1 = 1/2 + sqrt (1/4 + 2L) i r2 = 1/2 - sqrt (1/4 + 2L)

Svoju nejednakost možemo zapisati kao:

(S - r1) * (S - r2) < ; 0

S obzirom da je S - r2> 0 za bilo koji S> 0 i L> 0, trebamo sljedeće:

S - 1/2 - sqrt (1/4 + 2L) < ; 0

=> S <1/2 + sqrt (1/4 + 2L)

To je maksimalna brzina koju bismo eventualno mogli imati na pisti duljine L. Da imamo brzinu veću od te, ne bismo se mogli zaustaviti ni teoretski, bez obzira na položaj bodlji.

To znači da ukupna vremenska složenost ovisi samo o duljini piste L u sljedećem obliku:

O (L * sqrt (L)) što je bolje od O (L²)

O (L * sqrt (L)) je gornja granica vremenske složenosti

Sjajno, uspjeli ste! :)

Sedam koraka koje smo prošli trebali bi vam dati okvir za sustavno rješavanje bilo kojeg problema s dinamičkim programiranjem. Toplo preporučujem vježbanje ovog pristupa na još nekoliko problema kako biste usavršili svoj pristup.

Evo nekoliko sljedećih koraka koje možete poduzeti

  1. Proširite problem uzorka pokušavajući pronaći put do točke zaustavljanja. Riješili smo problem koji vam govori možete li se zaustaviti, ali što ako biste željeli znati i korake kako biste se na kraju zaustavili duž piste? Kako biste modificirali postojeću implementaciju da to učini?
  2. Ako želite učvrstiti svoje razumijevanje pamćenja i shvatite da je to samo predmemorija rezultata funkcije, trebali biste pročitati o dekoraterima u Pythonu ili sličnim konceptima na drugim jezicima. Razmislite o tome kako bi vam omogućili da uopće primijenite memoiziranje za bilo koju funkciju koju želite memorirati.
  3. Radite na više problema s DP-om slijedeći korake koje smo prošli. Mnoštvo ih uvijek možete pronaći na mreži (npr. LeetCode ili GeeksForGeeks). Dok vježbate, imajte na umu jedno: učite ideje, ne učite probleme. Broj ideja je znatno manji i to je lakši prostor za osvajanje, koji će vam također poslužiti puno bolje.

Kad se osjećate kao da ste pobijedili ove ideje, provjerite Refdash gdje vas intervjuira stariji inženjer i dobit ćete detaljne povratne informacije o svom kodiranju, algoritmima i dizajnu sustava.

Izvorno objavljeno na blogu Refdash. Refdash je platforma za intervjuiranje koja pomaže inženjerima da anonimno intervjuiraju iskusne inženjere iz vodećih tvrtki poput Googlea, Facebooka ili Palantira i dobiju detaljne povratne informacije. Refdash također pomaže inženjerima otkriti nevjerojatne mogućnosti za posao na temelju njihovih vještina i interesa.