[Powered by Google Translate] [Seminar: Interviuri tehnice]
[Kenny Yu, Universitatea Harvard]
[Acest lucru este CS50.] [CS50.TV]
Max toată lumea, Sunt Kenny. Eu sunt în prezent o stiinta junior calculator studiază.
Sunt un fost CS TF, și am vrut să am asta când am fost un underclassman,
și de aceea am da acest seminar.
Așa că sper să vă placă.
Acest seminar este de aproximativ interviuri tehnice,
și toate resursele mele pot fi găsite la acest link,
această legătură într-aici, un cuplu de resurse.
Așa că am făcut o listă de probleme, de fapt, destul de câteva probleme.
De asemenea, un general resurse pagină unde puteți găsi sfaturi
cu privire la modul de a se pregăti pentru un interviu,
sfaturi cu privire la ce trebuie să faceți în timpul unui interviu real,
precum și modul de abordare a problemelor și a resurselor de referință în viitor.
E totul on-line.
Și doar pentru a prefața acestui seminar, o declarație de renunțare,
ca acest lucru nu ar trebui să - preparatul dumneavoastră interviu
nu ar trebui să fie limitată la această listă.
Acest lucru este menit să fie doar un ghid,
și trebuie să luați cu siguranta tot ceea ce spun, cu un bob de sare,
dar folosesc, de asemenea, tot ce am folosit pentru a te ajuta in pregatirea interviului.
>> Am de gând să accelereze prin următoarele câteva slide-uri
astfel încât să putem ajunge la studii de caz reale.
Structura unui interviu pentru o Dvs. puteti interveni pentru inginerie software,
de obicei, aceasta este de 30 la 45 de minute,
runde multiple, în funcție de companie.
De multe ori veți fi de codare pe o tablă albă.
Deci, o tablă albă ca asta, dar de multe ori pe o scară mai mică.
Dacă aveți un interviu telefonic, veți fi, probabil, folosind
fie collabedit sau un document Google astfel încât să poată vedea trăiți de codificare
în timp ce ești intervievat prin telefon.
Un interviu in sine este de obicei 2 sau 3 probleme
testa cunoștințele de informatică.
Și este aproape sigur va implica codificare.
Tipurile de întrebări pe care le veți vedea, de obicei, sunt structuri de date și algoritmi.
Și făcând aceste tipuri de probleme,
vă vor cere, place, ceea ce este timpul și complexitatea spațiului, Big O?
Adesea, ei cer, de asemenea, de nivel superior întrebări,
astfel, proiectarea unui sistem,
cum ai pune în codul?
Ce interfețe, ce clase, ce module aveți în sistemul dumneavoastră,
și cum acestea interacționează împreună?
Deci, structuri de date și algoritmi, precum și sistemele de proiectare.
>> Câteva sfaturi generale înainte de a ne arunca cu capul în studiile noastre de caz sa.
Cred că cea mai importantă regulă este să fie întotdeauna gândire cu voce tare.
Interviul se presupune a fi sansa ta de a scoate în evidență procesul de gândire.
Punctul de interviu este interviul pentru a măsura
cum crezi si cum te duci printr-o problemă.
Cel mai rau lucru il poti face este să tacă de-a lungul întregului interviu.
Asta e doar nu e bine.
Când vi se administrează o întrebare, de asemenea, doriți să vă asigurați că ați înțeles întrebarea.
Deci, întrebarea se repetă din nou în propriile tale cuvinte
și tentativa de a lucra amănunțite câteva cazuri simple de testare
să vă asigurați că ați înțeles întrebarea.
Lucru printr-o câteva cazuri de testare va oferi, de asemenea o intuiție cu privire la modul de a rezolva această problemă.
S-ar putea descoperi chiar câteva modele pentru a vă ajuta să rezolvați problema.
Sfat lor mare este să nu te frustrat.
Nu te frustrat.
Interviurile sunt provocatoare, dar cel mai rău lucru care le puteți face,
în afară de a fi tăcut, trebuie să fie vizibil frustrat.
Tu nu vrei să dau impresia că la un interviu.
Un lucru pe care îl - atât, mulți oameni, atunci când merg într-un interviu,
ei încearcă să încerce să găsească cea mai bună soluție în primul rând,
când, de fapt, există, de obicei, o soluție flagrant evidentă.
Acesta ar putea fi lent, ar putea fi ineficient, dar tu ar trebui să indice pur și simplu,
doar astfel încât să aveți un punct de pornire de la care să funcționeze mai bine.
De asemenea, subliniind soluția este lent, din punct de vedere
O mare complexitate timp sau spațiu de complexitate,
va demonstra că ați înțeles intervievatorului
aceste aspecte atunci când scrierea de cod.
Deci, nu vă fie teamă de a veni cu cea mai simplă algoritm prima
și de a lucra mai bine, apoi de acolo.
Orice întrebări până acum? Bine.
>> Deci, haideți să se scufunde în problema prima noastră.
"Având în vedere o serie de numere intregi n, scrie o funcție care amesteca matrice
în loc, astfel încât toate permutări ale întregi n sunt la fel de probabil. "
Și presupunem că aveți la dispoziție un generator de număr întreg aleator
care generează un număr întreg într-un interval de la 0 la i, gama de jumătate.
Are toată lumea să înțeleagă această întrebare?
Am să vă dau un tablou de întregi n, și vreau să-l amesteca.
În directorul meu, am scris câteva programe pentru a demonstra ceea ce vreau să spun.
Am de gând să shuffle o serie de 20 de elemente,
-10 - 9,
și vreau să vă scoate o listă ca asta.
Deci, aceasta este matrice mea de intrare sortate, și vreau să-l amesteca.
Noi vom face din nou.
Are toată lumea să înțeleagă întrebarea? Bine.
Deci, este de până la tine.
Care sunt unele idei? Poți să-l faci ca n ^ 2, n n log, n?
Deschis la sugestii.
Bine. Deci o idee, sugerata de Emmy,
este primul calcula un număr aleator, întreg aleatoriu, într-un interval de la 0 la 20.
Deci, presupun gama noastră are o lungime de 20.
În diagrama noastră de 20 de elemente,
aceasta este gama noastră de intrare.
Și acum, sugestia ei este de a crea o matrice nouă,
astfel încât acesta va fi matrice de ieșire.
Și pe baza m-am întors de rand -
așa că, dacă am fost, să zicem, 17,
copiați elementul saptesprezecelea în prima poziție.
Acum, avem nevoie pentru a șterge - avem nevoie pentru a schimba toate elementele aici
peste astfel încât să avem un decalaj de la capăt și nu găuri în mijloc.
Și acum vom repeta procesul.
Acum alegem un întreg nou aleator între 0 și 19.
Avem un nou aici i, iar noi să copiați acest element în această poziție.
Apoi ne-am schimba elementele de peste si am repeta procesul până când vom avea noastră gamă completă nouă.
Care este timpul de funcționare al acestui algoritm?
Ei bine, hai să ia în considerare impactul de acest lucru.
Suntem schimbă fiecare element.
Când ne-am eliminarea acestei i, suntem schimbă toate elementele după ce la stânga.
Și acesta este un O (n) costul
pentru că ceea ce dacă am elimina primul element?
Deci, pentru fiecare eliminare, vom elimina -
fiecare îndepărtare își asumă O (n) operarea,
și din moment ce ne-am n mutări, acest lucru duce la un O (n ^ 2) shuffle.
Bine. Atât de bun început. Bun început.
>> O altă sugestie este de a folosi ceva cunoscut sub numele de shuffle Knuth,
sau shuffle Fisher-Yates.
Și e de fapt un shuffle timp liniar.
Și ideea este foarte asemănătoare.
Din nou, avem gama noastră de intrare,
dar în loc de a folosi două matrice de intrare noastră / ieșire,
vom folosi prima parte a matrice pentru a urmări partea noastră amestecate,
și noi urmări, iar apoi vom lăsa restul de matrice noastre pentru porțiunea unshuffled.
Deci, aici e ceea ce vreau să spun. Vom începe cu - vom alege un i,
o matrice 0 la 20.
Indicatorul noastră actuală este orientată spre primul indice.
Am ales pentru unii aici i
iar acum suntem schimb.
Deci, în cazul în care aceasta a fost de 5 și acest lucru a fost de 4,
matrice rezultat va avea 5 aici și 4 aici.
Și acum am observat un marker aici.
Totul la stânga este amestecat,
și totul a dreapta este unshuffled.
Și acum putem repeta procesul.
Am alege un indice aleator între 1 și 20 acum.
Presupun că așa noul nostru i este aici.
Acum ne-am schimba această nouă poziție nostru curentă aici.
Deci, ce facem o pompare înainte și înapoi ca aceasta.
Lasă-mă să aduc codul pentru a face mai concret.
Vom începe cu alegerea noastră de I -
vom începe cu i egal cu 0, alegem o locație aleatorie j
în partea unshuffled de matrice, i la n-1.
Deci, dacă eu sunt aici, pentru a alege un indice aleator între aici și restul de matrice,
și am schimba.
Acest lucru este necesar pentru a amesteca codul matrice dumneavoastră.
Alte întrebări?
>> Ei bine, o nevoie de întrebare este, de ce este asta corect?
De ce este la fel de probabil ca fiecare permutare?
Și nu va trece prin dovada de acest lucru,
dar multe probleme din domeniul științei calculator poate fi dovedit prin inducție.
Câți dintre voi sunt familiarizați cu inducție?
Bine. Mișto.
Astfel încât să puteți dovedi corectitudinea acestui algoritm simplu prin inducție,
în cazul în care ipoteza de inducție ta ar fi, presupune că
Shuffle mea returnează fiecare permutare la fel de probabil
până la primele elemente i.
Acum, ia în considerare i + 1.
Și de modul în care ne alege j noastră index swap,
acest lucru duce la - si apoi lucrezi la detalii,
cel puțin o dovadă completă a acestui algoritm ce revine
fiecare permutare cu probabilitate la fel de probabil.
>> În regulă, următorul problema.
Deci, "având în vedere o serie de numere intregi, pozitiva, zero, negativ,
scrie o funcție care calculează suma maximă
cu privire la orice subarray continueous de matrice de intrare. "
Un exemplu aici este, în cazul în care toate numerele sunt pozitive,
atunci în prezent cea mai bună alegere este de a lua întreaga gamă.
1, 2, 3, 4, este egal cu 10.
Când aveți unele negative acolo,
în acest caz, vrem doar primele două
deoarece alegerea -1 și / sau -3 va aduce suma intre nostru în jos.
Uneori am putea avea să înceapă în mijlocul matrice.
Uneori vrem să aleagă nimic, la toate, cel mai bine este să nu ia nimic.
Și uneori e mai bine să ia toamna,
deoarece lucrul după ce este super mare. Deci, orice idei?
(Student, neinteligibil) >> Da.
Să presupunem că eu nu iau -1.
Apoi, fie aleg 1000 și 20.000,
sau aleg doar de 3 miliarde de euro.
Ei bine, cea mai bună alegere este de a lua toate numerele.
Acest -1, în ciuda fiind negativ,
întreaga sumă este mai bun decât au fost nu de a lua -1.
Deci unul dintre sfaturile le-am menționat mai devreme a fost să indice în mod clar evidente
și soluția brute force primul.
Care este soluția forta bruta în această problemă? Da?
[Jane] Ei bine, eu cred că soluția brute force
ar fi să aduni toate combinațiile posibile (neinteligibil).
[Yu] Ok. Deci, ideea lui Jane este de a lua orice este posibil -
Sunt parafrazarea - este de a lua orice subarray posibil, continuă,
calcula suma intre ei, și apoi să ia maximă a tuturor subarrays posibile continue.
Ce identifică în mod unic o matrice de intrare în subarray meu?
Ca, ce două lucruri am nevoie? Da?
(Student, neinteligibil) >> dreapta.
O limită inferioară pe indicele și un indice de limita superioară
determină în mod unic un subarray continuu.
[Elev Femeie] Ne-am estimare este o serie de numere unice?
[Yu] Nr Deci, întrebarea ei este, suntem presupunând gama noastră -
este gama noastră toate numerele unice, iar răspunsul este nu.
>> Dacă vom folosi soluția noastră forta bruta, apoi indicii de începere / terminare
unic determină subarray nostru continuu.
Deci, dacă am repeta pentru toate intrările de pornire posibile,
și pentru toate intrările end> ​​sau = pentru a începe, și <n,
vă calcula suma intre, iar apoi vom lua suma maximă care le-am văzut până acum.
Este clar acest lucru?
Care este O mare de această soluție?
Timewise.
Nu este destul de n ^ 2.
Rețineți că itera de la 0 la n,
asa ca asta e unul pentru buclă.
Am itera din nou de la aproape început până la sfârșit, o altă buclă pentru.
Și acum, în termen de faptul că, trebuie să ne rezuma la fiecare intrare,
asa ca asta e alta pentru buclă. Deci, avem trei imbricate pentru bucle, n ^ 3.
Bine. Acest lucru este valabil ca un punct de plecare.
Soluția noastră este mai rău decât n ^ 3.
Are toată lumea înțelege soluția forta bruta?
>> Bine. O soluție mai bună este o idee folosind numit de programare dinamică.
Dacă luați CS124, care este Algoritmi si Structuri de date,
vei deveni foarte familiarizat cu aceasta tehnica.
Iar ideea este, încercați să construiască soluții la problemele mai mici.
Ce vreau să spun prin asta este, avem în prezent trebuie să vă faceți griji despre două lucruri: de început și de sfârșit.
Și asta e enervant. Ce se întâmplă dacă am putea scăpa de una dintre aceste parametri?
O idee este de a - Suntem dat problema noastră inițială,
găsi suma maximă a oricărei subarray într-un interval [O, n-1].
Și acum avem o nouă subproblem, în cazul în care știm, în indexul nostru curent I,
noi știm că trebuie să încheie acolo. Subarray noastră trebuie să se încheie la indexul curent.
Deci, problema rămasă este, în cazul în care ar trebui să începem subarray nostru?
Are acest sens? Bine.
Așa că m-am codat asta, și să ne uităm la ceea ce înseamnă acest lucru.
În codirectory, există un program numit subarray,
și este nevoie de numărul de articole,
și returnează suma intre subarray maximă în lista mea de amestecat.
Deci, în acest caz, subarray nostru maximă este de 3.
Și asta a luat prin utilizarea doar 2 și 1.
Să-l rula din nou. Este, de asemenea 3.
Dar de data asta, notati cum am ajuns 3.
Am luat - am lua doar 3 sine
pentru ca este inconjurata de negative pe ambele fețe,
care va aduce o suma <3.
Să rula pe 10 elemente.
De data aceasta e 7, luăm de conducere 3 și 4.
De data aceasta este 8, și obținem că prin luarea de 1, 4 și 3.
Deci, pentru a vă oferi o intuiție despre cum putem rezolva această problemă transformat,
Să aruncăm o privire la acest subarray.
Suntem dată fiind această matrice de intrare, și știm răspunsul este 8.
Ne ia 1, 4, și 3.
Dar să ne uităm la modul în care am ajuns de fapt, acest răspuns.
Să ne uităm la subarray maximă care sa încheiat la fiecare dintre aceste indicii.
Care e subarray maximă care trebuie să se încheie la prima poziție?
[Student] Zero. Zero >>. Doar nu iau -5.
Aici va fi 0, de asemenea. Da?
(Student, neinteligibil)
[Yu] Oh, îmi pare rău, acesta este un -3.
Deci, aceasta este o 2, aceasta este o -3.
Bine. Deci -4, ceea ce e subarray maximă pentru a termina această poziție
în cazul în care este la -4? Zero.
Unul? 1, 5, 8.
Acum, trebuie să se încheie la locul unde este la -2.
Deci 6, 5, 7, iar ultima este de 4.
Știind că acestea sunt intrări mele
pentru problema transformat în cazul în care trebuie să se încheie la fiecare dintre aceste indici,
atunci răspunsul meu final este doar, să ia o matura peste,
și să ia numărul maxim.
Deci, în acest caz, e 8.
Acest lucru implică faptul că subarray maximă se termină la acest indice,
și a început undeva în fața sa.
Are toată lumea să înțeleagă asta subarray transformat?
>> Bine. Ei bine, hai să dau seama recurență pentru acest lucru.
Să ia în considerare doar primele câteva intrări.
Deci, aici a fost de 0, 0, 0, 1, 5, 8.
Și apoi a fost o -2 aici, și că a adus în jos la 6.
Deci, dacă am apela intrarea la pozitia i subproblem (i),
cum pot folosi răspunsul la o subproblem anterioară
pentru a răspunde la această subproblem?
Dacă mă uit la, să spunem, această intrare.
Cum pot calcula răspunsul 6 uitandu-se la
o combinație a acestei matrice și răspunsuri la subprobleme anterioare din acest tablou? Da?
[Elev Femeie] Tu iei matrice sumelor
în poziția corectă în fața sa, astfel încât 8,
și apoi adăugați subproblem curent.
[Yu] Deci sugestia ei este să se uite la aceste două numere,
acest număr și acest număr.
Deci, acest 8 se referă la răspunsul pentru subproblem (i - 1).
Și să numim A. meu matrice de intrare
În scopul de a găsi un subarray maximă care se termină la poziția i,
Am două opțiuni: pot continua, fie subarray
care a pus capăt la indexul anterior, sau de a începe o nouă matrice.
Dacă ar fi să continue subarray care a început la indicele precedent,
atunci suma maximă pot atinge este răspunsul la subproblem precedentă
plus de intrare matrice curent.
Dar, am, de asemenea, alegerea de a începe o nouă subarray,
caz în care suma este 0.
Deci, răspunsul este maxim la 0, subproblem I - 1, plus intrarea matrice curent.
Are această recurență sens?
Recurență noastră, așa cum tocmai am descoperit, este subproblem i
este egală cu valoarea maximă a subproblem anterior, plus intrarea mea matrice curent,
ceea ce înseamnă continua subarray precedent,
sau 0, începe o nouă subarray la indexul meu curent.
Și odată ce ne-am construit acest tabel de soluții, atunci raspunsul nostru final,
face doar o matura liniar peste matrice subproblem
și să ia numărul maxim.
Aceasta este o punere în aplicare exactă a ceea ce tocmai am spus.
Deci, vom crea o matrice subproblem nou, subprobleme.
Prima intrare este fie 0 sau prima intrare, maxim de cei doi.
Și pentru restul subprobleme
vom folosi repetarea exactă tocmai l-am descoperit.
Acum am calcula maxim de gama noastră subprobleme, și asta e raspunsul nostru final.
>> Deci, cât de mult spațiu suntem folosind în acest algoritm?
Dacă ați luat doar CS50, atunci nu s-ar fi discutat foarte mult spatiu.
Ei bine, un lucru de remarcat este faptul că i-am sunat malloc aici cu n dimensiuni.
Ce înseamnă acest sugeram dumneavoastra?
Acest algoritm folosește spațiu liniar.
Putem face mai bine?
Este ceva care observați că nu este necesară pentru a calcula raspunsul final?
Cred că o întrebare mai bună este, ce informații
nu avem nevoie pentru a transporta tot drumul până la capăt?
Acum, dacă ne uităm la aceste două linii,
ne pasă doar despre subproblem precedent,
și ne pasă doar de maxim care l-am văzut până acum.
Pentru a calcula răspunsul nostru final, nu avem nevoie de matrice întreaga.
Avem nevoie doar de ultimul număr, în ultimele două numere.
Ultimul numar de matrice subproblem, și ultimul număr de maxim.
Deci, de fapt, putem fuziona aceste bucle, împreună
și du-te din spațiu liniar în spațiu constantă.
Suma curent până în prezent, aici, inlocuieste rolul subproblem, gama noastră subproblem.
Deci suma actuală, până în prezent, este răspunsul la subproblem precedent.
Și această sumă, până în prezent, are loc de max noastre.
Noi calcula maximă mergem de-a lungul.
Și așa vom merge din spațiu liniar în spațiu constantă,
și avem, de asemenea, o soluție la problema liniar subarray nostru.
>> Aceste tipuri de întrebări pe care le va primi in timpul unui interviu.
Care este complexitatea timp, ceea ce este complexitatea spațiu?
Poți să o faceți mai bine? Există lucruri care nu sunt necesare pentru a menține în jurul valorii de?
Am făcut acest lucru pentru a evidenția analizele pe care ar trebui să ia pe cont propriu
cum lucrați prin aceste probleme.
Întotdeauna fi te intrebi, "Pot să fac mai bine?"
De fapt, am putea face mai bine decât asta?
Un fel de întrebare capcană. Tu nu poți, pentru că aveți nevoie să
cel puțin citit de intrare la problema.
Deci, faptul că trebuie să citească, cel puțin de intrare la problema
înseamnă că nu puteți face mai bine decât timpul linear,
și nu se poate face mai bine decât spațiul constanta.
Deci, aceasta este, de fapt, cea mai bună soluție pentru această problemă.
Întrebări? Bine.
>> Stocul de piață problema:
"Având în vedere o serie de numere intregi n, pozitiv, zero, sau negativ,
care reprezintă prețul unui stoc de peste zi n,
scrie o funcție pentru a calcula profitul maxim pe care îl poate face
dat fiind faptul că ați cumpăra și vinde exact 1 stoc în aceste zile n ".
În esență, dorim sa cumparam ieftin, vinzi scump.
Și vrem să aflăm mai bun profitul putem face.
Revenind la vârful meu, ceea ce este imediat clar, mai simplu raspuns, dar e lent?
Da? (Student, neinteligibil) >> Da.
Deci, v-ar >> du-te si uita-te la, deși prețurile în stoc
la fiecare punct din timp, (neinteligibil).
[Yu] Ok, deci o soluție - sugestia ei de calcul
Cel mai mic și cel mai mare calcul nu funcționează în mod necesar
deoarece cea mai mare s-ar putea să apară înainte de cea mai mică.
Deci, ce este soluția brute force la această problemă?
Care sunt cele două lucruri pe care am nevoie pentru a determina în mod unic profitul fac? Corect.
Soluția este forta bruta - oh, deci, sugestia lui George este avem nevoie doar de două zile
pentru a determina în mod unic de profit a acestor două zile.
Așa că am calcula fiecare pereche, ca cumpara / vinde,
calcula profitul, care ar putea fi negativ sau pozitiv sau zero.
Calculați profitul maxim pe care o facem după iterarea peste toate perechile de zile.
Care va fi răspunsul nostru final.
Și că această soluție va fi O (n ^ 2), deoarece nu există n alege două perechi -
de zile în care se poate alege între zi finali.
Ok, deci nu am de gând să merg peste soluția brute force aici.
Am de gând să vă spun că există o soluție n log n.
Ce părere aveți algoritm în prezent, știi că este n log n?
Nu este o întrebare capcană.
>> Merge sortare. Merge fel este n log n,
și, de fapt, o modalitate de a rezolva această problemă este de a utiliza
un fel de idee fel îmbinare numit, în general, dezbina si cucereste.
Iar ideea este după cum urmează.
Vrei pentru a calcula cel mai bun cumpărare / vânzare pereche în jumătatea stângă.
Gasesti cel mai bun profitul puteti face, doar cu n primul pe parcursul a două zile.
Apoi doriți să oompute cel mai bun cumpărare / vânzare pereche pe jumătatea din dreapta,
deci n ultimul timp de două zile.
Și acum întrebarea este, cum ne uni aceste soluții din nou împreună?
Da? (Student, neinteligibil)
Bine >>. Așa că lasă-mă să deseneze o imagine.
Da? (George, neinteligibil)
Exact >>. Soluția lui George este exact dreptate.
Deci sugestia lui este, cel mai bun calcula prima cumpărare / vânzare pereche,
și care are loc în jumătatea stângă, așa că hai să numesc asta stânga, stânga.
Cel mai bun cumpara / vinde pereche care are loc în jumătatea din dreapta.
Dar dacă ne-am comparat doar aceste două numere, ne lipsește cazul
în cazul în care vom cumpăra și vinde aici, undeva în jumătatea din dreapta.
Cumparam în jumătatea stângă, vinde în jumătatea din dreapta.
Și cel mai bun mod de a calcula cel mai bun cumpara / vinde pereche care se întinde pe ambele jumatati
este de a calcula minim aici și calcula maxim aici
și să ia diferența lor.
Deci, cele două cazuri în care perechea cumpărare / vânzare are loc numai aici,
numai aici, sau pe ambele jumatati este definit de aceste trei numere.
Deci, algoritmul nostru pentru a intra soluțiile noastre înapoi împreună,
vrem să calculăm cel mai bun cumpărare / vânzare pereche
în cazul în care vom cumpăra pe jumătatea stângă și să vândă pe jumătatea din dreapta.
Și cel mai bun mod de a face acest lucru este de a calcula cel mai mic preț în prima jumătate a anului,
cel mai mare preț în jumătatea dreaptă, și să ia diferența lor.
Rezultată trei profiturilor, aceste trei numere, luați maximă de trei,
si asta e cel mai bun profit poti face peste aceste primele zile și sfârșitul.
Aici liniile importante sunt în roșu.
Acesta este un apel recursiv pentru a calcula răspunsul în jumătatea stângă.
Acesta este un apel recursiv pentru a calcula răspunsul în jumătatea din dreapta.
Aceste două bucle pentru a calcula min și max pe jumătatea stângă și dreapta, respectiv.
Acum am calcula profitul pe care se întinde pe ambele jumatati,
și răspunsul final este maximă a acestor trei.
Bine.
>> Deci, sigur, avem un algoritm, dar întrebarea este mai mare,
ceea ce este complexitatea timp de asta?
Și motivul pentru care am menționat de îmbinare fel este faptul că această formă de diviza răspuns
în două și apoi fuzionarea soluțiile noastre înapoi împreună
este exact forma de sortare îmbinare.
Așa că lasă-mă să trec prin durata.
Dacă am definit o functie T (n) să fie numărul de pași
pentru n zile,
cele două apeluri recursive
sunt fiecare va costa T (n / 2),
și nu există două dintre aceste apeluri.
Acum am nevoie pentru a calcula minima de jumătatea stângă,
pe care eu pot face în n / 2 ora, plus maxim de jumătatea din dreapta.
Deci, aceasta este doar n.
Și apoi, plus ceva de lucru constantă.
Și această ecuație reapariției
este exact ecuația de recurență pentru sortare îmbinare.
Și știm cu toții că este un fel de îmbinare log n n timp.
Prin urmare, algoritmul nostru este, de asemenea, n log n timp.
Are această repetare a face sens?
Doar o recapitulare scurtă de acest lucru:
T (n) este numărul de pași pentru a calcula profitul maxim
pe parcursul a n zile.
Modul în care ne despărțim apeluri recursive noastre
este sunand la soluția noastră în primele zile n / 2,
așa că e un singur apel,
și atunci se numește din nou pe a doua jumătate.
Deci asta e două apeluri.
Și apoi vom găsi o minimă pe jumătatea stângă, pe care le putem face în timp liniar,
găsi maximă jumătatea dreaptă, pe care le putem face in timp liniar.
Deci, n / 2 + n / 2 este doar n..
Atunci avem ceva de lucru constantă, care este ca face aritmetica.
Această ecuație recurență este exact ecuația de recurență pentru sortare îmbinare.
Prin urmare, algoritmul nostru shuffle este, de asemenea n log n.
Deci, cât de mult spațiu suntem folosind?
Să ne întoarcem la codul.
>> O întrebare mai bună este, cât de multe cadre stack-avem vreodată la un moment dat?
Din moment ce suntem cu recursivitate,
numărul de cadre stack determină utilizarea nostru spațiu.
Să considerăm n = 8.
Facem apel la 8 amestecare,
care va apela shuffle pe primele patru intrări,
care va apela un shuffle pe primele două intrări.
Deci stack nostru este - aceasta este stiva noastră.
Și atunci se numește amestecare din nou la 1,
și asta e ceea ce cazul nostru de bază este, deci ne întoarcem imediat.
Avem tot mai mult de această cadre stack de multe?
Nu, pentru că de fiecare dată când facem o invocare,
o invocație recursivă la shuffle,
vom împărți dimensiunea noastră în jumătate.
Deci, numărul maxim de cadre stack avem vreodată la un moment dat
este pe ordinea de cadre log n stivă.
Fiecare cadru stivă are spațiu constanta,
și, prin urmare, valoarea totală a spațiului,
valoarea maximă de spațiu vom folosi vreodată este O (log n) spațiu
unde n este numărul de zile.
>> Acum, întrebați-vă mereu, "putem face mai bine?"
Și, în special, putem reduce această problemă într-o am deja rezolvat?
Un indiciu: am discutat doar două alte probleme înainte de acest lucru, și nu va fi shuffle.
Noi putem transforma această problemă piața bursieră în problema subarray maximă.
Cum putem face acest lucru?
Unul dintre voi? Emmy?
(Emmy, neinteligibil)
[Yu] Exact.
Deci, problema subarray maximă,
suntem în căutarea pentru o sumă de peste un subarray continuu.
Și sugestia lui Emmy pentru problema stocurilor,
ia în considerare schimbările, sau delte.
Și o imagine a acestui fapt este - aceasta este pretul unei actiuni,
dar dacă am luat diferenta dintre fiecare zi consecutiv -
asa ca am vedea că prețul maxim, profit maxim am putea face
este, dacă vom cumpăra și vinde aici aici.
Dar haideți să ne uităm la continuu - să ne uităm la problema subarray.
Deci, aici, putem face - merge de aici până aici,
avem o schimbare pozitivă, și apoi merge de aici până aici avem o schimbare negativ.
Dar apoi, mergând de aici până aici avem o schimbare uriașă pozitivă.
Și acestea sunt modificările pe care dorim să le rezuma pentru a obține profit nostru final.
Apoi, avem mai multe schimbări negative aici.
Cheia pentru reducerea problema noastră stoc în problema noastră subarray maximă
este să ia în considerare deltele dintre zile.
Deci, vom crea o matrice nou numit delte,
inițializa prima intrare a fi 0,
și apoi pentru fiecare triunghi (i), să fie faptul că diferența
de matrice meu de intrare (i), și matrice (i - 1).
Apoi, noi numim procedura noastră de rutina pentru un maxim subarray
trecerea într-o matrice delta.
Și pentru că subarray maximă este timpul liniar,
și această reducere, acest proces de creare a acestei matrice delta,
Este, de asemenea, timpul linear,
apoi soluția finală pentru stocurile este O (n) de muncă, plus O (n) de muncă, este încă O (n) de muncă.
Deci, avem o soluție de timp liniar la problema noastră.
Are toată lumea să înțeleagă această transformare?
>> În general, o idee buna pe care ar trebui să aveți întotdeauna
este să încercați pentru a reduce o problemă nouă, care te vezi.
În cazul în care se pare cunoscut la o problemă veche,
încercați să reduceți-l la o problema veche.
Și dacă puteți utiliza toate instrumentele pe care le-ați utilizat la vechea problemă
pentru a rezolva problema noua.
Deci, pentru a încheia, interviuri tehnice sunt provocatoare.
Aceste probleme sunt, probabil, unele dintre cele mai dificile probleme
pe care le-ar putea vedea într-un interviu,
așa că, dacă nu înțelegeți toate problemele pe care am reglementate, e în regulă.
Acestea sunt unele dintre cele mai dificile probleme.
Practică, practică, practică.
I-am dat o mulțime de probleme în fișa, deci cu siguranta verificați aceste afară.
Și noroc pe interviuri dvs.. Toate resursele mele sunt postate la acest link,
și unul dintre prietenii mei seniori a oferit să facă interviuri simulate tehnice,
asa ca daca esti interesat, e-mail va Yao la acea adresa de e-mail.
Dacă aveți unele întrebări, puteți să mă întrebi pe mine.
Nu voi aveți întrebări specifice legate de interviuri tehnice
sau orice probleme care le-am vazut pana acum?
Bine. Ei bine, noroc pe interviuri dvs..
[CS50.TV]