[Powered by Google Translate] [Seminar: Intervista teknike]
[Kenny Yu, Universiteti i Harvardit]
[Kjo është CS50.] [CS50.TV]
Hi everyone, unë jam Kenny. Unë jam aktualisht një i ri studiuar shkenca kompjuterike.
Unë jam një ish CS TF, dhe I wish I kishte kjo, kur unë isha një underclassman,
dhe kjo është arsyeja pse unë jam duke i dhënë në këtë seminar.
Kështu që unë shpresoj që ju të gëzojë atë.
Ky seminar është rreth intervistave teknike,
dhe të gjitha burimet e mia mund të gjendet në këtë lidhje,
kjo lidhje të drejtë këtu, një çift i burimeve.
Kështu që unë bëra një listë të problemeve, në fakt, mjaft disa probleme.
Gjithashtu një gjeneral burimet faqe ku ne mund të gjeni këshilla
se si të përgatiten për një intervistë,
këshilla mbi atë që ju duhet të bëni gjatë një intervistë aktuale,
si dhe se si t'i qasen problemeve dhe burimet për referencë në të ardhmen.
Kjo është e gjitha në internet.
Dhe vetëm për të parathënie këtë seminar, një mohim,
si kjo nuk duhet - përgatitjen tuaj intervistë
nuk duhet të kufizohet në këtë listë.
Kjo është për qëllim vetëm të jetë një udhëzues,
dhe ju duhet patjetër të marrë çdo gjë që unë them me një kokërr kripë,
por të përdorë gjithashtu edhe gjithçka kam përdorur për t'ju ndihmuar në përgatitjen tuaj intervistës.
>> Unë jam duke shkuar për të shpejtuar nëpër slides ardhshme
kështu që ne mund të merrni për studimet e rasteve aktuale.
Struktura e një intervistë për një pozitë inxhinieri software,
zakonisht është 30-45 minuta,
raunde të shumta, në varësi të kompanisë.
Shpesh ju do të kodimit në një bord të bardhë.
Pra, një bord të bardhë si kjo, por shpesh në një shkallë më të vogël.
Nëse ju jeni të paturit e një intervistë telefonike, ju ndoshta do të jetë duke përdorur
ose collabedit ose një Doc Google në mënyrë që ata mund të shohin jetoni coding
ndërkohë që jeni duke u intervistuar mbi telefon.
Një intervistë në vetvete është zakonisht 2 ose 3 probleme
testimin e njohurive shkenca e kompjuterit tuaj.
Dhe kjo do të përfshijë pothuajse patjetër coding.
Llojet e pyetjeve që ju do të shihni zakonisht janë strukturat e të dhënave dhe algoritmet.
Dhe duke bërë këto lloje të problemeve,
ata do të ju pyes, si, çfarë është koha dhe kompleksiteti hapësirë, i madh o?
Shpesh ata kërkojnë edhe më të larta të nivelit të pyetjeve,
kështu, të hartonin një sistem,
si do ta nxjerr kodin tuaj?
Çfarë Interfaces, çfarë klasa, çfarë module keni në sistemin tuaj,
dhe si këta bashkëveprojnë së bashku?
Prandaj të dhënat strukturat dhe algoritme si dhe sistemet projektim.
>> Disa këshilla të përgjithshme para se të zhyten në të studimeve tona të rasteve.
Unë mendoj se rregulli më i rëndësishëm është gjithmonë duke menduar me zë të lartë.
Intervista është menduar të jetë mundësia juaj për të treguar off procesin e të menduarit tuaj.
Pika e intervistës është për intervistuesit për të vlerësuar
si mendoni dhe si ju shkoni nëpër një problem.
Gjëja më e keqe që ju mund të bëni është të jetë i heshtur gjatë gjithë intervistës në tërësi.
Kjo është vetëm nuk është e mirë.
Kur ju jeni të dhënë një pyetje, edhe ju doni të bëni të sigurtë që ju e kuptoni pyetjen.
Pra, përsëris pyetjen përsëri në fjalët tuaja
dhe përpjekje për të punuar plota disa raste të thjeshta provë
për t'u siguruar që ju të kuptoni pyetjen.
Duke punuar përmes një provë disa raste gjithashtu do t'ju japë një intuitë se si për të zgjidhur këtë problem.
Ju mund të zbuloni edhe disa modele pak të ju ndihmojë të zgjidhur problemin.
Tip i tyre i madh është që të mos merrni frustruar.
A nuk merrni frustruar.
Intervistat janë sfiduese, por gjëja më e keqe që ju mund të bëni,
përveç për të qenë i heshtur, duhet të frustruar në mënyrë të dukshme.
Ju nuk duan të japin përshtypjen se në një intervistuesit.
Një gjë që ju - kështu, shumë njerëz, kur ata të shkojnë në një intervistë,
ata përpiqen të përpiqen për të gjetur zgjidhjen më të mirë e parë,
kur me të vërtetë, ka zakonisht një zgjidhje verbim e qartë.
Ajo mund të jetë i ngadalshëm, mund të jetë i paefektshëm, por ju duhet vetëm të deklarojë atë,
vetëm kështu që ju keni një pikënisje nga e cila për të punuar më mirë.
Gjithashtu, duke vënë në dukje zgjidhje është i ngadalshëm, në drejtim të
Kompleksiteti i madh o kohë apo kompleksiteti hapësirë,
do të demonstrojë të intervistuesit se ju e kuptoni
këto çështje kur shkruani kodin.
Pra, mos kini frikë për të dalë me algorithm thjeshtë parë
dhe pastaj të punojnë më mirë nga atje.
Çdo pyetje deri më tani? Rregull.
>> Pra, le të zhyten në problemin tonë të parë.
"Duke pasur parasysh një grup i integers n, shkruani një funksion që lëvizjet array
në vend të tillë që të gjitha permutations e integers n janë njëlloj të mundshme. "
Dhe të supozojmë që ju keni në dispozicion një gjenerator të rastit numër i plotë
që gjeneron një numër të plotë në një varg prej 0 deri i, varg e gjysmë.
A të gjithë e kuptojnë këtë pyetje?
Unë ju jap një rrjet të integers n, dhe unë dua që ju të riorganizimi atë.
Në directory time, kam shkruar disa programe për të demonstruar se çfarë dua të them.
Unë jam duke shkuar për riorganizimi një rrjet prej 20 elementeve,
nga -10 në 9,
dhe unë dua që ju të shkruani një listë si kjo.
Pra, kjo është array renditura im input, dhe unë dua që ju të riorganizimi atë.
Ne do të bëjmë atë përsëri.
A të gjithë e kuptojnë pyetjen? Rregull.
Kështu që është e deri tek ju.
Cilat janë disa ide? Ju mund të bëni atë si n ^ 2, n log n, n?
Hapur për sugjerime.
Rregull. Pra, një ide, sugjeruar nga Emmy,
është parë llogaritur një numër të rastit, integer rastit, në një varg 0-20.
Pra, supozojmë array jonë ka një gjatësi prej 20.
Në diagramin tonë të 20 elementeve,
kjo është koleksion tona input.
Dhe tani, sugjerimi i saj është që të krijojë një rrjet të ri,
kështu që kjo do të jetë array prodhimit.
Dhe në bazë të i kthyer nga rand -
Pra, nëse unë ishte, le të themi, 17,
kopjoni elementin 17 në vendin e parë.
Tani ne kemi nevojë për të fshirë - ne duhet të zhvendoset të gjitha elementet këtu
mbi kështu që ne kemi një boshllëk në fund dhe nuk ka vrima në mes.
Dhe tani ne përsëris procesin.
Tani ne të zgjedhë një numër të plotë të ri të rastit midis 0 dhe 19.
Ne kemi një i ri këtu, dhe ne kopje këtë element në këtë pozitë.
Pastaj ne zhvendoset artikuj mbi dhe ne përsërisin procesin derisa ne kemi të plotë rrjet tonë të ri.
Cila është koha të drejtuar e këtij algoritmi?
E pra, le të marrin në konsideratë ndikimin e kësaj.
Ne jemi zhvendosur çdo element.
Kur ne hiqni këtë unë, ne jemi zhvendosur të gjitha elementet pas atë të majtë.
Dhe që është një (N) kosto O
sepse ajo që në qoftë se ne të hequr elementin e parë?
Kështu që për çdo largim, kemi hequr -
secili heqjen krijon një operacion (n) O,
dhe që ne kemi n removals, kjo çon në një riorganizimi (n ^ 2) O.
Rregull. Pra, fillim i mirë. Fillim i mirë.
>> Një tjetër sugjerim është që të përdorin diçka të njohur si riorganizimi Knuth,
ose Fisher-Jets riorganizimi.
Dhe kjo është në fakt një riorganizimi lineare kohë.
Dhe ideja është shumë e ngjashme.
Përsëri, ne kemi koleksion tonë input,
por në vend të përdorimit të dy vargjeve për input / output tonë,
ne përdorim pjesën e parë të vektorit të mbajnë gjurmët e pjesës sonë riorganizoi,
dhe do të vazhdojmë rrugën, dhe pastaj kemi lënë pjesën tjetër të array tonë për pjesën unshuffled.
Kështu që këtu është ajo që dua të them. Ne nisem me - kemi zgjedhur një i,
një grup 0-20.
Akrep jonë e tanishme është vënë në indeksin e parë.
Ne të zgjedhin disa here i
dhe tani ne bie në ujdi.
Pra, nëse kjo ishte 5 dhe kjo ishte 4,
array rezulton do të ketë 5 këtu dhe 4 here.
Dhe tani ne vërejmë një shënues këtu.
Çdo gjë në të majtë është riorganizoi,
dhe çdo gjë në të djathtë është unshuffled.
Dhe tani ne mund të përsëris procesin.
Ne zgjidhni një indeks të rastit ndërmjet 1 dhe 20 tani.
Pra mendoj tonë të ri i është këtu.
Tani ne këtë shkëmbim i pozitës aktuale me tonë të re këtu.
Pra, ne do të shkëmbejnë një mbrapa dhe me radhë si kjo.
Më lejoni të sjell deri kodin për ta bërë atë më konkret.
Ne fillim me zgjedhjen tonë të I -
ne fillim me i barabartë me 0, ne të zgjedhë një j rastit vendndodhjen
në pjesën unshuffled e vektorit, I te n-1.
Pra, nëse unë jam këtu, zgjidhni një indeks të rastit midis këtu dhe pjesën tjetër të grup,
dhe ne swap.
Kjo është e gjitha kodin e nevojshme për të riorganizimi Array tuaj.
Çdo pyetje?
>> E pra, një pyetje e nevojshme është, pse është kjo e saktë?
Pse është çdo ndryshim në mënyrë të barabartë të ngjarë?
Dhe unë nuk do të shkojnë nëpër provë e kësaj,
por shumë probleme në shkenca kompjuterike mund të provohet me anë të induksionit.
Sa prej jush janë të njohur me induksion?
Rregull. Cool.
Kështu që ju mund të provojë saktësinë e këtij algoritmi me induksion të thjeshtë,
ku hipoteza juaj induksion do të jetë, të supozojmë se
riorganizimi im kthehet çdo ndryshim në mënyrë të barabartë të ngjarë
deri tek elementet parë kam.
Tani, unë e konsiderojnë + 1.
Dhe nga rruga, ne zgjidhni j tonë indeksi të bie në ujdi,
kjo çon në - dhe pastaj ju punojnë jashtë detajet,
të paktën një provë plotë i pse kjo algoritmi kthen
çdo ndërrim me probabilitet të barabartë të mundshme.
>> Të gjithë të drejtë, problemi tjetër.
Pra "jepet një rrjet të integers, postive, zero, negativ,
shkruajnë një funksion që llogarit shumën maksimale
e çdo subarray continueous e array input. "
Një shembull këtu është, në rastin kur të gjithë numrat janë pozitive,
pastaj aktualisht zgjidhja më e mirë është që të marrë array tërë.
1, 2, 3, 4, e barabartë me 10.
Kur ju keni disa negative në atje,
në këtë rast ne duam vetëm dy të parat
sepse zgjedhur -1 dhe / ose do të sjellë shumën -3 tonë poshtë.
Ndonjëherë ne mund të kemi për të filluar në mes të grup.
Ndonjëherë ne duam të zgjidhni asgjë në të gjitha, ajo është e mirë për të mos marrë asgjë.
Dhe nganjëherë kjo është më mirë për të marrë në vjeshtë,
sepse gjëja pasi ajo është super i madh. Pra, ndonjë ide?
(Student, i pakuptueshëm) >> Po.
Mendoj unë nuk do të marrë -1.
Pastaj ose kam zgjedhur 1.000 dhe 20.000,
ose unë vetëm të zgjedhin 3 miliardë.
E pra, zgjidhja më e mirë është që të marrë të gjitha numrat.
Kjo -1, pavarësisht se janë negative,
shuma e tërë është më mirë se unë nuk kanë qenë për të marrë -1.
Pra, një nga këshilla e kam përmendur më herët ishte të shtetit të qartë të dukshme
dhe zgjidhja e brute force parë.
Cila është zgjidhja brute force në këtë problem? Po?
[Jane] E pra, unë mendoj se zgjidhja brutale fuqi
do të jetë për të shtoni deri gjitha kombinimet e mundshme (pakuptueshëm).
[Yu] Okay. Pra, ideja Jane është që të marrë çdo mundur -
Unë jam Konvertime - është që të marrë çdo subarray mundshme të vazhdueshme,
llogaritin shumën e saj, dhe pastaj të marrë maksimumin e të gjitha subarrays mundshme të vazhdueshme.
Çfarë identifikon në mënyrë unike një subarray në grup tim input?
Si, çka dy gjëra nuk kam nevojë? Po?
(Student, i pakuptueshëm) E drejta. >>
Një ulët i detyruar në indeksin dhe një indeksi sipërme të lidhur
unike përcakton një subarray vazhdueshme.
[Student Femër] A kemi vlerësuar se është një grup i numrave unik?
[Yu] Nr Pra, pyetjes së saj është, jemi duke supozuar koleksion tonë -
është array tonë të gjithë numrat unik, dhe përgjigja është jo.
>> Nëse ne përdorim zgjidhje tonë shtazë fuqi, atëherë në fillim / fund indekset
unike përcakton subarray tonë të vazhdueshme.
Pra, nëse ne iterate për të gjitha shënimet e fillimit të mundshme,
dhe për të gjitha shënimet në fund të> ose = për të filluar, dhe <n,
ju llogaritin shumën, dhe pastaj ne kemi marrë shumën maksimale që kemi parë deri më tani.
A është kjo e qartë?
Çfarë është O e madhe e kësaj zgjidhjeje?
Timewise.
Jo mjaft n ^ 2.
Vini re se ne iterate nga 0 deri n,
kështu që është një për lak.
Ne iterate përsëri nga pothuajse për fillimin deri në fund, një tjetër për lak.
Dhe tani, në kuadër të kësaj, ne kemi për të përmbledhur çdo hyrje,
kështu që është një tjetër për lak. Pra, ne kemi tre mbivendosur për sythe, n ^ 3.
Rregull. Kjo shkon si një pikë fillimi.
Zgjidhja jonë nuk është më e keqe se n ^ 3.
A të gjithë e kuptojnë zgjidhje shtazë fuqi?
>> Rregull. Një zgjidhje më të mirë është duke përdorur një ide të quajtur programimi dinamik.
Nëse ju merrni CS124, e cila është Algoritmet dhe strukturat të dhënave,
ju do të bëhet shumë i njohur me këtë teknikë.
Dhe ideja është, do të përpiqen për të ndërtuar zgjidhje për problemet më të vogla të parë.
Çfarë dua të them me këtë është, ne aktualisht duhet të shqetësohen për dy gjëra: e fillimit dhe në fund.
Dhe kjo është i bezdisshëm. Çfarë ndodh nëse ne mund të shpëtoj nga një prej këtyre parametrave?
Një ide është që të - we're dhënë problemi ynë origjinal,
gjeni shumën maksimale të çdo subarray në një gamë [O, n-1].
Dhe tani ne kemi një subproblem ri, ku ne e dimë, në indeksin tonë të tanishëm i,
ne e dimë ne duhet të konkludojmë atje. Subarray jonë duhet të përfundojë në indeksin aktual.
Pra, problemi mbetur është, ku ne duhet të fillojë subarray tonë?
A ka kjo kuptim? Rregull.
Kështu që unë kam koduar këtë ide, dhe le të shohim se çfarë kjo do të thotë.
Në codirectory, ka një program të quajtur subarray,
dhe kjo merr numrin e artikujve,
dhe ai kthen shumën maksimale subarray në listën time riorganizoi.
Pra, në këtë rast, subarray tonë maksimal është 3.
Dhe kjo është marrë nga vetëm duke përdorur 2 dhe 1.
Le të drejtuar atë përsëri. Është gjithashtu 3.
Por këtë herë, vini re se si kemi marrë 3.
Ne mori - ne vetëm të marrë 3 vetë
sepse ajo është e rrethuar nga negative në të dyja anët,
e cila do të sjellë një shumë të <3.
Le të kandidojë në 10 objekte.
Këtë herë ajo është 7, ne kemi marrë 3 dhe 4 udhëheqës.
Këtë herë ajo është 8, dhe ne kemi marrë se duke marrë 1, 4 dhe 3.
Pra, për të ju jap një intuitë se si ne mund të zgjidhur këtë problem transformuar,
le të marrin një vështrim në këtë subarray.
Ne jemi duke i dhënë këtë koleksion input, dhe ne e dimë se përgjigja është 8.
Ne kemi marrë 1, 4, dhe 3.
Por le të shohim se si ne fakt mori atë përgjigje.
Le të shikojmë në subarray maksimal që përfundoi në secilin prej këtyre treguesve.
Çfarë është subarray maksimal që duhet të përfundojë në pozitën e parë?
[Student] zero. Zero >>. Vetëm mos të marrë -5.
Këtu ajo do të jetë 0 si. Po?
(, Student i pakuptueshëm)
[Yu] Oh, më vjen keq, kjo është një -3.
Kështu kjo është një 2, kjo është një -3.
Rregull. Pra -4, çfarë është subarray maksimal për t'i dhënë fund atë pozitë
ku -4 është në? Zero.
Një? 1, 5, 8.
Tani, unë duhet të përfundojë në vendin ku është në -2.
Kështu 6, 5, 7, dhe e fundit është 4.
Duke ditur se këto janë shënimet e mia
për problemin e transformuar, ku unë duhet të përfundojë në secilin prej këtyre indekseve,
atëherë përgjigjja ime përfundimtare është vetëm, të marrë një spastrim të gjithë,
dhe për të marrë numrin maksimal.
Kështu që në këtë rast është 8.
Kjo nënkupton që subarray maksimal përfundon në këtë indeks,
dhe ka filluar diku para tij.
A të gjithë e kuptojnë këtë subarray transformuar?
>> Rregull. E pra, le të kuptoj se për këtë përsëritje.
Le të konsiderojmë vetëm shënimet e para.
Kështu këtu ajo ishte 0, 0, 0, 1, 5, 8.
Dhe pastaj ka pasur një -2 këtu, dhe që e solli atë deri në 6.
Pra, nëse unë e quaj hyrja në pozicionin i subproblem (i),
si mund ta përdorin përgjigje për një subproblem mëparshme
për t'iu përgjigjur kësaj subproblem?
Nëse unë të shikoni në, le të themi, kjo hyrje.
Si mund të llogaritin përgjigje 6 duke shikuar në
një kombinim i këtij grup dhe përgjigjet ndaj subproblems mëparshme në këtë grup? Po?
[Student Femër] Ju merrni rrjet të shumave
në pozitë të drejtë para tij, kështu që 8,
dhe pastaj ju shtoni subproblem aktuale.
[Yu] Pra sugjerimi i saj është që të shikojmë në këto dy numra,
ky numër dhe ky numër.
Kështu kjo 8 referohet përgjigjes për subproblem (I - 1).
Dhe le të thërrasë A. array time input
Në mënyrë që të gjeni një subarray maksimal që përfundon në pozitën unë,
Unë kam dy zgjedhje: ose unë mund të vazhdojë subarray
që përfundoi në indeksin e mëparshme, apo të fillojë një koleksion të ri.
Nëse unë do të vazhdojë subarray që filloi në indeksin e mëparshme,
atëherë shuma maksimale që unë mund të arrijë është përgjigje për subproblem mëparshme
plus hyrja aktuale array.
Por, unë gjithashtu kanë zgjedhjen e fillimit të një subarray ri,
në të cilin rast shuma është 0.
Pra përgjigja është max e 0, subproblem i - 1, plus hyrja aktuale array.
Përsëritja e bën këtë kuptim?
Përsëritja jonë, si ne vetëm zbuluar, është i subproblem
është e barabartë me maksimumin e mëparshme subproblem plus hyrje aktual array tim,
që do të thotë të vazhdojë subarray mëparshme,
ose 0, të fillojë një subarray ri në indeksin tim aktual.
Dhe një herë ne kemi ndërtuar këtë tryezë të zgjidhjeve, atëherë përgjigjja jonë përfundimtare,
vetëm të bëjë një spastrim lineare përgjatë array subproblem
dhe për të marrë numrin maksimal.
Kjo është një zbatim i saktë i asaj që unë sapo thashë.
Pra, ne kemi krijuar një koleksion të ri subproblem, subproblems.
Hyrja e parë është ose 0 ose hyrja e parë, maksimale e atyre dyjave.
Dhe për pjesën tjetër të subproblems
ne përdorim përsëritjen e saktë kemi vetëm zbuluar.
Tani kemi llogaritur maksimumin e subproblems array tonë, dhe kjo është përgjigjja jonë përfundimtare.
>> Pra, sa hapësirë ​​jemi duke përdorur në këtë algorithm?
Nëse ju keni marrë vetëm CS50, atëherë ju nuk mund të ketë hapësirë ​​diskutuar shumë.
E pra, një gjë të theksohet është se unë quhet malloc këtu me madhësi n.
Çfarë do të sugjerojnë për ju?
Kjo algorithm përdor hapësirë ​​lineare.
Mund të bëjmë më mirë?
A ka ndonjë gjë që ju vini re se është e panevojshme për të llogaritur përgjigjen përfundimtare?
I guess një pyetje më e mirë është, çfarë informacioni
nuk kemi nevojë për të kryer gjatë gjithë rrugës deri në fund?
Tani, nëse ne shikojmë në këto dy linja,
ne vetëm kujdesen për subproblem mëparshëm,
dhe ne vetëm kujdesen për maksimumin që kemi parë ndonjëherë deri më tani.
Për të llogaritur përgjigjen tonë final, ne nuk kemi nevojë array tërë.
Ne duhet vetëm numrin e fundit, zgjasin dy numra.
Numri i fundit për grup subproblem, dhe numri i fundit për maksimum.
Pra, në fakt, ne mund të bashkohen këto sythe së bashku
dhe shkoni nga hapësira lineare në hapësirë ​​të vazhdueshme.
Shuma aktuale deri më tani, këtu, zëvendëson rolin e subproblem, array tonë subproblem.
Pra shuma aktuale, deri më tani, është përgjigje për subproblem mëparshëm.
Dhe se shuma, deri më tani, merr vendin e max tonë.
Ne llogaritur maksimumin si ne të shkojnë së bashku.
Dhe kështu ne do të shkojmë nga hapësira lineare në hapësirë ​​të vazhdueshme,
dhe ne gjithashtu kemi një zgjidhje për problemin tonë lineare subarray.
>> Këto lloje të pyetjeve që ju do të merrni gjatë një interviste.
Çfarë është kompleksiteti koha, çfarë është kompleksiteti hapësirë?
Ju mund të bëni më mirë? A ka gjëra që janë të panevojshme për të mbajtur rreth?
Unë e bëri këtë për analizat që ju duhet të marrë në tuaj
si ju jeni duke punuar me këto probleme.
Gjithmonë të jetë pyetur veten, "A mund të bëj më mirë?"
Në fakt, mund të bëjmë më mirë se kjo?
Lloj i një pyetje mashtrim. Ju nuk mund të, sepse keni nevojë për të
te pakten lexoni dhëna për problemin.
Pra, fakti që ju duhet të paktën të lexojnë të dhëna të problemit
do të thotë se ju nuk mund të bëni më mirë se koha lineare,
dhe ju nuk mund të bëni më mirë se hapësirë ​​të vazhdueshme.
Pra, kjo është, në fakt, zgjidhja më e mirë për këtë problem.
Pyetje? Rregull.
>> Stock market problem:
"Duke pasur parasysh një grup i integers N, pozitive, zero, ose negativ,
që përfaqësojnë çmimin e aksioneve gjatë ditëve n,
shkruajnë një funksion për të llogaritur fitimin maksimal që ju mund të bëni
duke qenë se ju blerë dhe shitur saktësisht 1 aksioneve brenda këtyre ditëve n. "
Në thelb, ne duam të blerë të ulët, të shesë të lartë.
Dhe ne duam që të kuptoj se e fitimit më të mirë ne mund të bëjë.
Going back to majë tim, ajo është menjëherë e qartë, përgjigja më e thjeshtë, por është e ngadaltë?
Po? (Student, i pakuptueshëm) >> Po.
Pra, ju do >> të shkoni vetëm dhe pse të shikojmë në çmimet e aksioneve
në çdo pikë në kohë, (pakuptueshëm).
[Yu] Mirë, kështu që zgjidhja e saj - sugjerimin e saj e informatikes
të ulët dhe informatikë të lartë nuk do të punojë
sepse mund të ndodhë para se të më të ulët.
Pra, çfarë është zgjidhja brute force për këtë problem?
Cilat janë dy gjëra që unë duhet të unike të përcaktuar fitimin kam bërë? Drejtë.
Zgjidhja brute force është - oh, kështu që, sugjerimi Gjergjit është që ne duhet vetëm dy ditë
për të përcaktuar unike fitimin e këtyre dy ditëve.
Pra, ne llogaritin çdo palë, si të blerë / shitur,
llogaritur fitimin, i cili mund të jetë pozitiv ose negativ ose zero.
Llogaritur fitimin maksimal që kemi bërë pas iterating mbi të gjitha palë ditë.
Kjo do të jetë përgjigjja jonë përfundimtare.
Dhe se zgjidhja do të jetë në O (n ^ 2), për shkak se ka n zgjedh dy çifte -
e ditëve që ju mund të zgjidhni në mes të ditëve të fundit.
Mirë, kështu që unë nuk jam duke shkuar për të shkuar mbi zgjidhjen e forcës brutale këtu.
Unë jam duke shkuar për të ju them se ka një n log n zgjidhje.
Çfarë algoritmi ju momentalisht e dini se është n log n?
Kjo nuk është një pyetje mashtrim.
>> Merge lloj. Merge lloj është n log n,
dhe në fakt, një mënyrë për të zgjidhur këtë problem është që të përdorin
një lloj lloj bashkojë të idesë quajtur, në përgjithësi, përça dhe sundo.
Dhe ideja është si vijon.
Ju dëshironi për të llogaritur mirë të blej / shitur palë në gjysmën e majtë.
Gjej fitim të mirë që ju mund të bëni, vetëm me n e parë mbi dy ditësh.
Pastaj ju doni të oompute mirë të blej / shitur palë në gjysmën e djathtë,
kështu që n fundit gjatë dy ditëve.
Dhe tani pyetja është, si nuk kemi bashkojë këto zgjidhje përsëri së bashku?
Po? (, Student i pakuptueshëm)
Mirë >>. Pra më lejoni të nxjerrë një foto.
Po? (George, i pakuptueshëm)
Pikërisht >>. Zgjidhja Gjergjit është saktësisht e drejtë.
Pra sugjerimi i tij është, së pari të llogaritur mirë palë Blej / Shes,
dhe që ndodh në gjysmën e majtë, kështu që le ta quajmë se majtë, u largua.
Më të mirë të blerë / shitur palë që ndodh në gjysmën e duhur.
Por në qoftë se ne krahasim me vetëm këto dy numra, ne jemi të humbur rastin
ku kemi blerë dhe shitur këtu diku në gjysmën e duhur.
Ne blerë në gjysmën e majtë, të shitur në gjysmën e duhur.
Dhe mënyra më e mirë për të llogaritur mirë palë Blej / Shes që përfshin të dy gjysmave
është për të llogaritur minimumin këtu dhe llogaritur maksimumin këtu
dhe për të marrë diferencën e tyre.
Kështu të dy rastet ku Blej / Shes palë ndodh vetëm këtu,
vetëm këtu, apo në të dy gjysmave është përcaktuar nga këto tre numra.
Pra algorithm tonë të bashkojë zgjidhjet tona përsëri së bashku,
ne duam të llogaritur mirë palë Blej / Shes
ku kemi blerë në gjysmën e majtë dhe të shitur në gjysmën e djathtë.
Dhe mënyra më e mirë për të bërë këtë është për të llogaritur çmimin më të ulët në gjysmën e parë,
çmimi më i lartë në gjysmën e duhur, dhe për të marrë diferencën e tyre.
Rezultojnë me tre fitimet, këto tre numra, ju merrni maksimumin e tre,
dhe kjo është fitimi më i mirë që ju mund të bëni mbi këto ditët e para dhe në fund.
Këtu linja të rëndësishme janë në të kuqe.
Kjo është një thirrje rekursive për të llogaritur përgjigjen në gjysmën e majtë.
Kjo është një thirrje rekursive për të llogaritur përgjigjen në gjysmën e duhur.
Këto dy sythe për të llogaritur min dhe max në gjysmën e majtë dhe të djathtë, respektivisht.
Tani unë llogaris fitimin që përfshin të dy gjysmave,
dhe përgjigja përfundimtare është maksimumi i këtyre tre.
Rregull.
>> Pra, i sigurt, ne kemi një algoritëm, por pyetja e madhe është,
çfarë është kompleksiteti koha e kjo?
Dhe arsyeja pse kam përmendur lloj bashkojë është se kjo formë e ndajnë përgjigje
në dy dhe pastaj bashkimi zgjidhjet tona përsëri së bashku
është pikërisht forma e lloj bashkohen.
Pra më lejoni të shkoj nëpër kohëzgjatje.
Nëse ne definuar një funksion t (n) të jetë numri i hapave
për ditë n,
thirrje dy tona gjithkund rekursive
janë secili do të kushtojë t (n / 2),
dhe ka dy këtyre thirrjeve.
Tani kam nevojë për të llogaritur minimumin e gjysmës së majtë,
që unë mund të bëjë në të n / 2 kohë, plus maksimum prej gjysmës së djathtë.
Pra, kjo është vetëm n.
Dhe pastaj plus disa punë të vazhdueshme.
Dhe ky ekuacion përsëritje
është pikërisht përsëritje ekuacioni për lloj bashkohen.
Dhe ne të gjithë e dimë se lloj bashkojë është log n n kohë.
Prandaj, algorithm tonë është gjithashtu n log n kohë.
A ka kjo përsëritje kuptim?
Vetëm një radhitje të shkurtër të kësaj:
T (n) është numri i hapave për të llogaritur fitimin maksimal
gjatë ditëve n.
Mënyra se si ndahet thirrjet tona gjithkund rekursive
është duke bërë thirrje zgjidhje tonë në ditët e para n / 2,
kështu që është një thirrje,
dhe pastaj ne e quajmë përsëri në gjysmën e dytë.
Pra, kjo është dy telefonata.
Dhe atëherë ne gjejmë një minimum në gjysmën e majtë, të cilat ne mund të bëjmë në kohë lineare,
gjeni maksimumin e gjysmës së djathtë, të cilat ne mund të bëjmë në kohë lineare.
Pra, n / 2 + n / 2 është vetëm n.
Pastaj ne kemi disa punë të vazhdueshme, e cila është bërë si aritmetikë.
Ky ekuacion është pikërisht përsëritje ekuacioni për përsëritje lloj bashkohen.
Prandaj, algorithm tonë riorganizimi është gjithashtu n log n.
Pra, sa hapësirë ​​jemi duke përdorur?
Le të kthehemi në kodin.
>> Një pyetje më e mirë është, sa korniza rafte nuk kemi ndonjëherë kanë në çdo moment të caktuar?
Që ne jemi duke përdorur recursion,
numri i kornizave rafte përcakton përdorimin tonë hapësirë.
Le të konsiderojmë n = 8.
Ne e quajmë riorganizim më 8,
e cila do të thërrasë riorganizimi në katër shënimet e parë,
e cila do të thërrasë një riorganizim në të dy shënimet e para.
Pra, rafte ynë është - kjo është rafte tonë.
Dhe pastaj ne e quajmë riorganizim përsëri në 1,
dhe kjo është ajo që rasti ynë bazë është, kështu që ne të kthehet menjëherë.
A kemi ndonjëherë kanë më shumë se kjo rafte korniza shumë?
Nr Sepse çdo herë që ne bëjmë një risi,
një thirrje e muzës recursive për të riorganizimi,
ne ndarje madhësinë tonë në gjysmën e saj.
Pra, numri maksimal i kornizave rafte ne ndonjëherë kemi në çdo moment të caktuar
është në mënyrë të log n rafte korniza.
Çdo kornizë pirg ka hapësirë ​​të vazhdueshëm,
dhe prandaj shuma e përgjithshme e hapësirës,
shuma maksimale e hapësirës ne ndonjëherë përdorin është O (log n) hapësirë
ku n është numri i ditëve.
>> Tani, gjithmonë të pyesni veten, "A mund të bëjmë më mirë?"
Dhe në veçanti, mund të zvogëlojë këtë për një problem që ne kemi zgjidhur tashmë?
Një aluzion: ne vetëm dy diskutuan probleme të tjera para kësaj, dhe kjo nuk do të jetë riorganizimi.
Ne mund të konvertohet në këtë problem të tregut të aksioneve në problemin subarray maksimal.
Si mund ta bëjë këtë?
Njëri prej jush? Emmy?
(Emmy, i pakuptueshëm)
[Yu] Pikërisht.
Pra, problemi maksimal subarray,
ne jemi duke kërkuar për një shumë mbi një subarray vazhdueshme.
Emmy dhe sugjerim për problemin rezervave,
konsideratë ndryshimet, ose deltat.
Dhe një foto e kjo është - kjo është çmimi i një gjendje,
por në qoftë se ne e mori dallimin në mes të çdo dite radhazi -
kështu ne shohim se çmimi maksimal, fitimi maksimal ne mund të bëjë
është nëse kemi blerë këtu dhe shesin këtu.
Por le të shohim në të vazhdueshëm - le të shohim problemin subarray.
Kështu që këtu, ne mund të bëjë - duke shkuar nga këtu për këtu,
ne kemi një ndryshim pozitiv, dhe pastaj duke shkuar nga këtu për këtu kemi një ndryshim negativ.
Por atëherë, duke shkuar nga këtu që këtu kemi një ndryshim të madh pozitiv.
Dhe këto janë ndryshimet që ne duam të përmbledhur për të marrë fitim tonë përfundimtar.
Pastaj kemi ndryshime më negativ këtu.
Çelësi për të zvogëluar problemin e aksioneve në problemin tonë maksimal subarray
është që të marrë në konsideratë deltat mes ditë.
Pra, ne kemi krijuar një koleksion të ri të quajtur Deltat,
nisja hyrjen e parë të jetë 0,
dhe pastaj për secilin delta (I), le që të jetë ndryshimi
i grup im dhëna (I), dhe grup (I - 1).
Pastaj ne e quajmë procedurë rutinë tonë për një subarray maksimal
kalimin në grup një delta-së.
Dhe për shkak se subarray maksimal është koha lineare,
dhe ky reduktim, ky proces i krijimit të kësaj grup delta,
Është gjithashtu koha lineare,
atëherë zgjidhja përfundimtare për rezervat është O (n) plus o puna (n) të punës, është ende O (n) të punës.
Pra, ne kemi një zgjidhje lineare kohë për problemin tonë.
A e kuptojnë të gjithë këtë transformim?
>> Në përgjithësi, një ide e mirë që ju duhet të keni gjithmonë
po përpiqen për të reduktuar një problem të ri që ju jeni duke parë.
Në qoftë se kjo duket e njohur për një problem të vjetër,
përpiqen reduktuar atë në një problem të vjetër.
Dhe në qoftë se ju mund të përdorni të gjitha mjetet që ju keni përdorur në problemin e vjetër
për të zgjidhur problemin e ri.
Pra, për të përfunduar, intervista teknike janë sfiduese.
Këto probleme janë ndoshta disa nga problemet më të vështira
që ju mund të shihni në një intervistë,
kështu që nëse ju nuk e kuptoni të gjitha problemet që kam mbuluar vetëm, kjo është në rregull.
Këto janë disa nga problemet më sfiduese.
Praktikë, praktikë, praktikë.
I dha një shumë problemeve në prospekt, kështu që patjetër të kontrolloni ato jashtë.
Dhe fat të mirë në intervistat tuaja. Të gjitha burimet e mia janë postuar në këtë link,
dhe një nga miqtë e mi të lartë ka ofruar për të bërë intervista tallen teknike,
kështu që nëse ju jeni të interesuar, email Will Yao në atë adresë e-mail.
Nëse keni ndonjë pyetje, ju mund të pyesni mua.
A ju djema keni pyetje specifike në lidhje me intervistat teknike
apo ndonjë problem që ne kemi parë deri më tani?
Rregull. E pra, fat të mirë në intervistat tuaja.
[CS50.TV]