[Powered by Google Translate] [Seminar: Tæknilegar Viðtöl] [Kenny Yu, Harvard University] [Þetta er CS50.] [CS50.TV] Hæ allir, ég er Kenny. Ég er nú yngri læra tölvunarfræði. Ég er fyrrverandi CS TF, og ég vildi að ég hefði þetta þegar ég var underclassman, og það er hvers vegna ég er að gefa þetta námskeið. Svo ég vona að þú njótir þess. Þetta námskeið er um tæknilega viðtölum, og allar auðlindir mínar er hægt að finna á þessum tengli, á þennan tengil hérna, a par af auðlindum. Þannig að ég gerði lista yfir vandamál, reyndar alveg nokkur vandamál. Einnig almenn auðlindir síðu þar sem við getum fundið ábendingar um hvernig á að undirbúa sig fyrir viðtalið, ábendingar um hvað þú átt að gera á meðan á raunverulegum viðtali, og hvernig á að nálgast vandamál og úrræði til hliðsjónar í framtíðinni. Það er allt á netinu. Og bara til að formála þetta námskeið, sem skilmála eins og það ætti ekki - viðtal undirbúning þinn ætti ekki að takmarkast við þennan lista. Þetta er einungis ætlað að vera handbók, og þú ættir örugglega að taka allt sem ég segi með korn af salti, en einnig nota allt sem ég nota til að hjálpa þér í undirbúningi viðtalið. 

Ég ætla að hraða í gegnum næstu skyggnur svo við getum fengið að raunverulegum dæmum. Uppbygging á viðtali fyrir verkfræði hugbúnaður postion, yfirleitt er það 30 til 45 mínútur, margar umferðir, eftir því hvaða fyrirtæki. Oft þú munt vera kóðun á hvítum borð. Svo hvítt borð eins og þetta, en oft á minni skala. Ef þú ert með síma viðtal, munt þú sennilega vera með annaðhvort collabedit eða Google Doc svo þeir geti séð þú býrð erfðaskrá meðan þú ert í viðtali í gegnum síma. An Viðtalið sjálft er oftast 2 eða 3 vandamál próf tölvunarfræði þekkingu þína. Og það verður nánast örugglega taka erfðaskrá. Þær tegundir af spurningum sem þú munt sjá eru yfirleitt gögn uppbygging og reiknirit. Og í að gera þessar tegundir af vandamál, Þeir munu spyrja þig, eins og, það er tími og rúm flókið, stórt O? Oft þeir spyrja líka hærri stigi spurningar, svo, að hanna kerfi, hvernig myndir þú leggja út númerið þitt? Hvaða tengi, hvaða flokkar, hvaða einingar ertu með í vélinni þinni, og hvernig þær virka saman? Svo gögn uppbygging og reiknirit eins og heilbrigður eins og hanna kerfi. 

Nokkrar almennar ábendingar áður en við kafa inn í dæmisögur okkar. Ég held að mikilvægasta reglan er alltaf að hugsa upphátt. Viðtalið á að vera tækifæri til að láta hugsun aðferð. Tilgangur viðtalsins er að spyrjandi að meta hvernig þér finnst og hvernig þú ferð í gegnum vandamál. Það versta sem þú getur gert er að þegja um allt viðtalið. Það er bara ekki gott. Þegar þú færð spurningu, vilt þú einnig að ganga úr skugga um að þú skiljir spurninguna. Svo endurtaka spurninguna til baka í eigin orðum og reyna að vinna ítarlegar nokkrum einföldum tilvikum próf til að ganga úr skugga um að þú skiljir spurninguna. Vinna með nokkrum tilvikum próf mun einnig gefa þér innsæi um hvernig á að leysa þetta vandamál. Þú gætir jafnvel uppgötva nokkrar mynstur til að hjálpa þér að leysa vandamál. Stór ábending þeirra er að ekki fá svekktur. Ekki fá svekktur. Viðtöl eru krefjandi, en það versta sem þú getur gert, auk þess að vera þögul, er að sýnilega svekktur. Þú vilt ekki að gefa því kynna til viðmælanda. Einn hlutur sem þú - svo margir, þegar þeir fara í viðtal, þeir reyna að reyna að finna bestu lausn fyrst, þegar í raun, það er yfirleitt glaringly augljós lausn. Það gæti verið hægt, gæti verið óhagkvæm, en þú ættir bara að koma fram það, bara svo þú hafa a upphafsstaður þar sem að vinna betur. Einnig að benda á lausn er hægur, með tilliti til stór O tími flókið eða rúm flókið, mun sýna að spyrjandi að þú skiljir þessi mál þegar þú skrifar kóðann. Svo ekki vera hræddur við að koma upp með einföldustu reiknirit fyrst og þá vinna betur þaðan. Einhverjar spurningar svo langt? Allt í lagi. 

Svo við skulum kafa í fyrsta vandamál okkar. "Í ljósi fylki með n heiltalna, skrifa fall sem stokkar array í stað þannig að allir permutations í N heiltölur eru jafn líklegt. " Og ráð fyrir að þú ert í boði handahófi heiltala rafall sem býr heiltölu á bilinu frá 0 til i, hálf svið. Þurfa allir að skilja þessa spurningu? Ég gef þér fjölda n heiltalna, og ég vil að þú að stokka það. Í skrá minn, skrifaði ég nokkur forrit til að sýna hvað ég meina. Ég ætla að uppstokkun fylki af 20 þáttum, úr -10 í +9, og ég vil að þú að framleiðsla á lista eins og þetta. Svo er þetta raðað inntak array minn, og ég vil að þú að stokka það. Við munum gera það aftur. Þurfa allir að skilja spurninguna? Allt í lagi. Svo það er komið að þér. Hvað eru nokkrar hugmyndir? Getur þú gert það eins og n ^ 2, n log n, n? Opinn fyrir öllu. Allt í lagi. Svo ein hugmynd, leiðbeinandi við Emmy, er fyrst reikna með handahófi númer, handahófi heiltala í bilinu 0-20. Svo ráð array okkar hefur lengd 20. Í myndinni okkar 20 þáttum, þetta er inntak array okkar. Og nú, tillaga hennar er að búa til nýjan array, þannig að þetta verður framleiðsla array. Og byggt á ég aftur eftir Rand - þannig að ef ég væri, segjum, 17, afrita 17. þáttur í fyrstu stöðu. Nú þurfum við að eyða - við þurfum að skipta á alla þætti hér yfir svo að við höfum bilið aftast og engin göt í miðju. Og nú erum við að endurtaka ferlið. Nú erum við að velja nýtt handahófi tala á milli 0 og 19. Við höfum nýtt ég hér, og við afrita þessa hluti í þessari stöðu. Þá erum við að skipta hlutum lokið og endurtaka ferlið þar til við höfum fulla new Array okkar. Hver er að keyra þegar þetta reiknirit? Jæja, við skulum íhuga áhrif þetta. Við erum að breytast í hvert frumefni. Þegar við fjarlægja þetta ég, við erum að breytast alla þætti eftir það til vinstri. Og það er O (n) kostnaður því hvað ef við fjarlægja fyrsta frumefni? Svo fyrir hvern flutningur, fjarlægja við - hver flutningur incurs O (n) til starfa, og þar sem við höfum n brottflutnings, þetta leiðir til O (n ^ 2) uppstokkun. Allt í lagi. Svo góð byrjun. Góð byrjun. 

Önnur tillaga er að nota eitthvað sem kallast Knuth rimmu, eða Fisher-Yates uppstokkun. Og það er í raun línuleg tími uppstokkun. Og hugmyndin er mjög svipuð. Aftur höfum við inntak array okkar, en í stað þess að nota tvö fylki fyrir hjálpina okkar / úttak, notum við fyrsta hluta fylkisins til að halda utan um stokkuð hluta okkar, og við höldum utan, og þá erum við að láta restina af array okkar fyrir unshuffled hluta. Svo hér er það sem ég meina. Við byrjum burt með - við veljum að ég, fylki 0-20. Núverandi músina okkar er að benda á fyrstu vísitölunni. Við valið nokkrar i hér og nú erum við að skipta. Þannig að ef þetta var 5 og þetta var 4, leiðir array verður 5 hér og 4 hér. Og nú erum við í huga að merki hér. Allt til vinstri er stokkuð, og allt til hægri er unshuffled. Og nú getum við að endurtaka ferlið. Við valið af handahófi vísitölu milli 1 og 20 núna. Svo ætla nýtt okkar ég er hér. Nú erum við að skipta þessu i við núverandi nýja stöðu okkar hér. Þannig að við að skipta fram og til baka eins og þetta. Leyfðu mér að koma upp kóða til að gera það steypu meira. Við byrjum með vali okkar á i - við að byrja með ég jafngilda 0, velja við handahófi staðsetningu J í unshuffled hluta fylkisins, til i n-1. Svo ef ég er hér, valið af handahófi vísitölu milli hér og annars staðar í fylkinu, og við skipta. Þetta er allur kóðinn þarf að stokka Array þínu. Einhverjar spurningar? 

Jæja, einn þarf spurningin er, hvers vegna er þetta rétt? Hvers vegna er hvert permutation jafn líklegt? Og ég mun ekki fara í gegnum sönnun af þessu, en mörg vandamál í tölvunarfræði getur verið sannað með innleiðingu. Hversu margir af þú ert kunnuglegur með að framkalla? Allt í lagi. Cool. Svo er hægt að sanna réttmæti þessa reiknirit með einföldu örvun, þar framkalla tilgáta þín væri gert ráð fyrir að uppstokkun minn skilar hvert permutation jafn líklegt upp fyrstu þætti i. Nú tel ég + 1. Og eftir því hvernig við veljum vísitölu J okkar að skipta, þetta leiðir til - og þá vinna út upplýsingar, að minnsta kosti full sönnun á því hvers vegna þetta reiknirit skilar hvert permutation með jafn líklegt líkum. 

Allt í lagi, næsta vandamál. Svo "gefið fjölda heiltalna, postive, núll, neikvæð, Skrifið fall sem reiknar hámarks fjárhæð hvaða continueous subarray inntak fylkisins. " Dæmi hér um er að ræða þar sem allir tölur eru jákvæðar, þá nú er besti kosturinn til að taka allt array. 1, 2, 3, 4, jafngildir 10. Þegar þú hefur nokkrar filmur þar, í þessu tilfelli sem við viljum bara fyrstu tveimur því að velja -1 og / eða -3 mun koma summan okkar niður. Stundum við gætum þurft að byrja í miðju fylkisins. Stundum viljum við að velja ekki neitt, það er best að ekki taka neitt. Og stundum er það betra að taka haust því málið eftir að það er frábær stór. Svo einhverjar hugmyndir? (Nemandi, óskiljanlegur) >> Já. Segjum að ég á ekki að taka -1. Þá annaðhvort ég velja 1.000 og 20.000, eða ég valið bara 3 milljarðar. Jæja, besti kosturinn er að taka allar tölur. Þetta -1, þrátt fyrir að vera neikvæð, allt sum er betra en þar sem ég ekki að taka -1. Svo ein af þeim ábendingum sem ég nefndi áðan var að koma fram skýrt augljóst og skepna afl lausn fyrst. Hvað er skepna afl lausn á þessu vandamáli? Já? [Jane] Jæja, ég held að skepna afl lausn væri að bæta upp allar mögulegar samsetningar (óskiljanlegur). [Yu] lagi. Svo er hugmynd Jane að taka allar mögulegar - Ég er paraphrasing - er að taka öll möguleg samfelld subarray, reikna fjárhæð hennar, og síðan taka allt af öllum mögulegum samfellt subarrays. Hvað skilgreinir einstaklega a subarray í array inntak mínu? Eins, hvað tvennt þarf ég? Já? (Nemandi, óskiljanlegur) >> Right. A lægri bundinn við vísitölu og efri vísitölu einstaklega ákvarðar samfellt subarray. [Kvenkyns nemandi] Erum við að meta það fylki einstaka tölur? [Yu] Nei Svo spurningunni sinni er, erum við ráð array okkar - er array okkar öll einstök númer, og svarið er nei. 

Ef við notum skepna afl lausn okkar, þá byrja / enda vísitölur einstaklega ákvarðar samfellt subarray okkar. Svo ef við iterate fyrir allar mögulegar færslur byrjun, og fyrir alla enda færslur> eða = að byrja, og <n, þú reikna summu, og þá erum við að taka hámarks upphæð sem við höfum séð hingað til. Er þetta ljóst? Hvað er stór O í þessari lausn? Timewise. Ekki alveg n ^ 2. Athugið að við iterate frá 0 til n, svo er það eitt til hliðar. Við iterate aftur frá nánast upphafi til enda, annar fyrir lykkju. Og nú, í það, verðum við að summa upp alla færslu, svo er það annar fyrir lykkju. Þannig að við höfum þrjá orpið fyrir lykkjur, n ^ 3. Allt í lagi. Þetta fer sem útgangspunkt. Lausnin okkar er ekki verri en n ^ 3. Er allir skilja skepna afl lausn? 

Allt í lagi. A betri lausn er að nota hugmynd sem kallast dynamic forritun. Ef þú tekur CS124, sem er Reiknirit og gögn uppbygging, þú verður mjög kunnuglegur með þessari tækni. Og hugmyndin er, að reyna að byggja upp lausnir til smærri vandamál fyrst. Það sem ég meina með þessu er, höfum við nú að hafa áhyggjur af tvennu: byrja og enda. Og það er pirrandi. Hvað ef við gætum losna við einn af þeim þáttum? Ein hugmynd er að - we're gefið upprunalega vandamál okkar, finna hámarks summa subarray í bilinu [O, n-1]. Og nú höfum við nýja subproblem, þar sem við þekkjum, í núverandi vísitölu okkar i, við vitum að við verðum gera þar. Subarray okkar verður að enda á núverandi vísitölu. Svo eftir stendur vandamálið er, hvar ættum við að byrja subarray okkar? Er þetta skynsamleg? Allt í lagi. Þannig að ég hef túlkað þetta upp, og við skulum líta á hvað þetta þýðir. Í codirectory, það er forrit sem heitir subarray, og það tekur fjölda af hlutum, og það skilar hámarks subarray summan í stokkuð listanum mínum. Svo í þessu tilfelli, hámarks subarray okkar er 3. Og það er tekið bara með því að nota 2 og 1. Við skulum hlaupa aftur. Það er einnig 3. En í þetta skiptið, athugaðu hvernig fengum við 3. Við tók - við að taka bara 3 sig því það er umkringdur filmur á báðum hliðum, sem vilja koma fjárhæð <3. Við skulum hlaupa á 10 atriðum. This tími það er 7, taka við leiðandi 3 og 4. This tími það er 8, og við að fá að með því að taka 1, 4 og 3. Svo til að gefa þér innsæi á því hvernig við getum leyst þetta umbreytt vandamál, láta 'taka a líta á þetta subarray. Við erum gefið þetta inntak array, og við vitum að svarið er 8. Við tökum 1, 4 og 3. En við skulum líta á hvernig við fengum reyndar að svar. Við skulum líta á hámarks subarray sem lauk á hverjum þessara vísitalna. Hvað er hámarks subarray sem þarf að enda í efstu stöðu? [Nemandi] Zero. >> Zero. Bara ekki taka -5. Hér það er að fara að vera 0 eins og heilbrigður. Já? (Nemandi, óskiljanlegur) [Yu] Ó, fyrirgefðu, það er -3. Þannig að þetta er 2, þetta er -3. Allt í lagi. Svo -4, hvað er hámarks subarray til enda þá stöðu þar -4 er á? Zero. Einn? 1, 5, 8. Nú verð ég að enda á þeim stað þar sem -2 er á. Svo 6, 5, 7, og það síðasta er 4. Vitandi að þetta eru færslurnar mínar fyrir breyttu vandamál þar sem ég þarf að ljúka við hvern þessara vísitalna, þá er síðasta svar mitt bara, taka sópa yfir, og taka hámarksfjölda. Þannig að í þessu tilviki það er 8. Þetta felur í sér að hámarks subarray endar á þessari vísitölu, og byrjaði einhvers staðar fyrir það. Þurfa allir að skilja þetta umbreytt subarray? 

Allt í lagi. Jæja, við skulum reikna út endurkomu fyrir þetta. Við skulum íhuga bara fyrstu færslur. Svo hér það var 0, 0, 0, 1, 5, 8. Og þá var -2 hér, og leiddi hana niður í 6. Svo ef ég kalla færslu í stöðu i subproblem (i), hvernig get ég notað svar við fyrri subproblem að svara þessari subproblem? Ef ég horfi á, við skulum segja, þessi færsla. Hvernig get ég reikna svarið 6 því að horfa á sambland af þessu fylki og svör við fyrri subproblems í þessu fylki? Já? [Kvenkyns nemandi] Þú tekur fjölda fjárhæðir í þeirri stöðu rétt fyrir það, þannig að 8, og þá bæta núverandi subproblem. [Yu] Svo tillaga hennar er að líta á þessar tvær tölur, þetta númer og þessi tala. Þannig vísar það 8 að svara fyrir subproblem (i - 1). Og við skulum kalla inntak array A. minn Til þess að finna hámarks subarray sem endar á stöðu i, Ég hef tvo kosti: Ég get annað hvort haldið áfram subarray sem endaði á milli vísitölu, eða hefja nýja fylki. Ef ég væri að halda áfram subarray sem hófst á fyrri vísitölu, þá er hámarks summan ég get náð svarið við fyrri subproblem auk núverandi array færslu. En, ég hef líka val um að byrja nýja subarray, í því tilviki summan er 0. Svo er svarið max 0, subproblem i - 1, auk núverandi array færslu. Er þetta endurtekning skynsamleg? Endurkoma okkar, eins og við uppgötva, er subproblem i er jöfn hámarki fyrri subproblem auk núverandi array færslu mína, sem þýðir að halda áfram fyrri subarray, eða 0, hefja nýtt subarray á núverandi vísitölu minn. Og þegar við höfum byggt upp þessa töflu af lausnum, svo endanlega svar okkar, bara gera línulega sópa yfir subproblem array og taka hámarksfjölda. Þetta er nákvæmlega framkvæmd af því sem ég sagði rétt. Þannig að við að búa til nýja subproblem fylki, subproblems. Fyrsta færsla er annaðhvort 0 eða fyrstu færslu, hámark þeirra tveggja. Og fyrir the hvíla af the subproblems við notum endurkomu við uppgötva. Nú erum við að reikna hámark subproblems array okkar, og það er endanlegt svar okkar. 

Svo hversu mikið pláss við erum að nota í reiknirit? Ef þú hefur aðeins tekið CS50, þá þú might ekki hafa rætt pláss mjög mikið. Jæja, einn hlutur að hafa í huga er að ég kallaði malloc hér með n stærð. Hvað er að benda á þig? Þetta reiknirit notar línuleg rúm. Getum við gert betur? Er eitthvað sem þú tekur eftir því er óþarfi að reikna endanlega svar? Ég held að betri spurning er, hvaða upplýsingar þurfum við ekki að bera alla leið í gegnum til enda? Nú, ef við lítum á þessar tvær línur, við umönnun aðeins um fyrri subproblem, og við umönnun aðeins um allt sem við höfum nokkurn tíma séð svo langt. Til að reikna endanlega svar okkar, þurfum við ekki allt array. Við þurfum aðeins síðasta númer, síðustu tveir tölustafir. Síðasta tala fyrir subproblem array, og síðasta númer fyrir hámark. Svo, í raun getum við mjúklega þessar lykkjur saman og fara úr línulegum rúm til stöðugum pláss. Núverandi summan svo langt, hér kemur, hlutverk subproblem, subproblem array okkar. Svo núverandi summan, svo langt, er svarið við fyrri subproblem. Og þessi summa, svo langt, tekur sæti max okkar. Við reikna allt sem við förum eftir. Og svo við förum úr línulegum rúm til föstu rými, og við höfum einnig línulega lausn subarray vandamál okkar. 

Þessar tegundir af spurningum sem þú munt fá í viðtali. Hvað er tími flókið, það er pláss flókið? Getur þú gert betur? Eru hlutir sem eru óþarfi að halda í kring? Ég gerði þetta til að varpa ljósi greiningar sem þú ættir að taka á eigin spýtur eins og þú ert að vinna í þessum vandamálum. Alltaf að spyrja sjálfan þig: "Get ég gert betur?" Í raun getum við gert betur en þetta? Konar bragð spurningu. Þú getur ekki, vegna þess að þú þarft að að minnsta kosti lesa inntak á vandanum. Þannig að sú staðreynd að þú þarft að minnsta kosti að lesa inntak á vandamáli þýðir að þú getur ekki gert betur en línulega tíma, og þú getur ekki gert betur en föstu rými. Svo er þetta í raun besta lausnin á þessu vandamáli. Spurningar? Allt í lagi. 

Verðbréfamarkaðurinn vandamál: "Í ljósi fylki af n heiltalna, jákvæð, núll eða neikvæð, að tákna verð á hlutabréfum á n daga, Skrifið fall til að reikna hámark gróði sem þú getur gert í ljósi þess að þú kaupa og selja nákvæmlega 1 birgðir innan þessa n daga. " Í meginatriðum, við viljum að kaupa lágt, selja hátt. Og við viljum að reikna út bestu hagnaði við getum gert. Fara aftur á enda minn, hvað er strax ljóst, einfaldasta svarið, en það er hægt? Já? (Nemandi, óskiljanlegur) >> Já. >> Svo þú myndir bara fara þó og líta á hlutabréfaverð á hverjum tíma, (óskiljanlegur). [Yu] Jæja, svo lausn hennar - tillaga hennar um tölvumál lægsta og reikna hæsta ekki endilega að vinna því hæsta gæti orðið áður en lægsta. Svo er það skepna afl lausn á þessu vandamáli? Hvað eru tveir hlutir sem ég þarf að einstaklega ákvarða hagnað sem ég gera? Hægri. Skepna afl lausn er - ó, svo tillaga George er við þurfum bara tvo daga að einstaklega ákvarða hagnað þessara tveggja daga. Þannig að við reikna hvert par, eins og að kaupa / selja, reikna hagnað, sem gæti verið neikvætt eða jákvætt eða núll. Reiknið hámarks hagnað að við tökum eftir iterating yfir öll pör daga. Það verður endanlega svar okkar. Og þessi lausn verður að vera O (n ^ 2), vegna þess að það er n valið tvö pör - daga sem þú getur valið á milli daga enda. Allt í lagi, þannig að ég ætla ekki að fara yfir skepna afl lausn hér. Ég ætla að segja ykkur að það er N log n lausn. Hvaða reiknirit veistu nú það er n log n? Það er ekki bragð spurning. 

Mergesort. Mergesort er n log n, og í raun ein leið til að leysa þetta vandamál er að nota a Mergesort konar hugmynd heitir, almennt skipta og sigra. Og hugmyndin er sem hér segir. Þú vilt að reikna bestu kaup / selja par á vinstri helming. Finndu bestu gróði sem þú getur gert, bara með fyrstu n í tvo daga. Síðan sem þú vilt að oompute bestu kaup / selja par á hægri hluta, svo síðasta N yfir í tvo daga. Og nú er spurningin, hvernig sameina við þessar lausnir saman aftur? Já? (Nemandi, óskiljanlegur) >> Lagi. Svo láta mig teikna mynd. Já? (George, óskiljanlegur) >> Einmitt. Lausn George er nákvæmlega rétt. Svo tillaga hans er fyrst reikna Kaupa / selja par, og sem á sér stað í vinstri hluta, þannig að við skulum kalla það vinstri, vinstri. Kaupa / selja par sem á sér stað í hægri hluta. En ef við saman bara þessar tvær tölur, við erum að missa málið þar sem við kaupum hér og selja einhvers staðar á hægri hluta. Við kaupum í vinstri hluta, selja í rétta hluta. Og besta leiðin til að reikna Kaupa / selja par sem spannar bæði helminga er að reikna amk hér og reikna hámarki hér og taka mismuninn þeirra. Svo tveimur tilvikum þar sem kaupa / selja par berst aðeins hér, aðeins hér, eða á báðum helminga er skilgreint af þessum þremur tölum. Svo reiknirit okkar að sameina lausnir okkar aftur saman, við viljum reikna Kaupa / selja par þar sem við kaupum á vinstri hluta og selja á réttum helming. Og besta leiðin til að gera það er að reikna lægsta verð á fyrri helmingi ársins, hæsta verð í hægri hluta, og taka máli þeirra. Sú þrjár hagnaður þessar þrjár tölur, taka þér mest þriggja, og það er besta hagnað sem þú getur gert á þessum fyrstu og endir daga. Hér mikilvæg línur eru í rauðu. Þetta er endurkvæma hringja til að reikna svarið í vinstri helming. Þetta er endurkvæma hringja til að reikna svarið á hægri hluta. Þessir tveir fyrir lykkjur reikna min og max á vinstri og hægri hluta, hver um sig. Nú er ég að reikna hagnað sem spannar bæði helminga, og endanleg svar er hámark þessara þriggja. Allt í lagi. 

Svo viss, verðum við reiknirit, en stærri spurning er, það er tími flókið þetta? Og ástæðan fyrir því að ég nefndi Mergesort er að þetta form skipta svarið í tvo og þá sameina lausnir okkar aftur saman er einmitt mynd af Mergesort. Svo láta mig fara í gegnum tíma. Ef við skilgreint fall t (n) að vera tala af skrefum fyrir n dögum, tvær okkar endurkvæma símtöl eru hver að fara að kosta t (n / 2), og það er tveir af þessum símtölum. Nú þarf ég að reikna amk vinstri hluta, sem ég get gert í N / 2 tíma, auk hámarks á hægri hluta. Þannig að þetta er bara n. Og svo plús sumir föstu starfi. Og þetta endurtekning jöfnu er einmitt endurkomu Jafna fyrir Mergesort. Og við vitum öll að Mergesort er n log n tíma. Því er reiknirit okkar líka n log n tíma. Er þetta endurtekning skynsamleg? Bara stutt ágrip af þessu: T (n) er fjöldi af skrefum til að reikna hámarks hagnað á meðan á n daga. Leiðin sem við skipt upp endurkvæma símtöl okkar er með því að kalla lausn okkar á fyrstu n / 2 daga, svo er það eitt símtal, og svo við köllum aftur á seinni hluta ársins. Svo er það tvö símtöl. Og þá erum við að finna að minnsta kosti á vinstri hluta, sem við getum gert í línulegum tíma, finna hámarki hægri hluta, sem við getum gert í línulegum tíma. Svo N / 2 + N / 2 er bara n. Þá höfum við nokkur stöðuga vinnu, sem er eins og að gera tölur. Endurkoma jafna er einmitt endurkomu Jafna fyrir Mergesort. Þess vegna, uppstokkun reiknirit okkar er einnig N log n. Svo hversu mikið pláss erum við að nota? Við skulum fara aftur til kóðann. 

A betri spurning er, hversu margir stafla ramma sem við höfum alltaf á hverri stundu? Þar sem við erum með endurkvæmni, fjölda ramma stafla ákvarðar rúm notkun okkar. Við skulum íhuga n = 8. Við köllum uppstokkun á 8, sem mun kalla uppstokkun á fyrstu fjórum færslum, sem mun kalla uppstokkun á fyrstu tveimur færslum. Svo stafla okkar - þetta er stafla okkar. Og þá erum við kalla uppstokkun aftur á 1, og það er það sem byggja mál okkar er, svo við aftur strax. Eigum við alltaf meira en þetta margir rammar stafla? Nei vegna þess að hvert skipti sem við gerum er ákall, a endurkvæma ákall á uppstokkun, við deilum stærð okkar í tvennt. Svo hámarksfjöldi ramma stafla við höfum alltaf á hverri stundu er á stærðargráðunni log n stafla ramma. Hver stafla ramma hefur stöðug pláss, og því alls pláss, hámarks pláss sem við notum alltaf er O (log n) rúm þar sem n er fjöldi daga. 

Nú, alltaf að spyrja sjálfan þig, "Getum við gert betur?" Og sérstaklega, getum við draga úr þessu á vandamáli sem við höfum þegar leyst? A Ábending: við ræddum aðeins tvö önnur vandamál fyrir þetta, og það er ekki að fara að vera uppstokkun. Við getum breytt þessum markaði lager vandamál í hámarks subarray vandamál. Hvernig getum við gert þetta? Einn af þér? Emmy? (Emmy, óskiljanlegur) [Yu] Einmitt. Þannig hámarks subarray vandamál, við erum að leita að summa yfir samfellt subarray. Og tillaga Emmy fyrir stokk vandamál, íhuga breytingar eða deltas. Og mynd af þessu er - þetta er verð á hlutabréfum, en ef við tókum muninn hverjum röð degi - svo sjáum við að hámarks verð, hámarks hagnað við gætum gert er ef við kaupum hér og selja hér. En við skulum líta á stöðugt - við skulum líta á subarray vandamál. Svo hér, getum við gert - að fara áfram til hér, við höfum jákvæð breyting, og þá fara áfram til hér við höfum neikvæð breyting. En þá að fara áfram í hér við erum með mikla jákvæða breytingu. Og þetta eru breytingar sem við viljum að summa upp til að fá endanlega hagnað okkar. Þá höfum við fleiri neikvæðar breytingar hér. Lykillinn að því að draga birgðir vandamál okkar í hámarks subarray vandamál okkar er að fjalla um deltas milli daga. Þannig að við að búa til nýtt array heitir deltas, frumstilla fyrstu færslu til að vera 0, og þá fyrir hverja Delta (i), láta það vera munur um inntak array mitt (i), og array (i - 1). Þá erum við að kalla venja aðferð okkar fyrir hámarks subarray liggur í fylkinu a Delta. Og af því að hámarks subarray er línuleg tími, og þessi lækkun, þetta ferli að búa til þetta delta fylking, er líka línuleg tími, þá er endanlega lausn fyrir hlutabréf O (n) vinna plús O (n) að vinna, er enn O (n) vinna. Þannig að við höfum línulega tíma lausn á vanda okkar. Þurfa allir að skilja þessa umbreytingu? 

Almennt er góð hugmynd að þú ættir alltaf að hafa er að reyna að draga úr nýja vandamál sem þú sérð. Ef það lítur þekkja gamla vandamál, reyna að draga úr því að gamla vandamál. Og ef þú getur notað öll þau tæki sem þú hefur notað á gömlu vandamáli að leysa nýtt vandamál. Svo til að vefja upp, eru tæknilega viðtöl krefjandi. Þessi vandamál eru sennilega sumir af the fleiri erfiðum vandamálum sem þú gætir séð í viðtali, þannig að ef þú skilur ekki öll vandamál sem ég falla bara, það er allt í lagi. Þessir ert sumir af the fleiri krefjandi vandamálum. Practice, æfa, æfa. Ég gaf fullt af vandamálum í útdeila svo ákveðið stöðva þá út. Og gangi þér vel á viðtölum þínum. Allar auðlindir mínar eru settar á þennan tengil og einn af eldri vinum mínum hefur boðist til að gera spotta tæknilegum viðtöl, þannig að ef þú hefur áhuga, email Will Yao á þetta netfang. Ef þið hafið einhverjar spurningar, getur þú spyrja mig. Ert þú krakkar hafa sérstakar spurningar sem tengjast tæknilegum viðtöl eða einhver vandamál sem við höfum séð hingað til? Allt í lagi. Jæja, gangi þér vel á viðtölum þínum. [CS50.TV]