Dünaamilise programmeerimise intervjuuprobleemide lahendamiseks toimige järgmiselt

Vaatamata märkimisväärsele kogemusele tarkvaratoodete loomisel tunnevad paljud insenerid mõtet algoritmidele keskenduva kodeerimisintervjuu läbimise peale. Olen intervjueerinud sadu insenere Refdashis, Google'is ja idufirmades, kus olen osalenud, ning mõned kõige levinumad küsimused, mis insenerid rahutuks teevad, on need, mis hõlmavad dünaamilist programmeerimist (DP).

Paljud tehnoloogiaettevõtted soovivad intervjuudes DP-d küsida. Ehkki saame arutada, kas nad hindavad tõhusalt kellegi insenerirollis tegutsemise võimet, on DP jätkuvalt ala, mis suunab insenere üles oma armastatud töö leidmisele.

Dünaamiline programmeerimine - ennustatav ja ettevalmistatav

Üks põhjus, miks ma isiklikult usun, et DP-küsimused ei pruugi olla parim viis insenerivõimete testimiseks, on see, et need on prognoositavad ja hõlpsasti sobitatavad. Need võimaldavad meil valmisoleku jaoks filtreerida palju rohkem kui insenerivõimekust.

Need küsimused tunduvad väljastpoolt tavaliselt üsna keerulised ja võivad jätta mulje, et inimene, kes neid lahendab, on algoritmides väga osav. Samamoodi võivad algoritmide tundmises tunduda üsna nõrgad inimesed, kes ei pruugi olla võimelised DP-st mõtet väänavatest mõistetest üle saama.

Tegelikkus on teine ​​ja nende esinemise suurim tegur on valmisolek. Nii et hoolitseme selle eest, et kõik oleksid selleks valmis. Viimast korda.

7 sammu dünaamilise programmeerimise probleemi lahendamiseks

Selles postituses vaatan üle ühe retsepti, mida saate järgida, et teada saada, kas probleem on “DP-probleem”, samuti välja selgitada sellise probleemi lahendus. Täpsemalt, läbin järgmised sammud:

  1. Kuidas DP-probleemi ära tunda
  2. Tuvastage probleemmuutujad
  3. Väljendage selgelt korduvussuhet
  4. Tehke kindlaks juhtumid
  5. Otsustage, kas soovite seda rakendada korduvalt või rekursiivselt
  6. Lisage memo
  7. Määrake aja keerukus

Proovi DP probleem

Selleks, et saada näide abstraktsioonidest, mida kavatsen teha, lubage mul tutvustada näidisprobleemi. Igas jaotises viitan probleemile, kuid võite lugeda ka jaotisi probleemist sõltumatult.

Probleemipüstituses:

Selles probleemis oleme meeletul hüppepallil, üritame peatuda, vältides samal ajal teel olevaid piike.

Reeglid on järgmised:

1) Teile antakse tasane rada, milles on hunnik piike. Rada on tähistatud tõeväärtusega massiiviga, mis näitab, kas konkreetses (diskreetses) kohas pole piike. See on selge ja vale, kui mitte selge.

Massiivi kujutise näide:

2) Teile antakse algkiirus S. S on mis tahes punktis mitte-negatiivne täisarv ja see näitab, kui palju te järgmise hüppega edasi liigute.

3) Iga kord, kui maandute kohapeal, saate enne järgmist hüpet oma kiirust reguleerida kuni 1 ühiku võrra.

4) soovite ohutult peatuda raja piki (ei pea asuma massiivi lõpus). Peatute siis, kui teie kiirus muutub 0. Kui aga mingil hetkel maandute naelu otsa, purskab teie hull põrkav pall ja see on mäng läbi.

Teie funktsiooni väljund peaks olema tõeväärtus, mis näitab, kas me saame rajal ohutult peatuda.

1. samm: kuidas dünaamilise programmeerimise probleemi ära tunda

Esiteks teeme selgeks, et DP on sisuliselt lihtsalt optimeerimise tehnika. DP on meetod probleemide lahendamiseks, jagades need lihtsamate alamprobleemide kogumiks, lahendades kõik need alamprobleemid vaid üks kord ja talletades nende lahendused. Järgmine kord, kui ilmneb sama alamprobleem, otsite selle lahenduse ümberarvutamise asemel lihtsalt varem arvutatud lahenduse. See säästab arvutusaega (loodetavasti) tagasihoidlike kulutuste arvelt salvestusruumis.

Selle probleemi lahendamise esimene ja sageli kõige raskem samm on tõdeda, et probleemi saab lahendada DP abil. Mida soovite endalt küsida, on see, kas teie probleemilahendust saab väljendada sarnaste väiksemate probleemide lahenduste funktsioonina.

Meie näidisprobleemi korral, kui antud punkt rajal, kiirus ja ees olev raja, võiksime määrata kohad, kuhu võiksime järgmisena hüpata. Pealegi näib, et see, kas suudame praegusest punktist praeguse kiirusega peatuda, sõltub ainult sellest, kas saaksime peatuda punktist, mille valime järgmiseks.

See on suurepärane asi, sest edasi liikudes lühendame eesolevat rada ja muudame oma probleemi väiksemaks. Peaksime suutma seda protsessi korrata, kuni jõuame punkti, kus on ilmne, kas suudame peatuda.

Dünaamilise programmeerimise probleemi äratundmine on sageli kõige raskem samm selle lahendamisel. Kas probleemilahendust saab väljendada sarnaste väiksemate probleemide lahenduste funktsioonina?

2. samm: tuvastage probleemsed muutujad

Nüüd oleme kindlaks teinud, et meie alamprobleemide vahel on mingi rekursiivne struktuur. Järgmisena peame probleemi väljendama funktsiooni parameetritega ja nägema, millised neist parameetritest muutuvad.

Tavaliselt on intervjuudel üks või kaks muutuvat parameetrit, kuid tehniliselt võib see olla mis tahes arv. Klassikaline näide ühe muutuva parameetriga probleemist on „n-nda Fibonacci arvu määramine”. Selline näide kahest muutuva parameetri probleemist on "Stringide redigeerimiskauguse arvutamine". Kui te pole nende probleemidega tuttav, ärge muretsege selle pärast.

Muutuvate parameetrite arvu kindlaksmääramise viis on loetleda mitme alamprobleemi näited ja võrrelda parameetreid. Muutuvate parameetrite arvu loendamine on väärtuslik, et määrata kindlaks lahendatavate alamprobleemide arv. See on oluline ka omaette, aidates meil 1. etapist alates paremini mõista korduvussuhet.

Meie näites on kaks parameetrit, mis võivad iga alamprobleemi jaoks muutuda:

  1. Massiivi asukoht (P)
  2. Kiirus (S)

Võib öelda, et ka ees olev rada muutub, kuid see oleks üleliigne, kui arvestada, et kogu muutumatu rada ja asukoht (P) juba kannavad seda teavet.

Nende kahe muutuva parameetri ja muude staatiliste parameetrite abil on nüüd meie alamprobleemide täielik kirjeldus.

Tehke kindlaks muutuvad parameetrid ja määrake alamprobleemide arv.

3. samm: väljendage selgelt korduvussuhet

See on oluline samm, millest paljud kiirustavad, et kodeerimisse jõuda. Korduvussuhte võimalikult selge väljendamine tugevdab teie probleemide mõistmist ja muudab kõik muu oluliselt lihtsamaks.

Kui olete aru saanud, et kordumissuhe on olemas, ja määrate probleemid parameetrite osas, peaks see olema loomulik samm. Kuidas on probleemid omavahel seotud? Teisisõnu, oletame, et olete arvutanud alaprobleemid. Kuidas arvutaksite põhiprobleemi?

Siinkohal mõtleme sellest oma prooviprobleemis:

Kuna enne järgmisele positsioonile hüppamist saate oma kiirust reguleerida kuni 1 võrra, on võimalikud ainult 3 kiirust ja seega 3 kohta, milles võiksime olla järgmine.

Vormiliselt võib öelda, et kui meie kiirus on S, positsioon P, võiksime minna punktist (S, P) järgmisele:

  1. (S, P + S) ; # kui me kiirust ei muuda
  2. (S - 1, P + S - 1) ; # kui muudame kiirust -1 võrra
  3. (S + 1, P + S + 1) ; # kui muudame kiirust +1 võrra

Kui suudame mõnes ülaltoodud alaprobleemis leida viisi peatumiseks, siis võime peatuda ka punktist (S, P). Selle põhjuseks on asjaolu, et saame ülemineku punktilt (S, P) ühele ülaltoodud kolmest võimalusest.

See on tavaliselt probleemist arusaamise hea tase (lihtne ingliskeelne seletus), kuid mõnikord võiksite seda seost ka matemaatiliselt väljendada. Kutsume funktsiooni, mida proovime arvutada, canStop. Siis:

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

Ohoo, tundub, et meil on meie korduvussuhe!

Korduvussuhe: kui arvate, et olete arvutanud alaprobleemid, siis kuidas arvutaksite põhiprobleemi?

4. samm: tehke kindlaks juhtumid

Baasjuhtum on alamprobleem, mis ei sõltu ühestki muust alamprobleemist. Selliste alamprobleemide leidmiseks soovite tavaliselt proovida mõnda näidet, vaadata, kuidas teie probleem lihtsustub väiksemateks alamprobleemideks, ja teha kindlaks, millisel hetkel ei saa seda veelgi lihtsustada.

Põhjus, miks probleemi ei saa veelgi lihtsustada, on see, et ühest parameetrist saaks väärtus, mis pole probleemi piiranguid arvestades võimalik .

Meie näiteülesandes on meil kaks muutuvat parameetrit, S ja P. Mõelgem sellele, millised võimalikud S ja P väärtused ei pruugi olla seaduspärased:

  1. P peaks olema antud raja piirides
  2. P ei saa olla selline, et rada [P] on vale, sest see tähendaks, et me seisame oras
  3. S ei saa olla negatiivne ja S == 0 näitab, et oleme valmis

Mõnikord võib parameetrite kohta tehtud väidete teisendamine programmeeritavateks baasjuhtumiteks olla veidi keeruline. Seda seetõttu, et lisaks väidete loetlemisele, kui soovite oma koodi lühikese väljanägemise ja mitte ebavajalike tingimuste kontrollimiseks, peate mõtlema ka sellele, millised neist tingimustest on üldse võimalikud.

Meie näites:

  1. P <0 || P> = raja pikkus tundub õige asi. Alternatiiviks võiks pidada P == raja raja võrdlemist alusjuhtumiks . Siiski on võimalik, et probleem jaguneb alamprobleemiks, mis ulatub raja otsast kaugemale, seega peame tõesti kontrollima ebavõrdsust.
  2. See tundub üsna ilmne. Saame lihtsalt kontrollida, kas rada [P] on vale .
  3. Sarnaselt # 1-ga võiksime lihtsalt kontrollida, kas S <0 ja S == 0. Kuid siin võime põhjendada, et S-i on võimatu olla <0, kuna S väheneb maksimaalselt 1 võrra, nii et see peaks läbima S == 0 juhtumit eelnevalt. Seetõttu on S == 0 parameetri S jaoks piisav alusjuhtum .

5. samm: otsustage, kas soovite seda rakendada korduvalt või rekursiivselt

See, kuidas me senistest sammudest rääkisime, võib viia teid mõttele, et peaksime probleemi rekursiivselt rakendama. Kuid kõik, millest oleme seni rääkinud, on täiesti agnostiline selles osas, kas otsustate probleemi rakendada rekursiivselt või korduvalt. Mõlemas lähenemisviisis peate määrama korduvuse seose ja juhtumid.

Et otsustada, kas minna korduvalt või rekursiivselt, peate hoolikalt kaaluma kompromisse .

Virna ülevooluprobleemid on tavaliselt tehingute katkestajad ja põhjus, miks te ei soovi (taustaprogrammi) tootmissüsteemis rekursiooni. Intervjuu eesmärgil peaksite seni, kuni mainite kompromisse, tavaliselt kummagi rakendusega hästi hakkama. Mõlemat peaksite rakendama mugavalt.

Meie konkreetses probleemis rakendasin mõlemad versioonid. Siin on selleks Pythoni kood:

Rekursiivne lahendus: (originaalkoodijupid leiate siit)

Korduv lahendus: (originaalkoodijupid leiate siit)

6. samm: lisage memo

Memodeerimine on DP-ga tihedalt seotud tehnika. Seda kasutatakse kallite funktsioonikõnede tulemuste salvestamiseks ja vahemällu salvestatud tulemuse tagastamiseks, kui samad sisendid esinevad uuesti.

Miks lisame oma rekursioonile memod? Me kohtame samu alamprobleeme, mida ilma memodeta arvutatakse korduvalt. Need kordused toovad sageli kaasa eksponentsiaalse aja keerukuse.

Rekursiivsete lahenduste korral peaks memode lisamine olema lihtne. Vaatame, miks. Pidage meeles, et memode lisamine on lihtsalt funktsiooni tulemuste vahemälu. Mõnikord soovite sellest määratlusest kõrvale kalduda, et mõned väiksemad optimeerimised välja pigistada, kuid memode töötlemine funktsiooni tulemuste vahemäluna on kõige intuitiivsem viis selle rakendamiseks.

See tähendab, et peaksite:

  1. Hoidke oma funktsiooni tulemus oma mälu enne iga tagastamise avalduse
  2. Enne muu arvutamise alustamist otsige funktsiooni tulemuse mälust üles

Siin on ülaltoodud kood koos lisatud memodega (lisatud read on esile tõstetud): (originaalkoodijupid leiate siit)

Memode ja erinevate lähenemisviiside tõhususe illustreerimiseks teeme mõned kiirtestid. Panen stressitesti proovile kõik kolm meetodit, mida oleme seni näinud. Siin on seadistatud:

  1. Lõin raja, mille pikkus oli 1000, naastudega juhuslikes kohtades (valisin, et tõenäosus, et ükskõik millises kohas on naast, on 20%)
  2. initSpeed ​​= 30
  3. Käitasin kõiki funktsioone 10 korda ja mõõtsin keskmist täitmise aega

Siin on tulemused (sekundites):

Näete, et puhas rekursiivne lähenemine võtab umbes 500x rohkem aega kui iteratiivne lähenemine ja umbes 1300x rohkem aega kui rekursiivne lähenemine memode abil. Pange tähele, et see lahknevus kasvaks raja pikkusega kiiresti. Soovitan teil proovida seda ise käivitada.

7. samm: määrake aja keerukus

On mõned lihtsad reeglid, mis võivad dünaamilise programmeerimisprobleemi aja keerukuse arvutamise palju lihtsamaks muuta. Siin on kaks sammu, mida peate tegema:

  1. Loendage olekute arv - see sõltub teie probleemi muutuvate parameetrite arvust
  2. Mõelge iga osariigi tehtud tööle. Teisisõnu, kui on arvutatud kõik muu kui üks olek, siis kui palju peate selle viimase oleku arvutamiseks tegema?

Meie näiteülesandes on olekute arv | P | * | S | kus

  • P on kõigi positsioonide hulk (| P | näitab elementide arvu punktis P)
  • S on kõigi kiiruste komplekt

Igas olekus tehtud töö on selles probleemis O (1), kuna kõiki teisi olekuid arvestades peame saadud oleku määramiseks lihtsalt vaatama 3 alamprobleemi.

Nagu me koodis varem märkisime, | S | on piiratud raja pikkusega (| P |), seega võiksime öelda, et olekute arv on | P | ² ja kuna igas olekus tehtud töö on O (1), on kogu aja keerukus O (| P | ²).

Tundub siiski, et | S | saab veelgi piirata, sest kui see oleks tõesti | P |, siis on väga selge, et peatumine pole võimalik, kuna peate esimesel käigul hüppama kogu raja pikkuse.

Nii et vaatame, kuidas saaksime | S | -i tihedamalt siduda. Nimetagem maksimaalseks kiiruseks S. Oletame, et alustame positsioonist 0. Kui kiiresti saaksime peatuda, kui üritaksime võimalikult kiiresti peatuda ja kui eiraksime potentsiaalseid piike?

Esimeses iteratsioonis peaksime jõudma vähemalt punkti (S-1), kohandades oma kiirust nulli -1 võrra. Sealt läheksime vähemalt mööda (S-2) samme edasi jne.

L pikkusega raja jaoks peab olema järgmine:

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

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

=> S² - S - 2L <0

Kui leiate ülaltoodud funktsiooni juured, on need järgmised:

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

Võime oma ebavõrdsuse kirjutada järgmiselt:

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

Arvestades, et mis tahes S> 0 ja L> 0 korral S - r2> 0, vajame järgmist:

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

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

See on maksimaalne kiirus, mis meil võiks olla rajal, mille pikkus on L. Kui meil oleks sellest suurem kiirus, ei saaks me teoreetiliselt peatuda, olenemata piikide asendist.

See tähendab, et kogu aja keerukus sõltub ainult raja L pikkusest järgmisel kujul:

O (L * sqrt (L)), mis on parem kui O (L²)

O (L * sqrt (L)) on aja keerukuse ülemine piir

Äge, sa said selle läbi! :)

Seitse sammu, mille läbisime, peaksid andma teile raamistiku kõigi dünaamiliste programmeerimisprobleemide süstemaatiliseks lahendamiseks. Soovitan tungivalt seda lähenemist veel mõne probleemi korral harjutada, et oma lähenemist täiustada.

Siin on mõned järgmised sammud, mida saate teha

  1. Laiendage prooviprobleemi, proovides leida teed peatuspunktini. Lahendasime probleemi, mis ütleb teile, kas saate peatuda, kuid mis oleks, kui soovite teada ka samme, mida astuda, et lõpuks rajal peatuda? Kuidas muudate olemasolevat rakendust selleks?
  2. Kui soovite kinnitada arusaamist memodest ja mõista, et see on lihtsalt funktsiooni tulemuste vahemälu, peaksite lugema Pythoni sisekujundajate või muude keelte sarnaste mõistete kohta. Mõelge, kuidas need võimaldaksid teil memode salvestamist üldiselt rakendada kõigi funktsioonide jaoks, mida soovite memo salvestada.
  3. Töötage rohkem DP-probleemidega, järgides meie läbitud samme. Hulga neist leiate alati veebist (nt LeetCode või GeeksForGeeks). Harjutades pidage meeles ühte asja: õppige ideid, ärge õppige probleeme. Ideede arv on oluliselt väiksem ja see on lihtsam ruumi vallutamiseks, mis teenib teid ka palju paremini.

Kui tunnete, et olete need ideed vallutanud, vaadake Refdashi, kus vaneminsener küsitleb teid, ja saate üksikasjalikku tagasisidet oma kodeerimise, algoritmide ja süsteemikujunduse kohta.

Algselt avaldatud Refdashi ajaveebis. Refdash on intervjueerimisplatvorm, mis aitab inseneridel anonüümselt intervjueerida tippettevõtete, näiteks Google, Facebook või Palantir, kogenud insenere ja saada üksikasjalikku tagasisidet. Refdash aitab inseneridel ka oma oskuste ja huvide põhjal avastada hämmastavaid töövõimalusi.