[Powered by Google Translate] [Seminár: Technické Rozhovory]
[Kenny Yu, Harvard University]
[To je CS50.] [CS50.TV]
Ahoj všetci, ja som Kenny. V súčasnej dobe som junior študuje počítačové vedy.
Som bývalý SK TF, a ja som si prial, aby som mal, keď som bol Underclassman,
a to je dôvod, prečo dávam tohto seminára.
Takže dúfam, že sa vám bude páčiť.
Tento seminár je o technických rozhovorov,
a všetky moje zdroje možno nájsť na tomto odkaze,
tento odkaz tu, pár zdrojov.
Tak som si urobil zoznam problémov, v skutočnosti, docela málo problémov.
Tiež všeobecné zdroje stránky, kde môžeme nájsť tipy
o tom, ako sa pripraviť na prijímací pohovor,
tipy na to, čo by ste mali urobiť, pri skutočnom rozhovore,
a ako pristupovať k problémom a zdroje pre budúce použitie.
Je to všetko on-line.
A len preto, aby predhovor tento seminár, zrieknutie,
takhle by to - váš rozhovor príprava
by nemal byť obmedzený v tomto zozname.
To je možné len má byť sprievodca,
a vy by ste mali určite vziať všetko, čo hovorím s trochou soli,
ale tiež použiť všetko, čo som použil, aby vám pomôžu vo vašej rozhovor príprave.
>> Idem do rýchlosti cez niekoľko ďalších snímok
takže sa môžeme dostať do skutočných prípadových štúdií.
Štruktúra rozhovore pre nachádza softvérového inžinierstva,
obvykle je to 30 a 45 minút,
viac kôl, v závislosti na spoločnosti.
Často budete kódovanie na bielom podklade.
Takže biele tabule, ako to, ale často v menšom meradle.
Ak máte telefónny rozhovor, budete pravdepodobne používať
buď collabedit alebo Google Doc, aby mohli vidieť v ktorom žijete, kódovanie
keď ste bol rozhovor po telefóne.
Rozhovor sám je typicky 2 až 3 problémy
testovanie počítačovej vedy znalosti.
A to bude takmer určite zahŕňať kódovanie.
Typy otázok, ktoré uvidíte, sú zvyčajne dátové štruktúry a algoritmy.
A v tom tieto druhy problémov,
budú sa vás opýtať, páči, čo je časová a pamäťová zložitosť, veľký O?
Často sa tiež spýtať na vyššej úrovni otázky,
tak, navrhovanie systému,
ako by ste rozvrhnúť svoj kód?
Čo rozhranie, čo triedy, ktoré moduly máte vo vašom systéme,
a ako tieto ovplyvňujú spolu?
Takže dátové štruktúry a algoritmy, rovnako ako projekčné systémy.
>> Niektoré všeobecné tipy, ako sa ponoríme do našich prípadových štúdií.
Myslím, že najdôležitejšie pravidlo je vždy myslieť nahlas.
Rozhovor by mal byť vaša šanca predviesť svoje myslenie proces.
Bod rozhovore je pre anketára, aby zistili,
ako si myslíte, a ako si prejsť problém.
Najhoršie, čo môžete urobiť, je byť ticho celom rozhovore.
To je proste k ničomu.
Ak máte k dispozícii otázku, budete tiež chcieť, aby sa ubezpečil, aby ste pochopili otázku.
Takže zopakovať otázku späť vlastnými slovami
a pokus o prácu dôkladné niekoľko jednoduchých testovacích prípadov
aby sa ubezpečil, aby ste pochopili otázku.
Práca cez niekoľko testovacích prípadov bude aj vám intuícia o tom, ako tento problém vyriešiť.
Dalo by sa dokonca objaviť niekoľko vzory, ktoré vám pomôžu problém vyriešiť.
Ich veľkou tip je nie je frustrovaný.
Nenechajte si frustrovaní.
Rozhovory sú náročné, ale to najhoršie, čo môžete urobiť,
Okrem toho, že tichý, je potrebné viditeľne frustrovaný.
Nechcete, aby tento dojem na anketára.
Jedna vec, ktorú - tak, veľa ľudí, keď idú do rozhovoru,
sa pokúsi, aby sa pokúsili nájsť najlepšie riešenie prvej,
keď v skutočnosti, tam je zvyčajne bije do očí riešenie.
To môže byť pomalé, môže to byť neefektívne, ale mali by ste len uviesť to,
Len tak máte východiskový bod, z ktorého sa lepšie pracovať.
Tiež poukázal na riešenie je pomalý, pokiaľ ide o
Veľký O časová zložitosť alebo pamäťová zložitosť,
bude demonštrovať na anketára, že ste porozumeli
Tieto problémy pri písaní kódu.
Takže sa nebojte prísť s najjednoduchším algoritmom prvý
a potom pracovať lepšie odtiaľ.
Akékoľvek otázky tak ďaleko? Dobre.
>> Takže poďme sa ponoriť do našej prvý problém.
"Vzhľadom k tomu, pole celých čísel n, napísať funkciu, ktorá zamieša pole
na mieste tak, že všetky permutácie celých čísel n sú rovnako pravdepodobné. "
A predpokladáme, že máte k dispozícii náhodný generátor integer
ktorý generuje celé číslo v rozmedzí od 0 do i, polovičná rozsah.
Má každý pochopiť túto otázku?
Dávam vám radu celých čísel n, a ja chcem, aby ste to náhodné.
V mojom adresári, napísal som niekoľko programov, ktorými preukážu, čo mám na mysli.
Chystám sa miešať pole 20 prvkov,
-10 Až 9,
a ja chcem, aby ste výstup zoznam, ako je tento.
Tak toto je moja zoradená vstupné pole, a ja chcem, aby ste to náhodné.
Urobíme to znova.
Má každý pochopiť otázku? Dobre.
Takže je to na vás.
Aké sú niektoré nápady? Môžeš to urobiť ako n ^ 2, n log n, n?
Otvorte sa návrhy.
Dobre. Takže jeden nápad, navrhol Emmy,
je prvý vypočítať náhodné číslo, náhodné celé číslo, v rozsahu od 0 do 20 rokov.
Takže predpokladať, naše polia má dĺžku 20.
V našom schéme 20 prvkov,
to je naše vstupné pole.
A teraz, jej návrh je vytvoriť nové pole,
takže to bude výstupné pole.
A na základe aj vrátenej rand -
takže ak som bol, povedzme, 17,
skopírujte 17. prvok do prvej polohy.
Teraz musíme odstrániť - musíme presunúť všetky prvky tu
sa tak, že máme medzery na konci a žiadne diery v strede.
A teraz sme proces opakovať.
Teraz vyberáme nové náhodné číslo medzi 0 a 19.
Máme novú aj tu, a my sme skopírujte tento prvok do tejto polohy.
Potom sme posun položky za nami a my opakujeme, kým máme plnú novú radu.
Čo je doba behu tohto algoritmu?
Dobre, poďme zvážiť dopad tohto.
Sme presúva každý prvok.
Keď sme odstrániť túto ja, sme sa presúva všetky prvky po ňom doľava.
A to je O (n) náklady
pretože to, čo keby sme odstrániť prvý prvok?
Takže pre každý odber, odstránime -
Každý odstránenie nadobudne O (n) operácie,
a pretože sme n sťahovanie, to vedie k O (n ^ 2) miešať.
Dobre. Tak dobrý začiatok. Dobrý začiatok.
>> Ďalšou možnosťou je použiť známy ako shuffle Knuth,
alebo Fisher-Yates shuffle.
A je to vlastne lineárny čas shuffle.
A myšlienka je veľmi podobná.
Opäť, máme vstupné pole,
ale namiesto toho, aby pomocou dvoch polí pre náš vstup / výstup,
používame prvú časť poľa sledovať našej zamiešané časti,
a sledujeme, a potom nechať zvyšok našej pole pre unshuffled časti.
Tak tu je to, čo mám na mysli. Začneme s - zvolíme si aj,
poľa 0-20.
Náš súčasný ukazovateľ ukazuje na prvý index.
Vyberáme niektoré aj tu
a teraz sme vymeniť.
Takže v prípade, že bol 5 a to bolo 4,
Výsledné pole bude mať 5 Tu a 4 tu.
A teraz sme na vedomie, značku tu.
Všetko k ľavici zamiešané,
a všetko vpravo je unshuffled.
A teraz môžeme proces opakovať.
Sme si vybrať náhodný index medzi 1 a 20 teraz.
Takže predpokladám, náš nový aj tu.
Teraz vymeníme to som s našou súčasnou novú pozíciu tu.
Tak sme sa vymieňať tam a späť, ako toto.
Dovoľte mi, aby som vychovať kód, aby to viac konkrétny.
Začneme s našou voľbou aj -
začneme s i rovnať 0, vyberáme náhodné umiestnenie j
v unshuffled časti poľa, aj do n-1.
Takže ak som tu, skúste si vybrať náhodný index medzi tu a zvyšok poľa,
a vymeníme.
To všetko je kód nutné miešať vaše pole.
Nejaké otázky?
>> No, jeden potreboval otázka je, prečo je to správne?
Prečo je každý permutácií rovnako pravdepodobné?
A nebudem prechádzať dôkaz tohto,
ale mnoho problémov v informatike možno dokázať indukciou.
Ako mnohí z vás poznajú s indukciou?
Dobre. Cool.
Takže si môžete overiť správnosť tohto algoritmu jednoduchou indukciou,
, Kde sa vaše indukčné hypotéza by, predpokladajme, že
moje náhodné vracia každý permutácie rovnako pravdepodobné
až prvý som prvkov.
Teraz, zvážte i + 1.
A mimochodom sme sa rozhodli náš index j vymeniť,
to vedie k - a potom prísť na detaily,
aspoň plný dôkaz, prečo tento algoritmus vracia
Každý permutácie sa rovnako pravdepodobné pravdepodobnosťou.
>> Dobre, ďalší problém.
Takže "vzhľadom pole celých čísel, Postive, nula, záporná,
napísať funkciu, ktorá vypočíta maximálnu sumu
akékoľvek continueous subarray vstupné pole. "
Príkladom tu je, v prípade, že všetky čísla sú pozitívne,
potom v súčasnej dobe najlepšou voľbou je vziať celý rad.
1, 2, 3, 4, sa rovná 10.
Ak máte nejaké negatívy tam,
V tomto prípade chceme len prvé dva
pretože výber -1 a / alebo -3 prinesie náš súčet dole.
Niekedy sa môžu mať začať v polovici poľa.
Niekedy chceme vybrať vôbec nič, je to najlepšie, aby nemali nič.
A niekedy je lepšie padnúť,
pretože vec po ňom je super veľká. Takže nejaké nápady?
(Študent, nezrozumiteľné) >> Jo.
Predpokladajme, že neberiem -1.
Potom buď volím 1000 a 20000,
alebo som len stačí vybrať 3000000000.
No, najlepšou voľbou je vziať všetky čísla.
Tento -1, napriek tomu, že je negatívny,
Celá súčet je lepšia, než boli nemôžem vziať -1.
Takže jeden z tipov, ktoré som spomenul predtým, bolo uviesť jasne zrejmé
a hrubou silou riešenie ako prvý.
Čo je brutálna sila riešenie tohto problému? Jo?
[Jane] No, myslím, že brutálny sily roztok
by bolo pridať až všetky možné kombinácie (nezrozumiteľný).
[Yu] Dobre. Takže Jane nápad je vziať všetky možné -
Som prerozprávať - ​​je vziať všetky možné kontinuálne subarray,
vypočítať jej súčet, a potom mať maximálne všetkých možných priebežných subarrays.
Čo jednoznačne identifikuje subarray v mojom vstupné pole?
Rovnako ako to, čo dve veci potrebujem? Jo?
(Študent, nezrozumiteľné) >> Právo.
Dolná hranica indexu a hornú hranicu indexu
jednoznačne určuje priebežné subarray.
[Študentka] Už sme odhad, že je to rad unikátnych čísel?
[Yu] No tak jej otázku je, sme za predpokladu, že našu ponuku -
je naše pole všetky jedinečné čísla, a odpoveď je nie.
>> Ak budeme používať náš silovú riešenie, potom na začiatok / koniec indexov
jednoznačne určuje naše kontinuálne subarray.
Takže keď sme iterácii pre všetky možný štart položky,
a pre všetky koncové položky> alebo = začať, a <n,
môžete spočítať súčet, a potom sme sa na maximálnu čiastku sme videli doteraz.
Je to jasné?
Čo je to veľký O tohto roztoku?
TimeWise.
Nie tak celkom n ^ 2.
Všimnite si, že sme iterácii od 0 do n,
tak to je jeden pre sláčiky.
Sme iterácii opäť od takmer začiatku až do konca, ďalšie pre sláčiky.
A teraz, v to, že musíme sčítať všetky položky,
tak to je iná pre sláčiky. Takže máme tri vnorené cykly for, n ^ 3.
Dobre. To platí ako východiskový bod.
Naše riešenie nie je o nič horší ako n ^ 3.
Má každý pochopiť silovú riešenie?
>> Dobre. Lepším riešením je použitie predstavu názvom dynamické programovanie.
Ak ste užili CS124, čo je Algoritmy a dátové štruktúry,
stanete sa veľmi dobre oboznámení s touto technikou.
A myšlienka je, pokúsiť sa vybudovať riešenie menších problémov ako prvý.
Čo tým chcem povedať je to, v súčasnej dobe sa starať o dve veci: začiatok a koniec.
A to je nepríjemné. Čo keby sme sa mohli zbaviť jedného z týchto parametrov?
Jeden nápad je - Sme rovnako náš pôvodný problém,
nájsť maximálny súčet všetkých subarray v rozmedzí [O, n-1].
A teraz máme novú podproblém, kde vieme, v našom súčasnom indexu i,
vieme, že musíme urobiť záver, že. Naša subarray musí skončiť v aktuálnom indexe.
Takže zostávajúce problém je, mali kde sme začali našu subarray?
Má to zmysel? Dobre.
Takže som kódu hore, a poďme sa pozrieť na to, čo to znamená.
V codirectory, je tu program s názvom subarray,
a to trvá niekoľko položiek,
a vráti maximálnu subarray sumu v mojom zamiešané zozname.
Takže v tomto prípade, naša maximálna subarray je 3.
A to zhotovená len pomocou 2 a 1.
Poďme znova spustite. Je to tiež 3.
Ale tentoraz, všimnite si, ako sme sa dostali 3.
Vzali sme - sme jednoducho bralo 3 sám
pretože je obklopený negatívov na oboch stranách,
ktorá prinesie určitú čiastku <3.
Poďme beží na 10 položiek.
Tentoraz je to 7, vezmeme vedúci 3 a 4.
Tento čas je 8, a získame že tým, že sa 1, 4 a 3.
Takže vám intuícia o tom, ako môžeme vyriešiť tento transformovaný problém,
Poďme sa pozrieť na tento subarray.
Sme rovnako tento vstupné pole, a vieme, že odpoveď je 8.
Berieme 1, 4, a 3.
Ale poďme sa pozrieť na to, ako sme sa vlastne dostali túto odpoveď.
Poďme sa pozrieť na maximálnu subarray, ktorá skončila na každý z týchto indexov.
Aký je maximálny subarray, ktorý má skončiť na prvom mieste?
[Študent] Zero. >> Zero. Len neberte -5.
Tu to bude 0 rovnako. Jo?
(Študent, nezrozumiteľným)
[Yu] Oh, ospravedlňujem sa, je to -3.
Takže je 2, to je -3.
Dobre. Takže -4, čo je maximálna subarray ukončiť túto pozíciu
kde -4 je v? Zero.
Jeden? 1, 5, 8.
Teraz, musím končiť v mieste, kde je v -2.
Tak 6, 5, 7, a posledný je 4.
S vedomím, že to sú moje záznamy
pre transformované problém, kde musím skončiť v každom z týchto indexov,
potom môj posledný odpoveď je len, vziať zákrutu cez,
a pre maximálny celkový počet.
Takže v tomto prípade je to 8.
Z toho vyplýva, že maximálna subarray končí v tomto indexe,
a začal niekde pred ním.
Má každý pochopiť tento transformovaný subarray?
>> Dobre. Dobre, poďme zistiť, opakovanie pre tento.
Pozrime sa len prvých pár položiek.
Tak tu je to 0, 0, 0, 1, 5, 8.
A potom tam bol -2 tu, a že priniesla to až do 6.
Takže keď ti budem hovoriť položka na pozíciu aj podproblém (i),
Ako môžem použiť odpoveď na predchádzajúcu podproblém
odpoveď na túto podproblém?
Keď sa pozriem na, povedzme, táto položka.
Ako môžem spočítať odpoveď 6 pri pohľade na
Kombinácia tohto poľa a odpovede na predchádzajúce subproblems v tomto poli? Áno?
[Študentka] Tu sa pole súm
v polohe, priamo pred ňou, takže 8,
a potom pridáte aktuálne podproblém.
[Yu] Takže jej návrh je pozrieť sa na týchto dvoch čísel,
toto číslo a toto číslo.
Takže táto 8 odkazuje na odpovede pre podproblém (i - 1).
A hovorme môj vstupné pole A.
S cieľom nájsť maximálnu subarray, ktorá končí v polohe I,
Mám dve možnosti: môžem buď pokračovať v subarray
, Ktorá skončila na predchádzajúcu index, alebo začať nové pole.
Ak by som mal pokračovať v subarray, ktorá začala v predchádzajúcom indexu,
potom maximálna suma môžem dosiahnuť, je odpoveď na predchádzajúcu podproblém
plus aktuálne pole záznam.
Ale tiež mám na výber spustenie novej subarray,
v takom prípade je súčet je 0.
Takže odpoveď je max 0, podproblém i - 1, plus aktuálne pole záznam.
Znamená to opakovanie zmysel?
Naše opakovanie, ako sme práve zistili, je podproblém aj
sa rovná maximu predchádzajúceho podproblém navyše mojej súčasnej pole vstupu,
čo znamená, že aj naďalej predchádzajúce subarray,
alebo 0, začať nový subarray na mojom súčasnom indexe.
A akonáhle sme vybudovali túto tabuľku riešenie, potom je naša konečná odpoveď,
jednoducho lineárne ťahanie cez podproblém pole
a pre maximálny celkový počet.
To je presne realizácia toho, čo som práve povedal.
Tak sme vytvoriť novú podproblém pole, podproblémy.
Prvá položka je buď 0 alebo prvý vstup, maximálne tých dvoch.
A pre zvyšok subproblems
používame presný opakovanie sme práve objavili.
Teraz určíme maximum našej podproblémy pole, a to je naša konečná odpoveď.
>> Tak koľko miesta sme pomocou tohto algoritmu?
Ak ste len vziať CS50, potom ste možno ešte prerokované priestor veľmi veľa.
No, jedna vec k poznámke je, že som zavolal malloc tu veľkosti n
Čo to naznačujú vás?
Tento algoritmus používa lineárny priestor.
Môžeme to urobiť lepšie?
Je tam niečo, čo zistíte, že je zbytočné počítať konečnú odpoveď?
Myslím, že lepšie otázka je, aké informácie
my nie je potrebné vykonávať celú cestu až do konca?
Teraz, keď sa pozrieme na tieto dva riadky,
nás však zaujíma iba o predchádzajúcej podproblém,
a my sme len o maximálne sme kedy videli doteraz.
Pre výpočet našej konečnú odpoveď, nepotrebujeme celého poľa.
Budeme potrebovať iba posledné číslo, posledné dve čísla.
Posledné číslo pre podproblém pole, a posledné číslo pre maximum.
Takže, v skutočnosti, môžeme zničiť tieto slučky spolu
a ísť od lineárneho priestoru na konštantnú priestoru.
Aktuálna suma tak ďaleko, tu, nahradí úlohu podproblém, naše podproblém poľa.
Takže súčasná suma, tak ďaleko, je odpoveď na predchádzajúcu podproblém.
A táto suma, tak ďaleko, zaberie miesto nášho max.
Počítame maximálnu, ako sme ísť ďalej.
A tak ideme od lineárneho priestoru do konštantnej priestoru,
a tiež majú lineárne riešenie našej subarray problému.
>> Tieto druhy otázok získate počas rozhovoru.
Aká je časová zložitosť, čo je priestorová zložitosť?
Môžeš to urobiť lepšie? Sú tam veci, ktoré sú zbytočné, aby okolo?
Urobil som to zdôrazniť analýzy, ktoré by ste mali podniknúť na vlastnú päsť
ako budete prechádzať týmito problémami.
Vždy sa pýtať sami seba: "Môžem urobiť lepšie?"
V skutočnosti, môžeme robiť lepšie, než toto?
Druh chyták. Nemôžete, pretože je potrebné, aby
aspoň čítať vstup do problému.
Takže skutočnosť, že je potrebné, aby aspoň čítať vstup na problém
znamená, že nemôžete urobiť lepšie, než lineárnom čase,
a môžete to urobiť lepšie než neustále priestoru.
Takže je to, v skutočnosti, že najlepšie riešenie tohto problému.
Otázky? Dobre.
>> Akciový trh problém:
"Vzhľadom k tomu, pole celých čísel n, pozitívne, nula, alebo negatívne,
ktoré predstavujú cenu populácie nad n dní,
napísať funkciu pre výpočet maximálnej zisk si môžete urobiť
vzhľadom k tomu, si kúpiť a predať presne 1 tovar do týchto n dní. "
V podstate, chceme lacno kúpiť, draho predať.
A my chceme prísť na to najlepšie zisk môžeme urobiť.
Vráťme sa späť k môjmu tipu, čo je okamžite jasné, najjednoduchšie odpoveď, ale je to pomalé?
Áno? (Študent, nezrozumiteľné) >> Áno.
>> Takže by ste jednoducho ísť a keď sa pozrieť na ceny akcií
na každý bod v čase, (nezrozumiteľné).
[Yu] Dobre, takže jej riešenie - jej návrh výpočtovej
Najnižšia a výpočtovej najvyššej nutne pracovať
pretože najvyššia môže dôjsť pred najnižšia.
Takže to, čo je brutálna sila riešenie tohto problému?
Aké sú dve veci, ktoré musím jednoznačne určiť zisk urobím? Právo.
Brute force riešenie je - ach, áno, George návrh ich budeme potrebovať iba dva dni
jednoznačne určiť zisk týchto dvoch dní.
Takže počítame každú dvojicu, ako buy / sell,
vypočítať zisk, ktorý by mohol byť negatívne alebo pozitívne alebo nula.
Vypočítajte maximálny zisk, ktorý vyrábame po iterácia cez všetky páry dní.
To bude naša konečná odpoveď.
A to riešenie bude O (n ^ 2), pretože tam je n zvoliť dva páry -
dní, ktoré si môžete vybrať medzi koncovými dní.
Dobre, tak som to ísť cez brute force riešenie tu.
Chystám sa povedať, že je to n log n riešenia.
Čo algoritmus sa v súčasnej dobe vieme, že je n log n?
Nie je to chyták.
>> Zlúčiť radenie. Zlúčiť druh je n log n,
a v skutočnosti, jeden zo spôsobov riešenia tohto problému je použitie
druh zlúčenie druh myšlienky tzv všeobecne, rozdeľ a panuj.
A myšlienka je nasledovné.
Ak chcete vypočítať najlepšie kúpiť / predať pár v ľavej polovici.
Nájsť najlepšie zisk môžete urobiť, len s prvou n po dobu dvoch dní.
Potom chcete oompute najlepšie kúpiť / predať pár v pravej polovici,
takže posledný n do dvoch dní.
A teraz je otázkou, ako sme zlúčiť tieto riešenia dohromady?
Áno? (Študent, nezrozumiteľným)
Dobre >>. Dovoľte mi teda nakresliť obrázok.
Áno? (George, nezrozumiteľným)
Presne >>. Jiří riešenie je presne to pravé.
Takže jeho návrh je najprv spočítať najlepšie kúpiť / predať pár,
a ktorý sa vyskytuje v ľavej polovici, takže povedzme, že vľavo, vľavo.
Najlepší buy / sell pár, ktorý sa vyskytuje v pravej polovici.
Ale ak máme len porovnaní týchto dvoch čísel, nám chýba prípad
kde sme kúpiť tu a predávať niekde v pravej polovici.
Nakupujeme v ľavej polovici, predávať v pravej polovici.
A najlepší spôsob, ako spočítať najlepšie kúpiť / predať pár, ktorý pokrýva obe polovice
je pre výpočet minimálnej sem a vypočítať maximálnu tu
a vziať si ich rozdiel.
Takže dvoch prípadoch buy / sell pár vyskytuje iba tu,
iba tu, alebo na oboch poloviciach je definovaná v týchto troch čísel.
Takže náš algoritmus zlúčiť naše riešenie zase dohromady,
chceme spočítať najlepšie kúpiť / predať pár
kde sme kúpiť na ľavej polovici a predávať na pravej polovici.
A najlepší spôsob, ako to urobiť, je pre výpočet najnižšie ceny v prvej polovici,
najvyššia cena v pravej polovici, a vziať si ich rozdiel.
Vyplývání tri zisky, tieto tri čísla, budete mať maximálne tri,
a to je najlepší výsledok si môžete urobiť cez tieto prvé a koniec dní.
Tu dôležité linky sú v červenej farbe.
To je rekurzívny volanie vypočítať odpoveď v ľavej polovici.
To je rekurzívny volanie vypočítať odpoveď v pravej polovici.
Tieto dva cykly for počítať min a max na ľavej a pravej polovici, resp.
Teraz som vypočítať zisk, ktorý pokrýva obe polovice,
a konečná odpoveď je maximálna z týchto troch.
Dobre.
>> Takže, samozrejme, máme algoritmus, ale väčšie otázkou je,
čo je časová zložitosť tohto?
A dôvod, prečo som sa zmienil zlučovacie druhu je, že táto forma delenie odpoveď
do dvoch a potom zlučovať naše riešenie opäť dohromady
je presne forma druhu zlúčenie.
Tak nechaj ma ísť cez trvania.
Ak sme definovali funkciu t (n) sa rovná počtu krokov
pre n dní,
naše dve rekurzívne volania
sú každý bude stáť t (n / 2),
a tam sú dva z týchto výziev.
Teraz musím počítať minimálne v ľavej polovici,
ktoré môžem robiť v n / 2 času, plus maximálne v pravej polovici.
Takže je to len n
A potom plus nejakú konštantu práce.
A to opakovanie rovnice
je presne opakovanie rovnice pre radiť zlúčenie.
A všetci vieme, že zlúčenie sort n log n čas.
Preto je náš algoritmus tiež n log n čas.
Znamená to iterácie zmysel?
Len stručný súhrn toho, toto:
T (n) je počet krokov pre výpočet maximálnej zisk
v priebehu roka n dňoch.
Spôsob, akým sme sa rozišli naše rekurzívne volanie
je tým, že volá naše riešenia na prvých n / 2 dni,
tak to je jeden telefonát,
a potom nazývame opäť na druhej polovici.
Tak to je dva hovory.
A potom sme nájsť minimum na ľavej polovici, ktorú môžeme urobiť v lineárnom čase,
nájsť maximum v pravej polovici, ktorú môžeme urobiť v lineárnom čase.
Takže n / 2 + n / 2 je len n
Potom máme nejaké konštantné prácu, ktorá je ako robiť aritmetiku.
Toto opakovanie rovnica je presne opakovanie rovnice pre radiť zlúčenie.
Preto sme zamiešať algoritmus je tiež n log n
Tak koľko miesta sme používate?
Vráťme sa ku kódu.
>> Lepšie otázka je, koľko zásobník snímok máme niekedy v danom okamihu?
Vzhľadom k tomu, že sme s použitím rekurzia,
počet komínových snímok určuje náš využitie priestoru.
Uvažujme n = 8.
Hovoríme náhodné prehrávanie 8,
ktorá sa bude volať náhodné prehrávanie z prvých štyroch,
ktorá sa bude volať Shuffle na prvých dvoch položiek.
Takže naše stack je - to je náš stack.
A potom hovoríme, náhodné prehrávanie opäť na 1,
a to je to, čo naša základňa prípad je, a tak sme sa okamžite vráti.
Máme stále viac než toľkých zásobníka snímok?
Nie, pretože zakaždým, keď robíme invokace,
rekurzívne vyvolanie miešať,
delíme naše veľkosť na polovicu.
Takže maximálny počet komínových snímok sme niekedy v danom okamihu
je na poradí log n stack snímok.
Každý zásobník má rámček konštantný priestor,
a preto Celkové množstvo miesta,
maximálne množstvo priestoru sa niekedy používajú, je O (log n) priestor
, Kde n je počet dní.
>> Teraz, vždy opýtajte sa sami seba, "Môžeme to urobiť lepšie?"
A najmä, môžeme znížiť to problém sme už vyriešený?
Tip: sme len diskutovali dva ďalšie problémy skôr, než to, a to nebude miešať.
Môžeme previesť tento akciový problém do maximálnej subarray problému.
Ako to môžeme urobiť?
Jeden z vás? Emmy?
(Emmy, nezrozumiteľným)
[Yu] Presne tak.
Takže maximálnu subarray problému,
hľadáme pre súčet cez kontinuálne subarray.
A Emmy návrh pre populácie problému,
zvážiť zmeny, alebo sa delty.
A obraz je - to je cena akcií,
ale ak sme sa rozdiel medzi jednotlivými nasledujúci pracovný deň -
Vidíme teda, že maximálna cena, maximálny zisk by sme mohli
ak je nám kúpiť tu a predávať tu.
Ale poďme sa pozrieť na priebežné - poďme sa pozrieť na subarray problém.
Takže tu, môžeme - ísť odtiaľto až sem,
máme pozitívnu zmenu, a potom ísť odtiaľ až sem máme negatívne zmenu.
Ale potom, bude odtiaľ až sem máme obrovskú pozitívnu zmenu.
A to sú zmeny, ktoré chceme sčítať, aby boli naše posledné zisk.
Potom máme viac negatívne zmeny tu.
Kľúčom k zníženiu našej stock problém na našej maximálnej subarray problému
je posúdiť delty medzi dní.
Tak sme vytvoriť nové pole s názvom delty,
inicializovať prvú položku, ktorú chcete 0,
a potom sa pre každú delta (i), nech je to byť rozdiel
z mojej vstupné pole (i), a array (i - 1).
Potom hovoríme, naše rutinné postup pre maximálnu subarray
absolvovaní v poli delta je.
A pretože maximálna subarray je lineárny čas,
a toto zníženie, tento proces vytvorenia tohto delta poľa,
je tiež lineárna čas,
potom konečný roztok pre zásoby je O (n) práce a O (n) práce, je stále O (n) práce.
Takže máme lineárne časovú riešenie nášho problému.
Má každý pochopiť túto transformáciu?
>> Všeobecne platí, že dobrý nápad, že by ste mali mať vždy
je pokúsiť sa znížiť nový problém, že ste vidieť.
Ak to vyzerá známe starého problému,
skúste znížiť ju na starý problém.
A ak môžete používať všetky nástroje, ktoré ste použili na starý problém
riešiť nový problém.
Takže zabaliť, technické rozhovory sú náročné.
Tieto problémy sú pravdepodobne niektoré z ťažkých problémov
ktoré ste mohli vidieť v rozhovore,
takže ak nechcete pochopiť všetky problémy, ktoré som na ktoré sa vzťahuje, je to v poriadku.
To sú niektoré z viac náročných problémov.
Prax, prax, prax.
Dal som veľa problémov v letáku, tak rozhodne kontrolovať tie von.
A veľa šťastia na vašich rozhovorov. Všetky moje zdroje sú zverejnené na tomto odkaze,
a jeden z mojich starších priateľov ponúkol robiť falošné technické rozhovory,
takže ak máte záujem, Will email Yao na tejto e-mailovej adrese.
Ak máte nejaké otázky, môžete sa ma pýtate.
Myslíte si, chlapci majú špecifické otázky týkajúce sa technických rozhovorov
alebo nejaké problémy sme videli tak ďaleko?
Dobre. No, veľa šťastia na vašich rozhovorov.
[CS50.TV]