[Powered by Google Translate] [Seminaras: Techniniai Interviu] [Kenny J., Harvardo universitetas] [Tai CS50.] [CS50.TV] Hi everyone, Aš esu Kenny. Aš šiuo metu jaunesnysis studijuoja kompiuterių mokslas. Aš esu buvęs CS TF, ir aš noriu, aš turėjo tai, kai buvau antro kurso, ir tai, kodėl aš šį seminarą. Taigi, aš tikiuosi, kad jums patiks jį. Šis seminaras yra apie technines interviu, ir visi mano išteklius galima rasti šią nuorodą, šią nuorodą čia, išteklių pora. Todėl aš padariau problemų sąrašą, iš tikrųjų, nemažai problemų. Taip pat bendras ištekliai puslapis, kur mes galime rasti patarimų apie tai, kaip pasirengti pokalbiui, patarimų apie tai, ką jums reikia padaryti per faktinė interviu, taip pat, kaip spręsti problemas ir išteklius ateičiai. Tai viskas online. Ir tiesiog parašyti įžangą Šiame seminare Atsakomybės apribojimas kaip tai neturėtų - savo interviu rengimą neturėtų būti ribojamas į šį sąrašą. Tai tik reiškia būti vadovas, ir jums tikrai turėtų viską, ką sakau su druskos grūdų, bet taip pat naudoti viską, ką aš naudojamas, siekiant padėti jums jūsų interviu rengimo. 

Aš ruošiuosi pagreitinti per ateinančius keletą skaidrių todėl mes galime gauti į faktinę atvejų tyrimus. Programinės įrangos inžinerijos tikroje padėtyje interviu struktūra, paprastai tai yra nuo 30 iki 45 minučių, keli raundai, priklausomai nuo įmonės. Dažnai jums kodavimas balta lenta. Taigi balta lenta, kaip šis, bet dažnai dėl mažesnio masto. Jei esate turintys interviu telefonu, jūs tikriausiai naudojate arba collabedit arba "Google" dokumentus, kad jie gali matyti, kad jūs gyvenate kodavimo o jūs apklausiamas telefonu. Interviu pats yra paprastai 2 arba 3 problemos išbandyti savo informatikos žinias. Ir tai bus beveik neabejotinai įtraukti kodavimo. Klausimų tipų, kad jūs pamatysite paprastai yra duomenų struktūros ir algoritmai. Ir daro šių rūšių problemų, jie bus paprašyti jus, kaip, kas yra laiko ir erdvės sudėtingumą, Big O? Dažnai jie taip pat paprašyti aukštesnio lygio klausimus, , projektuojant sistemą, kaip jums išdėstyti savo kodą? Sąsajos, kokios klasės, kokie moduliai Ar turite savo sistemą,, ir kaip jie sąveikauja tarpusavyje? Taigi duomenų struktūros ir algoritmai, taip pat projektavimo sistemos. 

Keletas bendro pobūdžio patarimų, kol mes pasinerti į mūsų atvejų tyrimus. Manau, kad svarbiausia taisyklė visada būti mąstymas garsiai. Pokalbis turėtų būti jūsų šansas parodyti savo mąstymo procesą. Interviu interviu įvertinti kaip jūs manote ir kaip jūs einate per problema. Blogiausias dalykas, kurį galite padaryti, tai tylėti per visą interviu. Tai tiesiog nėra gera. Kai jums į klausimą, jūs taip pat norite įsitikinti, kad jūs suprantate, į klausimą. Taigi pakartoti klausimą savo žodžiais ir bando dirbti kruopščiai kelis paprastus testinius atvejus įsitikinkite, kad jums suprasti klausimą. Darbas per keletą bandymų atvejus, taip pat suteikti jums apie tai, kaip išspręsti šią problemą intuicija. Galbūt net atrasti keli modeliai, siekiant padėti jums išspręsti šią problemą. Jų didelis patarimas yra ne gauti nusivylė. Negalima gauti nusivylė. Interviu yra sudėtinga, tačiau blogiausia, ką galite padaryti, Be to, yra tylus, turi būti akivaizdžiai nusivylė. Jūs nenorite duoti, kad įspūdį apklausų. Vienas dalykas, kad jūs - taip, daug žmonių, kai jie eiti į interviu, jie bando pabandyti rasti geriausią sprendimą, tada, kai tikrai, ten paprastai yra akivaizdūs sprendimas. Tai gali būti lėtas, tai gali būti neefektyvus, bet jums tiesiog reikia nurodyti, tiesiog todėl jūs turite pradinį tašką, iš kurio dirbti geriau. Be to, nurodydama, kad sprendimas yra lėtas, kalbant apie Big O laikas sudėtingumas ar kosmoso sudėtingumą, bus parodyti pašnekovui, kad jūs suprantate, šie klausimai, kai rašyti kodą. Todėl nereikia bijoti sugalvoti nuo paprasčiausio algoritmo pirmą kartą ir tada dirbti geriau iš ten. Kokių nors klausimų, kiek? Gerai. 

Taigi, galime pasinerti į mūsų problemą. "Atsižvelgiant n sveikųjų skaičių masyvas, parašyti funkciją, kuri Shuffles masyvo tokios, kad visi sveikieji skaičiai n kombinacijų yra lygiai taip pat tikėtina. " Ir prisiimti turite atsitiktinį sveikąjį skaičių generatorių , kuris generuoja tam tikrame intervale, sveikasis skaičius nuo 0 iki i, pusė intervalas. Ar visi supranta, į šį klausimą? Aš jums n sveikųjų skaičių masyvas, ir aš noriu jums shuffle jį. Mano kataloge, parašiau kelias programas, kad parodytų, ką aš turiu galvoje. Aš ruošiuosi shuffle iš 20 elementų masyvas, nuo -10 iki 9, ir aš noriu, kad išėjimo panašus į šį sąrašą. Taigi tai yra mano surūšiuoti įvesties masyvas, ir aš noriu jums shuffle jį. Mes tai padaryti dar kartą. Ar visi supranta klausimą? Gerai. Todėl iki jums. Kokie yra keletas idėjų? Jūs galite padaryti jį kaip n ^ 2, n log n, n? Atidaryti pasiūlymus. Gerai. Taigi viena idėja, siūloma Emmy ", pirmiausia apskaičiuoti atsitiktinių skaičių, atsitiktinis sveikasis skaičius diapazone 0-20. Taigi manyti, mūsų masyvas yra 20 m ilgio. Mūsų diagrama 20 elementų, tai mūsų indėlis masyvas. Ir dabar, jos pasiūlymas yra sukurti naują masyvą, todėl tai bus išėjimo masyvas. Ir remiasi i grąžina rand Taigi, jei aš buvo, tarkim, 17, nukopijuokite 17 elementas į pirmąją poziciją. Dabar mums reikia ištrinti - mes turime perkelti visus elementus čia per tiek, kad mes turime spragą pabaigoje ir ne viduryje skyles. Ir dabar mes pakartokite šį procesą. Dabar mes pasirinkti naują atsitiktinis sveikasis skaičius tarp 0 ir 19. Mes turime naują aš čia, ir mes nukopijuokite šį elementą į šią poziciją. Tada mes pereiti elementus baigėsi ir mes pakartoti procesą, kol mes turime visiškai naują masyvą. Kas yra šio algoritmo veikimo laikas? Na, galime apsvarstyti šio poveikio. Perkeliant kiekvieną elementą. Kai pašaliname Tai aš, mes perkelti visus elementus, po to į kairę. Ir tai yra O (n) savikaina nes tai, ką, jei mes pašalinti pirmoji? Taigi kiekvieno atsargų, mes pašalinti Kiekviename leidime išvežti prisiima O (n) veikimą, nes mes n išsiuntimo, išsiuntimą, tai veda į O (n ^ 2) shuffle. Gerai. Taip gera pradžia. Gera pradžia. 

Be to, siūloma naudoti kažką, žinomą kaip Knuth shuffle, arba Fisher-Yates shuffle. Ir tai tikrai linijinis laikas shuffle. Ir idėja yra labai panašūs. Vėlgi, mes turime įvesties masyvo, bet vietoj to, naudojant du masyvų mūsų įvesties / išvesties, mes naudojame masyvo sekti mūsų išmaišytos dalis: pirmoji dalis, ir mes sekti, o tada mes palikti mūsų masyvas poilsio už unshuffled dalis. Taigi štai ką aš turiu galvoje. Mes pradėti su - mes pasirinkti i, masyvas 0-20. Mūsų dabartinė rodyklė nukreipta į pirmąjį indeksą. Mes pasirinkti kai aš čia ir dabar mes apsikeitimo. Taigi, jei tai buvo 5, ir tai buvo 4, masyvas bus 5 Čia ir 4 čia. Ir dabar mes pažymime žymeklį čia. Viskas į kairę išmaišytos ir viskas į dešinę unshuffled. Ir dabar mes galime pakartokite šį procesą. Mes pasirinkti atsitiktine tvarka indeksas nuo 1 iki 20 dabar. Taigi tarkime, kad mūsų nauja i čia. Dabar mes apsikeitimo Tai aš čia su mūsų dabartinės naują poziciją. Taigi mes Swapping pirmyn ir atgal, kaip šis. Leiskite man duoti kodą, kad būtų konkretesnis. Mes pradedame su mūsų pasirinkimas i - mes pradedame su i lygi 0, mes pasirinkti atsitiktinę vietą j į unshuffled masyvo dalį, aš iki n-1. Taigi, jei aš esu čia, pasirinkti atsitiktinį indeksą tarp čia ir iš masyvo poilsio, ir mes apsikeitimo. Tai kodas, būtina shuffle savo komplekta. Turite klausimų? 

Na, viena reikia Kyla klausimas, kodėl tai teisinga? Kodėl kiekvieną Kėliniai lygiai taip pat tikėtina? Ir aš ne eiti per tai įrodymas, bet gali būti įrodyta per daug problemų, kompiuterių mokslo indukcijos. Kaip daugelis iš jūsų yra susipažinę su indukcijos? Gerai. Cool. Todėl jūs galite įrodyti, kad šio algoritmo teisingumą paprastą indukcijos, ,, kur jūsų indukcija hipotezė būtų daryti prielaidą, kad mano shuffle grįžta kiekvieną Kėliniai lygiai taip pat tikėtina Pirmiausia aš elementų. Dabar i + 1. Ir beje mes renkamės į mūsų indekso j apsikeitimo, tai veda prie - ir tada jums išsiaiškinti detales, bent įrodymas, kodėl šis algoritmas grąžina Kėliniai kiekvienas vienodai tikėtinas tikimybe. 

Viskas gerai, problema. Taigi, "sveikųjų skaičių masyvas, postive, nulis, neigiamas, parašyti funkciją, kuri apskaičiuoja didžiausią sumą iš bet continueous įvesties masyvo subarray ". Čia yra pavyzdys, kad tuo atveju, jei visi skaičiai yra teigiami, šiuo metu geriausias pasirinkimas yra imtis daug įvairių. 1, 2, 3, 4, = 10. Jei turite kokių nors negatyvus ten, šiuo atveju mes tiesiog norime pirmieji du , nes pasirenkant -1 ir / arba -3 atneš mūsų sumą. Kartais mums gali tekti pradėti iš masyvo viduryje. Kartais mes norime pasirinkti nieko bendro, tai geriausia ne imtis nieko. O kartais tai geriau imtis rudenį, nes po jo dalykas yra super didelis. Taigi kokių nors idėjų? (Studentas, neįskaitomai) >> Taip. Tarkime, aš nemanau, -1. Tada arba aš pasirinksiu 1.000 iki 20.000 arba aš tiesiog pasirinkti 3 mlrd. Na, geriausias pasirinkimas yra imtis visų numerių. Tai -1, nepaisant to, kad būdamas neigiamas, visa suma yra geriau, nei aš negaliu imtis -1. Taigi vienas iš patarimų minėjau anksčiau pareikšti, kad visiškai akivaizdu, ir brutalia jėga sprendimas pirmas. Kas yra brutalia jėga šios problemos sprendimas? Taip? [Jane] Na, manau, brute force tirpalo būtų pridėti visus galimus derinius (nesuprantamas). [J.] Gerai. Taigi Jane idėja imtis visų įmanomų Aš tikiu, perfrazuojant - imtis visų įmanomų nuolat subarray apskaičiuoti jo sumą ir tada imtis visų galimų nuolatinių subarrays daugiausiai. Kas unikaliai identifikuoja subarray Mano indėlis masyvo? Pavyzdžiui, ką aš turiu du dalykai? Taip? (Studentas, neįskaitomai) >> Teisingai. Apatinę rodyklės ir viršutinė riba indeksas vienareikšmiškai nustato nuolat subarray. [Moteris studentas] Ar mes įvertinant tai unikalių skaičių masyvas? [J.] L. Taigi savo klausimą, mes darant prielaidą, kad mūsų masyvas - mūsų masyvas visi unikalūs numeriai ir atsakymas yra ne. 

Jei mes naudojame mūsų brute force tirpalą, po pradžios / pabaigos indeksai vienareikšmiškai nustato mūsų nuolat subarray. Taigi, jei mes pakartoti visų galimų pradėti įrašus, ir visiems galutiniams įrašų> arba = pradėti, ir <n, apskaičiuoti sumą, ir tada mes imtis didžiausią sumą, mes matėme iki šiol. Ar tai aišku? Kas yra big O šio tirpalo? Timewise. Ne visai n ^ 2. Atkreipkite dėmesį, kad mes kartoti nuo 0 iki n, kad viena kilpa. Mes vėl pakartoti beveik iš pat pradžių iki galo, o kitą už linijos. Ir dabar, kad mes turime Apibendrinant kiekvieną įrašą, kad kitas už linijos. Taigi, mes turime tris įdėtos kilpos, n ^ 3. Gerai. Tai eina kaip atskaitos tašką. Mūsų sprendimas yra ne blogiau nei n ^ 3. Ar visi supranta, brute force tirpalą? 

Gerai. Geresnis sprendimas yra vadinamas dinaminio programavimo idėja. Pavartojus per CS124, kuri yra algoritmai ir duomenų struktūros, jums bus labai gerai susipažinęs su šia technika. Ir idėja, pabandykite sukurti sprendimus mažesnių problemų. Ką reiškia tai, šiuo metu mes turime nerimauti dėl dviejų dalykų: pradžios ir pabaigos. Ir tai erzina. Ką daryti, jei mes galime atsikratyti vieno iš šių parametrų? Viena idėja yra - mes mūsų problema, rasti didžiausią sumą bet kokio diapazono subarray [O, n-1 metai]. Ir dabar mes turime naują subproblem, kai mes žinome, mūsų dabartinės i indekso mes žinome, privalo sudaryti. Esamo indekso Mūsų subarray turi baigtis. Taigi likusi problema yra, kur reikėtų pradėti mūsų subarray? Ar tai prasminga? Gerai. Taigi aš koduojami tai padaryti, ir pažvelkime, ką tai reiškia. Į codirectory, ten yra programa, vadinama subarray, ir tai trunka elementų skaičių, ir ji grąžina maksimaliai subarray sumą mano išmaišytos sąrašą. Taigi šiuo atveju, mūsų maksimalus subarray yra 3. Ir tai tik naudojant 2 ir 1. Leiskite jį vėl. Jis taip pat 3. Bet šį kartą, atkreipkite dėmesį, kaip mes turime 3. Mes priėmėme - mes tiesiog patį 3 , nes jis apsuptas negatyvų iš abiejų pusių, kuris atneš suma, kurią <3. Leiskite veikti 10 elementų. Šį kartą tai 7, mes imtis lyderio 3 ir 4. Šį kartą tai 8 ir gauname, kad atsižvelgiant 1, 4 ir 3. Taigi, duoti jums apie tai, kaip intuicija problemą, mes galime išspręsti šią transformuoti, Paimkime bent šios subarray išvaizdą. Mes šį įvesties masyvą, ir mes žinome, atsakymas yra 8. Mes priimame 1, 4 ir 3. Bet pažvelkime, kaip mes iš tikrųjų gavo šį atsakymą. Pažvelkime maksimalaus subarray, kuris baigėsi kiekvieną iš šių indeksų. Kas yra maksimalus subarray, kad turi baigtis ne į pirmąją poziciją? [Studentų] Zero. >> Nulis. Tiesiog nereikia vartoti -5. Čia tai bus 0, taip pat. Taip? (Studentas, neįskaitomai) [J.] Oi, atsiprašau, tai yra -3. Taigi tai yra 2, tai yra -3. Gerai. Taip -4, kas, maksimalus subarray baigti šią poziciją kur -4 yra? Nuliui. Vienas? 1, 5, 8. Dabar, aš turi baigtis toje vietoje, kur -2 yra. Taigi, 6, 5, 7, ir naujausia yra 4. Žinant, kad tai yra mano įrašai transformuotų problema, kai aš turi liautis į kiekvieną iš šių indeksų, tada mano galutinis atsakymas yra teisingas, iššluoti per ir maksimalų skaičių. Taigi šiuo atveju tai 8. Tai reiškia,, kad maksimali subarray baigiasi šio rodiklio, ir pradėjo kažkur prieš jį. Ar visi supranta šį transformuoti subarray? 

Gerai. Na, galime išsiaiškinti, už tai nepasikartotų. Apsvarstykite tik pirmuosius kelis įrašai. Taigi čia buvo 0, 0, 0, 1, 5, 8. Ir tada ten buvo -2, ir kad išvedė jį žemyn iki 6. Taigi, jei aš vadinu padėtyje įrašas i subproblem (i), kaip aš galiu naudoti atsakyti į ankstesnį subproblem atsakyti šį subproblem? Jei aš žiūriu, tarkim, šis įrašas. Kaip aš galiu apskaičiuoti atsakymą 6 pažvelgus derinys šio masyvo ir atsakymai į ankstesnes šio masyvo subproblems? Taip? [Moteris studentas] sumų masyvo tokioje padėtyje anksčiau, todėl 8 ir tada jums pridėti esamą subproblem. [J.] Taigi, jos pasiūlymas yra pažvelgti į šių dviejų skaičių, šis skaičius ir šį skaičių. Taigi tai 8 tai už subproblem atsakymui (i - 1). Ir leiskite paskambinti savo įvesties masyvo A Produktais tam kad rasti maksimaliai subarray, kad baigiasi ne i padėtyje, Aš turiu du pasirinkimus: galiu tęsti subarray ankstesniojo indekso, kuris baigėsi, arba pradėti naują masyvą. Jei aš būčiau toliau subarray, kuris prasidėjo ne ankstesniojo indekso, tai maksimali suma, kurią galiu pasiekti yra atsakymas į ankstesnį subproblem pridedant einamąjį masyvo įrašas. Bet aš taip pat turiu pasirinkti pradedant naują subarray tokiu atveju ši suma yra 0. Taigi atsakymas yra max 0, subproblem i - 1, plius dabartinis masyvas įrašas. Ar tai pasikartojimo prasmės? Mūsų pasikartojimas, kaip mes ką tik atrado, yra subproblem i yra lygi praėjusių subproblem ne daugiau, plius mano dabartinis masyvo įrašą, o tai reiškia, tęsti ankstesnę subarray, arba 0, pradėti naują subarray ne mano esamo indekso. Ir kai mes sukūrėme šį sprendimų lentelę, tada mūsų galutinis atsakymas, tiesiog padaryti linijinį nurašymas visoje subproblem masyvo ir maksimalų skaičių. Tai tiksli įgyvendinti tai, ką aš ką tik pasakė. Taigi, mes sukurti naują subproblem masyvą, subproblems. Pirmasis įrašas yra 0 arba pirmasis įrašas, daugiausia iš šių dviejų. Ir kitų subproblems mes naudojame tikslią pasikartojimo, mes ką tik atrado. Dabar mes apskaičiuoti mūsų subproblems masyvo daugiausiai, ir tai yra mūsų galutinis atsakymas. 

Taigi, kiek vietos mes šio algoritmo? Jei jūs tik tuomet, CS50, tada jums gali aptarti vietos labai daug. Na, vienas dalykas, reikia pažymėti, kad aš čia n yra vadinamas malloc. Ką tai rodo jums? Šis algoritmas naudoja tiesinę erdvę. Mes galime padaryti geriau? Ar yra kas nors, kad jūs pastebėsite, kad nereikėtų apskaičiuoti galutinį atsakymą? Manau, geriau klausimas, kokia informacija mes ne reikia atlikti visą kelią iki pabaigos? Dabar, jei pažvelgsime į šių dviejų linijų, rūpi tik ankstesnio subproblem o mes tik rūpintis apie didžiausią mes kada nors matė iki šiol. Apskaičiuoti mūsų galutinio atsakymo, mes nereikia visą masyvą. Mums reikia tik paskutinį numerį, paskutiniai du skaičiai. Paskutinio numerio už subproblem masyvą, ir paskutinis skaičius būtų maksimaliai. Taigi, iš tiesų, mes galime saugiklis šias kilpas kartu ir eiti linijinės erdvėje nuolat erdvėje. Aktualus suma iki šiol, čia pakeičia subproblem, mūsų subproblem masyvo vaidmenį. Taigi dabartinė suma, iki šiol yra atsakymas į ankstesnį subproblem. Ir ta suma, iki šiol užima vietą mūsų maks. Mes apskaičiuoti ne daugiau, kaip mes einame kartu. Ir taip mes einame iš linijinės erdvėje nuolat erdvę, ir mes taip pat turime linijinį mūsų subarray problemos sprendimą. 

Tokie klausimai gausite pokalbio metu. Kiek laiko sudėtingumas; kas yra erdvė sudėtingumas? Jūs galite padaryti geriau? Ar yra dalykų, kurie yra nebūtina išlaikyti aplink? Aš padariau, tai atkreipti dėmesį į tyrimus, kad jums reikia imtis savo kaip jūs dirbate per šių problemų. Visada turi būti užduoti sau klausimą: "Ar galiu tai padaryti geriau?" Iš tiesų, mes galime padaryti geriau nei tai? Rūšiuoti triukas klausimą. Jūs negalite, nes jums reikia bent jau perskaityti prisidėti prie problemos. Taigi tai, kad jums reikia bent jau perskaityti prisidėti prie šios problemos reiškia, kad jūs negalite padaryti geriau ne linijinis, ir jūs negalite padaryti geriau nei nuolat erdvę. Taigi, tai yra, iš tiesų, geriausias šios problemos sprendimas. Turite klausimų? Gerai. 

Vertybinių popierių rinkos problema: "Atsižvelgiant į tai masyvas n sveikieji skaičiai, teigiamas, nulį, arba neigiamas, kurios atstovauja akcijų kaina per n parų, parašyti funkciją apskaičiuoti maksimalų pelną, jūs galite padaryti atsižvelgiant į tai, kad jums pirkti ir parduoti lygiai 1 atsargų per šių n dienų. " Iš esmės, mes norime pirkti mažai, parduoti aukštos. Ir mes norime išsiaiškinti geriausią pelną mes galime padaryti. Grįžtant prie mano galo, kas yra iš karto aišku, paprasčiausias atsakymas, bet tai lėtas? Taip? (Studentas, neįskaitomai) >> Taip. >> Taigi, jūs tiesiog eiti, nors ir pažvelgti akcijų kainų kiekvienas laiko taškas (nesuprantamas). [J.] Gerai, todėl jos sprendimas - jos skaičiavimo pasiūlymas žemiausia ir apskaičiuojant didžiausias nebūtinai dirbti nes aukščiausia gali atsirasti prieš žemiausias. Taigi, kas yra brutalia jėga išspręsti šią problemą? Kokie yra du dalykai, kad man reikia vienareikšmiškai nustatyti pelną? Į dešinę. Brutalia jėga sprendimas - O, taip, Jurgio pasiūlymas, mes tik reikia dvi dienas unikaliai nustatyti šių dviejų dienų pelną. Taigi, mes apskaičiuoti kiekvieną porą, norite pirkti / parduoti, apskaičiuoti pelną, kuris gali būti neigiamas arba teigiamas arba lygus nuliui. Apskaičiuoti maksimalų pelną, kad mes gaminame po iteravimu per visas dienas porų. Tai bus mūsų galutinis atsakymas. Ir kad sprendimas bus O (n ^ 2), nes yra n pasirinkti dvi poros - dienų, kad jūs galite pasirinkti tarp galutinių dienų. Gerai, kad aš nesiruošia čia eiti per brutalia jėga tirpalo. Aš ruošiuosi pasakyti, kad yra n log n sprendimas. , Ką algoritmas jūs dabar žinote, kad yra n log n? Tai nėra triukas klausimas. 

Sujungti rūšiuoti. Sujungti rūšiuoti n log n, ir iš tiesų, vienas iš būdų išspręsti šią problemą yra naudoti sujungti rūšiuoti rūšies idėja vadinosi, apskritai, skaldyk ir valdyk. Ir idėja yra tokia. Norite apskaičiuoti geriausia pirkti / parduoti porą kairę pusę. Rasti geriausius pelno jūs galite padaryti, tik su pirmąja n per dvi dienas. Tada jūs norite oompute geriausia pirkti / parduoti porą dešinėje pusėje, taigi paskutinis n per dvi dienas. Ir dabar kyla klausimas, kaip mes atgal kartu sujungti šiuos sprendimus? Taip? (Studentas, neįskaitomai) >> Gerai. Taigi, leiskite man atkreipti paveikslėlį. Taip? (George, neįskaitomai) >> Būtent. Jurgio sprendimas yra visiškai teisus. Taip, kad jo pasiūlymas yra, pirma apskaičiuoti geriausią pirkti / parduoti porą, ir kad vyksta kairę pusę, todėl galime skambinti, kad į kairę, į kairę. Geriausia pirkti / parduoti porą, esantį dešinėje pusėje. Bet jei mes tik palyginti šiuos du skaičius, mes trūkstamus bylą kur mes perkame ir parduoti kažkur dešinėje pusėje. Mes perkame kairę pusę, parduoti dešinėje pusėje. Ir geriausias būdas apskaičiuoti geriausią pirkti / parduoti porą, kuri apima abi puses yra apskaičiuoti minimalų čia ir apskaičiuoti maksimalų čia ir imtis jų skirtumą. Taigi šių dviejų atvejų, kur pirkti / parduoti porą atsiranda tik čia, tik čia, arba abiejų puselės yra apibrėžta šių trijų skaičių. Taigi, mūsų algoritmas atgal kartu sujungti savo sprendimus, mes norime apskaičiuoti geriausia pirkti / parduoti porą kur mes perkame kairę pusę ir parduoti dešinėje pusėje. Ir geriausias būdas tai padaryti yra apskaičiuoti mažiausią kainą pirmąjį pusmetį, aukščiausia kaina, dešinėje pusėje, ir imtis jų skirtumą. Gautas pelną, šie trys skaičiai, jūs imtis iš trijų daugiausiai kad geriausias pelnas, kurį jūs galite padaryti per šių pirmųjų ir pabaigos dienų. Čia svarbios linijos yra raudonai. Tai rekursinis skambinti apskaičiuoti atsakymą į kairę pusę. Tai yra rekursinis kvietimas apskaičiuoti atsakymą dešinėje pusėje. Tai du kilpų apskaičiuoti MIN ir MAX kairėje ir dešinėje pusėje, atitinkamai. Dabar aš apskaičiuoti pelną, kuris apima abi puses, ir galutinis atsakymas yra daugiausiai iš šių trijų. Gerai. 

Taigi, tikrai, mes turime algoritmą, bet didesnis klausimas, kas yra laikas sudėtingumas? Ir priežastis, kodėl minėjau sujungti rūšiuoti yra tai, kad ši forma padalinti atsakymą į dvi ir tada atgal kartu sujungti savo sprendimus tiksliai Merge sort forma. Taigi, leiskite man eiti per trukmę. Jei mes apibrėžta funkcija T (n) žingsnių skaičius n parų, mūsų du pasikartojantys ragina kiekvieną iš jų kainuos t (n / 2), ir ten yra du iš šių pasiteiravimų. Dabar man reikia apskaičiuoti mažiausiai kairę pusę, Galiu padaryti n / 2 laiko, taip pat dešinėje pusėje daugiausiai. Todėl tai n. Ir tada plius kai nuolatinis darbas. Ir tai pasikartojimo lygtis yra būtent pasikartojimo lygtis sujungti rūšiuoti. Ir mes visi žinome, kad sujungti rūšiuoti n log n laiko. Todėl, mūsų algoritmas taip pat n log n laiko. Ar tai iteracijos prasmės? Tiesiog trumpai primenama apie tai: T (n) žingsnių apskaičiuoti maksimalų pelną per n parų. Būdas, mes padalinti mūsų rekursinių skambučius paskambinę mūsų sprendimas dėl pirmųjų n / 2 dienų kad vienas skambutis, ir tada vėl mes vadiname antrąjį pusmetį. Kad du ragina. Ir tada mes rasti mažiausiai kairėje pusėje, kurį mes galime padaryti eilutėmis, rasti daugiausia dešinėje pusėje, kurį mes galime padaryti eilutėmis. Taigi n / 2 + n / 2 yra tiesiog n. Tada mes turime tam tikrą pastovų darbą, kuris yra kaip daro aritmetines operacijas. Šie požymiai lygtis yra tiksliai sujungti rūšiuoti pasikartojimo lygtis. Taigi, mūsų shuffle algoritmas taip pat n log n. Taigi, kiek vietos naudojate? Eikime vėl į kodą. 

Geresnis klausimas yra, kaip kamino rėmai mes kada nors bet kuriuo momentu? Kadangi mes naudojame rekursija, kamino kadrų skaičius lemia mūsų vietos naudojimą. Apsvarstykite n = 8. Mes vadiname shuffle 8, , kurie kreipsis shuffle pirmieji keturi elementai, kurie kreipsis dėl pirmųjų dviejų įrašų shuffle. Taigi, mūsų kamino - tai mūsų kamino. Ir tada mes vėl skambinti shuffle 1, ir tai, ką mūsų bazinį scenarijų, todėl mes nedelsiant. Ar mes kada nors daugiau nei tai daug kamino kadrų? Nes kiekvieną kartą, kai mes darome pritaikymo, shuffle, rekursinis maldavimas mes padalinti mūsų apimtys per pusę. Taigi didžiausias skaičius kamino kadrų mes kada nors bet kuriuo momentu yra log n kamino kadrų tvarka. Kiekvieno aukšto rėmas yra pastovios vietos , todėl bendra suma erdvės, maksimali suma erdvėje mes kada nors naudoti yra O (log n) erdvė kur n yra dienų skaičius. 

Dabar, visada paklauskite savęs, "Ar mes padaryti geriau?" Ir visų pirma, mes galime sumažinti šią problema jau išspręsta? Patarimas: mes tik aptarti dvi kitas problemas prieš tai, ir tai nebus shuffle. Mes galime paversti šį akcijų rinkos problema į maksimalaus subarray problemos. Kaip mes galime tai padaryti? Vienas iš jūsų? "Emmy"? ("Emmy", neįskaitomai) [J.] Būtent. Taigi maksimalaus subarray problema, mes ieškome sumą, per nepertraukiamą subarray. Ir Emmy pasiūlymas dėl atsargų problemą, apsvarstyti pakeitimus ar deltą. Ir šį paveiksliuką - tai akcijų kaina, bet jei mes priėmėme skirtumą tarp kiekvieną dieną iš eilės - Taigi matome, kad maksimali kaina, maksimalų pelną, mes galime padaryti yra čia, jei mes perkame ir parduoti čia. Bet pažvelkime nuolat pažvelkime tuo subarray problema. Taigi čia, mes galime padaryti - iš čia į čia, mes turime teigiamus pokyčius, o tada eiti iš čia į čia mes turėti neigiamą. Bet tada, iš čia į čia mes turime didžiulį teigiamus pokyčius. Ir tai yra pakeitimai, kad mes norime Apibendrinant gauti mūsų galutinį pelną. Tada mes turime daugiau neigiamų pokyčių. Raktas į sumažinti mūsų atsargų problemą į mūsų maksimaliai subarray problemos atsižvelgti į deltą tarp dienų. Taigi, mes sukurti naują masyvą, vadinamą deltos, inicijuoti pirmąjį įrašą lygus 0, ir tada už kiekvieną deltos (i) leisti, kad skirtumas Mano indėlis array (i), array (i - 1). Tada mes vadiname mūsų įprastą procedūrą maksimalios subarray einančios Delta masyvo. Ir,, nes maksimalus subarray yra linijinė laiko, ir šis sumažėjimas, šis procesas kuriant šį delta masyvo, taip pat linijinis laikas, tada galutinis sprendimas išteklių yra O (n) darbo plius O (n) darbo, vis dar yra O (n) darbo. Taigi, mes turime linijinį laiko problemos sprendimo būdą. Ar visi supranta šią transformaciją? 

Apskritai, gera idėja, kad jūs visada turėtų turėti tai pabandyti sumažinti naują problemą, kad jūs matote. Jei atrodo, susipažinę su senosios problemos, pabandykite susiaurinant jį iki senosios problemos. Ir jei jūs galite naudoti visas priemones, kad jūs, naudojami ant senosios problemos spręsti naują problemą. Taigi, susivynioti, techniniai interviu yra sudėtinga. Tikriausiai kai šios problemos yra daugiau sudėtingų problemų , kad jūs galite pamatyti interviu, todėl, jei jūs neturite suprasti visas problemas, kad aš tiesiog, kuriems viskas gerai. Tai tik keletas iš sudėtingesnių problemų. Praktika, praktika, praktika. Aš davė daug problemų ruošinį, todėl tikrai jas patikrinti. Nuo jūsų interviu ir geros kloties. Visos mano ištekliai yra paskelbtas šią nuorodą, ir vienas iš mano vyresnysis draugų pasiūlė padaryti juoktis techninius interviu todėl, jei jus domina, elektroninio pašto adresas bus Yao tuo elektroninio pašto adresu. Jei turite kokių nors klausimų, galite paklausti. Ar jūs vaikinai turite konkrečius klausimus, susijusius su techninėmis interviu arba kokių nors problemų, mes matėme iki šiol? Gerai. Na, sėkmės ant savo interviu. [CS50.TV]