Følg disse trin for at løse ethvert dynamisk programmeringsinterviewsproblem

På trods af at de har stor erfaring med at opbygge softwareprodukter, føler mange ingeniører nervøse ved tanken om at gennemgå et kodningssamtale, der fokuserer på algoritmer. Jeg har interviewet hundreder af ingeniører hos Refdash, Google og ved opstart, jeg har været en del af, og nogle af de mest almindelige spørgsmål, der gør ingeniører urolige, er dem, der involverer dynamisk programmering (DP).

Mange teknologivirksomheder kan lide at stille DP-spørgsmål i deres interviews. Mens vi kan diskutere, om de er effektive til at evaluere nogens evne til at udføre en ingeniørrolle, er DP fortsat et område, der får ingeniører til at finde et job, de elsker.

Dynamisk programmering - forudsigelig og klar

En af grundene til, at jeg personligt mener, at DP-spørgsmål måske ikke er den bedste måde at teste ingeniørfærdighed på, er at de er forudsigelige og lette at matche. De giver os mulighed for at filtrere meget mere for beredskab i modsætning til teknisk evne.

Disse spørgsmål virker typisk ret komplekse udefra og kan give dig et indtryk af, at en person, der løser dem, er meget god til algoritmer. Tilsvarende kan folk, der muligvis ikke er i stand til at komme over nogle tankegangskoncepter for DP, virke ret svage i deres viden om algoritmer.

Virkeligheden er anderledes, og den største faktor i deres præstationer er beredskab. Så lad os sørge for, at alle er forberedt på det. Én gang for alle.

7 trin til løsning af et dynamisk programmeringsproblem

I resten af ​​dette indlæg vil jeg gennemgå en opskrift, som du kan følge for at finde ud af, om et problem er et "DP-problem" samt for at finde ud af en løsning på et sådant problem. Specifikt vil jeg gennemgå følgende trin:

  1. Sådan genkendes et DP-problem
  2. Identificer problemvariabler
  3. Udtryk tydeligt gentagelsesforholdet
  4. Identificer basissagerne
  5. Beslut om du vil implementere det iterat eller rekursivt
  6. Tilføj memoization
  7. Bestem tidskompleksitet

Eksempel på DP-problem

Med det formål at have et eksempel på abstraktioner, som jeg vil lave, lad mig introducere et eksempel på et problem. I hvert af afsnittene vil jeg henvise til problemet, men du kan også læse sektionerne uafhængigt af problemet.

Problemformulering:

I dette problem er vi på en skør hoppebold, der prøver at stoppe, mens vi undgår pigge undervejs.

Her er reglerne:

1) Du får en flad landingsbane med en flok pigge i. Banen er repræsenteret af en boolsk matrix, der angiver, om et bestemt (diskret) sted er fri for pigge. Det er sandt for klart og falsk for ikke klart.

Eksempel på matrixrepræsentation:

2) Du får en starthastighed S. S er et ikke-negativt heltal på et givet punkt, og det indikerer, hvor meget du vil bevæge dig fremad med næste spring.

3) Hver gang du lander på et sted, kan du justere din hastighed med op til 1 enhed inden næste spring.

4) Du vil sikkert stoppe hvor som helst langs landingsbanen (behøver ikke være i slutningen af ​​arrayet). Du stopper, når din hastighed bliver 0. Hvis du når som helst lander på en spids, brister din skøre hoppende bold, og den er slut.

Resultatet af din funktion skal være en boolsk, der indikerer, om vi sikkert kan stoppe hvor som helst langs landingsbanen.

Trin 1: Sådan genkendes et dynamisk programmeringsproblem

Lad os først gøre det klart, at DP egentlig kun er en optimeringsteknik. DP er en metode til løsning af problemer ved at nedbryde dem i en samling af enklere delproblemer, løse hvert af disse underproblemer kun én gang og gemme deres løsninger. Næste gang det samme underproblem opstår, i stedet for at beregne løsningen igen, skal du blot slå den tidligere beregnede løsning op. Dette sparer beregningstid på bekostning af en (forhåbentlig) beskeden udgift på lagerplads.

At erkende, at et problem kan løses ved hjælp af DP, er det første og ofte det sværeste trin i at løse det. Hvad du vil spørge dig selv er, om din problemløsning kan udtrykkes som en funktion af løsninger på lignende mindre problemer.

I tilfælde af vores eksempelproblem, givet et punkt på landingsbanen, en hastighed og landingsbanen fremad, kunne vi bestemme de steder, hvor vi potentielt kunne hoppe næste. Desuden ser det ud til, at om vi kan stoppe fra det aktuelle punkt med den aktuelle hastighed, kun afhænger af, om vi kunne stoppe fra det punkt, vi vælger at gå til næste.

Det er en stor ting, for ved at komme videre forkorter vi landingsbanen fremad og gør vores problem mindre. Vi skal være i stand til at gentage denne proces, indtil vi kommer til et punkt, hvor det er indlysende, om vi kan stoppe.

At anerkende et dynamisk programmeringsproblem er ofte det sværeste skridt til at løse det. Kan problemløsningen udtrykkes som en funktion af løsninger på lignende mindre problemer?

Trin 2: Identificer problemvariabler

Nu har vi fastslået, at der er en eller anden rekursiv struktur mellem vores underproblemer. Dernæst er vi nødt til at udtrykke problemet med hensyn til funktionsparametrene og se, hvilke af disse parametre der ændrer sig.

Typisk i interviews vil du have en eller to skiftende parametre, men teknisk set kan dette være et hvilket som helst tal. Et klassisk eksempel på et problem med én ændring af parametre er "bestem et n. Fibonacci-nummer". Et sådant eksempel på et problem med to ændringer af parametre er "Beregn redigeringsafstand mellem strenge". Hvis du ikke er bekendt med disse problemer, skal du ikke bekymre dig om det.

En måde at bestemme antallet af skiftende parametre på er at liste eksempler på flere underproblemer og sammenligne parametrene. At tælle antallet af skiftende parametre er værdifuldt for at bestemme antallet af underproblemer, vi skal løse. Det er også vigtigt i sig selv at hjælpe os med at styrke forståelsen af ​​gentagelsesforholdet fra trin 1.

I vores eksempel er de to parametre, der kan ændres for hvert underproblem:

  1. Matrixposition (P)
  2. Hastighed (S)

Man kan sige, at landingsbanen forude også ændrer sig, men det ville være overflødigt i betragtning af at hele den ikke-skiftende landingsbane og positionen (P) allerede har denne information.

Nu, med disse 2 skiftende parametre og andre statiske parametre, har vi den komplette beskrivelse af vores underproblemer.

Identificer de skiftende parametre, og bestem antallet af underproblemer.

Trin 3: Udtryk tydeligt gentagelsesforholdet

Dette er et vigtigt skridt, som mange skynder sig for at komme ind i kodning. At udtrykke gentagelsesforholdet så tydeligt som muligt vil styrke din problemforståelse og gøre alt andet væsentligt lettere.

Når du har fundet ud af, at gentagelsesforholdet eksisterer, og du angiver problemerne med hensyn til parametre, skal dette komme som et naturligt trin. Hvordan relaterer problemer sig til hinanden? Lad os med andre ord antage, at du har beregnet delproblemerne. Hvordan ville du beregne hovedproblemet?

Sådan tænker vi over det i vores prøveproblem:

Fordi du kan justere din hastighed med op til 1, før du hopper til næste position, er der kun 3 mulige hastigheder, og derfor 3 steder, hvor vi kunne være næste.

Mere formelt, hvis vores hastighed er S, position P, kan vi gå fra (S, P) til:

  1. (S, P + S) ; # hvis vi ikke ændrer hastigheden
  2. (S - 1, P + S - 1) ; # hvis vi ændrer hastigheden med -1
  3. (S + 1, P + S + 1) ; # hvis vi ændrer hastigheden med +1

Hvis vi kan finde en måde at stoppe i et af underproblemerne ovenfor, kan vi også stoppe fra (S, P). Dette skyldes, at vi kan skifte fra (S, P) til en af ​​ovenstående tre muligheder.

Dette er typisk et godt niveau af forståelse af problemet (almindelig engelsk forklaring), men du vil nogle gange måske også udtrykke forholdet matematisk. Lad os kalde en funktion, som vi prøver at beregne canStop. Derefter:

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

Woohoo, det ser ud til, at vi har vores gentagelsesforhold!

Gentagelsesforhold: Hvis du antager, at du har beregnet delproblemerne, hvordan ville du beregne hovedproblemet?

Trin 4: Identificer basissagerne

En basissag er et underproblem, der ikke afhænger af noget andet underproblem. For at finde sådanne underproblemer ønsker du typisk at prøve et par eksempler, se hvordan dit problem forenkles til mindre delproblemer og identificere på hvilket tidspunkt det ikke kan forenkles yderligere.

Årsagen til, at et problem ikke kan forenkles yderligere, er, at en af ​​parametrene bliver en værdi, der ikke er mulig i betragtning af problemets begrænsninger .

I vores eksempelproblem har vi to skiftende parametre, S og P. Lad os tænke over, hvilke mulige værdier af S og P, der muligvis ikke er lovlige:

  1. P skal være inden for den givne landingsbanes grænser
  2. P kan ikke være sådan, at landingsbane [P] er falsk, fordi det vil betyde, at vi står på en spids
  3. S kan ikke være negativ, og en S == 0 indikerer, at vi er færdige

Nogle gange kan det være lidt udfordrende at konvertere påstande, som vi fremsætter om parametre, til programmerbare basissager. Dette skyldes, at ud over at anføre påstandene, hvis du vil få din kode til at se kort og ikke kontrollere unødvendige forhold, skal du også overveje, hvilke af disse betingelser der endda er mulige.

I vores eksempel:

  1. P <0 || P> = landingsbanens længde virker som den rigtige ting at gøre. Et alternativ kan være at overveje at lave P == ende af landingsbane som en basissag. Det er dog muligt, at et problem opdeles i et underproblem, der går ud over enden af ​​landingsbanen, så vi er virkelig nødt til at kontrollere for ulighed.
  2. Dette virker ret åbenlyst. Vi kan bare kontrollere, om landingsbane [P] er falsk .
  3. Svarende til nr. 1 kunne vi simpelthen kontrollere for S <0 og S == 0. Her kan vi dog begrunde, at det er umuligt for S at være <0, fordi S falder med højst 1, så det bliver nødt til at gå igennem S == 0 sag på forhånd. Ther efore S == 0 er en tilstrækkelig base tilfældet for S parameter.

Trin 5: Beslut om du vil implementere det iterativt eller rekursivt

Den måde, vi har talt om trinnene hidtil, kan få dig til at tænke, at vi skal implementere problemet rekursivt. Alt, hvad vi hidtil har talt om, er imidlertid helt agnostisk for, om du beslutter at implementere problemet rekursivt eller iterativt. I begge tilgange skal du bestemme gentagelsesrelationen og basissagerne.

For at beslutte, om du vil gå iterativt eller rekursivt, vil du nøje overveje kompromiserne .

Stackoverløbsproblemer er typisk en deal breaker og en grund til, at du ikke ønsker at have rekursion i et (backend) produktionssystem. Men med henblik på interviewet, så længe du nævner kompromiserne, skal du typisk have det godt med nogen af ​​implementeringerne. Du skal have det godt med at implementere begge dele.

I vores særlige problem implementerede jeg begge versioner. Her er pythonkode til det:

En rekursiv løsning: (originale kodestykker kan findes her)

En iterativ løsning: (originale kodestykker kan findes her)

Trin 6: Tilføj memoization

Memoization er en teknik, der er tæt forbundet med DP. Det bruges til at gemme resultaterne af dyre funktionsopkald og returnere det cachelagrede resultat, når de samme indgange forekommer igen.

Hvorfor tilføjer vi memoization til vores rekursion? Vi støder på de samme delproblemer, som uden memoization beregnes gentagne gange. Disse gentagelser fører ofte til eksponentielle tidskompleksiteter.

I rekursive løsninger skal tilføjelse af memoisering føles ligetil. Lad os se hvorfor. Husk, at memoization kun er en cache af funktionsresultaterne. Der er tidspunkter, hvor du vil afvige fra denne definition for at presse nogle mindre optimeringer ud, men behandling af memoization som et funktionsresultat cache er den mest intuitive måde at implementere den på.

Dette betyder, at du skal:

  1. Opbevar din funktion resultat i din hukommelse før hver tilbagevenden opgørelse
  2. Slå hukommelsen op for funktionsresultatet, inden du begynder at foretage andre beregninger

Her er koden ovenfra med tilføjet memoization (tilføjede linjer er fremhævet): (originale kodestykker kan findes her)

For at illustrere effektiviteten af ​​memoization og forskellige tilgange, lad os lave nogle hurtige tests. Jeg vil stresstest alle tre metoder, som vi hidtil har set. Her er opsætningen:

  1. Jeg oprettede en landingsbane med længde 1000 med spidser tilfældige steder (jeg valgte at have en sandsynlighed for, at en spids på et givet sted var 20%)
  2. initSpeed ​​= 30
  3. Jeg kørte alle funktioner 10 gange og målte den gennemsnitlige udførelsestid

Her er resultaterne (i sekunder):

Du kan se, at den rene rekursive tilgang tager cirka 500 gange mere tid end den iterative tilgang og cirka 1300 gange mere tid end den rekursive tilgang med memoization. Bemærk, at denne uoverensstemmelse vil vokse hurtigt med landingsbanens længde. Jeg opfordrer dig til at prøve at køre det selv.

Trin 7: Bestem tidskompleksitet

Der er nogle enkle regler, der kan gøre computertidskompleksiteten af ​​et dynamisk programmeringsproblem meget lettere. Her er to trin, du skal gøre:

  1. Tæl antallet af stater - dette afhænger af antallet af skiftende parametre i dit problem
  2. Tænk på det arbejde, der er udført pr. Stat. Med andre ord, hvis alt andet end en tilstand er beregnet, hvor meget arbejde skal du gøre for at beregne den sidste tilstand?

I vores eksempelproblem er antallet af stater | P | * | S | hvor

  • P er sættet med alle positioner (| P | angiver antallet af elementer i P)
  • S er sættet med alle hastigheder

Arbejdet udført pr. Hver stat er O (1) i dette problem, fordi vi i betragtning af alle andre tilstande blot skal se på 3 underproblemer for at bestemme den resulterende tilstand.

Som vi bemærkede i koden før, | S | er begrænset af landingsbanens længde (| P |), så vi kan sige, at antallet af stater er | P | ², og fordi arbejde udført pr. tilstand er O (1), så er den samlede tidskompleksitet O (| P | ²).

Det ser imidlertid ud til, at | S | kan begrænses yderligere, for hvis det virkelig var | P |, er det meget klart, at stoppe ikke ville være muligt, fordi du skulle springe længden af ​​hele landingsbanen ved første træk.

Så lad os se, hvordan vi kan lægge en strammere bånd på | S |. Lad os kalde maksimumhastighed S. Antag, at vi starter fra position 0. Hvor hurtigt kunne vi stoppe, hvis vi forsøgte at stoppe hurtigst muligt, og hvis vi ignorerer potentielle pigge?

I den første iteration skulle vi i det mindste komme til punktet (S-1) ved at justere vores hastighed på nul med -1. Derfra vil vi i det mindste gå forbi (S-2) skridt fremad og så videre.

For en landingsbane med længde L skal følgende holde:

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

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

=> S² - S - 2L <0

Hvis du finder rødderne til ovenstående funktion, vil de være:

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

Vi kan skrive vores ulighed som:

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

I betragtning af at S - r2> 0 for enhver S> 0 og L> 0, har vi brug for følgende:

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

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

Det er den maksimale hastighed, som vi muligvis kunne have på en landingsbane med en længde L. Hvis vi havde en hastighed højere end det, kunne vi ikke stoppe selv teoretisk, uanset piggenes position.

Det betyder, at den samlede tidskompleksitet kun afhænger af længden af ​​landingsbanen L i følgende form:

O (L * sqrt (L)), som er bedre end O (L²)

O (L * sqrt (L)) er den øvre grænse for tidskompleksiteten

Awesome, du klarede det! :)

De 7 trin, som vi har gennemgået, skal give dig en ramme til systematisk at løse ethvert dynamisk programmeringsproblem. Jeg kan varmt anbefale at øve denne tilgang på et par flere problemer for at gøre din tilgang perfekt.

Her er nogle af de næste trin, du kan tage

  1. Udvid prøveproblemet ved at prøve at finde en sti til et stoppunkt. Vi løste et problem, der fortæller dig, om du kan stoppe, men hvad hvis du også vil vide, hvilke skridt der skal tages for at stoppe til sidst langs landingsbanen? Hvordan vil du ændre den eksisterende implementering for at gøre det?
  2. Hvis du vil styrke din forståelse af memoization og forstå, at det kun er en funktionsresultatcache, skal du læse om dekoratører i Python eller lignende koncepter på andre sprog. Tænk over, hvordan de giver dig mulighed for at implementere memoization generelt for enhver funktion, du vil huske.
  3. Arbejd med flere DP-problemer ved at følge de trin, vi har gennemgået. Du kan altid finde en masse af dem online (f.eks. LeetCode eller GeeksForGeeks). Når du træner, skal du huske en ting: lær ideer, lær ikke problemer. Antallet af ideer er betydeligt mindre, og det er en lettere plads at erobre, som også vil tjene dig meget bedre.

Når du har lyst til at have erobret disse ideer, skal du tjekke Refdash, hvor du bliver interviewet af en senioringeniør og få en detaljeret feedback om din kodning, algoritmer og systemdesign.

Oprindeligt offentliggjort på Refdash-bloggen. Refdash er en interviewplatform, der hjælper ingeniører med at interviewe anonymt med erfarne ingeniører fra topvirksomheder som Google, Facebook eller Palantir og få en detaljeret feedback. Refdash hjælper også ingeniører med at opdage fantastiske jobmuligheder baseret på deres færdigheder og interesser.