Atlikite šiuos veiksmus, kad išspręstumėte bet kokias dinaminio programavimo interviu problemas

Nepaisant to, kad turi didelę patirtį kuriant programinės įrangos produktus, daugelis inžinierių jaučiasi sujaudinti, galvodami apie kodavimo interviu, kuriame daugiausia dėmesio skiriama algoritmams. Apklausiau šimtus inžinierių „Refdash“, „Google“ ir pradedančiose įmonėse, kuriose dalyvavau, ir keletas dažniausiai pasitaikančių klausimų, dėl kurių inžinieriai nerimauja, yra susiję su dinaminiu programavimu (DP).

Daugelis technologijų kompanijų savo interviu metu mėgsta užduoti klausimus DP. Nors mes galime diskutuoti, ar jie veiksmingai vertina kieno nors sugebėjimą atlikti inžinerijos vaidmenį, DP ir toliau yra sritis, kuri kelia inžinierių kelią ieškant mylimo darbo.

Dinaminis programavimas - nuspėjamas ir parengiamas

Viena iš priežasčių, kodėl aš asmeniškai manau, kad DP klausimai gali būti ne geriausias būdas išbandyti inžinerinius sugebėjimus, yra ta, kad jie yra nuspėjami ir lengvai suderinami. Jie leidžia mums daug daugiau filtruoti pasirengimą, o ne inžinerinius sugebėjimus.

Šie klausimai paprastai atrodo gana sudėtingi išorėje, todėl gali susidaryti įspūdis, kad juos sprendžiantis asmuo puikiai moka algoritmus. Panašiai žmonės, kurie gali nesugebėti įveikti kai kurių protą verčiančių DP sąvokų, gali atrodyti gana silpni žinodami algoritmus.

Realybė yra kitokia, o didžiausias jų pasirodymo veiksnys yra pasirengimas. Taigi įsitikinkime, kad visi tam pasiruošę. Galutinai.

7 veiksmai, kaip išspręsti dinaminio programavimo problemą

Likusioje šio įrašo dalyje apžvelgsiu receptą, kurio galite laikytis, kad išsiaiškintumėte, ar problema yra „DP problema“, taip pat išsiaiškinti tokios problemos sprendimą. Konkrečiai, aš atliksiu šiuos veiksmus:

  1. Kaip atpažinti DP problemą
  2. Nustatykite problemos kintamuosius
  3. Aiškiai išreikškite pasikartojimo santykį
  4. Nurodykite pagrindinius atvejus
  5. Nuspręskite, ar norite tai įgyvendinti kartotinai, ar rekursiškai
  6. Pridėti atmintinę
  7. Nustatykite laiko sudėtingumą

DP problemos pavyzdys

Norėdamas pateikti pavyzdį abstrakcijoms, kurias ketinu padaryti, leiskite pristatyti pavyzdinę problemą. Kiekviename iš skyrių aš nurodysiu problemą, bet jūs taip pat galėtumėte perskaityti skyrius nepriklausomai nuo problemos.

Problemos pareiškimas:

Šioje problemoje mes ant pašėlusio šuolio kamuolio, bandome sustoti, vengdami smaigalių kelyje.

Štai taisyklės:

1) Jums suteikiamas plokščias kilimo ir tūpimo takas, kuriame yra krūva smaigalių. KTT žymi loginė matrica, nurodanti, ar tam tikroje (atskiroje) vietoje nėra smailių. Tai teisinga aiškiam, o netiesa - neaiškiam.

Masyvo pavaizdavimo pavyzdys:

2) Jums suteikiamas pradinis greitis. S yra neigiamas sveikasis skaičius bet kuriame taške ir tai rodo, kiek judėsite į priekį atlikdami kitą šuolį.

3) Kiekvieną kartą nusileidę vietoje, prieš kitą šuolį galite reguliuoti greitį iki 1 vieneto.

4) Norite saugiai sustoti bet kurioje kilimo ir tūpimo tako vietoje (nebūtina būti masyvo gale). Sustojate, kai jūsų greitis tampa 0. Tačiau, jei bet kuriuo metu nusileisite ant smaigalio, jūsų pašėlęs šokinėjantis kamuolys sprogs ir žaidimas baigsis.

Jūsų funkcijos išvestis turėtų būti loginė, nurodant, ar galime saugiai sustoti bet kurioje kilimo ir tūpimo tako vietoje.

1 žingsnis: Kaip atpažinti dinaminio programavimo problemą

Pirmiausia pasakykime, kad DP iš esmės yra tik optimizavimo technika. DP yra būdas išspręsti problemas, suskaidant jas į paprastesnių subproblemų rinkinį, kiekvieną kartą išsprendžiant kiekvieną iš tų subproblemų ir saugant jų sprendimus. Kitą kartą, kai atsiras tas pats potvarkis, užuot perskaičiavus jo sprendimą, paprasčiausiai ieškote anksčiau apskaičiuoto sprendimo. Tai taupo skaičiavimo laiką sąskaita (tikiuosi) kuklioms išlaidoms saugojimo vietoje.

Pripažinimas, kad problemą galima išspręsti naudojant DP, yra pirmas ir dažnai sunkiausias žingsnis ją sprendžiant. Ko norite savęs paklausti, ar jūsų problemos sprendimas gali būti išreikštas kaip panašių mažesnių problemų sprendimo funkcija.

Mūsų pavyzdžio problemos atveju, atsižvelgiant į kilimo ir tūpimo tako tašką, greitį ir priekinį kilimo ir tūpimo taką, mes galėtume nustatyti vietas, kuriose galėtume šokti toliau. Be to, atrodo, ar tai, ar galime sustoti iš dabartinio taško dabartiniu greičiu, priklauso tik nuo to, ar galėtume sustoti nuo taško, kurį pasirinkome eiti toliau.

Tai puikus dalykas, nes judėdami į priekį, mes sutrumpiname kilimo ir tūpimo taką į priekį ir sumažiname savo problemą. Turėtume sugebėti pakartoti šį procesą visą kelią, kol pasieksime tašką, kuriame akivaizdu, ar galime sustoti.

Dinaminio programavimo problemos atpažinimas dažnai yra sunkiausias žingsnis ją sprendžiant. Ar problemos sprendimas gali būti išreikštas kaip panašių mažesnių problemų sprendimo funkcija?

2 žingsnis: nustatykite probleminius kintamuosius

Dabar mes nustatėme, kad tarp mūsų papročių yra tam tikra rekursinė struktūra. Toliau turime išsakyti problemą funkcijos parametrais ir pamatyti, kurie iš tų parametrų keičiasi.

Paprastai interviu metu turėsite vieną ar du kintančius parametrus, tačiau techniškai tai gali būti bet koks skaičius. Klasikinis vieno kintančio parametro problemos pavyzdys yra „nustatyti n-ąjį Fibonacci skaičių“. Toks dviejų parametrų kintančių problemų pavyzdys yra „Apskaičiuokite redagavimo atstumą tarp eilučių“. Jei nesate susipažinę su šiomis problemomis, nesijaudinkite dėl jų.

Kintančių parametrų skaičiaus nustatymo būdas yra išvardyti kelių paprogramių pavyzdžius ir palyginti parametrus. Skaičiuojant besikeičiančių parametrų skaičių, yra naudinga nustatyti, kiek problemų turime išspręsti. Tai taip pat svarbu atskirai, kad padėtų mums suprasti pasikartojimo santykio supratimą nuo 1 žingsnio.

Mūsų pavyzdyje yra du parametrai, kurie gali keistis kiekvienam papunkčiui:

  1. Masyvo padėtis (P)
  2. Greitis (S)

Galima sakyti, kad keičiasi ir priekyje esantis kilimo ir tūpimo takas, tačiau tai būtų nereikalinga, turint omenyje, kad visa nekintanti kilimo ir tūpimo takas ir padėtis (P) jau turi tą informaciją.

Dabar, pasikeitus šiems 2 parametrams ir kitiems statiniams parametrams, mes turime išsamų savo problemų aprašymą.

Nustatykite besikeičiančius parametrus ir nustatykite papildomų problemų skaičių.

3 žingsnis: aiškiai išreikškite pasikartojimo santykį

Tai yra svarbus žingsnis, kurį daugelis skuba, norėdami pereiti prie kodavimo. Kuo aiškiau išreikšdami pasikartojimo ryšį, sustiprinsite savo problemos supratimą ir visa kita žymiai palengvinsite.

Kai išsiaiškinsite, ar pasikartojimo ryšys egzistuoja, ir nurodysite problemas, susijusias su parametrais, tai turėtų būti natūralus žingsnis. Kaip problemos susijusios tarpusavyje? Kitaip tariant, tarkime, kad jūs apskaičiavote papunkčius. Kaip apskaičiuotumėte pagrindinę problemą?

Štai kaip mes apie tai galvojame savo pavyzdinėje problemoje:

Kadangi prieš peršokdami į kitą poziciją galite reguliuoti greitį iki 1, galimi tik 3 greičiai, taigi ir 3 taškai, kuriuose galėtume būti kiti.

Formaliau, jei mūsų greitis yra S, padėtis P, mes galime pereiti nuo (S, P) iki:

  1. (S, P + S) ; # jei nekeisime greičio
  2. (S - 1, P + S - 1) ; # jei greitį pakeisime -1
  3. (S + 1, P + S + 1) ; # jei greitį pakeisime +1

Jei mes galime rasti būdą sustoti bet kuriame iš aukščiau nurodytų problemų, tada mes taip pat galime sustoti nuo (S, P). Taip yra todėl, kad galime pereiti nuo (S, P) prie bet kurio iš pirmiau nurodytų trijų variantų.

Paprastai tai yra geras problemos supratimo lygis (paprastas paaiškinimas angliškai), tačiau kartais galbūt norėsite santykį išreikšti ir matematiškai. Paskambinkime funkcijai, kurią bandome apskaičiuoti „canStop“. Tada:

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

Oho, atrodo, kad mes turime savo pasikartojimo ryšį!

Pasikartojimo ryšys: darant prielaidą, kad apskaičiavote papunkčius, kaip apskaičiuotumėte pagrindinę problemą?

4 žingsnis: nustatykite pagrindinius atvejus

Pagrindinis atvejis yra papildoma problema, kuri nepriklauso nuo jokios kitos problemos. Norėdami rasti tokių subproblemų, paprastai norėtumėte išbandyti keletą pavyzdžių, sužinoti, kaip jūsų problema supaprastėja į mažesnius subproblemas, ir nustatyti, kada jos negalima toliau supaprastinti.

Priežastis, dėl kurios problemos toliau supaprastinti negalima, yra ta, kad vienas iš parametrų taptų verte, kuri neįmanoma atsižvelgiant į problemos apribojimus .

Mūsų pavyzdžio problemoje turime du kintančius parametrus - S ir P. Pagalvokime, kokios galimos S ir P reikšmės gali būti neteisėtos:

  1. P turėtų būti nurodyto kilimo ir tūpimo tako ribose
  2. P negali būti toks, kad kilimo ir tūpimo takas [P] yra klaidingas, nes tai reikštų, kad mes stovime ant smaigalio
  3. S negali būti neigiamas, o S == 0 rodo, kad baigėme

Kartais teiginius apie parametrus paversti programuojamais pagrindiniais atvejais gali būti šiek tiek nelengva. Taip yra todėl, kad be teiginių išvardijimo, jei norite, kad kodas atrodytų glaustas ir nepatikrintumėte nereikalingų sąlygų, taip pat turite pagalvoti, kurios iš šių sąlygų netgi yra įmanomos.

Mūsų pavyzdyje:

  1. P <0 || P> = KTT ilgis atrodo teisingas. Alternatyva galėtų būti pagrindo atvejis, kai P == pakilimo tako galas yra panašus . Tačiau gali būti, kad problema išskaidoma į kilimo ir tūpimo tako galą viršijančią problemą, todėl iš tikrųjų turime patikrinti, ar nėra nelygybės.
  2. Tai atrodo gana akivaizdu. Mes galime tiesiog patikrinti, ar KTT [P] yra klaidingas .
  3. Panašiai kaip # 1, mes galime tiesiog patikrinti, ar S <0 ir S == 0. Tačiau čia mes galime pagrįsti, kad neįmanoma, kad S būtų <0, nes S mažėja daugiausiai 1, taigi jis turėtų praeiti S == 0 atvejis iš anksto. Ther prieš tiekdamas S == 0 yra pakankama bazė atvejis S parametro.

5 žingsnis: nuspręskite, ar norite tai įgyvendinti kartotinai, ar rekursiškai

Tai, kaip kalbėjome apie ligšiolinius veiksmus, gali paskatinti jus galvoti, kad problemą turėtume įgyvendinti rekursiškai. Tačiau viskas, apie ką kalbėjome iki šiol, yra visiškai agnostinė, nesvarbu, ar nuspręsite problemą įgyvendinti rekursyviai, ar pakartotinai. Abiem būdais turėtumėte nustatyti pasikartojimo santykį ir pagrindinius atvejus.

Norint nuspręsti, ar kartoti, ar rekursiškai, reikia gerai pagalvoti apie kompromisus .

„Stack overflow“ problemos paprastai yra sandorių pertraukiklis ir priežastis, kodėl nenorite, kad (backend) gamybos sistemoje būtų rekursija. Tačiau pokalbio tikslais, jei jūs paminėjate kompromisus, paprastai turėtumėte gerai atlikti bet kurį iš jų. Turėtumėte jaustis įgyvendindami abu.

Konkrečioje mūsų problemoje įgyvendinau abi versijas. Štai python kodas tam:

Rekursinis sprendimas: (originalius kodo fragmentus galite rasti čia)

Pakartotinis sprendimas: (originalius kodo fragmentus galite rasti čia)

6 veiksmas: pridėkite atmintinę

Įsiminimas yra technika, kuri yra glaudžiai susijusi su DP. Jis naudojamas saugoti brangių funkcijų iškvietimų rezultatus ir grąžinti talpykloje esantį rezultatą, kai vėl atsiranda tie patys įėjimai.

Kodėl mes įtraukiame atmintines į savo rekursiją? Susiduriame su tomis pačiomis problemomis, kurios be atminties yra skaičiuojamos pakartotinai. Tie kartojimai labai dažnai sukelia eksponentinį laiko sudėtingumą.

Rekursiškuose sprendimuose pridėti atmintį turėtų būti paprasta. Pažiūrėkime, kodėl. Atminkite, kad atmintinė yra tik funkcijos rezultatų talpykla. Kartais norima nukrypti nuo šio apibrėžimo, kad būtų išspręstos kelios smulkios optimizacijos, tačiau atminties įrašymas kaip funkcijos rezultatų talpykla yra pats intuityviausias būdas ją įgyvendinti.

Tai reiškia, kad turėtumėte:

  1. Saugokite savo funkcijos rezultatą atmintyje prieš kiekvieną grąžinimo pareiškimą
  2. Prieš pradėdami atlikti kitus skaičiavimus, ieškokite funkcijos rezultatų atminties

Čia yra kodas iš viršaus su pridėta atmintine (paryškintos pridėtos eilutės): (originalius kodo fragmentus galite rasti čia)

Norėdami parodyti atminties efektyvumą ir skirtingus metodus, atlikime keletą greitų testų. Aš išbandysiu visus tris iki šiol matytus metodus. Čia nustatyta:

  1. Sukūriau 1000 ilgio kilimo ir tūpimo taką su smaigaliais atsitiktinėse vietose (pasirinkau, kad tikimybė, kad smaigalys bet kurioje vietoje bus 20%)
  2. initSpeed ​​= 30
  3. 10 kartų vykdžiau visas funkcijas ir matavau vidutinį vykdymo laiką

Čia pateikiami rezultatai (sekundėmis):

Galite pastebėti, kad grynas rekursyvus metodas užtrunka apie 500 kartų daugiau laiko nei kartojamasis metodas ir apie 1300 kartų daugiau nei rekursinis metodas su atmintimi. Atkreipkite dėmesį, kad šis neatitikimas sparčiai didės bėgio tako ilgiui. Aš raginu jus pabandyti jį paleisti patys.

7 veiksmas: nustatykite laiko sudėtingumą

Yra keletas paprastų taisyklių, kurios gali žymiai palengvinti dinaminio programavimo problemos sudėtingumą. Štai du veiksmai, kuriuos turite atlikti:

  1. Skaičiuokite būsenų skaičių - tai priklausys nuo jūsų problemos parametrų skaičiaus keitimo
  2. Pagalvokite apie kiekvienoje valstijoje atliktą darbą. Kitaip tariant, jei buvo apskaičiuota visa kita, išskyrus vieną būseną, kiek turite dirbti, kad apskaičiuotumėte tą paskutinę būseną?

Mūsų pavyzdžio problemoje būsenų skaičius yra | P | * | S | kur

  • P yra visų padėčių rinkinys (| P | rodo elementų skaičių P)
  • S yra visų greičių rinkinys

Kiekvienoje būsenoje atliktas darbas yra O (1) šioje problemoje, nes, atsižvelgiant į visas kitas būsenas, mes tiesiog turime pažvelgti į 3 papunkčius, kad nustatytume gautą būseną.

Kaip anksčiau pažymėjome kode, | S | yra ribojamas kilimo ir tūpimo tako ilgio (| P |), todėl galėtume sakyti, kad būsenų skaičius yra | P | ² ir kadangi kiekvienai būsenai atliktas darbas yra O (1), tada bendras laiko sudėtingumas yra O (| P | ²).

Tačiau panašu, kad | S | gali būti dar labiau ribojama, nes jei tai būtų iš tikrųjų | P |, labai aišku, kad sustoti neįmanoma, nes pirmą žingsnį turėtum peršokti viso pakilimo tako ilgį.

Taigi pažiūrėkime, kaip galime sugriežtinti | S |. Pavadinkime maksimalų greitį S. Tarkime, kad pradedame nuo 0 padėties. Kaip greitai galėtume sustoti, jei bandytume kuo greičiau sustoti ir nepaisytume galimų šuolių?

Pirmajame kartojime turėtume pasiekti bent tašką (S-1), sureguliuodami savo greitį nuliu -1. Iš ten mes bent jau eitume (S-2) žingsniais į priekį ir pan.

L ilgio kilimo ir tūpimo takui reikia:

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

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

=> S² - S - 2L <0

Jei rasite pirmiau minėtos funkcijos šaknis, jos bus:

r1 = 1/2 + kvrt (1/4 + 2L) ir r2 = 1/2 - kvrt (1/4 + 2L)

Savo nelygybę galime parašyti taip:

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

Atsižvelgiant į tai, kad S - r2> 0 bet kuriam S> 0 ir L> 0, mums reikia:

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

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

Tai yra maksimalus greitis, kurį galbūt galėtume pasiekti ilgio L kilimo ir tūpimo takelyje. Jei turėtume didesnį greitį, negalėtume sustoti net teoriškai, neatsižvelgdami į smaigalių padėtį.

Tai reiškia, kad bendras laiko sudėtingumas priklauso tik nuo kilimo ir tūpimo tako L ilgio tokia forma:

O (L * sqrt (L)), kuris yra geresnis už O (L²)

O (L * sqrt (L)) yra viršutinė laiko sudėtingumo riba

Nuostabu, jūs tai padarėte! :)

Septyni žingsniai, kuriuos atlikome, turėtų suteikti jums pagrindą sistemingai spręsti bet kokias dinaminio programavimo problemas. Labai rekomenduoju praktikuoti šį požiūrį dar kelioms problemoms, kad jūsų požiūris būtų tobulesnis.

Štai keli tolesni veiksmai, kuriuos galite atlikti

  1. Išplėskite pavyzdinę problemą bandydami rasti kelią į sustojimo tašką. Mes išsprendėme problemą, nurodančią, ar galite sustoti, bet ką daryti, jei taip pat norėtumėte žinoti veiksmus, kurių reikia imtis norint galiausiai sustoti palei pakilimo taką? Kaip modifikuotumėte esamą diegimą, kad tai padarytumėte?
  2. Jei norite sustiprinti supratimą apie atmintį ir suprantate, kad tai tik funkcijos rezultatų talpykla, turėtumėte perskaityti apie „Python“ dekoratorius ar panašias sąvokas kitomis kalbomis. Pagalvokite, kaip jie leistų jums apskritai įdiegti bet kurios funkcijos, kurią norite įrašyti, atmintį.
  3. Spręskite daugiau DP problemų vykdydami atliktus veiksmus. Krūvą jų visada galite rasti internete (pvz., „LeetCode“ arba „GeeksForGeeks“). Praktikuodami nepamirškite vieno: mokykitės idėjų, nesimokykite problemų. Idėjų skaičius yra žymiai mažesnis, ir tai yra lengviau užkariaujama erdvė, kuri taip pat bus jums naudingesnė.

Kai jaučiatės užkariavęs šias idėjas, apsilankykite „ Refdash“, kur jus kalbina vyresnysis inžinierius, ir gaukite išsamų atsiliepimą apie savo kodavimą, algoritmus ir sistemos dizainą.

Iš pradžių paskelbta „Refdash“ tinklaraštyje. „Refdash“ yra interviu platforma, padedanti inžinieriams anonimiškai interviu su patyrusiais inžinieriais iš geriausių bendrovių, tokių kaip „Google“, „Facebook“ ar „Palantir“, ir gauti išsamų atsiliepimą. „Refdash“ taip pat padeda inžinieriams atrasti nuostabias darbo galimybes, pagrįstas jų įgūdžiais ir pomėgiais.