[Powered by Google Translate] [Seminář: Technické Rozhovory]
[Kenny Yu, Harvard University]
[To je CS50.] [CS50.TV]
Ahoj všichni, já jsem Kenny. V současné době jsem junior studuje počítačové vědy.
Jsem bývalý CS TF, a já jsem si přál, abych měl, když jsem byl underclassman,
a to je důvod, proč dávám tohoto semináře.
Takže doufám, že se vám bude líbit.
Tento seminář je o technických rozhovorů,
a všechny mé zdroje lze nalézt na tomto odkazu,
tento odkaz tady, pár zdrojů.
Tak jsem si udělal seznam problémů, ve skutečnosti, docela málo problémů.
Také obecné zdroje stránky, kde můžeme najít tipy
o tom, jak se připravit na přijímací pohovor,
tipy na to, co byste měli udělat, při skutečném rozhovoru,
a jak přistupovat k problémům a zdroje pro budoucí použití.
Je to vše on-line.
A jen proto, aby předmluva tento seminář, zřeknutí,
takhle by to - váš rozhovor příprava
by neměl být omezen v tomto seznamu.
To je možné pouze má být průvodce,
a vy byste měli určitě vzít všechno, co říkám s trochou soli,
ale také použít vše, co jsem použil, aby vám pomohou ve vaší rozhovor přípravě.
>> Jdu do rychlosti přes několik dalších snímků
takže se můžeme dostat do skutečných případových studií.
Struktura rozhovoru pro nalézá softwarového inženýrství,
obvykle je to 30 a 45 minut,
více kol, v závislosti na společnosti.
Často budete kódování na bílém podkladu.
Takže bílé tabule, jako to, ale často v menším měřítku.
Pokud máte telefonní rozhovor, budete pravděpodobně používat
buď collabedit nebo Google Doc, aby mohli vidět ve kterém žijete, kódování
když jste byl rozhovor po telefonu.
Rozhovor sám je typicky 2 až 3 problémy
testování počítačové vědy znalosti.
A to bude téměř určitě zahrnovat kódování.
Typy otázek, které uvidíte, jsou obvykle datové struktury a algoritmy.
A v tom tyto druhy problémů,
budou se vás zeptat, líbí, co je časová a paměťová složitost, velký O?
Často se také zeptat na vyšší úrovni otázky,
tak, navrhování systému,
jak byste rozvrhnout svůj kód?
Co rozhraní, co třídy, které moduly máte ve vašem systému,
a jak tyto ovlivňují spolu?
Takže datové struktury a algoritmy, stejně jako projekční systémy.
>> Některé obecné tipy, než se ponoříme do našich případových studií.
Myslím, že nejdůležitější pravidlo je vždy myslet nahlas.
Rozhovor by měl být vaše šance předvést své myšlení proces.
Bod rozhovoru je pro tazatele, aby zjistily,
jak si myslíte, a jak si projít problém.
Nejhorší, co můžete udělat, je být zticha celém rozhovoru.
To je prostě k ničemu.
Pokud máte k dispozici otázku, budete také chtít, aby se ujistil, abyste pochopili otázku.
Takže zopakovat otázku zpět vlastními slovy
a pokus o práci důkladné několik jednoduchých testovacích případů
aby se ujistil, abyste pochopili otázku.
Práce přes několik testovacích případů bude také vám intuice o tom, jak tento problém vyřešit.
Dalo by se dokonce objevit několik vzory, které vám pomohou problém vyřešit.
Jejich velkou tip je není frustrovaný.
Nenechte si frustrovaný.
Rozhovory jsou náročné, ale to nejhorší věc, kterou můžete udělat,
Kromě toho, že tichý, je třeba viditelně frustrovaný.
Nechcete, aby tento dojem na tazatele.
Jedna věc, kterou - tak, mnoho lidí, když jdou do rozhovoru,
se pokusí, aby se pokusili najít nejlepší řešení první,
když ve skutečnosti, tam je obvykle bije do očí řešení.
To může být pomalé, může to být neefektivní, ale měli byste jen uvést to,
Jen tak máte výchozí bod, ze kterého se lépe pracovat.
Také poukázal na řešení je pomalý, pokud jde o
Velký O časová složitost nebo paměťová složitost,
bude demonstrovat na tazatele, že jste porozuměli
Tyto problémy při psaní kódu.
Takže se nebojte přijít s nejjednodušším algoritmem první
a pak pracovat lépe odtamtud.
Jakékoliv otázky tak daleko? Dobře.
>> Takže pojďme se ponořit do naší první problém.
"Vzhledem k tomu, pole celých čísel n, napsat funkci, která zamíchá pole
na místě tak, že všechny permutace celých čísel n jsou stejně pravděpodobné. "
A předpokládáme, že máte k dispozici náhodný generátor integer
který generuje celé číslo v rozmezí od 0 do i, poloviční rozsah.
Má každý pochopit tuto otázku?
Dávám vám řadu celých čísel n, a já chci, abyste to náhodné.
V mém adresáři, napsal jsem několik programů, kterými prokáží, co mám na mysli.
Chystám se míchat pole 20 prvků,
-10 až 9,
a já chci, abyste výstup seznam, jako je tento.
Tak tohle je moje seřazena vstupní pole, a já chci, abyste to náhodné.
Uděláme to znovu.
Má každý pochopit otázku? Dobře.
Takže je to na vás.
Jaké jsou některé nápady? Můžeš to udělat jako n ^ 2, n log n, n?
Otevřete se návrhy.
Dobře. Takže jeden nápad, navrhl Emmy,
je první vypočítat náhodné číslo, náhodné celé číslo, v rozsahu od 0 do 20 let.
Takže předpokládat, naše pole má délku 20.
V našem schématu 20 prvků,
to je naše vstupní pole.
A teď, její návrh je vytvořit nové pole,
takže to bude výstupní pole.
A na základě i vrácené rand -
takže pokud jsem byl, řekněme, 17,
zkopírujte 17. prvek do první polohy.
Nyní musíme odstranit - musíme přesunout všechny prvky zde
se tak, že máme mezery na konci a žádné díry ve středu.
A teď jsme proces opakovat.
Nyní vybíráme nové náhodné číslo mezi 0 a 19.
Máme novou i tady, a my jsme zkopírujte tento prvek do této polohy.
Pak jsme posun položky za námi a my opakujeme, dokud máme plnou novou řadu.
Co je doba běhu tohoto algoritmu?
Dobře, pojďme zvážit dopad tohoto.
Jsme přesouvá každý prvek.
Když jsme odstranit tuto já, jsme se přesouvá všechny prvky po něm doleva.
A to je O (n) náklady
protože to, co kdybychom odstranit první prvek?
Takže pro každý odběr, odstraníme -
Každý odstranění nabude O (n) operace,
a protože jsme n stěhování, to vede k O (n ^ 2) míchat.
Dobře. Tak dobrý začátek. Dobrý začátek.
>> Další možností je použít známý jako shuffle Knuth,
nebo Fisher-Yates shuffle.
A je to vlastně lineární čas shuffle.
A myšlenka je velmi podobná.
Opět, máme vstupní pole,
ale místo toho, aby pomocí dvou polí pro náš vstup / výstup,
používáme první část pole sledovat naší zamíchány části,
a sledujeme, a pak nechat zbytek naší pole pro unshuffled části.
Tak tady je to, co mám na mysli. Začneme s - zvolíme si i,
pole 0-20.
Náš současný ukazatel ukazuje na první index.
Vybíráme některé i zde
a teď jsme vyměnit.
Takže v případě, že byl 5 a to bylo 4,
Výsledné pole bude mít 5 Tady a 4 zde.
A teď jsme na vědomí, značku zde.
Vše k levici zamíchány,
a všechno vpravo je unshuffled.
A nyní můžeme proces opakovat.
Jsme si vybrat náhodný index mezi 1 a 20 teď.
Takže předpokládám, náš nový i zde.
Nyní vyměníme to jsem s naší současnou novou pozici zde.
Tak jsme se vyměňovat tam a zpět, jako tohle.
Dovolte mi, abych vychovat kód, aby to více konkrétní.
Začneme s naší volbou i -
začneme s i rovnat 0, vybíráme náhodné umístění j
v unshuffled části pole, i do n-1.
Takže pokud jsem tady, zkuste si vybrat náhodný index mezi tady a zbytek pole,
a vyměníme.
To vše je kód nutné míchat vaše pole.
Nějaké otázky?
>> No, jeden potřeboval otázka je, proč je to správné?
Proč je každý permutací stejně pravděpodobné?
A nebudu procházet důkaz tohoto,
ale mnoho problémů v informatice lze dokázat indukcí.
Jak mnozí z vás znají s indukcí?
Dobře. Cool.
Takže si můžete ověřit správnost tohoto algoritmu prostou indukcí,
, kde se vaše indukční hypotéza by, předpokládejme, že
moje náhodné vrací každý permutace stejně pravděpodobné
až první jsem prvků.
Nyní, zvažte i + 1.
A mimochodem jsme se rozhodli náš index j vyměnit,
to vede k - a pak přijít na detaily,
alespoň plný důkaz, proč tento algoritmus vrací
Každý permutace se stejně pravděpodobné pravděpodobností.
>> Dobře, další problém.
Takže "vzhledem pole celých čísel, Postive, nula, záporná,
napsat funkci, která vypočítá maximální částku
jakékoli continueous subarray vstupní pole. "
Příkladem zde je, v případě, že všechna čísla jsou pozitivní,
pak v současné době nejlepší volbou je vzít celou řadu.
1, 2, 3, 4, se rovná 10.
Pokud máte nějaké negativy tam,
V tomto případě chceme jen první dva
protože výběr -1 a / nebo -3 přinese náš součet dolů.
Někdy se mohou mít začít v polovině pole.
Někdy chceme vybrat vůbec nic, je to nejlepší, aby neměli nic.
A někdy je lepší padnout,
protože věc po něm je super velká. Takže nějaké nápady?
(Student, nesrozumitelné) >> Jo.
Předpokládejme, že neberu -1.
Pak buď volím 1000 a 20000,
nebo jsem jen stačí vybrat 3000000000.
No, nejlepší volbou je vzít všechny čísla.
Tento -1, přesto, že je negativní,
Celá součet je lepší, než byly nemohu vzít -1.
Takže jeden z tipů, které jsem zmínil dříve, bylo uvést jasně zřejmé
a hrubou silou řešení jako první.
Co je brutální síla řešení tohoto problému? Jo?
[Jane] No, myslím, že brutální síly roztok
by bylo přidat až všechny možné kombinace (nesrozumitelný).
[Yu] Dobře. Takže Jane nápad je vzít všechny možné -
Jsem parafrázovat - je vzít všechny možné kontinuální subarray,
vypočítat její součet, a pak mít maximálně všech možných průběžných subarrays.
Co jednoznačně identifikuje subarray v mém vstupní pole?
Stejně jako to, co dvě věci potřebuji? Jo?
(Student, nesrozumitelné) >> Právo.
Dolní mez indexu a horní hranici indexu
jednoznačně určuje průběžné subarray.
[Studentka] Už jsme odhad, že je to řada unikátních čísel?
[Yu] No tak její otázku je, jsme za předpokladu, že naší nabídku -
je naše pole všechny jedinečné čísla, a odpověď je ne.
>> Pokud budeme používat náš silovou řešení, pak na začátek / konec indexů
jednoznačně určuje naše kontinuální subarray.
Takže když jsme iteraci pro všechny možný start položky,
a pro všechny koncové položky> nebo = začít, a <n,
můžete spočítat součet, a pak jsme se na maximální částku jsme viděli doposud.
Je to jasné?
Co je to velký O tohoto roztoku?
Timewise.
Ne tak docela n ^ 2.
Všimněte si, že jsme iteraci od 0 do n,
tak to je jeden pro smyčce.
Jsme iteraci opět od téměř počátku až do konce, další pro smyčce.
A nyní, v to, že musíme sečíst všechny položky,
tak to je jiná pro smyčce. Takže máme tři vnořené cykly for, n ^ 3.
Dobře. To platí jako výchozí bod.
Naše řešení není o nic horší než n ^ 3.
Má každý pochopit silovou řešení?
>> Dobře. Lepším řešením je použití představu názvem dynamické programování.
Jestliže jste užil CS124, což je Algoritmy a datové struktury,
stanete se velmi dobře obeznámeni s touto technikou.
A myšlenka je, pokusit se vybudovat řešení menších problémů jako první.
Co tím chci říct je to, v současné době se starat o dvě věci: začátek a konec.
A to je nepříjemné. Co kdybychom se mohli zbavit jednoho z těchto parametrů?
Jeden nápad je - Jsme stejně náš původní problém,
najít maximální součet všech subarray v rozmezí [O, n-1].
A teď máme novou podproblém, kde víme, v našem současném indexu i,
víme, že musíme učinit závěr, že. Naše subarray musí skončit v aktuálním indexu.
Takže zbývající problém je, měli kde jsme začali naši subarray?
Má to smysl? Dobře.
Takže jsem Kódujete nahoru, a pojďme se podívat na to, co to znamená.
V codirectory, je tu program s názvem subarray,
a to trvá několik položek,
a vrátí maximální subarray částku v mém zamíchány seznamu.
Takže v tomto případě, naše maximální subarray je 3.
A to pořízena jen pomocí 2 a 1.
Pojďme znovu spusťte. Je to také 3.
Ale tentokrát, všimněte si, jak jsme se dostali 3.
Vzali jsme - jsme prostě bralo 3 sám
protože je obklopen negativů na obou stranách,
která přinese určitou částku <3.
Pojďme běží na 10 položek.
Tentokrát je to 7, vezmeme vedoucí 3 a 4.
Tento čas je 8, a získáme že tím, že se 1, 4 a 3.
Takže vám intuice o tom, jak můžeme vyřešit tento transformovaný problém,
Pojďme se podívat na tento subarray.
Jsme stejně tento vstupní pole, a víme, že odpověď je 8.
Bereme 1, 4, a 3.
Ale pojďme se podívat na to, jak jsme se vlastně dostali tuto odpověď.
Pojďme se podívat na maximální subarray, která skončila na každý z těchto indexů.
Jaký je maximální subarray, který má skončit na prvním místě?
[Student] Zero. >> Zero. Jen neberte -5.
Tady to bude 0 stejně. Jo?
(Student, nesrozumitelným)
[Yu] Oh, omlouvám se, je to -3.
Takže je 2, to je -3.
Dobře. Takže -4, jaký je maximální subarray ukončit tuto pozici
kde -4 je v? Zero.
Jeden? 1, 5, 8.
Teď, musím končit v místě, kde je v -2.
Tak 6, 5, 7, a poslední je 4.
S vědomím, že to jsou mé záznamy
pro transformované problém, kde musím skončit v každém z těchto indexů,
pak můj poslední odpověď je jen, vzít zatáčku přes,
a pro maximální celkový počet.
Takže v tomto případě je to 8.
Z toho vyplývá, že maximální subarray končí v tomto indexu,
a začal někde před ním.
Má každý pochopit tento transformovaný subarray?
>> Dobře. Dobře, pojďme zjistit, opakování pro tento.
Podívejme se jen prvních pár položek.
Tak zde je to 0, 0, 0, 1, 5, 8.
A pak tam byl -2 zde, a že přinesla to až do 6.
Takže když ti budu říkat položka na pozici i podproblém (i),
Jak mohu použít odpověď na předchozí podproblém
odpověď na tuto podproblém?
Když se podívám na, řekněme, tato položka.
Jak mohu spočítat odpověď 6 při pohledu na
Kombinace tohoto pole a odpovědi na předchozí subproblems v tomto poli? Ano?
[Studentka] Zde se pole částek
v poloze, přímo před ní, takže 8,
a pak přidáte aktuální podproblém.
[Yu] Takže její návrh je podívat se na těchto dvou čísel,
toto číslo a toto číslo.
Takže tato 8 odkazuje na odpovědi pro podproblém (i - 1).
A říkejme můj vstupní pole A.
Za účelem nalezení maximální subarray, která končí v poloze I,
Mám dvě možnosti: mohu buď pokračovat v subarray
, která skončila na předchozí index, nebo začít nové pole.
Pokud bych měl pokračovat v subarray, která začala v předchozím indexu,
pak maximální částka mohu dosáhnout, je odpověď na předchozí podproblém
plus aktuální pole záznam.
Ale také mám na výběr spuštění nové subarray,
v takovém případě je součet je 0.
Takže odpověď je max 0, podproblém i - 1, plus aktuální pole záznam.
Znamená to opakování smysl?
Naše opakování, jak jsme právě zjistili, je podproblém i
se rovná maximu předchozího podproblém navíc mé současné pole vstupu,
což znamená, že i nadále předchozí subarray,
nebo 0, začít nový subarray na mém současném indexu.
A jakmile jsme vybudovali tuto tabulku řešení, pak je naše konečná odpověď,
prostě lineární tažení přes podproblém pole
a pro maximální celkový počet.
To je přesně realizace toho, co jsem právě řekl.
Tak jsme vytvořit novou podproblém pole, podproblémy.
První položka je buď 0 nebo první vstup, maximálně těch dvou.
A pro zbytek subproblems
používáme přesný opakování jsme právě objevili.
Nyní určíme maximum naší podproblémy pole, a to je naše konečná odpověď.
>> Tak kolik místa jsme pomocí tohoto algoritmu?
Pokud jste jen vzít CS50, pak jste možná ještě projednány prostor velmi mnoho.
No, jedna věc k poznámce je, že jsem zavolal malloc zde velikosti n.
Co to naznačují vás?
Tento algoritmus používá lineární prostor.
Můžeme to udělat lépe?
Je tam něco, co zjistíte, že je zbytečné počítat konečnou odpověď?
Myslím, že lepší otázka je, jaké informace
my není třeba provádět celou cestu až do konce?
Teď, když se podíváme na tyto dva řádky,
nás však zajímá pouze o předchozí podproblém,
a my jsme jen o maximálně jsme kdy viděli doposud.
Pro výpočet naší konečnou odpověď, nepotřebujeme celého pole.
Budeme potřebovat pouze poslední číslo, poslední dvě čísla.
Poslední číslo pro podproblém pole, a poslední číslo pro maximum.
Takže, ve skutečnosti, můžeme zničit tyto smyčky spolu
a jít od lineárního prostoru na konstantní prostoru.
Aktuální částka tak daleko, tady, nahradí roli podproblém, naše podproblém pole.
Takže současná suma, tak daleko, je odpověď na předchozí podproblém.
A tato částka, tak daleko, zabere místo našeho max..
Počítáme maximální, jak jsme jít dál.
A tak jdeme od lineárního prostoru do konstantní prostoru,
a také mají lineární řešení naší subarray problému.
>> Tyto druhy otázek získáte během rozhovoru.
Jaká je časová složitost, co je prostorová složitost?
Můžeš to udělat lépe? Jsou tam věci, které jsou zbytečné, aby kolem?
Udělal jsem to zdůraznit analýzy, které byste měli podniknout na vlastní pěst
jak budete procházet těmito problémy.
Vždy se ptát sami sebe: "Můžu udělat lépe?"
Ve skutečnosti, můžeme dělat lépe, než tohle?
Druh chyták. Nemůžete, protože je třeba, aby
alespoň číst vstup do problému.
Takže skutečnost, že je třeba alespoň číst vstup problému
znamená, že nemůžete udělat lépe, než lineárním čase,
a můžete to udělat lépe než neustálé prostoru.
Takže je to, ve skutečnosti, že nejlepší řešení tohoto problému.
Otázky? Dobře.
>> Akciový trh problém:
"Vzhledem k tomu, pole celých čísel n, pozitivní, nula, nebo negativní,
které představují cenu populace nad n dnů,
napsat funkci pro výpočet maximální zisk si můžete udělat
vzhledem k tomu, si koupit a prodat přesně 1 zboží do těchto n dnů. "
V podstatě, chceme levně koupit, draze prodat.
A my chceme přijít na to nejlepší zisk můžeme udělat.
Vraťme se zpět k mému tipu, co je okamžitě jasné, nejjednodušší odpověď, ale je to pomalé?
Ano? (Student, nesrozumitelné) >> Ano.
>> Takže byste prostě jít a když se podívat na ceny akcií
na každý bod v čase, (nesrozumitelné).
[Yu] Dobře, takže její řešení - její návrh výpočetní
Nejnižší a výpočetní nejvyšší nutně pracovat
protože nejvyšší může dojít před nejnižší.
Takže to, co je brutální síla řešení tohoto problému?
Jaké jsou dvě věci, které musím jednoznačně určit zisk udělám? Právo.
Brute force řešení je - ach, ano, George návrh je budeme potřebovat pouze dva dny
jednoznačně určit zisk těchto dvou dnů.
Takže počítáme každou dvojici, jako buy / sell,
vypočítat zisk, který by mohl být negativní nebo pozitivní nebo nula.
Vypočítejte maximální zisk, který vyrábíme po iterace přes všechny páry dnů.
To bude naše konečná odpověď.
A to řešení bude O (n ^ 2), protože tam je n zvolit dva páry -
dnů, které si můžete vybrat mezi koncovými dnů.
Dobře, tak jsem to jít přes brute force řešení zde.
Chystám se říct, že je to n log n řešení.
Co algoritmus se v současné době víme, že je n log n?
Není to chyták.
>> Sloučit řazení. Sloučit druh je n log n,
a ve skutečnosti, jeden ze způsobů řešení tohoto problému je použití
druh sloučení druh myšlenky tzv. obecně, rozděl a panuj.
A tato myšlenka je následující.
Chcete-li vypočítat nejlepší koupit / prodat pár v levé polovině.
Najít ty nejlepší zisk můžete udělat, jen s první n po dobu dvou dnů.
Pak chcete oompute nejlepší koupit / prodat pár v pravé polovině,
takže poslední n do dvou dnů.
A teď je otázkou, jak jsme sloučit tato řešení dohromady?
Ano? (Student, nesrozumitelným)
Dobře >>. Dovolte mi tedy nakreslit obrázek.
Ano? (George, nesrozumitelným)
Přesně >>. Jiří řešení je přesně to pravé.
Takže jeho návrh je nejprve spočítat nejlepší koupit / prodat pár,
a který se vyskytuje v levé polovině, takže řekněme, že vlevo, vlevo.
Nejlepší buy / sell pár, který se vyskytuje v pravé polovině.
Ale pokud máme jen srovnání těchto dvou čísel, nám chybí případ
kde jsme koupit zde a prodávat někde v pravé polovině.
Nakupujeme v levé polovině, prodávat v pravé polovině.
A nejlepší způsob, jak spočítat nejlepší koupit / prodat pár, který pokrývá obě poloviny
je pro výpočet minimální sem a vypočítat maximální zde
a vzít si jejich rozdíl.
Takže dvou případech buy / sell pár vyskytuje pouze zde,
pouze zde, nebo na obou polovinách je definována v těchto třech čísel.
Takže náš algoritmus sloučit naše řešení zase dohromady,
chceme spočítat nejlepší koupit / prodat pár
kde jsme se koupit na levé polovině a prodávat na pravé polovině.
A nejlepší způsob, jak to udělat, je pro výpočet nejnižší ceny v první polovině,
nejvyšší cena v pravé polovině, a vzít si jejich rozdíl.
Vyplývání tři zisky, tyto tři čísla, budete mít maximálně tři,
a to je nejlepší výsledek si můžete udělat přes tyto první a konec dnů.
Zde důležité linky jsou v červené barvě.
To je rekurzivní volání pro výpočet odpověď v levé polovině.
To je rekurzivní volání vypočítat odpověď v pravé polovině.
Tyto dva cykly for počítat min a max na levé a pravé polovině, resp.
Teď jsem vypočítat zisk, který pokrývá obě poloviny,
a konečná odpověď je maximální z těchto tří.
Dobře.
>> Takže, samozřejmě, máme algoritmus, ale větší otázkou je,
co je časová složitost tohoto?
A důvod, proč jsem se zmínil slučovací druhu je, že tato forma dělení odpověď
do dvou a pak slučovat naše řešení opět dohromady
je přesně forma druhu sloučení.
Tak nech mě jít přes trvání.
Pokud jsme definovali funkci t (n) se rovná počtu kroků
pro n dnů,
naše dvě rekurzivní volání
jsou každý bude stát t (n / 2),
a tam jsou dva z těchto výzev.
Teď musím počítat minimálně v levé polovině,
které mohu dělat v n / 2 času, plus maximálně v pravé polovině.
Takže je to jen n.
A pak plus nějakou konstantu práce.
A to opakování rovnice
je přesně opakování rovnice pro řadit sloučení.
A všichni víme, že sloučení sort n log n čas.
Proto je náš algoritmus také n log n čas.
Znamená to iterace smysl?
Jen stručný souhrn toho, toto:
T (n) je počet kroků pro výpočet maximální zisk
v průběhu roku n dnech.
Způsob, jakým jsme se rozešli naše rekurzivní volání
je tím, že volá naše řešení na prvních n / 2 dny,
tak to je jeden telefonát,
a pak nazýváme opět na druhé polovině.
Tak to je dva hovory.
A pak jsme najít minimum na levé polovině, kterou můžeme udělat v lineárním čase,
najít maximum v pravé polovině, kterou můžeme udělat v lineárním čase.
Takže n / 2 + n / 2 je jen n.
Pak máme nějaké konstantní práci, která je jako dělat aritmetiku.
Toto opakování rovnice je přesně opakování rovnice pro řadit sloučení.
Proto jsme zamíchat algoritmus je také n log n.
Tak kolik místa jsme používáte?
Vraťme se ke kódu.
>> Lepší otázka je, kolik zásobník snímků máme někdy v daném okamžiku?
Vzhledem k tomu, že jsme s použitím rekurze,
počet komínových snímků určuje náš využití prostoru.
Uvažujme n = 8.
Říkáme náhodné přehrávání 8,
která se bude volat náhodné přehrávání z prvních čtyř,
která se bude volat Shuffle na prvních dvou položek.
Takže naše stack je - to je náš stack.
A pak říkáme, náhodné přehrávání opět na 1,
a to je to, co naše základna případ je, a tak jsme se okamžitě vrátí.
Máme stále více než tolika zásobníku snímků?
Ne, protože pokaždé, když děláme invokace,
rekurzivní vyvolání míchat,
dělíme naše velikost na polovinu.
Takže maximální počet komínových snímků jsme někdy v daném okamžiku
je na pořadí log n stack snímků.
Každý zásobník má rámeček konstantní prostor,
a proto Celkové množství místa,
maximální množství prostoru se někdy používají, je O (log n) prostor
, kde n je počet dnů.
>> Nyní, vždy zeptejte se sami sebe, "Můžeme to udělat lépe?"
A zejména, můžeme snížit to problém jsme již vyřešen?
Tip: jsme jen diskutovali dva další problémy dříve, než to, a to nebude míchat.
Můžeme převést tento akciový problém do maximální subarray problému.
Jak to můžeme udělat?
Jeden z vás? Emmy?
(Emmy, nesrozumitelným)
[Yu] Přesně tak.
Takže maximální subarray problému,
hledáme pro součet přes kontinuální subarray.
A Emmy návrh pro populace problému,
zvážit změny, nebo delty.
A obraz je - to je cena akcií,
ale pokud jsme se rozdíl mezi jednotlivými následující pracovní den -
Vidíme tedy, že maximální cena, maximální zisk bychom mohli
je-li nám koupit zde a prodávat zde.
Ale pojďme se podívat na průběžné - pojďme se podívat na subarray problém.
Takže tady, můžeme - jít odsud až sem,
máme pozitivní změnu, a pak jít odtud až sem máme negativní změnu.
Ale pak, bude odtud až sem máme obrovskou pozitivní změnu.
A to jsou změny, které chceme sečíst, aby byly naše poslední zisk.
Pak máme více negativní změny zde.
Klíčem ke snížení naší stock problém na naší maximální subarray problému
je posoudit delty mezi dní.
Tak jsme vytvořit nové pole s názvem delty,
inicializovat první položku, kterou chcete 0,
a pak se pro každou delta (i), ať je to být rozdíl
z mé vstupní pole (i), a array (i - 1).
Pak říkáme, naše rutinní postup pro maximální subarray
absolvování v poli delta je.
A protože maximální subarray je lineární čas,
a toto snížení, tento proces vytvoření tohoto delta pole,
je také lineární čas,
pak konečný roztok pro zásoby je O (n) práce a O (n) práce, je stále O (n) práce.
Takže máme lineární časovou řešení našeho problému.
Má každý pochopit tuto transformaci?
>> Obecně platí, že dobrý nápad, že byste měli mít vždy
je pokusit se snížit nový problém, že jste vidět.
Pokud to vypadá známé starého problému,
zkuste snížit ji na starý problém.
A pokud můžete používat všechny nástroje, které jste použili na starý problém
řešit nový problém.
Takže zabalit, technické rozhovory jsou náročné.
Tyto problémy jsou pravděpodobně některé z obtížných problémů
které jste mohli vidět v rozhovoru,
takže pokud nechcete pochopit všechny problémy, které jsem na něž se vztahuje, je to v pořádku.
To jsou některé z více náročných problémů.
Praxe, praxe, praxe.
Dal jsem spoustu problémů v letáku, tak rozhodně kontrolovat ty ven.
A hodně štěstí na vašich rozhovorů. Všechny mé zdroje jsou zveřejněny na tomto odkazu,
a jeden z mých starších přátel nabídl dělat falešné technické rozhovory,
takže pokud máte zájem, Will email Yao na této e-mailové adrese.
Pokud máte nějaké otázky, můžete se mě ptáte.
Myslíte si, kluci mají specifické otázky týkající se technických rozhovorů
nebo nějaké problémy jsme viděli tak daleko?
Dobře. No, hodně štěstí na vašich rozhovorů.
[CS50.TV]