[Powered by Google Translate] [Seminar: Tehnične Intervjuji]
[Kenny Yu, Harvard University]
[To je CS50.] [CS50.TV]
Pozdravljeni vsi, jaz sem Kenny. Trenutno sem junior študira računalništvo.
Sem nekdanji CS TF, jaz želeti sem imel, ko sem bil underclassman,
in zato dajem ta seminar.
Zato upam, da boste uživali.
Seminar je o tehničnih pogovorov,
in se lahko vsi moji viri so na voljo na tej povezavi,
ta link tukaj, nekaj sredstev.
Zato sem naredil seznam težav, pravzaprav kar nekaj težav.
Tudi splošna virov stran, kjer lahko najdemo nasvete
o tem, kako se pripraviti na razgovor,
nasvetov o tem, kaj je treba storiti v času dejanskega razgovor,
pa tudi, kako se lotiti problemov in sredstev za poznejšo uporabo.
Vse je na spletu.
In samo uvod v ta seminar, disclaimer,
kot je ta, ne bi smeli - vaš intervju priprave
ne sme biti omejena na ta seznam.
To je mišljeno samo za različna
in si je vsekakor treba vzeti vse, kar sem rekel z zrna soli,
pa tudi vse, kar sem uporabo, ki se uporablja, da vam pomaga pri pripravi intervjuja.
>> Jaz bom pospešil skozi naslednjih nekaj diapozitivov
Tako lahko pridemo do dejanske študije primerov.
Struktura intervjuju za Medsebojno lego programske opreme,
Običajno je 30 do 45 minut,
več krogov, odvisno od podjetja.
Pogosto boste kodiranje na tabli.
Torej bela board, kot je ta, pogosto pa v manjšem obsegu.
Če imate telefonsko intervju, boste verjetno uporabljali
bodisi collabedit ali Google Doc, tako da lahko vidim v živo kodiranje
ko ste se na razgovor po telefonu.
Intervju je sama po navadi 2 ali 3 težave
testiranje svoje znanje računalništva.
In bo skoraj zagotovo vključuje kodiranja.
Vrste vprašanj, ki jih boste videli ponavadi podatkovne strukture in algoritmi.
In pri tem te vrste težav,
vas bodo vprašali, kot so, kaj je časovna in prostorska zahtevnost, veliki O?
Pogosto zahtevajo tudi višje ravni vprašanja,
Tako, oblikovanje sistema,
kako bi si začrtate kodo?
Kaj vmesniki, kaj razredi, kaj moduli Ali imate v vašem sistemu,
in kako ti vplivajo skupaj?
Torej podatkovne strukture in algoritmi, kot tudi oblikovanje sistemov.
>> Nekaj ​​splošnih nasvetov, preden se potopite v naše študije primerov.
Mislim, da je najbolj pomembno pravilo je vedno treba razmišljati na glas.
Intervju naj bi bila vaša priložnost, da pokažejo svoje mišljenje postopek.
Bistvo intervjuja je za popisovalca, da bi ocenili
Kako mislite, in kako si šel skozi problem.
Najslabša stvar, ki jo lahko naredimo je biti tiho v celotnem intervjuju.
To sploh ni dobro.
Ko ste dobili vprašanje, tudi vi želite, da poskrbite, da boste razumeli vprašanje.
Torej, ponovimo vprašanje, spet s svojimi besedami
in poskus, da bi delo temeljito nekaj preprostih testnih primerov
poskrbite, da boste razumeli vprašanje.
Delo z nekaj testnih primerov bo tudi vam intuicijo o tem, kako rešiti ta problem.
Morda celo odkrili nekaj vzorcev, ki vam pomaga rešiti problem.
Njihov nasvet je, da veliko zaslužiti uničen.
Ne bodi uničen.
Intervjuji so izziv, vendar najslabše kar lahko storite,
poleg tega, da molči, je treba vidno razočaran.
Vi ne želite, da bi ta vtis z anketarjem.
Ena stvar, ki jo - tako je veliko ljudi, ko gredo v intervjuju,
skušajo, da bi poskušali najti najboljšo rešitev po eni strani,
ko je res, tam je ponavadi potihoma očitna rešitev.
Morda bi bilo počasno, je morda neučinkovit, vendar pa je treba samo navesti,
samo zato, da imaš izhodišče, iz katerih se delajo bolje.
Prav tako opozarja na rešitev, je počasen, kar zadeva
O velika časovna zahtevnost in kompleksnost prostora,
bo pokazal, da anketarjem, da razumete
ta vprašanja pri pisanju kode.
Torej, ne bojte se, da bi prišli do najbolj preprost algoritem 1.
in nato deluje bolje od tam.
Vsa vprašanja tako daleč? Ok.
>> Torej se potopite v naši prvi problem.
"Glede na niz celih števil n, napisati funkcijo, ki shuffles matriko
na mestu, tako da so vse permutacije o števil n enako verjetno. "
In Predvidevam, da imaš na voljo naključno celo število generator
ki ustvarja celo število v območju od 0 do i, pol območje.
Ali vsi razumejo to vprašanje?
Dam niz števil n, in želim, da jo shuffle.
V mojem imeniku, sem napisal nekaj programov, iz katerih je razvidno, kaj mislim.
Jaz bom shuffle paleto 20 elementov,
od -10 do 9,
in želim si, da izvrgel, kot je ta.
Torej, to je moj vnos razvrščenih matrika, in želim, da jo shuffle.
Mi bomo še enkrat.
Ali vsi razumejo vprašanje? Ok.
Torej je odvisno od vas.
Katere so nekatere ideje? Lahko to storite n ^ 2, n log n, n?
Odprt za predloge.
Ok. Torej, ena ideja, ki jo predlaga Emmy,
je najprej izračunati naključno število, naključno celo število, v območju od 0 do 20.
Tako prevzemajo naša matrika ima dolžino 20.
V našem diagramu 20 elementov,
To je naš prispevek polje.
In zdaj je njen predlog je, da ustvarite nov niz,
Tako bo to izhodna matrika.
In na podlagi i vrne rand -
Torej, če sem bil, recimo, 17,
kopirate 17. element v prvem položaju.
Zdaj moramo izbrisati - moramo preusmeriti vse elemente, ki tu
kot da smo vrzel na koncu in brez lukenj v sredini.
In zdaj smo ponovite postopek.
Zdaj smo izbrali novo naključno celo število med 0 in 19.
Imamo nov sem tukaj in mi kopijo tega elementa v tem položaju.
Potem smo prehod čez predmete in ponovimo postopek, dokler imamo polno novo paleto.
Kaj je čas teka tega algoritma?
No, pa menijo, da je učinek tega.
Mi se spreminja vsak element.
Ko smo odstranili to jaz, sva se spreminja vse elemente, potem ko je na levi strani.
In to je O (n) stroški
ker kaj pa če odstranimo prvi element?
Torej za vsako odpremo, odstranimo -
Vsaka odstranitev nastopi O (n) delovanje,
in ker smo n odstranitev to pripelje do O (n ^ 2) shuffle.
Ok. Tako dober začetek. Dober začetek.
>> Drug predlog je, da uporabite nekaj znana kot shuffle Knuth,
ali Fisher-Yates shuffle.
In to je pravzaprav linearen čas shuffle.
In ideja je zelo podobna.
Spet imamo vhodni niz,
ampak namesto dveh polj za našo vhodno / izhodnih,
bomo uporabili prvi del niza, da bi spremljali naše premešan obrok,
in smo spremljali, potem pa gremo na ves naš niz za unshuffled del.
Torej, tukaj je tisto, kar sem mislil. Smo začeli z - smo se odločili za i,
matrika 0-20.
Naš trenutni kazalec kaže na prvem indeksu.
Izbrali smo nekaj sem tu
in zdaj smo zamenjali.
Torej, če je to 5 in to je bilo 4,
posledična matrika bo imel 5 tukaj in 4 tukaj.
In zdaj smo ugotovili, označevalec tukaj.
Vse na levi je premešan,
in unshuffled vse na desni.
In zdaj lahko ponovite postopek.
Smo izbrali naključno indeks med 1 in 20 zdaj.
Torej, predvidevam naš novi i je tukaj.
Zdaj smo zamenjali To sem z našo trenutno drugo mesto tukaj.
Tako smo se menjava naprej in nazaj, kot je ta.
Naj bruhati kodo, da bi postala bolj konkretna.
Začeli smo z našo izbiro i -
začnemo z i enak 0, smo izbrali naključno j lokacijo
V unshuffled del matrike, i n-1.
Torej, če sem tukaj, izbrati naključno indeks med tu in drugod po matriki,
in smo zamenjali.
Vse to je potrebno, da koda shuffle svoje polje.
Kakšno vprašanje?
>> No, ena je potrebno vprašanje je, zakaj je to pravilno?
Zakaj je vsako permutacijo enako verjetno?
In ne bom šel skozi dokazila o tem,
vendar pa lahko veliko problemov v računalništvu izkazal z indukcijo.
Koliko ste seznanjeni z indukcijo?
Ok. Kul.
Tako boste lahko dokazali pravilnost tega algoritma z navadno sesanje,
če bi bil vaš indukcija hipoteza je, predpostavimo, da
moj shuffle vrne vse permutacije enako verjetno
do prvih i elementov.
Zdaj menijo, i + 1.
In mimogrede, izbira naš indeks j zamenjati,
to ima za posledico - in potem dogovorijo o podrobnostih,
vsaj polni dokaz o tem, zakaj je ta algoritem vrne
vsako permutacijo z enako verjetnostjo verjetno.
>> V redu, naslednji problem.
Torej, "glede na niz števil, postive, nič negativnega,
napisati funkcijo, ki izračuna najvišji znesek
vseh continueous subarray za vnos niza. "
Primer za to je, da v primeru, če vse številke so pozitivni,
Nato trenutno najboljša izbira je, da se celotno paleto.
1, 2, 3, 4, znaša 10.
Če imate nekaj negativov tam,
v tem primeru hočemo samo prvi dve
ker bo izbira -1 in / ali -3 bi naše vsoto navzdol.
Včasih moramo začeti v sredini polja.
Včasih želimo izbrati sploh nič, je najbolje, da ne bo nič.
In včasih je bolje, da se je padec,
ker je stvar, potem ko ji je bila super velik. Torej, vse ideje?
(Študent, nerazumljiv) >> Ja.
Recimo, da ne jemljem -1.
Potem sem se odločil, 1000 in 20000,
ali pa sem samo izbrati 3000000000.
No, najboljša izbira je, da se vse številke.
Ta -1, čeprav je negativna,
celotna vsota je bila boljša kot jaz, da ne bo -1.
Torej, eden od nasvetov sem omenil prej je bilo jasno navesti očitno
in silo rešitev prvi.
Kaj je silo rešitev tega problema? Ja?
[Jane] No, mislim, da je surovo silo raztopina
bi bilo sešteti vse možne kombinacije (nerazumljivo).
[Yu] Ok. Torej ideja Jane je, da vsak možen -
Jaz sem parafraziramo - je, da se v največji možni meri neprekinjeno subarray,
izračuna svojo vsoto, in nato z največ vseh mogočih stalnih subarrays.
Kaj nedvoumno identificira subarray v mojem vhodni matriki?
Všeč mi je, kaj se dve stvari potrebujem? Ja?
(Študent, nerazumljiv) >> desno.
Spodnja meja na indeks in indeks zgornjo mejo
enolično določa stalno subarray.
[Ženski študentski] Ali oceni, da je niz enoličnih številk?
[Yu] No torej njeno vprašanje je, smo ob predpostavki, da portfelj -
je naša matrika vse unikatne številke, in odgovor je ne.
>> Če uporabljamo naše grobo silo rešitev, nato pa začetek / konec indeksov
enolično določa naša stalna subarray.
Torej, če želimo ponoviti na vseh možnih začetnih vpisov,
in za vse končne geslih> ali = začetek in <n,
da izračunati vsoto, nato pa smo se najvišji znesek, ki smo jih videli do sedaj.
Je to jasno?
Kaj je velik O te rešitve?
Timewise.
Ni čisto n ^ 2.
Upoštevajte, da izbirate od 0 do n,
tako, da je ena zanka.
Ponovil smo spet od skoraj začetka do konca, drugo za zanko.
In zdaj, v tem smo imeli, da povzamem vse vstopa,
tako da je še ena zanka. Torej imamo 3 vgnezdeno for zanke, n ^ 3.
Ok. To velja kot izhodišče.
Naša rešitev je nič slabši od n ^ 3.
Ali vsi razumejo grobo silo rešitev?
>> Ok. Boljša rešitev je uporaba idejo, imenovano dinamično programiranje.
Če ste vzeli CS124, ki je Algoritmi in podatkovne strukture,
boste postali zelo seznanjeni s to tehniko.
In ideja je, poskusite zgraditi rešitve za manjše težave prvi.
Kaj mislim s tem je, da imamo zdaj skrbeti za dve stvari: začetek in konec.
In to je nadležno. Kaj, če bi se znebimo enega od teh parametrov?
Ena ideja je, da - glede na naš prvotni sva problem,
je bil najvišji znesek vsakega subarray v območju [O, n-1].
In zdaj imamo novo podproblema, če vemo, v našem trenutnega indeksa i,
vemo, da se mora zaključiti tam. Naša subarray se mora končati na trenutnega indeksa.
Tako je preostala težava je, kje naj začnemo subarray?
Ali je to smiselno? Ok.
Tako sem kodirani to gor, in si oglejmo, kaj to pomeni.
V codirectory, tam je program, imenovan subarray,
in je potrebno število predmetov,
in vrne maksimalno vsoto subarray na mojem seznamu premešajo.
Torej v tem primeru je naša največja subarray je 3.
In to je delo samo z 2 in 1.
Naj ga ponovno zaženete. To je tudi 3.
Toda tokrat si oglejte, imamo 3.
Mi je - mi vzemite 3 se
zato, ker je obkrožen z negativov na obeh straneh,
ki bo prinesla vsoto, <3.
Naj deluje na 10 točk.
Tokrat je 7, bomo vodilni 3 in 4.
Tokrat je 8 in dobimo, da je s tem, 1, 4 in 3.
Tako, da vam intuicijo o tem, kako lahko rešimo ta problem preoblikuje,
pa si oglejte na tej subarray.
Mi smo glede tega vhodni niz, in vemo, da je odgovor 8.
Menimo, 1, 4 in 3.
Toda poglejmo, kako smo dejansko dobili ta odgovor.
Oglejmo si največjim subarray ki se je končalo na vsaki izmed teh indeksov.
Kaj je največja subarray, ki se mora končati na prvem mestu?
[Študent] Zero. >> Zero. Samo ne na -5.
Tukaj se dogaja, da je 0, kot dobro. Ja?
(Študent, nerazumljiv)
[Yu] Oh, oprostite, to je -3.
Torej, to je 2, to je -3.
Ok. Torej, -4, kaj je največja subarray do konca tega položaja
-4 kjer je na? Zero.
Ena? 1, 5, 8.
Zdaj pa moram končati na lokaciji, kjer je na -2.
Torej, 6, 5, 7 in zadnja je 4.
Vedoč, da so to moji vnosi
za transformacijo problem, če moram končati na vsaki od teh indeksov,
potem moj zadnji odgovor je le, da je zamah čez,
in se največje število.
Torej, v tem primeru je 8.
To pomeni, da je bila največja subarray konča na ta indeks,
in začela nekje pred njim.
Ali vsi razumejo ta preoblikuje subarray?
>> Ok. No, pa ugotovimo ponovitev za to.
Oglejmo si le prvih nekaj vnosov.
Torej, tukaj je 0, 0, 0, 1, 5, 8.
In potem je bila -2 tukaj, in to je znižal na 6.
Torej, če sem poklical vstop na položaju i podproblema (i)
kako lahko uporabim odgovor na prejšnje podproblema
Odgovor na to podproblema?
Če gledam, recimo, ta vnos.
Kako lahko izračunamo odgovor 6 jih je videti na
Kombinacija tega niza in odgovore na prejšnjih podproblemov v tem polju? Ja?
[Ženski študentski] Vzameš matriko zneskov
v položaju, tik pred njim, tako da je 8,
in nato dodate trenutno podproblema.
[Yu] Zato njen predlog je, da si v teh dveh številk,
to število in ta številka.
Torej, to 8 se nanaša na odgovor za podproblema (i - 1).
In recimo moj A. vhodni niz
Da bi našli maksimalnega subarray, ki se konča v položaj I,
Imam dve možnosti: lahko bodisi nadaljevati subarray
, ki se je končalo na prejšnjem indeksa, ali ustvarite novo zbirko.
Če bi še naprej subarray, ki se je začel v prejšnjem indeks,
Nato je največja vsota, da lahko doseže, je odgovor na prejšnje podproblema
plus tekoči niz vnos.
Ampak, jaz tudi imeti možnost, da se začne nova subarray,
V tem primeru je vsota 0.
Torej, odgovor je max 0, podproblema i - 1, plus tekoči niz vnos.
Ali to ponovitev smiselno?
Naša ponovitev, kot smo pravkar odkrili, je podproblema i
je enaka največ prejšnjega podproblema plus mojega trenutnega polja vstopa,
kar pomeni nadaljevanje prejšnje subarray,
ali 0, začetek novega subarray na mojega trenutnega indeksa.
In ko smo zgradili to tabelo rešitev, potem naš končni odgovor,
pač linearno zamah po podproblema niz
in se največje število.
To je točno izvedba, kaj sem rekel.
Tako smo ustvarili novo vrsto podproblema, podproblemov.
Prvi vnos je lahko samo 0 ali 1. vnos, največ teh dveh.
In za ostale podproblemov
bomo uporabili natančno ponovitev smo pravkar odkrili.
Sedaj izračunamo največ naših niz podproblemov, in to je naš končni odgovor.
>> Torej, koliko prostora smo z uporabo tega algoritma?
Če ste le, CS50, potem ne bi razpravljal prostora zelo veliko.
No, ena stvar je tudi omeniti, da sem klical sem z malloc velikosti n.
Kaj to predlagamo, da vas?
Ta algoritem uporablja linearni prostor.
Lahko naredimo bolje?
Ali obstaja kaj, da ste opazili, da ni treba izračunati končni odgovor?
Mislim, boljše vprašanje je, kakšne informacije
ne bomo potrebovali za izvedbo vso pot skozi do konca?
No, če pogledamo na teh dveh linij,
smo samo zanima prejšnjega podproblema,
in smo le skrbi največ kar smo jih kdaj videli do sedaj.
Za izračun naš končni odgovor, ne potrebujemo celotno paleto.
Potrebujemo samo zadnjo številko, zadnji dve številki.
Zadnja številka za podproblema polju, in zadnji številka za največje.
Torej, v bistvu, lahko varovalko te zanke skupaj
in gredo iz linearnega prostora za stalno prostora.
Trenutni znesek do sedaj, tukaj nadomešča vlogo podproblema, naša podproblema diod.
Torej trenutni znesek, če je odgovor na prejšnje podproblema.
In to je znesek, do sedaj se postavlja v naš max.
Izračunamo maksimalno sproti.
In tako sva šla iz linearnega prostora za stalno prostora,
in imamo tudi linearno rešitev za naš problem subarray.
>> Te vrste vprašanj, ki jih boste dobili v intervjuju.
Kakšna je časovna zahtevnost, kar je prostorska zahtevnost?
Lahko narediš bolje? Ali obstajajo stvari, ki so nepotrebne, da bo okoli?
To sem naredil, da označite analiz, ki bi morali sami
kot delate s temi težavami.
Vedno se sprašujete, "Ali lahko še boljši?"
V bistvu, lahko naredimo boljše od tega?
Nekakšen trik vprašanje. Ne moreš, ker moraš
vsaj prebral prispevek k problemu.
Zato je dejstvo, da boste morali vsaj prebral prispevek k problemu
pomeni, da ne morete narediti bolje kot linearni čas,
in ne moreš narediti bolje kot stalni prostor.
Torej je to dejansko najboljša rešitev za ta problem.
Vprašanja? Ok.
>> Borzni trg težavah:
"Glede na niz celih števil n, pozitivno, nič ali negativen,
ki predstavljajo ceno staleža nad n dneh,
napisati funkcijo za izračun največje dobičke, lahko bi
glede na to, da kupujejo in prodajajo natanko 1 zalog v teh n dni. "
V bistvu smo želeli kupiti nizka, prodajati visoko.
In želimo, da ugotovimo, najboljši dobiček moremo narediti.
Če se vrnemo na moj namig, kaj je takoj jasno, Najpreprostejši odgovor, vendar je počasi?
Ja? (Študent, nerazumljiv) >> Ja.
>> Torej bi si šel, in čeprav pogled na tečaje delnic
Na vsaki točki v času, (nerazumljivo).
[Yu] Ok, zato se je njena rešitev - njen predlog računalništva
najnižja in najvišja izračun ni nujno delo
ker lahko pride do najvišje najnižja.
Torej, kaj je silo rešitev za ta problem?
Kaj sta dve stvari, ki jih moram enolično določiti dobička sem naredil? Prav.
The silo rešitev je - oh, tako, predlog Jurija je potrebujemo le dva dni
enoznačno določitev dobička teh dveh dneh.
Tako smo izračunati vsak par, kot nakup / prodajo,
izračun dobička, kar je lahko negativen ali pozitiven ali enak nič.
Izračunajte največji dobiček, da bi po ponavljanjem na vseh parov dni.
To bo naš končni odgovor.
In to bo rešitev O (n ^ 2), ker je n izbere dva para -
dni, ki jih lahko izbirate med končnimi dni.
Ok, tako da ne bom šel čez surovo silo rešitev tukaj.
Jaz ti bom povedal, da obstaja n log n rešitev.
Kaj algoritem ti veš, da je trenutno n log n?
To ni trik.
>> Zlivanjem. Zlivanjem je n log n,
in v resnici, eden od načinov za reševanje tega problema je, da uporabite
neke vrste spajanja ideje pozval, na splošno, deli in vladaj.
In ideja je, kot sledi.
Če želite izračunati najbolje kupiti / prodati par v levi polovici.
Najdi najboljše dobiček, ki ga lahko da, samo s prvim n čez dva dni.
Potem želite oompute najboljši nakup / prodajo par na desni polovici,
Tako je bila nazadnje n čez dva dni.
In sedaj je vprašanje, kako združiti te rešitve spet skupaj?
Ja? (Študent, nerazumljiv)
>> Redu. Torej, naj narišejo sliko.
Ja? (George, nerazumljiv)
>> Točno tako. Rešitev Jurija je ravno prav.
Torej je njegov komentar je prvi izračun najboljše kupiti / prodati par,
in da se pojavlja v levi polovici, tako da recimo, da je levo, levo.
Najboljše kupiti / prodati par, ki se pojavi na desni polovici.
Ampak, če smo le glede teh dveh številk, nam manjka zadeve
če kupujemo in prodajamo tukaj nekje na desni polovici.
Kupimo v levi polovici, prodajajo na desni polovici.
In najboljši način za izračun najboljše kupiti / prodati par, ki se razteza čez obe polovici
je za izračun vsaj tu in izračun najvišje tukaj
in sprejmejo razliko.
Torej dveh primerih, kjer je za nakup / prodajo par pojavlja samo pri nas,
Samo tukaj, ali pa na obeh polovicah je opredeljeno v teh treh številk.
Torej, naš algoritem združiti naše rešitve spet skupaj
želimo izračunati najboljše kupiti / prodati par
če kupimo na levi in ​​prodajajo na desni polovici.
In najboljši način za to, da se za izračun najnižje cene v prvi polovici leta,
najvišja cena na desni polovici, in sprejmejo razliko.
Iz tega izhajajoči dobički 3, te tri številke, si vzemite največ treh,
in to je najboljši dobiček, ki ga lahko v teh prvih dneh in konec.
Tu so pomembni linije so v rdeči barvi.
To je rekurzivni klic za izračun odgovora na levi polovici.
To je rekurzivni klic za izračun odgovora na desni polovici.
Ti dve zanki za izračun min in max na levi in ​​desni pol, v tem zaporedju.
Zdaj sem izračunati dobiček, ki se razteza čez obe polovici,
in končni odgovor je najvišja od teh treh.
Ok.
>> Torej, prepričani, da imamo algoritem, vendar večje vprašanje je,
Kakšna je časovna zahtevnost tega?
In razlog, zakaj sem omenil zlivanjem je, da je ta oblika razdeli odgovor
na dve leti in nato združitev naše rešitve spet skupaj
je ravno oblika vrste spajanja.
Torej, pustite me skozi čas.
Če smo določili funkcijo t (n) je število korakov
n dni,
naši dve rekurzivne klice
se vsako stalo t (n / 2),
in tam je dva od teh razpisov.
Zdaj moram izračunati najmanj levi polovici,
kar lahko storim v n / 2 ure, plus največ desni polovici.
Torej je to samo n.
In potem skupaj z nekaj stalnega dela.
In to ponovitev enačba
je ravno ponovitev enačba za razvrščanje spajanja.
In vsi vemo, da z zlivanjem je n log n čas.
Zato je naš algoritem tudi n log n čas.
Ali to ponovitev smiselno?
Samo kratek ponovno na to:
T (n) je število korakov za izračun največje dobičke
tekom n dneh.
Tako smo razdeljeni naše rekurzivnih klicev
je s pozivom našo rešitev v prvih dneh n / 2,
tako, da je en klic,
in potem spet poklical na drugi polovici.
Torej, to je dva razpisa.
In potem je bil vsaj na levi polovici, kar lahko storimo v linearnem času,
našli največ desni polovici, kar lahko storimo v linearnem času.
Torej n / 2 + n / 2 je le n.
Potem imamo nekaj stalnega dela, ki je, kot počne računanje.
Ta ponovitev enačba je točno ponovitev enačba za razvrščanje spajanja.
Zato je naša shuffle algoritem je tudi n log n.
Torej, koliko prostora smo uporabljate?
Pojdimo nazaj na kodo.
>> Boljše vprašanje je, koliko odvodnikom okvirji ne bomo nikoli imeli v danem trenutku?
Ker smo z uporabo rekurzije,
število sličic dimnika določa našo vesoljsko uporabo.
Vzemimo n = 8.
Pravimo shuffle 8.,
ki bo poklical shuffle o prvih štirih vpisov,
ki bo poklicala shuffle na prvih dveh vnosov.
Torej, naš sklad je - to je naš sklad.
In potem pravimo ponovno shuffle 1,
in to je tisto, kar naša baza zadeva, zato smo se nemudoma vrne.
Ali smo kdaj imeli več kot to veliko odvodnikom okviri?
Število Ker vsakič počnemo invokacijo,
rekurzivna proženje shuffle,
delimo našo velikost na polovico.
Zato je največje število sličic dimnika smo jih kdaj imeli v danem trenutku
je o vrstnem redu okvirjev log n sklad.
Vsak sklad okvir ima stalno prostora,
in zato je skupna količina prostora,
največja količina prostora bomo kdaj uporabiti O (log n) prostor
kjer je n število dni.
>> No, vedno se vprašajte: "Lahko naredimo bolje?"
In predvsem, bomo lahko zmanjšali to težavo, smo že rešili?
Namig: le razpravljal o dveh drugih težav pred tem, in to ne bo shuffle.
Mi lahko pretvorite to težavo na borzi v največjem problemu subarray.
Kako lahko to storimo?
Eden od vas? Emmy?
(Emmy, nerazumljiv)
[Yu] Točno tako.
Torej največjim problemom subarray,
iščemo za znesek nad neprekinjeno subarray.
In komentar Emmy za problem zalog,
preučiti spremembe, ali Delte.
In slika je to - to je cena staleža,
če pa smo razliko med vsakim zaporednim dan -
Tako vidimo, da je najvišja cena, največji dobiček, lahko naredimo
je, če kupite tukaj in prodajajo tukaj.
Toda poglejmo na stalno - poglejmo na subarray problem.
Torej, tukaj lahko naredimo - od tu do tu,
imamo pozitivne spremembe, nato pa bo od tu do tu imamo negativno spremembo.
Ampak potem, bomo od tu do tu imamo veliko pozitivnih sprememb.
In to so spremembe, ki jih želimo, da bi povzeli, da se naš končni izid.
Potem imamo več negativnih sprememb tukaj.
Ključ do zmanjševanju zalog problem v našem največjem problemu subarray
je obravnavati delte med dni.
Tako smo ustvarili novo vrsto, imenovano delte,
inicializirati prvi vstop biti 0,
in potem za vsako delto (i), pustite, da se je razlika
za moje vhod array (i) in polja (i - 1).
Potem smo pokličite naš redni postopek za maksimalno subarray
poteka v nizu Delta je.
In ker je največja subarray je linearen čas,
in to zmanjšanje je ta proces ustvarjanja ta delta niz,
je linearen čas,
Nato je končna rešitev za staleže je O (n) dela ter O (n) dela, je še vedno O (n) dela.
Torej imamo linearno časovno rešitev za naš problem.
Ali vsi razumejo to preobrazbo?
>> Na splošno je dobra ideja, da bi morali vedno imeti
je poskusil zmanjšati nov problem, ki ga vidite.
Če je videti, da poznajo starega problema,
poskusite zmanjšati do starega problema.
In če lahko uporabite vsa orodja, ki ste jih uporabljali na starem problemu
rešiti nov problem.
Torej, da bi sklenil, tehnične pogovore izziv.
Te težave so verjetno nekaj več težkih problemov
, ki jih lahko vidite v intervjuju,
tako da če ne razumeš vseh težav, ki sem zajeti, je že v redu.
To so nekateri od bolj zahtevnih problemov.
Praksa, praksa, praksa.
Dal sem veliko težav v letaka, zato zagotovo preverite jih ven.
In veliko sreče na vaši pogovori. Vsi moji viri so objavljeni na tej povezavi,
in je eden od mojih prijateljev visokih voljo do lažnih tehničnih pogovorov,
Torej, če vas zanima, Will email Yao na ta e-poštni naslov.
Če imate vprašanja, lahko vprašate mene.
Ali vi imate posebna vprašanja, povezana s tehničnimi pogovori
ali kakršne koli težave, ki smo jih videli do sedaj?
Ok. No, veliko sreče na vaši pogovori.
[CS50.TV]