Følg disse trin for at løse eventuelle dynamiske programmeringsintervjueproblemer

På trods af, at de har betydelig erfaring med at opbygge softwareprodukter, føler mange ingeniører rystelser 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 Dynamic Programming (DP).

Mange tech-virksomheder kan lide at stille DP-spørgsmål i deres interviews. Selvom vi kan diskutere, om de er effektive til at evaluere nogens evne til at udføre i en ingeniørrolle, er DP fortsat et område, der rejser ingeniører på vej til at finde et job, som de elsker.

Dynamisk programmering - forudsigelig og forberedelig

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

Disse spørgsmål virker typisk temmelig komplicerede udefra og kan give dig et indtryk af, at en person, der løser dem, er meget god til algoritmer. Tilsvarende kan mennesker, der måske ikke er i stand til at komme over nogle tankevridende koncepter af DP, synes temmelig 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 at løse 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. Bestem, om du vil implementere det iterativt 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 prøveproblem. I hver af sektionerne vil jeg henvise til problemet, men du kan også læse sektionerne uafhængigt af problemet.

Problemformulering:

I dette problem er vi på en vanvittig springkugle og prøver at stoppe, mens vi undgår pigge undervejs.

Her er reglerne:

1) Du får en flad bane med en masse pigge i den. Landingsbanen er repræsenteret af et boolskt array, der angiver, om et bestemt (diskret) sted er fri for pigge. Det er sandt for klart og usant for ikke klart.

Eksempel på arrayrepræsentation:

2) Du får en starthastighed S. S er et ikke-negativt heltal på et givet tidspunkt, og det angiver, hvor meget du vil komme videre med det 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 ønsker at stoppe sikkert hvor som helst langs landingsbanen (behøver ikke være i slutningen af ​​matrixen). Du stopper, når din hastighed bliver 0. Hvis du lander på en spike på ethvert tidspunkt, sprænger din skøre hoppende bold, og det er spillet forbi.

Outputet fra din funktion skal være en boolsk, der angiver, 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 at løse problemer ved at opdele dem i en samling af enklere underproblemer, løse hvert af disse underproblemer bare én gang og gemme deres løsninger. Næste gang det samme underproblem opstår, i stedet for at beregne dets løsning, skal du blot slå den tidligere beregnede løsning op. Dette sparer beregningstid på bekostning af en (forhåbentlig) beskeden udgift i 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 til lignende mindre problemer.

I tilfælde af vores eksempelproblem, med et punkt på landingsbanen, en hastighed og landingsbanen foran, kunne vi bestemme de steder, hvor vi potentielt kunne springe næste. Derudover 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 gå videre, forkorter vi landingsbanen foran og gør vores problem mindre. Vi burde være i stand til at gentage denne proces hele vejen, indtil vi kommer til et punkt, hvor det er indlysende, om vi kan stoppe.

Genkendelse af et dynamisk programmeringsproblem er ofte det sværeste trin i at løse det. Kan problemløsningen udtrykkes som en funktion af løsninger til lignende mindre problemer?

Trin 2: Identificer problemvariabler

Nu har vi konstateret, at der er en vis rekursiv struktur mellem vores underproblemer. Dernæst er vi nødt til at udtrykke problemet med hensyn til funktionsparametre og se, hvilke af disse parametre ændrer.

I interviews har du typisk en eller to ændrede parametre, men teknisk set kan dette være et hvilket som helst antal. Et klassisk eksempel på et parameter, der skifter parameter, er “bestemme et n-th Fibonacci-nummer”. Et sådant eksempel på et problem med to skiftende 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 ændrede parametre er at liste eksempler på flere underproblemer og sammenligne parametrene. Det er værdifuldt at tælle antallet af ændrede parametre til at bestemme antallet af underproblemer, vi skal løse. Det er også i sig selv vigtigt 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. Array position (P)
  2. Hastighed (S)

Man kan sige, at landingsbanen foran ændrer sig også, men det ville være overflødigt i betragtning af, at hele ikke-skiftende landingsbane og position (P) allerede har disse oplysninger.

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

Identificer de ændrede parametre, og bestemm antallet af underproblemer.

Trin 3: Udtryk tydeligt gentagelsesforholdet

Dette er et vigtigt trin, som mange skynder sig igennem for at komme i kodning. At udtrykke gentagelsesforholdet så klart som muligt vil styrke din problemforståelse og gøre alt andet markant lettere.

Når du har fundet ud af, at gentagelsesforholdet eksisterer, og du specificerer 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 det største problem?

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

Fordi du kan justere din hastighed med op til 1, før du hopper til den 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, kunne 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, så kan vi også stoppe fra (S, P). Dette er fordi vi kan overføre fra (S, P) til en af ​​ovenstående tre muligheder.

Dette er typisk et fint niveau for forståelse af problemet (almindelig engelsk forklaring), men du kan undertiden 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 det største problem?

Trin 4: Identificer basissagerne

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

Årsagen til, at et problem ikke kan forenkles yderligere, er, at en af ​​parametrene ville blive 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 måske ikke er lovlige:

  1. P skal være inden for den givne bane
  2. P kan ikke være sådan, at landingsbanen [P] er falsk, fordi det ville betyde, at vi står på en pigge
  3. S kan ikke være negativ, og en S == 0 angiver, at vi er færdige

Nogle gange kan det være lidt udfordrende at konvertere påstande, som vi laver om parametre til programmerbare basissager. Dette skyldes, at du ud over at angive påstandene, hvis du ønsker at få din kode til at se kortfattet og ikke kontrollere for unødvendige forhold, også skal 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 gøre P == enden af ​​landingsbanen til en base sag. 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 temmelig indlysende. Vi kan blot kontrollere, om landingsbanen [P] er falsk.
  3. I lighed med nr. 1 kunne vi simpelthen tjekke for S <0 og S == 0. Her kan vi imidlertid 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. Derfor er S == 0 et tilstrækkeligt basistilfælde for S-parameteren.

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

Den måde, vi talte om indtil videre, kunne føre til, at du tænker, at vi skulle implementere problemet rekursivt. Alt, hvad vi har talt om indtil videre, er dog fuldstændig agnostisk for, om du beslutter at implementere problemet rekursivt eller iterativt. I begge fremgangsmåder er du nødt til at bestemme gentagelsesforholdet og basissagerne.

Hvis du vil beslutte, om du vil gå iterativt eller rekursivt, ønsker du nøje at tænke over afvejningerne.

Problemer med stackoverløb er typisk en deal breaker og en grund til, at du ikke ønsker at have rekursion i et (backend) produktionssystem. Imidlertid bør du typisk være i orden med en af ​​implementeringerne, så længe du nævner trade-offs, med henblik på samtalen. Du skal føle dig godt tilpas med at implementere begge dele.

I vores særlige problem implementerede jeg begge versioner. Her er python-kode til det:
 En rekursiv løsning: (originale kodestykker findes her)

En iterativ løsning: (originale kodestykker 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 underproblemer, der uden memoisering beregnes gentagne gange. Disse gentagelser fører ofte til eksponentielle tidskompleksiteter.

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

Dette betyder, at du skal:

  1. Opbevar dit funktionsresultat i din hukommelse inden hver returnering
  2. Slå hukommelsen op efter funktionsresultatet, inden du begynder at foretage nogen anden beregning

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

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

  1. Jeg oprettede en bane med længde 1000 med pigge på tilfældige steder (jeg valgte at have en sandsynlighed for, at en spike er på et givet sted til at være 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 omkring 500 gange mere tid end den iterative tilgang, og ca. 1300 gange mere tid end den rekursive tilgang med memoisering. Bemærk, at dette uoverensstemmende vil vokse hurtigt med længden af ​​landingsbanen. 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 i 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 ændrede parametre i dit problem
  2. Tænk på det arbejde, der udføres pr. Stat. Med andre ord, hvis alt andet end én 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 af alle positioner (| P | angiver antallet af elementer i P)
  • S er sæt med alle hastigheder

Det arbejde, der udføres pr. Stat, er O (1) i dette problem, fordi vi i betragtning af alle andre tilstande simpelthen skal se på 3 underproblemer for at bestemme den resulterende tilstand.

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

Det ser dog ud til, at | S | kan være yderligere begrænset, for hvis det virkelig var | P |, er det meget tydeligt, at stop ikke ville være muligt, fordi du skulle hoppe længden på hele landingsbanen ved første træk.

Så lad os se, hvordan vi kan sætte en strammere bundet på | S |. Lad os kalde maksimal hastighed S. Antag, at vi starter fra position 0. Hvor hurtigt kunne vi stoppe, hvis vi forsøgte at stoppe så hurtigt som muligt, og hvis vi ignorerer potentielle pigge?

I den første iteration bliver vi nødt til at komme mindst til punktet (S-1) ved at justere vores hastighed på nul med -1. Derfra vil vi som minimum gå forbi (S-2) skridt fremad, og så videre.

For en bane med længde L er følgende nødt til at holde:

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

=> S * (S-1) / 2

=> S² - S - 2L <0

Hvis du finder rødder 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 alle 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 bane af en længde L. Hvis vi havde en hastighed, der var højere end det, kunne vi ikke engang teoretisk stoppe, uanset positionen af ​​piggene.

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

O (L * sqrt (L)) hvilket er bedre end O (L²)

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

Fantastisk, du klarede det! :)

De 7 trin, vi gik igennem, skulle 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 perfektionere din tilgang.

Her er nogle næste trin, som 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å ville vide, hvilke skridt du skal tage for at stoppe til sidst langs landingsbanen? Hvordan ville du ændre den eksisterende implementering for at gøre det?
  2. Hvis du vil styrke din forståelse af memoisering og forstå, at det kun er en cache til funktionsresultater, 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 memoize.
  3. Arbejd med flere DP-problemer ved at følge de trin, vi gik gennem. 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 markant 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 på din kodning, algoritmer og systemdesign.

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