[Powered by Google Translate] [Seminar: Tehnički Intervjui]
[Kenny Yu, Sveučilište Harvard]
[Ovo je CS50.] [CS50.TV]
Pozdrav svima, ja sam Kenny. Ja sam trenutno studira juniorska informatike.
Ja sam bivši CS TF, i ja bih da sam imao to kad sam bio underclassman,
i to je razlog zašto sam daje ovaj seminar.
Dakle, nadam se da ćete uživati ​​u njoj.
Ovaj seminar je o tehničkim razgovorima,
i svi moji resursi se mogu naći na ovom linku,
ovaj link ovdje, par resursa.
Tako sam napravio popis problema, zapravo, dosta problema.
Također opće resursi stranica gdje možete pronaći savjete
o tome kako se pripremiti za intervju,
savjeta o tome što bi trebalo učiniti tijekom stvarnog razgovora,
kao i kako prići probleme i resurse za buduću referencu.
To je sve online.
I samo da predgovor ovaj seminar, odricanju,
ovako ne treba - vaše intervju pripremu
ne bi trebao biti ograničen na ovom popisu.
To je samo značilo da se vodič,
i svakako treba uzeti sve što kažem s rezervom,
ali i koristiti sve što sam koristio kako bi vam pomoći u vašem intervju pripreme.
>> Idem na brzinu kroz sljedećih nekoliko slajdova
tako možemo doći do stvarne studije slučaja.
Struktura intervjuu za polozaj programskog inženjerstva,
obično je 30 do 45 minuta,
više metaka, ovisno o mjestu.
Često ćete se kodiranje na bijeloj ploči.
Dakle, bijela ploča kao što je ovaj, ali često na manjem opsegu.
Ako imate telefonski intervju, vjerojatno ćete biti koristeći
bilo collabedit ili Google Doc, tako da oni mogu vidjeti živite kodiranja
dok god se intervju preko telefona.
Intervju je sama po sebi obično 2 ili 3 problemi
testiranje vaše znanje informatike.
I to će gotovo sigurno značiti kodiranja.
Vrste pitanja koja ćete vidjeti su obično strukture podataka i algoritmi.
I u tome ove vrste problema,
oni će vas, kao što je vrijeme i prostor složenost, veliki O?
Često su također pitati nadređene pitanja,
tako, projektiranje sustava,
kako bi ti stavi svoj kod?
Što sučelja, što klase, što modula Imate li u svom sustavu,
i kako to komunicirati zajedno?
Dakle, strukture podataka i algoritmi, kao i projektiranje sustava.
>> Neki opći savjeti prije nego što smo zaroniti u našim studijama slučaja.
Mislim najvažnije pravilo uvijek se razmišlja naglas.
Intervju je trebao biti vaša šansa da pokaže svoj proces razmišljanja.
Smisao intervjuu je za razgovor kako bi se ocijenilo
kako vi mislite i kako vam ide kroz problema.
Najgore što možete učiniti je šutjeti tijekom cijelog razgovora.
To je samo ne dobro.
Kada se daje pitanje, također želite da provjerite da li razumijem pitanje.
Dakle, ponavljam pitanje natrag u svojim riječima
i pokušaj da se radi temeljite nekoliko jednostavnih slučajeva testa
kako bi bili sigurni da razumijem pitanje.
Rad kroz nekoliko testnih slučajeva također će vam dati intuiciju o tome kako riješiti ovaj problem.
Možda čak i otkrijete nekoliko uzoraka će vam pomoći da se riješi problem.
Njihova velika savjet je da ne dobiti frustriran.
Ne dobiti frustriran.
Razgovori su izazovna, ali najgora stvar koju možete učiniti,
osim što je šutio, je vidljivo frustriran.
Vi ne želite dati taj dojam na ispitivača.
Jedna stvar koju - tako, mnogi ljudi, kada idu u intervjuu,
oni pokušati pokušati naći najbolje rješenje prvo,
kad stvarno, tu je obično sijevajući očigledan rješenje.
To bi moglo biti spor, to bi moglo biti neučinkovit, ali samo treba ga navesti,
samo tako imate početnu točku od koje se rade bolje.
Također, istaknuvši rješenje je spor, u smislu
Veliki O vremenu složenost ili prostor složenosti,
će pokazati interviewer da ste razumjeli
ta pitanja prilikom pisanja koda.
Dakle, nemojte se bojati da se uz najjednostavnije algoritma prvi
i onda raditi bolje od tamo.
Sva pitanja do sada? Ok.
>> Dakle, neka je roniti u našem prvom problemu.
"S obzirom na niz od n cijelih brojeva, napisati funkciju koja shuffles u niz
u mjestu tako da sve permutacije od n cijelih brojeva jednako vjerojatno. "
I pretpostavimo da imate na raspolaganju slučajni prirodni generator
koji generira cijeli u rasponu od 0 do ja, pola raspon.
Da li svi razumjeli ovo pitanje?
Ja vam dati niz od n cijelih brojeva, a ja želim da ga dvoličnost.
U mom imeniku, napisao sam nekoliko programa kako bi pokazali što mislim.
Idem dvoličnost niz od 20 elemenata,
od -10 do 9,
i želim vam da ispisati popis ovako.
Dakle, ovo je moj razvrstani ulaz polje, i želim vam da ga dvoličnost.
Mi ćemo to učiniti opet.
Da li svatko razumije pitanje? Ok.
Dakle, to je do vas.
Koje su neke ideje? Može li se to učiniti kao n ^ 2, n log n, n?
Otvoren za prijedloge.
Ok. Dakle, jedna ideja, predložio Emmy,
je prvi izračunali slučajni broj, slučajni cijeli broj, u rasponu od 0-20.
Dakle, pretpostavimo naš niz ima duljinu od 20.
U našoj shemi od 20 elemenata,
ovo je naš ulaz polje.
I sada, njezin prijedlog je stvoriti novi niz,
tako da će to biti niz izlaz.
I na temelju vratio sam se po rand -
Dakle, ako sam bio, recimo, 17,
kopirajte 17. elementa u prvoj poziciji.
Sada moramo izbrisati - moramo prebaciti sve elemente ovog
više, tako da imamo prazninu na kraju i nema rupe u sredini.
I sada smo ponoviti postupak.
Sada smo odabrati novi slučajni cijeli broj između 0 i 19.
Imamo novu sam ovdje, a mi kopirati taj element u tom položaju.
Onda smo pomak stavke više, a mi ponovite postupak dok mi imamo punu novi niz.
Što je pokrenuti vrijeme ovog algoritma?
Pa, neka je uzeti u obzir utjecaj to.
Mi mijenjaju svaki element.
Kada smo uklonili ovo ja smo se prebacuje sve elemente nakon njega na lijevoj strani.
I da je O (n) trošak
jer što ako smo uklonili prvi element?
Dakle, za svaku uklanjanje, mi ukloniti -
svaki uklanjanje nastaje jedan O (n) rad,
a budući da smo n selidbe, to dovodi do O (n ^ 2) iskorakom.
Ok. Tako dobar početak. Dobar početak.
>> Drugi prijedlog je da koristite nešto poznat kao Knuth dvoličnost,
ili Fisher-Yates dvoličnost.
I to je zapravo linearni vremenski dvoličnost.
A ideja je vrlo sličan.
Opet, imamo ulazni niz,
ali umjesto dva polja za naš ulaz / izlaz,
mi koristimo prvi dio niza pratiti naše miješaju dijela,
i mi pratiti, a onda ćemo ostaviti ostatak naše niz za unshuffled dijela.
Dakle, ovdje je ono što mislim. Mi krenuti sa - mi izabrati ja,
polje 0-20.
Naš trenutni pokazivač pokazuje na prvi indeksu.
Mi smo odabrali neke sam ovdje
i sad mi zamijeniti.
Dakle, ako je to 5 i to je 4,
što je rezultiralo niz će imati pet ovdje i 4 ovdje.
I sad smo na umu marker ovdje.
Sve na lijevoj se miješaju,
i sve to pravo unshuffled.
I sada možemo ponoviti postupak.
Mi izabrati slučajni indeks između 1 i 20 sada.
Dakle, pretpostavimo da naš novi sam ovdje.
Sada smo zamijenili ovo sam s našim trenutnim novi položaj ovdje.
Dakle, mi ne zamjene naprijed i natrag kao što je ovaj.
Pusti me dovesti do koda da bi ga više betona.
Mi smo započeli s našim izborom i -
smo započeli s ja jednaka 0, mi pokupiti slučajni j lokacije
u unshuffled dijelu niza, ja se n-1.
Dakle, ako sam ja ovdje, odabrati slučajni indeks između ovdje i ostatka polja,
i mi mijenjati.
To je sve kod potrebno dvoličnost svoj niz.
Ima li pitanja?
>> Pa, jedan je potreban pitanje je, zašto je to točno?
Zašto je svaka permutacija jednako vjerojatno?
I neću ići kroz dokaz toga,
ali mnogi problemi u računalnoj znanosti može biti dokazano kroz indukcije.
Kako mnogi od vas su upoznati s indukcijom?
Ok. Cool.
Tako možete dokazati ispravnost ovog algoritma po jednostavnom indukcije,
gdje indukcija hipoteza bi, pretpostavljamo da
moj shuffle vraća svaki permutacijom jednako vjerojatno
do prvih sam elemenata.
Sada, razmislite i + 1.
I usput smo izabrali naš indeks j za swap,
to dovodi do - i onda raditi na detaljima,
barem puni dokaz zašto je ovaj algoritam vraća
svaka permutacija s jednako vjerojatne vjerojatnosti.
>> U redu, sljedeći problem.
Dakle, "dao niz brojeva, postive, nula, negativna,
napisati funkciju koja će izračunati maksimalni iznos
bilo continueous subarray od ulaznog niza. "
Primjer je ovdje, u slučaju kada su svi brojevi su pozitivni,
onda trenutno najbolji izbor je da se cijeli niz.
1, 2, 3, 4, jednako 10.
Kada imate neke negative tamo,
u ovom slučaju samo želimo prvo dvoje
jer odabiru -1 i / ili -3 će naš zbroj dolje.
Ponekad mi možda morati početi u sredini niza.
Ponekad želimo izabrati ništa na sve, to je najbolje da ne poduzeti ništa.
A ponekad je bolje da se pad,
jer stvar nakon toga je super velika. Dakle, bilo koji ideja?
(Učenik, nerazumljivo) >> Da.
Pretpostavimo da ne uzimam -1.
Onda ni sam odabrati 1000 i 20000,
ili sam samo odabrati 3000000000.
Pa, najbolji izbor je da će poduzeti sve brojeve.
Ovo -1, unatoč tome što je negativno,
cijela suma je bolje nego što su mi da se ne -1.
Dakle, jedan od savjeta koje sam spomenuo ranije bio navesti jasno vidljivo
i na silu rješenje prvi.
Što je gruba sila rješenje u ovom problemu? Da?
[Jane] Pa, mislim silu Rješenje
da bi se zbrojiti sve moguće kombinacije (nerazumljivo).
[Yu] Ok. Dakle, Jane ideja je da se svaki mogući -
Ja sam parafrazirajući - je da se svaki mogući kontinuirani subarray,
izračunati svoj iznos, a zatim se najviše od svih mogućih kontinuiranih subarrays.
Što jedinstveno identificira subarray u mom ulazni niz?
Kao što su dvije stvari trebam? Da?
(Učenik, nerazumljivo) >> Točno.
Donju granicu indeksa i gornju granicu indeksa
jedinstveno određuje kontinuirani subarray.
[Žensko student] Jesmo procjene da je niz jedinstvenih brojeva?
[Yu] No Dakle njezino pitanje je, pretpostavljamo da je naš niz -
je naš niz svi jedinstveni brojevi, a odgovor je ne.
>> Ako ćemo koristiti naše brute force rješenje, tada start / kraj indekse
jedinstveno određuje naša kontinuirana subarray.
Dakle, ako smo ponoviti za sve moguće start unosa,
i za sve krajnje unosa> ili = za početak, i <n,
ti izračunati iznos, a onda smo se maksimalno zbroj smo vidjeli do sada.
Je li to jasno?
Što je veliki O tog rješenja?
Timewise.
Nije sasvim n ^ 2.
Imajte na umu da smo ponoviti od 0 do n,
tako da je to jedna za petlju.
Mi ponoviti opet od gotovo samog početka do kraja, drugi za petlju.
A sada, unutar toga, moramo zbrojiti sve zapis,
tako da je još za petlju. Dakle, imamo tri ugniježđena za petlje, n ^ 3.
Ok. To ide kao polazište.
Naše rješenje je ne gori od n ^ 3.
Da li svi razumiju brute force rješenje?
>> Ok. Bolje rješenje je korištenje ideju pod nazivom dinamičko programiranje.
Ako uzmete CS124, koji je Algoritmi i strukture podataka,
ćete postati vrlo upoznat s ovom tehnikom.
A ideja je, pokušati izgraditi rješenja za manje problema prvi.
Što mislim je to, mi trenutno imaju brinuti o dvije stvari: početak i kraj.
I to je neugodno. Što ako bismo mogli riješiti jedan od tih parametara?
Jedna od ideja je da se - intenzivno dao naš originalni problem,
pronaći najveću sumu bilo subarray u rasponu [O, n-1].
I sada imamo novi subproblem gdje znamo, u našem trenutnom indeksa i,
znamo da moramo zaključiti postoji. Naš subarray mora završiti u tekućoj indeksa.
Tako je preostali problem je, gdje bismo trebali započeti naš subarray?
Ima li to smisla? Ok.
Tako sam kodirane ovo gore, i pogledajmo što to znači.
U codirectory, postoji program koji se zove subarray,
i to traje nekoliko stavki,
i vraća maksimalnu subarray zbroj u mom miješaju popisu.
Dakle, u ovom slučaju, naša najveća subarray je tri.
A da je snimljen za samo pomoću dva i jedan.
Idemo ga ponovno pokrenuti. To je također tri.
No, ovaj put, imajte na umu kako imamo tri.
Mi uzeo - mi samo uzeti 3 sama
jer je okružen negativa na obje strane,
koji će donijeti zbroj <3.
Idemo raditi na 10 predmeta.
Ovaj put to je 7, uzmemo vodeću tri i četiri.
Ovaj put to je 8, a mi dobivamo da uzimanje 1, 4 i 3.
Tako da vam dati intuiciju o tome kako možemo riješiti ovaj pretvara problem,
ajmo pogledati ovaj subarray.
Mi smo dali ovu ulazni niz, a znamo da je odgovor 8.
Mi uzeti jedan, četiri i tri.
No, pogledajmo kako smo zapravo dobio taj odgovor.
Pogledajmo maksimalne subarray da je završila na svakom od tih indeksa.
Što je maksimalni subarray da mora završiti na prvom mjestu?
[Studentski] Zero. >> Zero. Samo nemoj uzeti -5.
Ovdje to će biti 0, kao dobro. Da?
(Učenik, nerazumljiv)
[Yu] Oprosti, to je -3.
Dakle, ovo je 2, ovo je -3.
Ok. Dakle, -4, što je maksimalna subarray završiti tu poziciju
gdje je na -4? Zero.
Jedan? 1, 5, 8.
Sada, moram završiti na mjestu gdje je -2 u.
Dakle 6, 5, 7, a posljednji je 4.
Znajući da su to moji zapisi
za transformirane problem gdje moram završiti na svakom od tih indeksa,
onda je moj konačni odgovor je samo, uzeti zamah preko,
i uzeti maksimalan broj.
Dakle, u ovom slučaju to je 8.
To znači da maksimalna subarray završava na ovom indeksu,
i počeo negdje prije njega.
Da li svi razumiju ovu pretvara subarray?
>> Ok. Pa, neka je shvatiti ponavljanje za to.
Razmotrimo samo prvih nekoliko unose.
Dakle, ovdje je bilo 0, 0, 0, 1, 5, 8.
A onda je -2 ovdje, i to je doveo do šest.
Dakle, ako ja zovem ulazak na poziciji ja subproblem (i),
kako mogu koristiti odgovor na prethodnu subproblem
odgovoriti na ovu subproblem?
Ako gledam, recimo, ovaj unos.
Kako mogu izračunati odgovor šest gleda na
Kombinacija ovog polja i odgovore na prethodnim subproblemi u ovom polju? Da?
[Žensko student] Ti se niz iznosa
u položaju neposredno prije njega, tako da 8,
i onda dodati trenutni subproblem.
[Yu] Dakle, njezin prijedlog je da pogledate tih dvaju brojeva,
taj broj i taj broj.
Dakle, ovo se odnosi na 8 odgovora za subproblem (i - 1).
I nazovimo moj A. ulaznog polje
Kako pronaći maksimalnu subarray koja završava na sam položaj,
Imam dva izbora: Ja može nastaviti subarray
da je završio na prethodnu indeksa, ili pokrenuti novi niz.
Ako mi je nastaviti subarray koji je započeo u prethodnom indeksa,
onda je maksimalni iznos mogu postići je odgovor na prethodno subproblem
plus struja niz ulaz.
Ali, ja također imaju izbor počinju novi subarray,
u kojem slučaju je zbroj 0.
Dakle, odgovor je max od 0, subproblem ja - 1, plus struja niz ulaz.
Znači li to ponavljanje smisla?
Naš ponavljanja, kao što smo upravo otkrili, je subproblem ja
je jednaka maksimalno prethodne subproblem plus mog trenutnog array ulazak,
što znači da i dalje na prethodnu subarray,
ili 0, započeti novi subarray na mog trenutnog indeksa.
A kad smo izgradili ovu tablicu rješenja, onda je naša konačna odgovor,
samo ne linearno pomesti preko subproblem niz
i uzeti maksimalan broj.
To je točno provedba ono što sam upravo rekao.
Tako smo stvorili novu subproblem niz, subproblemi.
Prvi unos je bilo 0 ili prvi ulazak, najviše onih dviju.
A za ostatak subproblemi
mi koristimo točan ponavljanje smo upravo otkrili.
Sada smo izračunati maksimum našeg subproblemi niz, i to je naš konačni odgovor.
>> Dakle, koliko prostora koristimo u ovom algoritmu?
Ako ste samo uzeti CS50, onda možda niste razgovarali prostor jako puno.
Pa, jedna stvar je imati na umu da je sam nazvao malloc ovdje s veličine n.
Što znači da predloži vas?
Ovaj algoritam koristi linearni prostor.
Možemo li bolje?
Ima li išta što ćete primijetiti da je nepotrebno izračunati konačni odgovor?
Valjda bolje pitanje je, što informacije
mi ne trebaju nositi sve do kraja?
Sada, ako gledamo ove dvije linije,
smo samo stalo na prethodnu subproblem,
a mi samo stalo do maksimuma koji smo ikada vidjeli tako daleko.
Da biste izračunali naš konačni odgovor, mi ne treba cijeli niz.
Mi samo trebate posljednji broj, zadnja dva broja.
Posljednji broj za subproblem niz, i posljednji broj za maksimalno.
Dakle, u stvari, možemo osigurač ove petlje zajedno
i otići iz linearni prostor stalnom prostoru.
Trenutni iznos do sada, ovdje, zamjenjuje ulogu subproblem, naša subproblem polja.
Dakle trenutni zbroj, do sada, je odgovor na prethodno subproblem.
I taj iznos, do sada, zauzima mjesto naše max.
Mi računamo maksimum kao što smo ići zajedno.
I tako idemo od linearnog prostora stalnom prostoru,
i mi također imaju linearno rješenje za naše subarray problema.
>> Ove vrste pitanja ćete dobiti tijekom intervjua.
Što je vrijeme složenosti, što je prostor složenost?
Može li bolje? Postoje stvari koje su nepotrebno držati oko?
Učinio sam to za isticanje analize koju treba poduzeti na svoju ruku
kao da radite preko tih problema.
Uvijek se pitate, "Mogu li to učiniti bolje?"
U stvari, mi možemo učiniti bolje od toga?
Sortiraj trik pitanje. Vi ne možete, jer morate
barem pročitati ulaz problema.
Dakle, činjenica da morate barem pročitati ulaz na problem
znači da ne možete učiniti bolje od linearnog vremena,
i da ne možete učiniti bolje od constant prostora.
Dakle, ovo je, u stvari, najbolje rješenje za ovaj problem.
Pitanja? Ok.
>> Burza problem:
"S obzirom na niz od n cijelih brojeva, pozitivna, nula ili negativna,
koji predstavljaju cijenu dionice preko n dana,
napisati funkciju za izračun maksimalni profit možete napraviti
s obzirom da ste kupiti i prodati točno 1 dionice unutar tih n dana. "
U suštini, želimo kupiti niske, visoke prodati.
I želimo shvatiti najbolji profit možemo napraviti.
Vraćajući se moj savjet, ono što je odmah bilo jasno, najjednostavniji odgovor, ali to je spor?
Da? (Učenik, nerazumljivo) >> Da.
>> Dakle, vi bi samo ići iako i pogledate cijene dionica
u svakoj točki u vremenu, (nerazumljivo).
[Yu] Ok, pa joj rješenje - njezin prijedlog računalstva
najniža i najviša računanje ne mora nužno raditi
jer najviše može dogoditi prije nego što je najniža.
Dakle, ono što je na silu rješenje za ovaj problem?
Koje su dvije stvari koje moram jedinstveno utvrditi dobit ću učiniti? Točno.
The silu rješenje je - oh, tako, George prijedlog je trebamo samo dva dana
jedinstveno odrediti dobit od ta dva dana.
Tako smo izračunali svaki par, željeli kupiti / prodati,
izračunati dobit, koja bi mogla biti negativna ili pozitivna ili jednaka nuli.
Izračunajte maksimalnu dobit da ćemo napraviti nakon Ponavljanje nad svim parovima dana.
To će biti naš konačni odgovor.
I da će rješenje biti O (n ^ 2), jer tu je n izabrati dva para -
dana koje možete izabrati među krajnjim dana.
Ok, tako da ja ne idem preko brute force rješenje ovdje.
Ja ću vam reći da je n log n rješenje.
Što algoritam ti trenutno znamo da je n log n?
To nije trik pitanje.
>> Spoji vrsta. Spoji vrsta je n log n,
i zapravo, jedan od načina rješavanja ovog problema je korištenje
vrsta spajanja vrsta ideje zove, u cjelini, podijeli pa vladaj.
A ideja je kako slijedi.
Želite izračunati najbolje kupiti / prodati par u lijevoj polovici.
Pronađite najbolje profit možete napraviti, samo s prvim n nad dva dana.
Tada želite oompute najbolje kupiti / prodati par na desnoj polovici,
tako da je posljednja n tijekom dva dana.
I sada se postavlja pitanje, kako ćemo spojiti ta rješenja vratiti zajedno?
Da? (Učenik, nerazumljiv)
>> Ok. Pa neka mi nacrtati sliku.
Da? (George, nerazumljiv)
>> Točno. George rješenje je točno.
Dakle, njegov prijedlog je, prvo izračunati najbolje kupiti / prodati par,
te da se javlja u lijevoj polovici, pa nazovimo to lijevo, lijevo.
Najbolji kupiti / prodati par koji se pojavljuje u desnoj polovici.
Ali ako mi samo u usporedbi ova dva brojeve, mi nedostaje slučaj
gdje smo kupiti i prodati ovdje negdje u desnoj polovici.
Mi kupiti u lijevoj polovici, prodati u desnoj polovici.
A najbolji način da se izračunati najbolje kupiti / prodati par koji se proteže u oba poluvremena
je izračunati minimalno ovdje i izračunati maksimum ovdje
i uzeti njihovu razliku.
Dakle, ta dva slučaja gdje kupiti / prodati par pojavljuje samo ovdje,
samo ovdje, ili na oba poluvremena definiran tih triju brojeva.
Dakle, naš algoritam za spajanje naših rješenja natrag zajedno,
želimo izračunati najbolje kupiti / prodati par
gdje smo kupiti na lijevoj polovici i prodati na desnoj polovici.
A najbolji način da to učinite je izračunati najnižu cijenu u prvoj polovici,
najviša cijena u desnoj polovici, i uzeti njihovu različitost.
Dobivena tri dobit, ta tri broja, možete uzeti najviše tri,
i da je najbolji dobit možete napraviti preko ovih prvih i kraj dana.
Ovdje važne linije su u crvenom.
Ovo je rekurzivna poziva izračunati odgovor u lijevoj polovici.
Ovo je rekurzivna poziva izračunati odgovor u desnoj polovici.
Ove dvije petlje za izračunati MIN i MAX na lijevoj i desnoj polovici, respektivno.
Sada sam izračunati dobit koja se proteže u oba poluvremena,
i konačni odgovor je najveća od tih triju.
Ok.
>> Dakle, svakako, imamo algoritam, ali pitanje je veći,
što je vrijeme složenost ovo?
A razlog zašto sam spomenuo spajanja vrsta je da je ovaj oblik podjele odgovor
u dva, a zatim spajanje naših rješenja ponovno zajedno
je točno oblik spajanja vrste.
Tako da me pusti kroz trajanja.
Ako smo definirali funkcije t (n) da se broj koraka
za n dana,
naša dva rekurzivni pozivi
su svaki ide na trošak t (n / 2),
i tamo je dvije od tih pozive.
Sada moram izračunati minimalno lijevoj polovici,
što mogu učiniti u N / 2 vremena, plus maksimalno desnoj polovici.
Dakle, ovo je samo n.
I onda plus neki konstantan rad.
I to ponavljanje jednadžba
je točno ponavljanje jednadžba za spajanje vrste.
A svi znamo da je spajanje vrsta je n log n vrijeme.
Dakle, naš algoritam je također n log n vrijeme.
Da li je ovo iteracija smisla?
Samo kratka rekapitulacija ovo:
T (n) je broj koraka kako bi izračunali maksimalni profit
tijekom n dana.
Način na koji smo se razdvojili naše rekurzivnih poziva
je pozivom naše rješenje na prvih n / 2 dana,
tako da je jedan poziv,
i onda zovemo ponovno na drugoj polovici.
Tako da je dva poziva.
I onda smo pronašli najmanje na lijevoj polovici, što možemo učiniti u linearnom vremenu,
pronaći najviše desnoj polovici, što možemo učiniti u linearnom vremenu.
Dakle n / 2 + n / 2 je samo n.
Onda imamo neke konstantan rad, koji je kao što radiš aritmetiku.
Ovo ponavljanje jednadžba je točno ponavljanje jednadžba za spajanje vrste.
Dakle, naša dvoličnost algoritam je također n prijavite n.
Dakle, koliko prostora smo koristite?
Idemo natrag u kodu.
>> Bolje pitanje je, koliko stack okviri mi ikada imati u bilo kojem trenutku?
Budući da smo koristeći rekurziju,
broj stog okvire određuje našu korištenja prostora.
Razmotrimo n = 8.
Zovemo shuffle na 8,
koja će se zvati shuffle na prva četiri unosa,
koji će pozvati shuffle na prve dvije stavke.
Dakle, naš stack - to je naš stog.
I onda mi zovemo shuffle opet na jednom,
i to je ono što naša baza slučaj, tako da smo se odmah vratiti.
Da li ćemo ikada imati više od toga mnogi stog okvire?
Ne Budući da svaki put radimo jedan prizivanje,
rekurzivna prizivanje dvoličnost,
podijelimo našu veličinu na pola.
Tako je najveći broj kadrova stog smo ikada imali u bilo kojem trenutku
je na redu log n stog okvire.
Svaki stog okvir ima stalnu prostor,
i stoga je ukupan iznos od prostora,
maksimalni iznos od prostora koji smo ikada koristiti je O (log n) prostora
gdje je n broj dana.
>> Sada, uvijek zapitajte se, "Možemo li bolje?"
A posebno, možemo smanjiti na problem smo već riješeno?
Hint: možemo samo raspravljati dvije druge probleme prije toga, i to ne će biti dvoličan.
Mi može pretvoriti ovaj problem na tržištu dionica u maksimalnom subarray problema.
Kako možemo to učiniti?
Jedan od vas? Emmy?
(Emmy, nerazumljiv)
[Yu] Točno.
Dakle, maksimalno subarray problema,
mi smo u potrazi za iznos preko kontinuiranog subarray.
I Emmy je prijedlog za dionice problema,
uzeti u obzir promjene, ili delte.
A slika je to - to je cijena dionica,
ali ako mi je razlika između svake uzastopne dana -
pa vidimo da je maksimalna cijena, maksimalna dobit mogli bismo
je, ako ćemo kupiti ovdje i prodati ovdje.
No pogledajmo kontinuirano - pogledajmo na subarray problema.
Dakle, ovdje, možemo napraviti - ide odavde do ovdje,
imamo pozitivne promjene, a zatim ide odavde do ovdje imamo negativnu promjenu.
Ali onda, ide odavde do ovdje imamo veliku pozitivnu promjenu.
A to su promjene koje želimo sumirati da biste dobili naš konačni profit.
Onda imamo više negativnih promjena ovdje.
Ključ za smanjenje naše zalihe problem u našoj maksimalne subarray problema
je uzeti u obzir delte između dana.
Tako smo stvoriti novi niz zove deltas,
inicijalizirati prvi unos biti 0,
a zatim za svaki delta (I), pustiti da se razlika
moga ulaz array (i), i niz (i - 1).
Onda mi zovemo naš rutinski postupak za maksimalne subarray
prolazi u neke Deltina.
I zato maksimalni subarray je linearno vrijeme,
i to smanjenje, ovaj proces stvaranja ovog delta niz,
Također je linearno vrijeme,
zatim konačno rješenje za zalihe je O (n) rad plus O (n) rad, još uvijek je O (n) rad.
Dakle, imamo linearni vremenski rješenje za naš problem.
Da li svi razumiju ovu transformaciju?
>> U principu, dobra ideja da uvijek treba imati
je pokušati smanjiti novi problem koji vidite.
Ako to izgleda poznato da stari problem,
pokušajte ga smanjiti na stari problem.
I ako možete koristiti sve alate koje ste koristili na stari problem
riješiti novi problem.
Dakle završiti, tehnički razgovori su zahtjevni.
Ovi problemi su vjerojatno neke od težih problema
koje ste mogli vidjeti u intervjuu,
tako da ako ne razumijem sve probleme koje sam pokrivena, to je u redu.
Ovo su neke od više izazovan problema.
Praksa, praksa, praksa.
Dao sam puno problema u brošuri, tako da definitivno provjeriti one out.
I sretno na svojim intervjuima. Svi moji resursi su objavili na ovom linku,
i jedan od mojih starijih prijatelja je ponudio da to lažna tehničke razgovore,
pa ako ste zainteresirani, e Hoće Yao na tom adresom.
Ako imate neka pitanja, možete me pitati.
Nemojte vi imate konkretnih pitanja vezanih uz tehničke intervjua
ili bilo kakvi problemi koje smo vidjeli do sada?
Ok. Pa, sretno na svojim intervjuima.
[CS50.TV]