[Powered by Google Translate] [Seminar: Tehniline Intervjuud] [Kenny Yu, Harvard University] [See on CS50.] [CS50.TV] Tere kõigile, ma olen Kenny. Olen praegu noorem õpib arvutiteadus. Ma olen endine CS TF, ja ma soovin, et oli see, kui ma olin underclassman, ja sellepärast ma annan selle seminari. Nii et ma loodan, et te naudite seda. See seminar on umbes tehniline intervjuud, ja kõik minu ressursid võib leida seda linki, seda linki just siin, paar ressursse. Tegin nimekirja probleemidest, tegelikult üsna palju probleeme. Ka üldine ressursside lehel kus me võime leida vihjeid kuidas valmistuda intervjuu, vihjeid selle kohta, mida sa peaksid tegema ajal tegelik intervjuu, samuti kuidas läheneda probleeme ja ressursse edaspidiseks. See kõik on võrgus. Ja just eessõna seminari, disclaimer, nagu see ei tohiks - sinu intervjuu ettevalmistus ei tohiks piirduda sellesse nimekirja. See on mõeldud ainult juhistena, ja siis tuleb kindlasti võtta kõik, mida ma öelda tera soola, aga kasutada ka kõik, mida ma kasutada, et aidata teil oma intervjuu ettevalmistus. 

Ma lähen Speed ​​läbi järgmise paari slaidid nii saame tegeliku juhtumiuuringud. Struktuuri intervjuus tarkvaratehnika asendis, tavaliselt on 30 kuni 45 minutit, Mitme vooru, olenevalt äriühingust. Sageli saate kodeering valge tahvel. Nii valge tahvel meeldib see, kuid sageli ka väiksemas mastaabis. Kui sul on telefon intervjuu, peate ilmselt kasutama kas collabedit või Google Doc et nad saaksid näha sa elad kodeerimine kui oled intervjuul telefoni teel. Intervjuu ise on tavaliselt 2 või 3 probleeme testida oma arvuti teadust teadmised. Ja see on peaaegu kindlasti kaasata kodeerimine. Tüüpi küsimusi, mida te näete on tavaliselt andmestruktuurid ja algoritmid. Ja seda tehes selliseid probleeme, nad teilt küsida, nagu, mis on ajas ja ruumis keerukus, suur O? Tihti nad ka küsida kõrgema taseme küsimusi, nii, projekteerimine süsteem, kuidas sa panema oma koodi? Mis liidesed, mida klassid, mida moodulid on teil oma süsteemi, ja kuidas need mõjutavad üksteist? Nii andmestruktuurid ja algoritmid, samuti disainida süsteeme. 

Mõned üldised nõuanded enne kui me sukelduda meie juhtumiuuringud. Arvan, et kõige tähtsam reegel on alati mõtlesin valjusti. Intervjuu peaks olema sinu võimalus uhkeldama oma mõtlemisprotsessi. Punkt intervjuu on intervjueerija hinnata kuidas te arvate ja kuidas te lähete kaudu probleem. Halvim, mida saate teha, on olla vait kogu intervjuu. See on lihtsalt ei ole hea. Kui teile antakse küsimus, sa ka tahad teha kindel, et sa küsimusest aru. Nii et kordan küsimust tagasi oma sõnadega ja üritab teha põhjalik mõne lihtsa katse juhtudel veenduge küsimusest aru. Töö kaudu paar katsejuhtumite teile ka intuitsiooni, kuidas seda probleemi lahendada. Sa võid isegi leida mõned mudelid, mis aitavad teil probleemi lahendada. Nende suur ots on mitte saada pettunud. Ärge saage pettunud. Intervjuud on raske, kuid kõige hullem asi, mida teha, lisaks on vaikne, tuleb nähtavalt pettunud. Sa ei taha anda seda muljet, et küsitleja. Üks asi, mida - nii paljud inimesed, kui nad lähevad vestlusele nad üritavad püüda leida parim lahendus esiteks, kui tõesti, seal on tavaliselt pimestavalt ilmne lahendus. See võib olla aeglane, siis võib olla ebaefektiivne, kuid siis tuleb lihtsalt märkida see, lihtsalt nii et teil on lähtepunkt, millest paremini tööle. Samuti, juhtides tähelepanu lahendus on aeglane, nii Big O ajakeerukust või ruumi keerukus, näitab, et intervjueerija et saate aru neid teemasid kirjalikult koodi. Nii et ärge kartke tulla kõige lihtsam algoritm 1. ja siis koo parem sealt. Kõik küsimused siiani? Okei. 

Nii et olgem sukelduda meie esimene probleem. "Arvestades array n täisarvu kirjutada funktsioon, mis segab massiivi paika nii, et kõik permutatsiooni n täisarvu on võrdselt tõenäoline. " Ja eeldada, teil on olemas juhuslik täisarv generaator mis tekitab täisarv vahemikus 0 kuni i, pool vahemikus. Kas kõik mõistavad seda küsimust? Ma annan teile massiivi n täisarvu ja ma tahan, et sa shuffle ta. Minu kataloogis, ma kirjutasin mõned programmid näidata, mida ma mõtlen. Ma lähen shuffle array 20 elementi, -10 kuni +9, ja ma tahan, et sa väljastada nimekirja niimoodi. Nii et see on minu järjestatud massiivist, ja ma tahan, et sa shuffle ta. Me teeme seda jälle. Kas kõik küsimusest aru? Okei. Nii et see on kuni teil. Mis on mõned ideed? Kas sa seda kui n ^ 2, n log n, n? Avatud ettepanekutele. Okei. Nii et üks idee, soovitas Emmy, kõigepealt arvutada juhusliku numbri, juhuslik täisarv, vahemikus 0-20. Nii et meil on meie massiivi pikkus on 20. Meie diagramm 20 elementi, see on meie massiivist. Ja nüüd, tema ettepanek on luua uus massiiv, nii et see on väljund massiivi. Ja mis põhineb i poolt tagastatud rand - nii et kui ma olin, ütleme, 17, kopeerida 17. element esimesel kohal. Nüüd tuleb kustutada - me peame minema kõik elemendid siin üle, et meil on lõpupoole ja auke keskel. Ja nüüd me protsessi korrata. Nüüd korja uus juhuslik täisarv vahemikus 0 ja 19. Meil on uus i siin, ja me kopeerida see element selles asendis. Siis me vahetustega teemad üle ja me protsessi korrata, kuni meil on meie terve uue massiivi. Mis on läbijooksuaeg Selle algoritmi? Noh, olgem kaaluma, millist mõju see. Meil on hakanud iga element. Kui me eemaldada selle mina, me nihkuvad kõik elemendid peale seda vasakule. Ja see on O (n) maksumus sest mis siis, kui me eemaldage esimene element? Nii et iga eemaldamine, me eemaldada - iga eemaldamine kannab O (n) käitamine, ja kuna me oleme n kolimine, see viib O (n ^ 2) shuffle. Okei. Nii et hea algus. Hea algus. 

Teine võimalus on kasutada midagi, mida nimetatakse Knuth shuffle, või Fisher-Yates shuffle. Ja see on tegelikult lineaarne aeg shuffle. Ja see idee on väga sarnased. Jällegi on meil massiivist, kuid selle asemel kahe massiivi meie sisend / väljund, me kasutame esimest osa massiivi jälgida meie segatud osa, ja me jälgida, ja siis me lahkume meie ülejäänud massiivi unshuffled osa. Nii et siin on, mida ma mõtlen. Me alustad - me valime i, massiivi 0-20. Meie praegune osuti osutab esimesele indeks. Valisime mõned i siin ja nüüd me vahetada. Nii et kui see oli 5 ja see oli 4, tulemuseks massiivi on 5 siin ja 4. siin. Ja nüüd pange tähele marker siin. Kõik vasakul on segatud, ja kõike seda õigust unshuffled. Ja nüüd saame protsessi korrata. Valisime juhuslik indeks 1 ja 20 vahel nüüd. Olgu, oletame meie uus i on siin. Nüüd vaheta seda ma meie praegune uus positsioon siin. Nii et me vahetada edasi-tagasi niimoodi. Lubage mul tuua kood, et oleks konkreetsem. Alustame meie valikut i - alustame i võrdne 0, me valime suvalise koha j aastal unshuffled osa massiiv, i kuni n-1. Nii et kui ma olen siin, valida juhuslik indeks vahel siin ja ülejäänud massiiv, ja me vahetada. See on kõik koodi vaja shuffle oma massiivi. Kas on küsimusi? 

Noh, üks vaja küsimusele, miks on see õige? Miks on iga permutatsioon sama tõenäoline? Ja ma ei lähe läbi selle tõestuseks, kuid palju probleeme arvuti teadust saab tõestada läbi induktsiooni. Kui palju te olete tuttav induktsioon? Okei. Lahe. Nii saab õigsuse tõendamisel seda algoritmi lihtsate induktsioon, kus teie induktsiooni hüpotees oleks eeldada, et minu shuffle naaseb iga permutatsioon sama tõenäoline kuni esimese i elemente. Nüüd leiavad i + 1. Ja muide me valime meie indeks j vahetada, see viib - ja siis töötada välja andmed, vähemalt täis tõend selle kohta, miks see algoritm tagastab iga permutatsioon koos sama tõenäoline tõenäosus. 

Olgu, järgmine probleem. Nii et "antud massiivi täisarvud, positiivse väärtuse, null, negatiivne, kirjutada funktsioon, mis arvutab maksimaalne summa mis tahes continueous subarray on massiivist. " Üheks näiteks on siin, juhul kui kõik numbrid on positiivne, siis praegu parim valik on võtta terve rida. 1, 2, 3, 4, võrdub 10. Kui teil on mõned negatiivid seal, Sel juhul me lihtsalt tahame kahe esimese sest valides -1 ja / või -3 toovad meie summa maha. Vahel me võib-olla hakata keset massiivi. Vahel tahame valida midagi üldse on parem mitte võtta midagi. Ja mõnikord on parem võtta sügisel, sest asja pärast on super suur. Nii et mingeid ideid? (Õpilane, arusaamatult) >> Jah. Oletame, et ma ei võta -1. Siis kas ma valida 1000 ja 20000, või ma lihtsalt valida 3 miljardit eurot. Noh, parim valik on võtta kõik numbrid. See -1, hoolimata sellest, et negatiivne, kogu summa on parem kui oleksin mitte võtta -1. Nii et ühe vihjeid mainisin oli märgitud selgelt ilmne ja jõuvõtete lahendus esimesena. Mis on jõuvõtete lahendus sellele probleemile? Jah? [Jane] Ma arvan, et jõuvõtete lahendus oleks lisada kuni kõik võimalikud kombinatsioonid (arusaamatu). [Yu] Okei. Nii et Jane'i idee on teha kõik võimalik - Ma olen parafraseerides - on võtta kõikvõimalikke pidev subarray, arvutada selle summa ja seejärel võtta maksimaalselt kõik võimalikud pidev subarrays. Mis identifitseerib subarray minu massiivist? Nagu, mida kaks asja on vaja? Jah? (Õpilane, arusaamatult) >> Õigus. Alampiiri indeks ja ülemise indeksiga üheselt kindlaks pidev subarray. [Naine üliõpilane] Kas me selle hindamine on array ainulaadne numbrid? [Yu] No Nii et tema küsimus on, kas me eeldades meie massiivi - on meie massiivi kõik kordumatud numbrid, ja vastus on ei. 

Kui me kasutame oma jõuvõtete lahendus, siis start / lõpp indeksid üheselt määrab meie pidev subarray. Nii et kui me itereerima kõigi võimalike algus kirjed ja kõik lõpuks kanded> või = alustada, ja <n, sa arvutama summa, ja siis võtame maksimaalse summa oleme näinud siiani. Kas see selge? Mis on suur O see lahendus? Ajalises mõttes. Mitte päris n ^ 2. Pange tähele, et me itereerima 0 kuni n, nii et on üks silmus. Me itereerima taas peaaegu algusest lõpuni, teine ​​silmus. Ja nüüd, selles on meil Kokkuvõttes iga kirje, nii see on teine ​​silmus. Nii et meil on kolm nested jaoks silmuseid, n ^ 3. Okei. See läheb lähtepunktiks. Meie lahendus ei ole halvem kui n ^ 3. Kas kõik mõistavad jõuvõtete lahendus? 

Okei. Parem lahendus on kasutada mõte nimetatakse dünaamilise programmeerimise. Kui te võtate CS124, mis on Algoritmid ja andmestruktuurid, sinust saab väga hästi seda tehnikat. Ja see idee on, proovige luua lahendusi väiksemad probleemid esimesena. Mida ma mõtlen on see, meil on praegu muretsema kahte asja: algus ja lõpp. Ja see on tüütu. Mis siis, kui me võiksime saada lahti üks neist parameetrid? Üks mõte on - Me oleme andnud meie algne probleem, leida maksimaalne summa igal subarray vahemikus [O, n-1]. Ja nüüd on meil uus subproblem, kus me teame, et meie praegustes indeks i, me teame, et me peame järeldama seal. Meie subarray peab lõppema indeks. Nii et ülejäänud probleem on, kus me peaksime alustama meie subarray? Kas see on mõttekas? Okei. Nii et ma olen kodeeritud see üles ja vaatame, mida see tähendab. Aastal codirectory, seal on programm nimega subarray, ja see võtab mitmeid punkte, ja see tagastab maksimaalse subarray summa minu segatud nimekirja. Nii et antud juhul meie maksimaalse subarray on 3. Ja see on võtnud lihtsalt kasutades 2 ja 1. Olgem käivitage see uuesti. See on ka 3. Aga seekord, pange tähele, kuidas me saime 3. Tegime - me lihtsalt võtame 3 ise sest see on ümbritsetud negatiivid mõlemalt poolt, mis toob summa <3. Lähme sõitma 10 vastet. Seekord on see 7, võtame juhtiv 3 ja 4. Seekord on see 8, ning saame, et võttes 1, 4 ja 3. Nii et teile intuitsiooni sellest, kuidas me saame lahendada selle ümber probleemi, võtame pilk see subarray. Me arvestades seda massiivist, ja me teame, et vastus on 8. Võtame 1, 4 ja 3. Aga vaatame, kuidas me tegelikult sain selle vastuse. Vaatame maksimaalne subarray mis lõppes kell Kõigi nende indeksite. Mis on maksimaalne subarray et peab lõppema Esimesel kohal? [Student] Null. >> Zero. Lihtsalt ei võta -5. Siin see läheb 0. samuti. Jah? (Õpilane, arusaamatult) [Yu] Oh, vabandust, see on -3. Nii et see on 2, see on -3. Okei. Nii -4, mis on maksimaalne subarray lõppu selles asendis kus -4 on? Null. Üks? 1, 5, 8. Nüüd pean end kohas, kus -2 on kell. Nii et 6, 5, 7, ja viimane on 4. Teades, et need on minu sissekanded jaoks ümber probleem, kus ma peab lõppema igal neist indeksid, siis minu lõplik vastus on lihtsalt, kui heita pühkima üle, ja võtta maksimaalse arvu. Nii et antud juhul on see 8. See tähendab, et maksimaalne subarray lõpeb see indeks ja hakkas kuskil enne seda. Kas kõik mõistavad seda muutnud subarray? 

Okei. Noh, olgem nuputada kordumise selle eest. Vaatleme ainult paar esimest kirjet. Nii et siin oli 0, 0, 0, 1, 5, 8. Ja siis oli -2 siin, ja et tõi ta alla 6. Nii et kui ma kutsun kanne positsioonis i subproblem (i), kuidas ma saan kasutada vastus varem subproblem vastata sellele subproblem? Kui ma vaatan, ütleme, et see sissekanne. Kuidas arvutada vastus 6 vaadates kombinatsioon selle massiivi ja vastused eelmine subproblems selles massiivi? Jah? [Naine üliõpilane] Sa võta massiivi summade asendis just enne seda, seega 8, ja siis lisada praeguse subproblem. [Yu] Nii et tema soovitus on vaadata need kaks numbrit, see number ja see number. Nii et see 8 viidatakse vastus subproblem (i - 1). Ja olgem helistan oma massiivist A. Selleks, et leida maksimaalne subarray et lõpeb asendis i, Mul on kaks valikut: võin kas jätkata subarray mis lõppes eelmisel indeks, või alustada uue massiivi. Kui ma peaksin jätkama subarray et algas eelmisel indeks, siis maksimaalne summa võin saavutada, on vastus eelmisele subproblem pluss praegune massiivi kirje. Aga mul on ka valik algab uus subarray, sel juhul summa on 0.. Nii et vastus on max 0, subproblem i - 1, millele lisandub jooksev massiivi kirje. Kas see kordub mõtet? Meie kordumine, nagu me just avastasin, on subproblem i on võrdne maksimaalse eelmise subproblem pluss minu praegune massiivi kirje mis tähendab jätkata eelmise subarray, või 0, alustada uut subarray minu praegune indeks. Ja kui oleme rajanud tabelis lahendusi, siis meie lõplik vastus, lihtsalt ei lineaarse pühkima kogu subproblem massiivi ja võtta maksimaalse arvu. See on täpne rakendamine, mida ma just ütlesin. Nii loome uue subproblem massiiv, subproblems. Esimene sissekanne on kas 0 või esimese sisenemise, kuni need kaks. Ja kogu ülejäänud subproblems me kasutame täpne kordumine me just avastanud. Nüüd arvutage maksimaalne meie subproblems massiiv, ja see on meie lõplik vastus. 

Nii et kui palju ruumi on meil kasutades seda algoritmi? Kui oled ainult võtta CS50, siis sa ei pruugi arutanud ruumi väga palju. Noh, üks asi on tähele panna, et ma helistasin malloc siin arvu n. Mida see sulle ütleb? See algoritm kasutab lineaarse ruumi. Kas me teha paremini? Kas on midagi, mida te teate, et ei ole vaja arvutada lõplik vastus? Ma arvan, et parem küsimus on, millist teavet me ei pea tegema kogu tee kuni lõpuni? Nüüd, kui me vaatame neid kahte ritta, me ainult hoolid eelmise subproblem, ja me ainult hoolid maksimaalne oleme kunagi näinud siiani. Arvutada meie lõplik vastus, et me ei pea kogu massiivi. Meil on vaja ainult viimase numbri kaks viimast numbrit. Viimase numbri jaoks subproblem massiiv, ja viimane number on maksimaalne. Nii, et tegelikult me ​​ei sulavad need silmad koos ja minna lineaarse ruumi pidevalt ruumi. Praegune summa seni siin, asendab rolli subproblem, meie subproblem massiivi. Nii et praegune summa, seni on vastus eelmisele subproblem. Ja see summa, seni on koht meie maks. Me arvutame maksimaalne kui me läheme mööda. Ja nii me minna lineaarse ruumi pidevalt ruumi, ja meil on ka lineaarne lahendus meie subarray probleem. 

Sellised küsimused saad vestluse käigus. Mis on aeg keerukus; mida on ruumi keerukus? Kas sa suudad paremini? Kas on asju, mis on vajalik, et hoida umbes? Ma tegin seda rõhutada analüüsid, mida peaks arvesse võtma oma kui te töötate läbi nende probleeme. Alati tuleb küsida endalt: "Kas ma saan teha paremini?" Tegelikult me ​​saame teha paremini kui see? Omamoodi konksuga küsimus. Sa ei saa, sest sa pead vähemalt lugeda sisendi probleem. Nii et teil on vaja vähemalt lugeda sisendi probleem tähendab, et te ei saa teha paremini kui lineaarne aeg, ja sa ei saa seda teha paremini kui pidev ruumi. Nii et see on tegelikult parim lahendus sellele probleemile. Küsimused? Okei. 

Aktsiaturg probleem: "Arvestades array n täisarvu, positiivne, null, või negatiivne, mis esindavad hind börsil üle n päeva, Kirjuta funktsioon arvutada maksimaalset kasumit saab teha sest sa osta ja müüa täpselt 1 laos nendes n päeva. " Sisuliselt tahame osta madal, müüa kõrge. Ja me tahame välja nuputada parim kasum saame teha. Tulles tagasi minu otsa, mis on kohe selge, lihtsaim lahendus, kuid see on aeglane? Jah? (Õpilane, arusaamatult) >> Jah. >> Et siis lihtsalt minna küll ja vaadata aktsia hinda igal ajahetkel (arusaamatu). [Yu] Okei, nii et tema lahendus - tema soovitus arvutustehnika madalaim ning arvutamise kõrgeima ei pruugi toimida sest kõrgeim võivad ilmneda enne madalaim. Mis on jõuvõtete lahendus sellele probleemile? Millised on kaks asja, mida ma pean üheselt määrata kasumi teen? Õigus. Jõuvõtete lahendus on - oh, jah, Jüri ettepanek on meil vaja ainult kaks päeva üheselt kindlaks kasum nende kahe päeva jooksul. Nii et me arvutame iga paari meeldib osta / müüa, arvutada kasumit, mis võiks olla negatiivne või positiivne või null. Arvuta maksimaalne kasum, et me teeme pärast itereerimise üle kõik paari päeva jooksul. See on meie lõplik vastus. Ja see lahendus on O (n ^ 2), sest seal on n valida kaks paari - päevade saab valida seas lõpus päeva. Okei, nii et ma ei lähe üle jõuvõtete lahendus siin. Ma ütlen teile, et seal on n log n lahendus. Mis algoritm sa praegu tean, et on n log n? See ei ole trikiga küsimus. 

Merge omamoodi. Merge sorteerida on n log n, ja tegelikult üks viis selle probleemi lahendamiseks on kasutada ühendamise omamoodi selline idee nimega üldiselt jaga ja valitse. Ja mõte on järgmine. Sa tahad arvutada parim osta / müüa paari vasakul pool. Leia parimaid kasumit saad teha, lihtsalt esimese n üle kahe päeva. Siis sa tahad oompute parim osta / müüa paar paremal pool, nii viimane n üle kahe päeva. Ja nüüd on küsimus selles, kuidas me ühendada need lahendused jälle koos? Jah? (Õpilane, arusaamatult) >> Okei. Las ma joonistan pildi. Jah? (George, arusaamatult) >> Täpselt. George lahendus on täpselt õige. Nii et tema ettepanek on esimene arvutada parim osta / müüa paar, ja mis toimub vasakul pool, nii et olgem nimetame seda vasakule, vasakule. Parim osta / müüa paar, mis toimub paremal pool. Aga kui me ainult võrreldes nende kahe arvu, et meil puuduvad juhul kus me ostame siin ja müüa kusagil paremal pool. Ostame vasakul pool, müüa paremal pool. Ja parim viis arvutada parim osta / müüa paar, mis ulatub mõlemal poolajal on arvutada miinimum siin ja arvutage maksimaalne siia ja võtta nende erinevus. Nii et kaks juhtumit, kus osta / müüa paar esineb ainult siin, ainult siin, või mõlemas otsas on määratletud need kolm numbrit. Nii et meie algoritm ühendada meie lahenduste tagasi kokku, me tahame arvutada parim osta / müüa paar kus me ostame vasakul pool ja müüa paremal pool. Ja parim viis seda teha on arvutada madalaima hinnaga aasta esimesel poolel, kõrgeima hinnaga paremal pool, ja võtta nende erinevus. Saadud 3 kasumist, need kolm numbrit, siis võtab maksimaalselt kolm, ja see on parim kasum saad teha üle need esimesed ja lõpuks päeva. Siin tähtsamad read on punased. See on rekursiivne kõne arvutada vastus vasakul pool. See on rekursiivne kõne arvutada vastus paremal pool. Need kaks silmuseid arvutama min ja max vasakul ja paremal pool võrra. Nüüd ma arvutama kasumit, mis ulatub mõlemas otsas, ja lõplik vastus on suurim neist kolmest. Okei. 

Niisiis, muidugi, meil on algoritm, kuid suurem küsimus on, Kui pikk on aeg keerukus seda? Ja põhjus, miks ma mainisin ühendamise omamoodi on see, et selles vormis jagada vastus kaheks ja siis ühinevad meie lahendusi taas kokku Just kujul ühendamise omamoodi. Nii et lubage mul minna läbi kestus. Kui me defineerinud funktsiooni t (n) olla mitmeid samme kui n päeva, meie kahe rekursiivne kõne on iga läheb maksma t (n / 2), ja seal on kaks neist kõned. Nüüd on mul vaja arvutada vähemalt vasakul pool, mis ma teha saan n / 2 aega, pluss maksimaalselt paremal pool. Nii et see on lihtsalt n. Ja siis pluss mõned pidevat tööd. Ja see kordub võrrand Just kordumise võrrand ühendamise omamoodi. Ja me kõik teame, et ühendamise sorteerida on n log n korda. Seega, meie algoritmi ka n log n korda. Kas see iteratsiooni on mõtet? Lihtsalt lühikokkuvõtet sellest: T (n) on mitmeid samme, et arvutada maksimaalne kasum jooksul n päeva. Kuidas me lahku meie rekursiivne kõne on helistades meie lahendus esimese n / 2 päeva, nii et on üks kõne ja siis me kutsume taas aasta teisel poolel. Nii et kaks kõnet. Ja siis me leiame vähemalt vasakul pool, mis me teha saame, on lineaarne aeg, leida maksimaalselt paremal pool, mida me saame teha lineaarne aeg. Nii n / 2 + n / 2 on lihtsalt n. Siis meil on mõned pidev töö, mis on nagu tehes aritmeetika. See kordumise võrrand on täpselt kordumise võrrand ühendamise omamoodi. Seega, meie shuffle algoritm on ka n log n. Nii et kui palju ruumi on meil kasutada? Lähme tagasi kood. 

Parem küsimus on, kui palju korstna raamid me kunagi igal ajahetkel? Kuna me kasutame rekursioon, arvu korstnat raamid määrab meie ruumikasutuse. Vaatleme n = 8. Kutsume shuffle 8., mis kutsuvad shuffle esimese nelja kirjed mis kutsuvad shuffle kahe esimese kanded. Nii et meie stack on - see on meie pinu. Ja siis me kutsume shuffle jälle 1 ja see, mida meie tugipunkt on, et me kohe tagasi. Kas me kunagi olla rohkem kui nii palju korstna raame? No Sest iga kord, kui me teeme appihüüd, rekursiivne pöördumine shuffle, me jagame meie suuruste poole. Nii maksimaalne arv virnas raamid me kunagi igal ajahetkel on järjekorras log n korstnat raame. Iga freimi on pidev ruumi, ja seega kogusumma ruumi, maksimaalne summa ruumi me kunagi kasutada on O (log n) ruum kus n on päevade arv. 

Nüüd, alati endalt küsima, "Kas me teha paremini?" Ja eriti, kas me saame vähendada seda probleemi me oleme juba lahendatud? Vihje: me ainult arutasid kahe teise probleeme enne seda, ja see ei kavatse olla shuffle. Me ei saa muuta seda aktsiaturu probleem arvesse maksimaalne subarray probleem. Kuidas me saame seda teha? Üks teist? Emmy? (Emmy, arusaamatult) [Yu] Täpselt. Nii maksimaalne subarray probleem, me otsime summa üle pideva subarray. Ja Emmy ettepanekut varude probleem, kaaluda muudatusi või deltad. Ja pilt on see - see on hind börsil, kuid kui me võtame vahe iga järgneva päeva - nii me näeme, et maksimaalne hind, maksimaalne kasum saaksime on see, kui me ostame siin ja müüvad siin. Aga vaatame pidevalt - vaatame subarray probleem. Nii et siin, saame teha - lähed siit siiani, meil on positiivne muutus, ja siis läheb siit siiani meil on negatiivne muutus. Aga siis läheb siit siiani meil on suur positiivne muutus. Ja need muutused, mida me tahame kokku saada meie lõplik kasum. Siis on meil rohkem negatiivseid muutusi siin. Vähendamisel ülioluline meie varu probleem meie maksimaalse subarray probleem on kaaluda deltad päeva vahel. Nii loome uue massiivi nimega deltadega initsialiseerida esimese sisenemise olema 0, ja siis iga delta (i), olgu see erinevus minu massiivist (i), ja massiiv (i - 1). Siis me nimetame meie rutiinne protseduur maksimaalne subarray läbivad Delta massiivi. Ja kuna maksimaalne subarray on lineaarne aeg, ja see vähenemine, see loomas see delta massiiv, Samuti on lineaarne aeg, siis lõplik lahendus varud on O (n) töö pluss O (n) töö on ikka O (n) tööd. Nii et meil on lineaarne aeg lahendus meie probleemile. Kas kõik mõistavad selle muutuse? 

Üldiselt on hea mõte, et sa peaksid alati olema on püüda vähendada uus probleem, et te näete. Kui tundub tuttav vana probleem, proovige vähendada seda vana probleem. Ja kui sa ei kasuta kõiki vahendeid, mida olen kasutanud vana probleem lahendada uusi probleeme. Nii et soojalt riidesse panema, tehniline intervjuud on keeruline. Need probleemid on ilmselt ühed kõige raskemad probleemid et võite näha intervjuus, nii et kui sa ei mõista kõiki probleeme, et ma lihtsalt kaetud, see on okei. Need on mõned rohkem probleemid. Praktika, praktika, praktika. Ma andsin palju probleeme jaotusmaterjali, nii kindlasti vaadata need läbi. Ja hea õnne oma intervjuud. Kõik minu ressursid on postitanud seda linki, ja üks mu vanem sõbrad on pakkunud teha mõnitama tehnilise intervjuud, nii et kui olete huvitatud, email Yao tol e-posti aadress. Kui teil on küsimusi, võite küsida mind. Kas teiega on konkreetseid küsimusi, mis on seotud tehnilise intervjuud või mingeid probleeme oleme näinud nii kaugele? Okei. Noh, õnne oma intervjuud. [CS50.TV]