[Powered by Google Translate] [Szeminárium: Technical Interjúk]
[Kenny Yu, a Harvard Egyetem]
[Ez a CS50.] [CS50.TV]
Szia mindenki, én vagyok Kenny. Én jelenleg a junior tanul számítástechnika.
Én egy korábbi CS TF, és azt kívánom, bárcsak volna ezt, amikor voltam underclassman,
és ezért adok ezen a szemináriumon.
Szóval remélem, élvezni.
A szeminárium a technikai interjúk,
és minden erőforrás találhatók meg ezt a linket,
meg ezt a linket itt, egy pár a források.
Úgyhogy csináltam egy listát azokról a problémákról, valóban, jó néhány problémát.
Szintén általános erőforrások oldalt, ahol találunk tippeket
, hogyan kell felkészülni egy interjúra,
tippeket, mit kell tennie során tényleges interjú
valamint azt, hogyan kell megközelíteni problémák és források a jövőben is.
Ez mind online.
És csak bevezetést a szeminárium, a nyilatkozat,
így nem szabad - az interjú elkészítése
nem kell korlátozni ezt a listát.
Ez csak azt jelenti, hogy egy útikönyv,
és akkor feltétlenül tegyen mindent, amit mondok egy csipet só,
hanem használja mindent, amit alkalmaznak, hogy segítsen Önnek az interjú előkészítése.
>> Megyek, hogy gyorsítsa a következő néhány diák
így juthatunk a valós esettanulmányok.
A szerkezet egy interjút a szoftverfejlesztés pozícióját,
Jellemzően 30 és 45 perc,
Több fordulóban, attól függően, hogy a vállalat számára.
Gyakran leszel kódoló egy fehér tábla.
Tehát egy fehér tábla, mint ez, de gyakran kisebb léptékben.
Ha nem egy telefon interjúban, akkor valószínűleg használni
akár collabedit vagy a Google Doc így láthatja élsz kódoló
közben interjút telefonon keresztül.
Egy interjú maga általában 2 vagy 3 problémák
tesztelése a számítástechnikai ismeretek.
És ez szinte biztosan jár kódolás.
A fajta kérdés, hogy látni fogod általában adatstruktúrák és algoritmusok.
És ennek ilyen jellegű problémák,
fogják kérdezni, tetszik, mi az idő és a tér bonyolult, nagy O?
Gyakran ők is kérni magasabb szintű kérdések,
így, tervezése a rendszer,
hogyan kíván feküdt ki a kódot?
Mi interfészek, milyen osztályok, mit modulok nem van a rendszerben,
és hogyan hatnak ezek együtt?
Szóval adatstruktúrák és algoritmusok, valamint a tervezés rendszerek.
>> Néhány általános tipp, mielőtt merülni a mi esettanulmányok.
Azt hiszem, a legfontosabb szabály mindig is hangosan gondolkodtam.
Az interjú állítólag az alkalom, hogy megmutassák a gondolkodási folyamat.
A lényeg az interjú a kérdező, hogy mérje
mit gondol, és hogyan megy keresztül egy probléma.
A legrosszabb dolog, amit tehetünk, csendben az egész interjú.
Ez csak nem jó.
Ha kap egy kérdést, akkor is szeretnénk, hogy győződjön meg róla, hogy megértette a kérdést.
Tehát ismételjük meg a kérdést vissza a saját szavaiddal
és megpróbálja a munka alapos néhány egyszerű vizsgálati esetek
, hogy győződjön meg róla, hogy megértette a kérdést.
Munka egy pár teszt esetek is kapsz egy intuíció, hogy hogyan oldja meg ezt a problémát.
Lehet, hogy még felfedezni néhány mintát, hogy segítsen megoldani a problémát.
A nagy tipp, hogy nem kap csalódott.
Ne hagyd, hogy csalódott.
Interjúk a kihívást, de a legrosszabb dolog, amit tehetünk,
azon kívül, hogy csendes be kell láthatóan csalódott.
Nem akarod, hogy ennek a benyomást kelti, hogy egy interjúban.
Egy dolog, hogy te - így sok ember, amikor bemegy egy interjúban,
megpróbálják, hogy megpróbálja megtalálni a legjobb megoldást az első,
ha tényleg, ott általában nyilvánvalóvá megoldást.
Lehet, hogy lassú, lehet, hogy nem jó, de akkor csak jelölni azt,
Csak így van egy kiindulási pont, ahonnan jobban működnek.
Is, rámutatva a megoldás lassú, tekintve
big O idő összetettsége vagy térben összetettsége,
bemutatja a kérdezőnek, hogy érti
ezeket a kérdéseket, amikor kódot írni.
Szóval ne félj, hogy dolgozzon ki a legegyszerűbb algoritmus először
majd jobban működjön onnan.
Van még kérdése eddig? Oké.
>> Szóval belevetik magukat az első probléma.
"Mivel egy sor n egészek, írj egy függvényt, amely összekeveri a tömb
helyén oly módon, hogy valamennyi permutációi az n egész számok egyformán valószínű. "
És feltételezzük, hogy van szabad véletlen egész szám generátor
generáló egész szám egy 0-tól I, fél tartomány.
Mindenki érti ezt a kérdést?
Adok neked egy sor n egész számok, és azt akarom, hogy shuffle azt.
Az én könyvtárban írtam néhány programot annak bizonyítására, mire gondolok.
Megyek shuffle egy sor 20-elemek,
-10 és +9,
, és azt akarom, hogy kimenetet egy ilyen lista.
Szóval ez az én rendezett input tömb, és azt akarom, hogy shuffle azt.
Megcsináljuk újra.
Mindenki érti a kérdést? Oké.
Tehát rajtad múlik.
Milyen ötlet? Meg tudod csinálni, mint n ^ 2-n log n, n?
Nyissa meg a javaslatokat.
Oké. Tehát az egyik ötlet által javasolt Emmy,
először kiszámítása egy véletlen szám, véletlen egész szám, egy 0-tól 20-ig.
Így vállalnak a tömb hossza 20.
A mi diagram 20-elemek,
ez a mi input tömb.
És most, az ő javaslata az, hogy hozzon létre egy új tömböt,
így ez lesz a kimeneti tömbben.
Alapján, valamint az i által visszaadott rand -
tehát ha én, mondjuk, 17,
másolja a 17. elemet az első helyen.
Most el kell törölni - meg kell váltani az összes elemet itt
, úgy, hogy van egy rés a végén, és nem lyukak a közepén.
És most ismételje meg a folyamatot.
Most válasszon egy új véletlen egész szám 0 és 19.
Van egy új vagyok itt, és másolja ezt az elemet ebbe a helyzetbe.
Aztán műszak tételeket át, és megismételjük a folyamatot, amíg megvan a teljesen új tömb.
Mi a futási idő ezen algoritmus?
Nos, nézzük meg ennek hatását.
Mi változik minden elemét.
Amikor eltávolításához i, mi változik az összes elemet, miután a bal oldalon.
És ez egy O (n) költség
mert mi van, ha eltávolítja az első elem?
Tehát minden eltávolítására, akkor távolítsa el -
elszállításáról minden egyes alkalommal keletkezik O (n) üzemeltetés,
és mivel már n költöztetés, ez ahhoz vezet, hogy O (n ^ 2) shuffle.
Oké. Szóval jó kezdés. Jó kezdet.
>> Egy másik javaslat az, hogy valami ismert, mint a Knuth shuffle,
vagy a Fisher-Yates shuffle.
És ez valójában egy lineáris idő shuffle.
És az ötlet nagyon hasonló.
Ismét megvan a bemeneti tömb,
de ahelyett, hogy a két tömb számára bemenet / kimenet,
használjuk az első rész a tömb, hogy nyomon követhesse a mi csoszogott részt,
és mi nyomon, majd hagyjuk a többi a mi tömb a unshuffled részét.
Szóval, itt van, amit gondolok. Kezdjük le - mi válasszon i,
tömb 0-20.
A jelenlegi mutató mutat az első index.
Mi választani néhány i itt
és most cserélni.
Szóval, ha ez 5 és ez 4,
A kapott tömb lesz itt 5 és 4 itt.
És most, vegye figyelembe a marker itt.
Minden, ami a bal oldalon van csoszogott,
és minden a jog unshuffled.
És most mi is ismételje meg a folyamatot.
Mi választjuk ki véletlenszerűen index 1 és 20 között van.
Tehát tegyük fel, az új i itt van.
Most cserélni ezt én a mi jelenlegi új helyzet van.
Szóval mi a csere oda-vissza, mint ez.
Hadd hívjam fel a kódot, hogy ez több beton.
Kezdjük a mi választott i -
kezdjük i értéke 0, akkor válasszon egy random helyre j
a unshuffled részében a tömb, az i n-1.
Szóval, ha itt vagyok, válasszon egy véletlenszerű index között, itt és a többi tömb,
és mi cserélni.
Ez mind a kód szükséges shuffle a tömb.
Van még kérdése?
>> Nos, az egyik szükséges, kérdés az, hogy miért van ez a helyes?
Miért van minden permutáció egyformán valószínű?
És nem megy át a bizonyíték erre,
de sok probléma számítógép-tudomány bizonyítani lehet a indukció.
Hányan ismerik indukciós?
Oké. Cool.
Így be lehet bizonyítani a helyességét ezen algoritmus egyszerű indukció,
ahol az indukciós feltevés lenne, feltételezik, hogy
my shuffle visszatér minden permutáció egyformán valószínű
fel, hogy az első i elemeket.
Nos, úgy i + 1.
És hogy hogyan választjuk meg j index a swap,
ez vezet - és akkor dolgozzanak ki a részleteket,
legalább egy teljes bizonyítékot, hogy miért ez az algoritmus visszatér
minden permutáció egyformán valószínű a valószínűsége.
>> Rendben, következő probléma.
Így "az adott tömb egész számok, Pozitív, nulla, negatív,
írni egy függvényt, amely kiszámítja a maximális összeget
bármely continueous subarray a bemeneti tömb. "
Egy példa itt van, abban az esetben, ahol az összes pozitív szám,
akkor jelenleg a legjobb választás az, hogy az egész tömb.
1, 2, 3, 4, egyenlő 10.
Ha van néhány negatív ott,
ebben az esetben csak azt az első két
mert a választott -1 és / vagy -3 viszi a összeget le.
Néha talán el kell kezdenünk a közepén a tömb.
Néha szeretnénk választani semmit, ez a legjobb, hogy nem vesz semmit.
És néha jobb, hogy a bukás,
mert a dolog, miután az szuper nagy. Szóval valami ötleted?
(Diák, érthetetlen) >> Igen.
Tegyük fel, hogy nem veszem -1.
Akkor sem úgy döntök, 1.000 és 20.000,
vagy én csak válassza ki a 3 milliárd euró.
Nos, a legjobb választás az, hogy az összes számot.
Ez a -1, annak ellenére, hogy negatív,
a teljes összeg jobb, mint volt, én nem, hogy -1.
Tehát az egyik a tippeket már korábban említettem volt, hogy azt az egyértelműen nyilvánvaló
és a brute force megoldás először.
Mi a brute force megoldás erre a problémára? Igen?
[Jane] Nos, azt hiszem, a brute force megoldás
lenne, ha összeadja az összes lehetséges kombinációt (érthetetlen).
[Yu] Oké. Tehát Jane ötlete az, hogy minden lehetséges -
Én parafrázisa -, hogy tegyenek meg minden lehetséges folyamatos subarray,
kiszámítása az összeg, majd megteszi a legnagyobb az összes lehetséges folyamatos subarrays.
Mi az egyedileg azonosítja a subarray az én bemeneti tömb?
Mint, milyen két dolgot kell tennem? Igen?
(Diák, érthetetlen) >> Rendben.
Az alsó korlátot az index és a felső kötött index
egyértelműen meghatározza a folyamatos subarray.
[Nő diák] vagyunk becslése, hogy ez egy sor egyedi számok?
[Yu] Szóval ő kérdés az, hogy mi vagyunk feltételezve array -
a mi tömb minden egyedi számokat, és a válasz nem.
>> Ha használja a brute force megoldás, akkor a start / end indexek
egyértelműen meghatározza a folyamatos subarray.
Tehát ha navigálhat az összes lehetséges kezdő tétel,
és minden bejegyzés végére> vagy = kezdeni, és <n,
Ön kiszámítása az összeget, és akkor megteszi a legnagyobb pénzösszeget láttunk eddig.
Érthető ez?
Mi a nagy O e megoldás?
Timewise.
Nem egészen n ^ 2.
Vegyük észre, hogy navigálhat 0-tól n,
úgy, hogy az egyik a hurok.
Mi ismételget újra szinte elejétől a végéig, a másik a hurok.
És most, ezen belül is meg kell összegezni minden bejegyzést,
annak érdekében, hogy egy másik a hurok. Tehát van három egymásba a hurok, n ^ 3.
Oké. Ez megy, mint egy kiindulási pont.
A megoldás nem rosszabb, mint n ^ 3.
Mindenki érti a brute force megoldás?
>> Oké. Egy jobb megoldás segítségével egy ötlet nevű dinamikus programozás.
Ha az előírtnál CS124, amely Algoritmusok és adatszerkezetek,
akkor lesz nagyon ismerik ezt a technikát.
És az ötlet, próbálja felépíteni megoldásokat a kisebb problémákat először.
Mit jelent ez, jelenleg nem kell aggódnia, két dolgot: kezdetét és végét.
És ez bosszantó. Mi lenne, ha tudnánk megszabadulni egy ilyen paraméterek?
Az egyik elképzelés az, hogy - az adott we're az eredeti probléma,
A maximálisan összege bármely subarray közötti tartományban [O-, n-1].
És most van egy új subproblem, ha tudjuk, hogy a jelenlegi i index,
tudjuk, hogy meg kell kötni ott. A subarray véget kell vetni az aktuális index.
Tehát a probléma az, hol kezdjük subarray?
Van ennek értelme? Oké.
Szóval kódolt e fel, és nézzük meg, mit jelent ez.
A codirectory van egy program neve subarray,
és tart tételek száma,
és visszaadja a maximális subarray összeg az én csoszogott listában.
Tehát ebben az esetben, a maximális subarray 3 lehet.
És ez által csak a 2 és az 1.
Fussunk újra. Ez is 3.
De ez alkalommal, vegye figyelembe, hogy megvan a 3.
Mi volt a - mi csak vegye a 3 is
mert ez körül negatívok mindkét oldalon,
amely fog egy összeget <3.
Fussunk a 10 darab.
Ezúttal 7, vesszük a vezető 3 és 4.
Ezúttal 8, és azt kapjuk, hogy azáltal, hogy 1, 4 és 3.
Szóval, hogy ön egy intuíció, hogyan tudjuk megoldani ezt a problémát át,
vessünk egy pillantást erre subarray.
Mi tekintettel e input tömb, és tudjuk, hogy a válasz: 8.
Vesszük a 1, 4, és 3.
De nézzük meg, hogy hogyan van, hogy tényleg választ.
Nézzük meg a maximális subarray végződő mindegyik ilyen indexek.
Mi az a maximális subarray amely véget az első helyen?
[Student] Zero. >> Zero. Csak ne szedje a -5.
Itt lesz 0 is. Igen?
(Diák, érthetetlen)
[Yu] Ó, sajnálom, ez egy -3.
Tehát ez egy 2, ez egy -3.
Oké. Szóval -4, mi a maximális subarray véget ez az álláspont
ahol -4 van? Zero.
Egy? 1, 5, 8.
Nos, véget kell vetni a helyen, ahol a -2 címen.
Így 6, 5, 7, és az utolsó 4 lehet.
Tudva, hogy ezek az én bejegyzések
A transzformált probléma, ahol véget kell vetni ezen egyes indexek
majd a végső válasz csak, hogy egy sweep-át,
és megteszi a maximális számát.
Tehát ebben az esetben ez a 8.
Ez azt jelenti, hogy a maximális subarray ér véget ez a mutató,
és elkezdte valahol előtte.
Mindenki érti ezt át subarray?
>> Oké. Nos, kitaláljuk, a kiújulás erre.
Nézzük csak az első néhány bejegyzéseket.
Így itt volt 0, 0, 0, 1, 5, 8.
És ott volt a -2 itt, és azt hozta le 6-ra.
Tehát, ha hívom a belépési pozícióban i subproblem (i),
hogyan használhatom a választ egy korábbi subproblem
válaszolni erre subproblem?
Ha megnézzük, mondjuk, ezt a bejegyzést.
Hogyan lehet kiszámítani a választ a 6 nézi most
kombinációja a tömb, és a válaszokat az előző alproblémát ebben a tömbben? Igen?
[Nő diák] Veszel a tömbben összegek
abban a helyzetben, közvetlenül előtte, így a 8,
és akkor hozzá az aktuális subproblem.
[Yu] Szóval ő javaslata, hogy nézd meg a két szám,
ezt a számot, és ezt a számot.
Tehát ez 8 utal a választ a subproblem (i - 1).
És hívjuk a bemeneti tömb A.
Annak érdekében, hogy a maximális subarray végződő pozícióban i,
Van két lehetőség közül választhat: vagy tudom folytatni subarray
hogy véget ért a korábbi index, vagy indítson új tömb.
Ha én lennék, hogy folytassák a subarray indult az előző index,
akkor a maximális összeg tudom elérni a válasz az előző subproblem
és a folyó tömb bejegyzést.
De, én is a választás a kezdő új subarray,
amely esetben az összeg 0.
Tehát a válasz: max 0, subproblem i - 1, valamint a jelenlegi tömb bejegyzést.
Van ennek megismétlődése értelme?
A kiújulás, ahogy most fedezem fel, nem subproblem i
egyenlő a maximális az előző subproblem plusz mostani tömb bejegyzés,
ami azt jelenti, továbbra is a korábbi subarray,
vagy 0, indítson új subarray én aktuális index.
És ha egyszer már épített ki ezt a táblázatot a megoldások, majd a végső választ,
Csak nem egy lineáris sweep-szerte subproblem tömb
és megteszi a maximális számát.
Ez egy pontos megvalósítása, amit mondtam.
Tehát egy új subproblem tömb, alproblémát.
Az első bejegyzés 0 vagy az első bejegyzés, a legnagyobb e kettő.
És a többi alproblémát
használjuk a pontos ismétlődés már csak fel.
Most kiszámítani a legnagyobb a mi alproblémát tömb, és ez a végső válasz.
>> Szóval, mennyi hely vagyunk használ ez az algoritmus?
Ha csak venni CS50, akkor lehet, hogy nem tárgyalt terület nagyon.
Nos, az egyik dolog megjegyezni, hogy hívtam malloc itt méretű n.
Mit javasol az Ön számára?
Ez az algoritmus lineáris tér.
Tehetünk a jobb?
Van valami, azt tapasztalja, hogy nem szükséges, hogy kiszámolja a végleges válasz?
Azt hiszem, egy jobb kérdés az, hogy milyen információk
tudjuk nem kell folytatni végig a vége?
Most, ha megnézzük a két vonal,
csak érdekel az előző subproblem,
és csak érdekel a legnagyobb, amit valaha láttunk eddig.
Ahhoz, hogy kiszámításához a végső választ, akkor nem kell az egész tömb.
Csak kell az utolsó szám, az elmúlt két szám.
Utolsó szám a subproblem tömb, és az utolsó szám a maximum.
Tehát, valójában, tudjuk biztosíték ezeket hurok együtt
és menjen a lineáris tér állandó helyet.
Jelenlegi összeget eddig itt, helyettesíti a szerepe subproblem, mi subproblem tömb.
Tehát a jelenlegi összeget, eddig a válasz az előző subproblem.
És ez az összeg, hogy eddig azon a helyen a mi max.
Mi kiszámításához a maximális, ahogy megy végig.
És így megy lineáris tér állandó hely,
és mi is lineáris megoldás a subarray probléma.
>> Az ilyen típusú kérdésekre kapsz egy interjú során.
Mennyi idő komplexitás, mi a tér bonyolult?
Tudsz jobbat? Vannak dolgok, amelyek felesleges, hogy itt van?
Én ezt kiemelni elemzéseket, hogy meg kell venni a saját
ahogy dolgozunk át ezeket a problémákat.
Mindig kell, hogy megkérdeznéd magadtól: "Tudok jobbat?"
Tény, hogy tudunk jobban, mint ez?
Valahogy egy beugratós kérdés. Nem lehet, mert kell, hogy
Legalább olvasd el a bemenetet a problémát.
Így az a tény, hogy meg kell, hogy legalább olvasni a bemeneti a probléma
azt jelenti, hogy nem jobb, mint a lineáris idő,
és akkor nem jobb, mint az állandó helyet.
Tehát ez, valójában, a legjobb megoldás erre a problémára.
Kérdései vannak? Oké.
>> Tőzsdei probléma:
"Mivel egy sor n egész számok, pozitív, nulla, vagy negatív
hogy képviselje az ára a készlet több mint n nap,
levelet funkció kiszámolja a maximális profit megteheti
tekintve, hogy vásárolni és eladni pontosan 1 stock ezekben n nap. "
Lényegében szeretnénk vásárolni alacsony eladni magas.
És azt akarjuk, hogy kitaláljuk, a legjobb eredmény tehetjük.
Visszatérve az én tip, mi az azonnal világos, legegyszerűbb válasz, de ez lassú?
Igen? (Diák, érthetetlen) >> Igen.
>> Szóval akkor csak menj, bár, és nézd meg a tőzsdei árfolyamok
minden egyes időpontban, (érthetetlen).
[Yu] Oké, szóval neki megoldás - ő javaslatára számítástechnika
a legalacsonyabb és a legmagasabb számítása nem feltétlenül működik
mert a legmagasabb előfordulhat, mielőtt a legalacsonyabb.
Tehát mi a brute force megoldás erre a problémára?
Mi az a két dolog, amit meg kell egyértelműen meghatározni a profit teszek? Rendben.
A brute force megoldás - Ó, igen, George javaslat az, hogy mindössze két nap alatt
egyedileg meghatározni a profit e két nap alatt.
Tehát számolni minden pár, mint vétel / eladás,
kiszámítja a profit, ami lehet pozitív vagy negatív, vagy nulla.
Számítsuk ki a maximális profit, hogy mi teszi után iterációjával egész pár nap.
Ez lesz a végső válasz.
És ez lesz a megoldás O (n ^ 2), mert n választani két pár -
napok közül lehet választani end nap.
Oké, én nem megyek át a brute force megoldás itt.
Fogom mondani, hogy van egy n log n megoldás.
Mi az algoritmus nem Ön jelenleg tudni, hogy n log n?
Ez nem egy trükkös kérdés.
>> Merge sort. Merge sort n log n,
és valóban, az egyik módja a probléma megoldása az, hogy az
összeolvasztás egyfajta egyfajta ötlet hívják, általában oszd meg és uralkodj.
És az elképzelés a következő.
Azt akarod, hogy kiszámolja a legjobb vétel / eladás pár a bal felét.
Keresse meg a legjobb eredmény lehet, hogy, csak az első n két nap alatt.
Ezután szeretnéd oompute legjobb vétel / eladás pár a jobb felét,
így az utolsó n keresztül két nap.
És most az a kérdés, hogyan egyesítik ezeket a megoldásokat újra együtt?
Igen? (Diák, érthetetlen)
>> Oké. Szóval hadd dolgozzon ki egy képet.
Igen? (George, érthetetlen)
>> Pontosan. George megoldás pontosan így van.
Szóval ő javaslatára az első kiszámíthatjuk a legjobb vétel / eladás pár,
és az fordul elő, hogy a bal oldalán, így hívjuk, hogy a bal, bal.
A legjobb vétel / eladás pár fordul elő, hogy a jobb felét.
De ha csak, mint a két szám, mi hiányzik az ügy
ahol vásárolni és eladni itt valahol a jobb felét.
Veszünk a bal fele, eladni a jobb felét.
És a legjobb módja annak, hogy kiszámolja a legjobb vétel / eladás pár ível Mindkét félidőt
van, hogy kiszámolja a minimális itt és kiszámítja a maximális ide
és megteszi a különbséget.
Így a két esetben, amikor a vásárlás / eladás pár fordul elő csak itt,
csak itt, vagy mindkét fél határozza három számokat.
Szóval mi algoritmus egyesítése megoldásaink újra együtt,
szeretnénk, hogy kiszámolja a legjobb vétel / eladás pár
ahol vásárolni a bal felét, és eladni a jobb felét.
És a legjobb módja, hogy az, hogy kiszámolja a legalacsonyabb árat az első félévben,
a legmagasabb ár a jobb felére, és megteszi a különbséget.
A kapott 3 nyereséget, ez a három számot, akkor megteszi a legnagyobb a három,
és ez a legjobb eredmény lehet, hogy át ezek az első és a végső napon.
Itt a legfontosabb vonalak piros.
Ez egy rekurzív hívás kiszámolja a választ a bal felét.
Ez egy rekurzív hívás kiszámolja a választ a jobb felét.
Ez a két hurok számára kiszámolja a min és a max szintjét a bal és jobb fele, illetve.
Most kiszámítani a nyereség, amely felöleli mindkét felét,
és a végső válasz a maximális e három.
Oké.
>> Szóval, biztos, hogy van egy algoritmust, de a nagyobb kérdés az,
mi az idő összetettsége ez?
És az ok, amiért említettem merge sort, hogy ez a formája osztani a válasz
két, majd egyesülő megoldásaink újra együtt
pontosan formában merge sort.
Szóval hadd menjen végig az időtartamot.
Ha definiált egy függvény t (n), hogy a lépések számát
n nap,
a két rekurzív hívás
mindegyike fog kerülni t (n / 2),
és van két ilyen hívások.
Most ki kell számolnunk a legkisebb a bal fele,
amit tehet n / 2 alkalommal, valamint a legnagyobb a jobb felét.
Tehát ez éppen n.
És akkor plusz néhány állandó munkát.
És ez az ismétlődés egyenlet
pontosan az ismétlődés egyenlet merge sort.
És mindannyian tudjuk, hogy az egyesítés rendezés n log n idő.
Ezért a mi algoritmus is n log n idő.
Van ennek iterációs értelme?
Csak egy rövid bedugni ebből:
T (n) a lépések számát, hogy kiszámolja a maximális profit
folyamán n nap.
Ahogy mi különválnak a rekurzív hívások
az hívja a megoldás az első n / 2 nap,
így ez egy hívás,
és akkor hívja újra a második felét.
Szóval ez két hívást.
Aztán találunk egy minimum a bal fele, amit tehetünk a lineáris idő,
megtalálja a legnagyobb a jobb fele, amit tehetünk a lineáris időben.
Így n / 2 + n / 2 csak n.
Aztán van néhány állandó munka, ami olyan, mint csinál számtani.
A visszatérő egyenlet pontosan az ismétlődés egyenlet merge sort.
Ezért, a shuffle algoritmus is n log n.
Szóval, mennyi hely vagyunk használ?
Menjünk vissza a kódot.
>> Egy jobb kérdés, hány stack frame tudjuk valaha is bármely adott pillanatban?
Mivel mi vagyunk a rekurzió,
száma stack frame meghatározza az űr használat.
Vegyük n = 8.
Felhívjuk shuffle 8-án,
amely hívja shuffle az első négy bejegyzéseket,
ami meg fogja hívni a shuffle az első két bejegyzés.
Így a verem - ez a mi verem.
És akkor hívjuk újra shuffle 1-jén,
és ez az, amit mi alap eset, úgyhogy vissza azonnal.
Vajon valaha több, mint ez a sok stack frame?
No. Mivel minden egyes alkalommal, amikor csinál egy könyörgés,
rekurzív hívása a shuffle,
osztjuk a mérete a felére.
Így a maximális számú köteg képkockák mi valaha bármely pillanatban
van nagyságrendű log n stack kereteket.
Minden stack frame van állandó hely,
és ezért a teljes összegét terület,
maximális összege hely amit valaha is használni O (log n) space
ahol n jelentése a napok száma.
>> Nos, mindig kérdezd meg magadtól: "Tudunk jobbat?"
És különösen, tudjuk csökkenteni, hogy ez egy probléma, amit már megoldott?
Egy tipp: csak tárgyalt két másik probléma, mielőtt ez, és ez nem lesz shuffle.
Mi lehet konvertálni a tőzsde problémát a maximális subarray problémát.
Hogyan tudjuk ezt megtenni?
Az egyik te? Emmy?
(Emmy, érthetetlen)
[Yu] Pontosan.
Tehát a maximális subarray problémát,
keresünk összeget több mint egy folyamatos subarray.
És Emmy javaslatot, a készletek probléma,
fontolja meg a változásokat, vagy a delták.
És egy képet ez - ez az ára a készlet,
de ha volt a különbség az egymást követő nap -
úgy látjuk, hogy a legmagasabb árat, maximális profit tudtuk, hogy
, ha vásárolunk itt és eladni itt.
De nézzük meg a folyamatos - nézzük a subarray problémát.
Tehát itt van, tudjuk, hogy - haladva itt van,
van egy pozitív változás, aztán megy innen, hogy itt van egy negatív változás.
De aztán, megy innen, hogy itt van egy óriási pozitív változást.
És ezek a változások, hogy szeretnénk összegezni, hogy a végső eredmény.
Akkor már több negatív változások itt.
A legfontosabb, hogy csökkentsük a Stock probléma a mi maximális subarray probléma
hogy fontolja meg a delta nap között.
Így létre egy új tömböt nevű delták,
inicializálni az első bejegyzés a 0,
, majd ezt követően minden egyes delta (i), legyen az a különbség
az én input array (i) és array (i - 1).
Aztán hívja rutin eljárás a maximális subarray
halad a delta a tömböt.
És mivel a maximális subarray lineáris idő,
és ez a csökkenés, ez a folyamat létrehozásának a delta tömb,
szintén lineáris idő,
majd a végső megoldás az állományok O (n) munkát plus O (n) a munka, még mindig O (n) munkát.
Tehát van egy lineáris idő megoldás a problémára.
Mindenki érti ezt az átalakulást?
>> Általában egy jó ötlet, hogy meg kell mindig
van próbálja csökkenteni egy új probléma, hogy látsz.
Ha úgy néz ki, ismerős egy régi probléma,
próbálja csökkenteni, hogy egy régi probléma.
És ha tudod használni minden eszközt, amit használni a régi probléma
, hogy megoldja az új problémát.
Szóval, hogy lezárja a műszaki interjúk kihívást jelent.
Ezek a problémák valószínűleg néhány a több nehéz problémákat
hogy lehet látni egy interjúban,
így ha nem érti a problémát, hogy én csak fedezni, ez rendben van.
Ezek közül néhány a nagyobb kihívást jelentő problémákat.
Gyakorlás, gyakorlás, gyakorlás.
Adtam egy csomó probléma a tájékoztatót, ezért feltétlenül ellenőrizze e meg.
És sok szerencsét a interjút. Minden az én források beírás most ezt a linket,
és az egyik magas rangú társaság felajánlotta, hogy csinál mock műszaki interjúk,
így ha érdekel, email Will Yao meg az e-mail címre.
Ha van kérdése, akkor kérdezzen.
Van srácok kapcsolatos speciális kérdésekre vonatkozó műszaki interjúk
vagy bármilyen problémát láttunk eddig?
Oké. Hát, sok szerencsét a interjút.
[CS50.TV]