Annak ellenére, hogy jelentős tapasztalattal rendelkezik a szoftvertermékek építésében, sok mérnök idegesnek érzi magát az algoritmusokra összpontosító kódolási interjú gondolatán. Több száz mérnököt interjúvoltam meg a Refdash-nál, a Google-nál és az induló vállalkozásoknál, amelyekben részese lehettem, és a mérnököket nyugtalanító kérdések közé tartoznak a dinamikus programozás (DP).
Számos technológiai vállalat szívesen tesz fel kérdéseket a DP-nek az interjúik során. Miközben vitatkozhatunk arról, hogy hatékonyak-e annak értékelésében, hogy valaki mérnöki szerepben teljesít-e, a DP továbbra is az a terület, amely a mérnököket felkeresi, hogy megtalálják a szeretett munkát.
Dinamikus programozás - kiszámítható és előkészíthető
Az egyik oka annak, hogy személy szerint úgy gondolom, hogy a DP-kérdések nem feltétlenül a legjobb módszerek a mérnöki képesség tesztelésére, az az, hogy kiszámíthatóak és könnyen összeilleszthetők. Lehetővé teszik számunkra, hogy a mérnöki képességekkel szemben sokkal többet szűrjünk a felkészültségre.
Ezek a kérdések általában kívülről meglehetősen bonyolultnak tűnnek, és azt a benyomást kelthetik, hogy az a személy, aki megoldja őket, nagyon jó az algoritmusokban. Hasonlóképpen, azok az emberek, akik esetleg nem tudnak túllépni a DP néhány tudatforgató fogalmán, elég gyengének tűnhetnek az algoritmusok ismeretében.
A valóság más, és teljesítményük legnagyobb tényezője a felkészültség. Tehát győződjünk meg róla, hogy mindenki felkészült rá. Egyszer, s mindenkorra.
7 lépés a dinamikus programozási probléma megoldásához
A bejegyzés további részében áttekintek egy receptet, amelyet követve megtudhatja, hogy a probléma „DP-probléma”-e, valamint hogy megoldást találjon egy ilyen problémára. Pontosabban a következő lépéseket fogom elvégezni:
- Hogyan lehet felismerni a DP problémát
- Azonosítsa a problémaváltozókat
- Világosan fejezze ki az ismétlődési összefüggést
- Határozza meg az alapeseteket
- Döntse el, hogy iteratívan vagy rekurzívan kívánja-e megvalósítani
- Jegyzet hozzáadása
- Határozza meg az idő összetettségét
Minta DP probléma
Annak érdekében, hogy legyen egy példa absztrakciókra, amelyeket fogok készíteni, hadd vezessek be egy minta problémát. Az egyes szakaszokban utalni fogok a problémára, de olvashatná a szakaszokat a problémától függetlenül is.
Probléma megállapítás:
Ebben a problémában egy őrült ugró labdán vagyunk, próbálunk megállni, miközben elkerüljük a tüskéket.
Itt vannak a szabályok:
1) Lapos kifutópályát kapsz, benne egy rakás tüskével. A kifutópályát logikai tömb reprezentálja, amely jelzi, hogy egy adott (diszkrét) hely nem rendelkezik-e tüskékkel. Igaz a világosra és a hamis a nem egyértelműre.
Példa tömb ábrázolásra:
2) Ön megkapja az S. kezdősebességet. S egy adott ponton nem negatív egész szám, és jelzi, hogy mennyit halad előre a következő ugrással.
3) Minden alkalommal, amikor egy helyszínen landol, a következő ugrás előtt legfeljebb 1 egységgel állíthatja be sebességét.
4) A kifutópálya mentén bárhol biztonságosan meg akar állni (nem kell a tömb végén lennie). Akkor áll meg, amikor a sebessége 0-ra válik. Ha azonban bármelyik ponton csúcsra száll, az őrült pattogó labdája felszakad, és a játéknak vége.
A függvény kimenetének logikai értéknek kell lennie, jelezve, hogy biztonságosan megállhatunk-e bárhol a kifutópálya mentén.
1. lépés: Hogyan lehet felismerni a dinamikus programozási problémát
Először tegyük világossá, hogy a DP lényegében csak egy optimalizálási technika. A DP módszer a problémák megoldására azáltal, hogy egyszerűbb részproblémák gyűjteményévé bontja őket, az egyes részproblémákat csak egyszer oldja meg, és tárolja a megoldásaikat. A következő alkalommal, amikor ugyanaz a részprobléma jelentkezik, ahelyett, hogy újraszámolná a megoldását, egyszerűen meg kell keresnie a korábban kiszámolt megoldást. Ez megtakarítja a számítási időt a (remélhetőleg) mérsékelt tárhely-ráfordítás rovására.
Az első és gyakran a legnehezebb lépés annak felismerése, hogy egy probléma megoldható a DP használatával. Azt szeretné feltenni magának, hogy a problémamegoldása kifejezhető-e hasonló kisebb problémák megoldásának függvényében.
Példaproblémánk esetén adott egy pontot a kifutópályán, a sebességet és az előttünk álló kifutópályát meghatározhattuk azokat a helyeket, ahol potenciálisan továbbugrhatunk. Továbbá úgy tűnik, hogy az, hogy megállhatunk-e az aktuális pontról az aktuális sebességgel, csak attól függ, hogy megállhatunk-e abból a pontról, amelyet választunk a következőre.
Ez nagyszerű dolog, mert az előre haladással lerövidítjük az előre futó pályát és kisebbé tesszük a problémánkat. Képesnek kell lennünk végig ismételni ezt a folyamatot, amíg el nem jutunk egy olyan ponthoz, ahol nyilvánvaló, hogy megállhatunk-e.
A dinamikus programozási probléma felismerése gyakran a legnehezebb lépés a megoldás megoldásában. Kifejezhető-e a problémamegoldás hasonló kisebb problémák megoldásának függvényében?2. lépés: A problémaváltozók azonosítása
Most megállapítottuk, hogy az alproblémáink között van némi rekurzív szerkezet. Ezután meg kell fejeznünk a problémát a függvényparaméterek szempontjából, és meg kell látnunk, hogy ezek a paraméterek melyik változik.
Az interjúk során általában egy vagy két változó paramétered lesz, de technikailag ez tetszőleges szám lehet. Az egy változó paraméterű probléma klasszikus példája a „n-edik Fibonacci-szám meghatározása”. Ilyen példa egy két változó paraméterű problémára: „A karakterláncok közötti szerkesztési távolság kiszámítása”. Ha nem ismeri ezeket a problémákat, ne aggódjon miatta.
A változó paraméterek számának meghatározásához több alprobléma példáját kell felsorolni és összehasonlítani a paramétereket. A változó paraméterek számbavétele értékes annak a részproblémának a meghatározásához, amelyet meg kell oldanunk. Önmagában is fontos, mivel segít megerősíteni az ismétlődő összefüggések megértését az 1. lépéstől kezdve.
Példánkban a két paraméter, amely minden részprobléma esetében megváltozhat:
- Tömb pozíció (P)
- Sebesség (S)
Mondhatnánk, hogy az előttünk álló kifutópálya is változik, de ez felesleges lenne, tekintve, hogy a teljes nem változó kifutópálya és a helyzet (P) már hordozza ezeket az információkat.
Ezzel a 2 változó paraméterrel és más statikus paraméterekkel megkapjuk az alproblémáink teljes leírását.
Határozza meg a változó paramétereket és határozza meg az alproblémák számát.3. lépés: Világosan fejezze ki az ismétlődési összefüggést
Ez egy fontos lépés, amelyet sokan végigszaladnak a kódoláshoz való hozzáférés érdekében. A megismétlődés relációjának lehető legegyértelműbb kifejezése megerősíti a probléma megértését és minden mást jelentősen megkönnyít.
Miután rájött, hogy az ismétlődési összefüggés létezik, és megadja a problémákat a paraméterek szempontjából, ennek természetes lépésnek kell lennie. Hogyan viszonyulnak egymáshoz a problémák? Más szóval, tegyük fel, hogy kiszámította az alproblémákat. Hogyan számolná ki a fő problémát?
Így gondolkodunk róla a mintaproblémánkban:
Mivel a következő pozícióba ugrás előtt akár 1-vel is beállíthatja a sebességét, csak 3 lehetséges sebesség áll rendelkezésre, tehát 3 olyan pont, amelyekben mi következhetnénk.
Formálisan, ha a sebességünk S, P helyzet, akkor az (S, P) pontról a következőre haladhatunk:
- (S, P + S) ; # ha nem változtatjuk meg a sebességet
- (S - 1, P + S - 1) ; # ha -1-el változtatjuk a sebességet
- (S + 1, P + S + 1) ; # ha +1-vel változtatjuk a sebességet
Ha a fenti részproblémák bármelyikében találunk megállási módot, akkor (S, P) is megállhatunk. Ennek oka az, hogy áttérhetünk az (S, P) lehetőségről a fenti három lehetőség bármelyikére.
Ez általában a probléma megértésének megfelelő szintje (egyszerű magyarázat), de néha érdemes matematikailag is kifejeznie a kapcsolatot. Hívjunk egy függvényt, amelyet a canStop kiszámításához próbálunk meg. Akkor:
canStop (S, P) = canStop (S, P + S) || canStop (S - 1, P + S - 1) || canStop (S + 1, P + S + 1)
Woohoo, úgy tűnik, megvan a visszatérő viszonyunk!
Ismétlődés összefüggés: Ha feltételezzük, hogy kiszámította az alproblémákat, hogyan számítja ki a fő problémát?4. lépés: Határozza meg az alapeseteket
Az alapeset olyan részprobléma, amely nem függ más részproblémától. Ilyen részproblémák megtalálásához általában néhány példát szeretne kipróbálni, megnézni, hogyan egyszerűsödik a problémája kisebb részproblémákká, és meghatározni, hogy melyik ponton nem lehet tovább egyszerűsíteni.
A probléma tovább nem egyszerűsíthető, mert az egyik paraméter olyan értékké válik, amely a probléma korlátai miatt nem lehetséges .
Példapéldánkban két változó paraméterünk van, S és P. Gondoljunk csak arra, hogy az S és P lehetséges értékei miért nem legálisak:
- P-nek az adott kifutópálya határain belül kell lennie
- P nem lehet olyan, hogy a [P] kifutópálya hamis, mert ez azt jelentené, hogy tüskén állunk
- S nem lehet negatív, és S == 0 azt jelzi, hogy készen vagyunk
Néha kissé nehéz lehet a paraméterekkel kapcsolatos állításokat programozható alapesetekké konvertálni. Ennek oka az, hogy az állítások felsorolása mellett, ha azt akarja, hogy a kód tömör legyen, és ne ellenőrizze a felesleges feltételeket, gondolkodnia kell azon is, hogy ezek a feltételek közül melyek is lehetségesek.
Példánkban:
- P <0 || P> = a kifutópálya hossza helyesnek tűnik. Alternatív megoldás lehet a P == kifutópálya végének hasonlítása alapesetnek. Lehetséges azonban, hogy egy probléma olyan részproblémává válik, amely túlmutat a kifutópálya végén, ezért valóban ellenőriznünk kell az egyenlőtlenséget.
- Ez elég nyilvánvalónak tűnik. Egyszerűen ellenőrizhetjük, hogy a [P] kifutópálya hamis-e .
- Hasonlóan az # 1-hez, egyszerűen ellenőrizhetjük, hogy S <0 és S == 0. Ugyanakkor itt megalapozhatjuk, hogy lehetetlen, hogy S <0 legyen, mert S legfeljebb 1-rel csökken, ezért át kell mennie S == 0 eset előzetesen. Ther efore S == 0 elegendő bázis esetében az S paraméter.
5. lépés: Döntse el, hogy iteratívan vagy rekurzívan kívánja-e megvalósítani
Az, ahogyan az eddigi lépésekről beszéltünk, arra késztetheti Önt, hogy rekurzív módon kell megoldanunk a problémát. Mindazonáltal, amiről eddig beszéltünk, teljesen agnosztikus abban a tekintetben, hogy a probléma rekurzív vagy iteratív végrehajtása mellett dönt. Mindkét megközelítésben meg kell határoznia a megismétlődés összefüggését és az alapeseteket.
Gondosan át kell gondolnia a kompromisszumokat annak eldöntéséhez, hogy iteratívan vagy rekurzívan folytassa-e .
A verem túlcsordulási problémák általában üzletkötők, és ezért nem akarnak rekurziót végrehajtani egy (háttér) termelési rendszerben. Az interjú szempontjából azonban mindaddig, amíg megemlíti a kompromisszumokat, általában bármelyik megvalósítással jól kell esnie. Kényelmesen éreznie kell mindkettőt.
Sajátos problémánkban mindkét verziót megvalósítottam. Itt van ennek python kódja:
Rekurzív megoldás: (eredeti kódrészletek itt találhatók)
Iteratív megoldás: (eredeti kódrészletek itt találhatók)
6. lépés: Adjon hozzá emlékeztetőt
A memória egy olyan technika, amely szorosan kapcsolódik a DP-hez. A drága függvényhívások eredményeinek tárolására és a gyorsítótárazott eredmény visszaadására szolgál, amikor ugyanazok a bemenetek ismét előfordulnak.
Miért egészítjük ki az emlékeztetőt a rekurziónkba? Ugyanazokkal a problémákkal találkozunk, amelyeket emlékeztetés nélkül többször kiszámolunk. Ezek az ismétlések nagyon gyakran exponenciális időbeli bonyolultsághoz vezetnek.
Rekurzív megoldásokban a memóriák hozzáadásának egyszerűnek kell lennie. Lássuk miért. Ne feledje, hogy az emlékeztető csak a függvény eredményeinek gyorsítótára. Vannak esetek, amikor el akar térni ettől a definíciótól néhány kisebb optimalizálás kiszűrése érdekében, de a memoizálás funkció-eredmény-gyorsítótárként való kezelése a leg intuitívabb módja annak megvalósítására.
Ez azt jelenti, hogy:
- Minden visszatérési utasítás előtt tárolja a funkció eredményét a memóriájában
- Mielőtt bármilyen más számítást végezne, keresse meg a memóriában a függvény eredményét
Itt van a fenti kód, hozzáadott emlékeztetővel (a hozzáadott sorok kiemelve vannak): (az eredeti kódrészletek itt találhatók)
Az emlékeztetés és a különböző megközelítések hatékonyságának bemutatása érdekében végezzünk néhány gyors tesztet. Stressz-tesztet teszek mindhárom módszerről, amelyet eddig láttunk. Itt van a beállítás:
- Létrehoztam egy 1000 hosszúságú kifutópályát, véletlenszerű helyeken lévő tüskékkel (úgy döntöttem, hogy annak a valószínűsége, hogy a tüske egy adott helyen 20% legyen)
- initSpeed = 30
- Minden funkciót tízszer futtattam, és mértem a végrehajtás átlagos idejét
Itt vannak az eredmények (másodpercben):
Láthatja, hogy a tiszta rekurzív megközelítés körülbelül 500-szor több időt vesz igénybe, mint az iteratív megközelítés, és körülbelül 1300-szor több időt vesz igénybe, mint a memóriával végzett rekurzív megközelítés. Vegye figyelembe, hogy ez az eltérés a kifutópálya hosszával gyorsan növekedni fog. Javaslom, próbálja ki maga a futtatást.
7. lépés: Határozza meg az idő összetettségét
Van néhány egyszerű szabály, amely megkönnyíti a dinamikus programozási probléma időbeli összetettségének kiszámítását. Itt van két lépés, amelyet meg kell tennie:
- Számolja meg az állapotok számát - ez a probléma változó paramétereinek számától függ
- Gondoljon az egyes államokban elvégzett munkára. Más szóval, ha egy állapot kivételével minden mást kiszámítottak, mennyi munkát kell elvégeznie az utolsó állapot kiszámításához?
Példapéldánkban az állapotok száma | P | * | S |, ahol
- P az összes pozíció halmaza (| | P | a P elemének számát jelöli)
- S az összes sebesség beállítása
Az egyes állapotok szerint elvégzett munka ebben a problémában O (1), mert az összes többi állapotra tekintettel egyszerűen 3 részproblémát kell megvizsgálnunk a kapott állapot meghatározásához.
Amint azt a kódban korábban megjegyeztük, | S | a futópálya hossza korlátozza (| P |), így azt mondhatnánk, hogy az állapotok száma | P | ² | ²).
Úgy tűnik azonban, hogy | S | tovább korlátozható, mert ha valóban | P | lenne, akkor nagyon egyértelmű, hogy a megállás nem lehetséges, mert az első lépésnél meg kell ugrania a teljes kifutópálya hosszát.
Tehát nézzük meg, hogyan tudnánk szorosabbra fűzni a | S | -t. Hívjuk a maximális sebességet S. Tegyük fel, hogy a 0. pozícióból indulunk ki. Mennyire tudnánk megállni, ha a lehető leghamarabb megpróbálnánk megállni, és ha figyelmen kívül hagynánk a lehetséges tüskéket?
Az első iterációban legalább a pontra (S-1) kellene jutnunk, ha nullánkat -1-el állítjuk. Innentől kezdve legalább (S-2) előrelépnénk, és így tovább.
L hosszúságú kifutópálya esetén a következőknek kell lenniük:
=> (S-1) + (S-2) + (S-3) +…. + 1 <L
=> S * (S-1) / 2 <L
=> S² - S - 2L <0
Ha megtalálja a fenti funkció gyökereit, ezek a következők lesznek:
r1 = 1/2 + sqrt (1/4 + 2L) és r2 = 1/2 - sqrt (1/4 + 2L)
Írhatjuk egyenlőtlenségünket:
(S - r1) * (S - r2) < ; 0
Figyelembe véve, hogy S - r2> 0 bármely S> 0 és L> 0 esetén, a következőkre van szükségünk:
S - 1/2 - sqrt (1/4 + 2L) < ; 0
=> S <1/2 + sqrt (1/4 + 2L)
Ez az a maximális sebesség, amelyet egy L hosszúságú kifutón megtehetünk. Ha ennél nagyobb sebességünk lenne, akkor elméletileg sem állhatnánk meg, függetlenül a tüskék helyzetétől.
Ez azt jelenti, hogy a teljes időbonyolultság csak az L kifutópálya hosszától függ a következő formában:
O (L * sqrt (L)), amely jobb, mint O (L²)
O (L * sqrt (L)) az idő bonyolultságának felső határaFélelmetes, végigcsináltad! :)
A 7 lépés, amelyet átéltünk, keretet adhat a dinamikus programozási problémák szisztematikus megoldásához. Nagyon ajánlom, hogy gyakorolja ezt a megközelítést még néhány problémán, hogy tökéletesítse a megközelítését.
Íme néhány következő lépés, amelyet megtehet
- Hosszabbítsa ki a minta problémáját úgy, hogy megpróbál egy utat találni egy megállóhoz. Megoldottunk egy problémát, amely megmondja, hogy tud-e megállni, de mi van akkor, ha meg szeretné tudni a lépéseket is, hogy végül megálljon a kifutópályán? Hogyan módosítaná a meglévő megvalósítást ennek érdekében?
- Ha meg akarja erősíteni az emlékeztetés megértését, és meg akarja érteni, hogy ez csak egy függvény eredmény-gyorsítótár, olvassa el a Python dekorátorait vagy más nyelvű hasonló fogalmakat. Gondoljon arra, hogyan engednék meg általánosságban a memóriák végrehajtását minden olyan funkcióhoz, amelyet memóriázni szeretne.
- Dolgozzon további DP-problémákon az általunk átélt lépések követésével. Egy csomót mindig megtalálhat online (pl. LeetCode vagy GeeksForGeeks). Gyakorlás közben tartson szem előtt egy dolgot: tanuljon ötleteket, ne tanuljon problémákat. Az ötletek száma lényegesen kisebb, és ez egy könnyebb teret hódítani, ami szintén sokkal jobban szolgál.
Amikor úgy érzi, hogy meghódította ezeket az ötleteket, nézze meg a Refdash oldalt, ahol egy vezető mérnök kérdezi meg Önt, és kapjon részletes visszajelzést a kódolásáról, az algoritmusokról és a rendszer tervezéséről.
Eredetileg a Refdash blogban jelent meg. A Refdash egy interjúplatform, amely segít a mérnököknek anonim interjúban olyan vezető vállalatok tapasztalt mérnökeivel, mint a Google, a Facebook vagy a Palantir, és részletes visszajelzést kapnak. A Refdash segít a mérnököknek is elképesztő munkalehetőségeket felfedezni képességeik és érdeklődésük alapján.