[Powered by Google Translate] [Seminaari: Tekninen Haastattelut] [Kenny Yu, Harvardin yliopisto] [Tämä on CS50.] [CS50.TV] Hi everyone, olen Kenny. Olen tällä hetkellä nuorempi opiskelee tietotekniikkaa. Olen entinen CS TF, ja olisin halunnut tämän, kun olin Underclassman, ja siksi annan tässä seminaarissa. Joten Toivottavasti nautitte siitä. Tämä seminaari on teknisen haastattelut, ja kaikki minun resurssit löytyvät tästä linkistä, linkki täällä, pari resursseja. Joten tein listan ongelmista, oikeastaan ​​melko vähän ongelmia. Myös yleinen resursseja sivun jossa voimme löytää vinkkejä miten valmistautua haastatteluun, vinkkejä siitä, mitä sinun pitäisi tehdä aikana varsinaista haastattelua, sekä miten lähestyä ongelmia ja resursseja tulevaisuutta varten. Se on verkossa. Ja vain esipuheen tähän seminaariin, vastuuvapauslauseke, näin ei pitäisi - haastattelussa valmistelu ei pitäisi rajoittua tähän luetteloon. Tämä on vain tarkoitus olla opas, ja kannattaa ehdottomasti ottaa kaiken sanon jyvän suolaa, mutta myös käyttää kaiken Käytin auttaa sinua haastattelussa valmistelussa. 

Aion nopeasti läpi muutaman diat jotta voimme saada todellisten tapaustutkimusten. Rakenne haastatteluun ohjelmistojen suunnittelu sijaintisi, tyypillisesti se on 30-45 minuuttia, useita kierroksia, riippuen yrityksen. Usein saat koodaus tussitaulu. Joten valkoinen lauta näin, mutta usein pienemmässä mittakaavassa. Jos sinulla on puhelin haastattelussa, luultavasti käyttää joko collabedit tai Google Doc, jotta he voivat nähdä asut koodaus kun olet haastatellaan puhelimitse. Haastattelu itsessään on tyypillisesti 2 tai 3 ongelmia testaat tietojenkäsittelytiede tietoa. Ja se on lähes varmasti mukana koodausta. Tyyppisiä kysymyksiä, näet yleensä tietorakenteita ja algoritmeja. Ja tekemään tällaisia ​​ongelmia, hän pyytää sinua, pidät, mikä on aikaa ja tilaa monimutkaisuus, iso O? Usein he myös pyytävät korkeamman tason kysymyksiin, niin, suunnittelu-järjestelmä, miten te asetella koodi? Mitä liitäntöjä, mitä luokkia, mitä moduuleja sinulla on järjestelmässä, ja miten nämä vuorovaikutuksessa toisiinsa? Joten tietorakenteet ja algoritmit sekä suunnittelu-järjestelmät. 

Joitakin yleisiä vinkkejä ennen kuin sukeltaa meidän tapaustutkimuksia. Mielestäni tärkein sääntö on aina ajatellut ääneen. Haastattelun on tarkoitus olla tilaisuutesi keuliminen ajattelun prosessi. Kohta haastattelu on haastattelijan mitata miten ajatella ja miten mennä läpi ongelma. Pahinta mitä voi tehdä on olla hiljaa koko haastattelu. Se vain ei ole hyvä. Kun sinulle annetaan kysymys, haluat myös ymmärrä kysymystä. Joten toistan kysymyksen takaisin omin sanoin ja yrittää työskennellä perusteellisesti muutamia yksinkertaisia ​​testitapauksia varmista, että olet ymmärtänyt kysymystä. Työskentely läpi muutamia testitapaukset saat myös intuitio siitä, miten ratkaista tämä ongelma. Saatat jopa löytää joitakin malleja, joiden avulla voit ratkaista ongelman. Heidän suuri kärki on ei turhaudu. Älä turhaudu. Haastattelut ovat haastavia, mutta pahinta mitä voit tehdä, sen lisäksi, että hiljainen, on näkyvästi turhautunut. Et halua antaa sitä vaikutelmaa haastattelija. Yksi asia, joka - niin, monet ihmiset, kun he menevät haastatteluun, he yrittävät yrittää löytää paras ratkaisu on ensimmäisenä, kun oikeasti, siellä on yleensä ilmiselviä ratkaisu. Se voi olla hidasta, se saattaa olla tehotonta, mutta sinun pitäisi vain todeta se, juuri niin sinulla on lähtökohta toimimaan paremmin. Lisäksi, muistuttaa ratkaisu on hidasta, mitattuna Big O aikakompleksisuus tai tilaa monimutkaisuus, osoittaa haastattelijan että ymmärrät näitä asioita kun kirjoitat koodia. Joten älä pelkää keksiä yksinkertaisin algoritmi ensimmäinen ja sitten toimivat paremmin sieltä. Kaikki kysymykset tähän mennessä? Okei. 

Joten sukeltaa ensimmäinen ongelma. "Koska joukko N ​​kokonaislukuja, kirjoittaa funktio, joka sekoittaa erilaisia paikalleen siten, että kaikki permutaatiot n kokonaisluvut ovat yhtä todennäköisiä. " Ja oletetaan, että olet käytettävissä satunnainen kokonaisluku generaattori joka tuottaa kokonaisluku välillä 0-i, puoli-alue. Onko jokainen ymmärtää tämän kysymyksen? Annan teille joukko n kokonaislukuja, ja haluan sinun sekoittaa sitä. Minun hakemistoon, kirjoitin muutamia ohjelmia osoittamaan mitä tarkoitan. Aion sekoittaa erilaisia ​​20 osia, -10-9, ja haluan sinun tulostaa listan näin. Joten tämä on minun lajiteltu tulo array, ja haluan sinun sekoittaa sitä. Teemme sen uudestaan. Onko jokainen ymmärrä kysymystä? Okei. Joten se on sinun. Mitkä ovat joitakin ideoita? Voitko tehdä sen n ^ 2, n log n, n? Avoin ehdotuksille. Okei. Eli yksi ajatus, ehdotti Emmy, on ensin laskemaan satunnaisluku, satunnainen kokonaisluku, joka vaihtelee 0-20. Joten kantamaan array pituus on 20. Meidän kaavio 20 osia, Tämä on meidän tulo array. Ja nyt hänen ehdotus on luoda uuden taulukon, joten tämä on lähtö array. Ja perustuu i palauttamat rand - joten jos olin, sanotaanko, 17, kopioida 17. elementin ensimmäisessä asennossa. Nyt täytyy poistaa - Meidän täytyy siirtää kaikki elementit tässä yli niin, että meillä on rako lopussa ja ei reikiä keskellä. Ja nyt me toista prosessi. Nyt haemme uutta satunnainen kokonaisluku väliltä 0 ja 19. Meillä on uusi i täällä, ja me kopioi tämä elementti tähän asentoon. Sitten siirtää kohteita yli ja toistamme, kunnes meillä on täysi new Array. Mikä on ajoaika tämä algoritmi? No, pitävät vaikutusta tämän. Olemme siirtymässä jokaisen elementin. Kun me poistaa tämän minä olemme siirtymässä kaikki elementit sen jälkeen vasemmalle. Ja joka on O (n) kustannukset sillä mitä jos me poistamme ensimmäisen osan? Joten Kunkin poiston, poistamme - Kunkin poiston aiheutuu O (n) toimintaa, ja koska meillä on n muutto, tämä johtaa O (n ^ 2) shuffle. Okei. Joten hyvä alku. Hyvä alku. 

Toinen ehdotus on käyttää jotain kutsutaan Knuth shuffle, tai Fisher-Yates shuffle. Ja se on todella lineaarisen ajan shuffle. Ja idea on hyvin samankaltainen. Jälleen meillä on tulo array, mutta sen sijaan, että käytetään kahta paneelit meidän input / output, käytämme ensimmäisen osan array seurata myös sekoitetaan osa, ja me seurata, ja sitten jätämme loput meidän matriisia unshuffled osan. Joten tässä mitä minä tarkoitan. Aloitamme pois - päätämme i, array 0-20. Nykyinen osoitin osoittaa ensimmäisen indeksin. Valitsemme muutamia i täällä ja nyt vaihtaa. Joten jos tämä oli 5, ja tämä oli 4, Tuloksena array on 5 täällä ja 4 täällä. Ja nyt huomaamme merkki tästä. Kaikkea vasemmalla on sekoitetaan, ja kaiken oikealla on unshuffled. Ja nyt voimme toistaa prosessin. Valitsemme satunnaisesti indeksi väliltä 1 ja 20 nyt. Joten kai uusi i on täällä. Nyt vaihtaa tätä olen meidän nykyinen uuteen paikkaan täällä. Joten meillä vaihtamalla edestakaisin näin. Saanen tuoda esille koodin tekemään konkreettisempaa. Aloitamme myös valita I - aloitamme I on 0, haemme satunnaiseen paikkaan j että unshuffled osaan array, i n-1. Joten jos olen täällä, valitse satunnainen indeksin välillä täällä ja muualla array, ja me vaihtaa. Tämä on kaikki koodi tarvitaan shuffle array. Kysyttävää? 

No, tarvittiin kysymys on, miksi on näin? Miksi jokainen permutaatio yhtä todennäköistä? Enkä mene läpi todisteita, mutta monia ongelmia tietojenkäsittelytieteessä voidaan todistaa induktion kautta. Kuinka moni teistä tuntevat induktio? Okei. Cool. Joten voit todistaa oikeellisuutta tämän algoritmin yksinkertaisella induktio, missä induktio hypoteesi olisi, olettaa, että minun shuffle palauttaa kaikki permutaatio yhtä todennäköisiä ensimmäiseen i elementtejä. Nyt harkita i + 1. Ja miten me valitsemme indeksi j vaihtaa, tämä johtaa - ja sitten treenata yksityiskohtia, ainakin täynnä todiste miksi tämä algoritmi palauttaa jokainen permutaatio kanssa yhtä todennäköistä todennäköisyydellä. 

Selvä, seuraava ongelma. Joten "annetaan joukko kokonaislukuja, postive, nolla, negatiivinen, Kirjoita funktio, joka laskee suurimman summan minkä tahansa continueous subarray tulon array ". Esimerkkinä tästä on, että tapauksessa, jossa kaikki luvut ovat positiivisia, Sitten hetkellä paras vaihtoehto on ottaa koko joukko. 1, 2, 3, 4, vastaa 10. Kun sinulla on joitakin negatiivisia siellä, Tässä tapauksessa haluamme vain kaksi ensimmäistä koska valitsemalla -1 ja / tai -3 tuo meidän summa alas. Joskus saatamme joutua aloittaa keskellä array. Joskus haluamme valita mitään, se on parasta olla ottamatta mitään. Ja joskus on parempi ottaa syksyllä, koska asia, kun se on super iso. Joten mitään ideoita? (Opiskelija, käsittämätön) >> Joo. Oletetaan En ota -1. Sitten joko Valitsen 1000 ja 20000, tai minä vain valita 3000000000. No, paras valinta on toteutettava kaikki numerot. Tämä -1, huolimatta negatiivinen, Koko summa on parempi kuin olivat minun olla ottamatta -1. Eli yksi vinkkejä mainitsin aiemmin oli todeta selvästi ilmeinen ja brute force ratkaisu on ensimmäisenä. Mikä on brute force ratkaisu tähän ongelmaan? Niin? [Jane] Luulen brute force ratkaisu olisi lisätä kaikkia mahdollisia yhdistelmiä (käsittämätön). [Yu] Okei. Joten Janen ajatus on tehdä kaikki mahdollinen - Olen mukaillen - on tehdä kaikki mahdollinen jatkuva subarray, laskea sen summa, ja sitten ottaa enintään kaikki mahdolliset jatkuvan subarrays. Mikä yksilöi subarray minun panos array? Kuten, mitä kaksi asiaa tarvitsen? Niin? (Opiskelija, käsittämätön) >> Oikea. Alaraja indeksi ja yläraja indeksi yksikäsitteisesti määrittää jatkuvan subarray. [Female student] Olemmeko arvioimiseksi se jono ainutlaatuisia numeroita? [Yu] No Joten hänen kysymykseen, olemmeko olettaen meidän array - on meidän array kaikki ainutlaatuisia numerot, ja vastaus on ei. 

Jos käytämme brute force ratkaisu, niin alku / loppu indeksit yksikäsitteisesti määrittää jatkuvan subarray. Joten jos me kerrata kaikki mahdollinen alku merkinnät, ja kaikki loppu merkinnät> tai = aloittaa, ja <n, sinä laskea summan, ja sitten otamme enimmäismäärä olemme nähneet tähän mennessä. Onko tämä selvä? Mikä on iso O tämän ratkaisun? Ajallisesti. Ei ihan n ^ 2. Huomaa, että me iteroida 0-n, niin se on yksi silmukka. Me toistaa jälleen lähes alusta loppuun, toinen silmukka. Ja nyt, tuossa meidän on tiivistää jokaisen merkinnän, niin se on toinen silmukka. Joten meillä on kolme sisäkkäistä silmukoita, n ^ 3. Okei. Tämä menee lähtökohtana. Ratkaisumme ei ole pahempaa kuin n ^ 3. Onko jokainen ymmärtää brute force ratkaisu? 

Okei. Parempi ratkaisu on käyttää idea nimeltään dynaaminen ohjelmointi. Jos otat CS124, joka on algoritmit ja tietorakenteet, sinusta tulee hyvin perehtynyt tähän tekniikkaan. Ja ajatus on, yritä rakentaa ratkaisuja pienempiä ongelmia ensin. Mitä tarkoitan tällä sitä, meillä on tällä hetkellä huolehtia kahdesta asiasta: alku ja loppu. Ja se on ärsyttävää. Mitä jos voisimme päästä eroon yksi niistä parametreista? Yksi idea on - Me olemme antaneet alkuperäinen ongelma, löytämään suurimman summan tahansa subarray useilla [O, n-1]. Ja nyt meillä on uusi subproblem, missä me tiedämme, meidän nykyisessä indeksin i, tiedämme on pääteltävä siellä. Meidän subarray tulee päättyä indeksin. Joten jäljellä ongelma on, missä meidän pitäisi aloittaa meidän subarray? Onko tämä järkevää? Okei. Joten olen koodattu tähän asti, ja katsotaanpa, mitä tämä tarkoittaa. Vuonna codirectory, siellä ohjelma nimeltä subarray, ja se kestää useita kohteita, ja se palauttaa maksimaalista subarray summa minun sekoitetaan luettelossa. Joten tässä tapauksessa, meidän maksimaalinen subarray on 3. Ja se on ottanut vain käyttämällä 2 ja 1. Katsotaanpa käyttää sitä uudelleen. Se on myös 3. Mutta tällä kertaa, huomata kuinka saimme 3. Otimme - me vain ottaa itse 3 koska se ympäröi negatiivit molemmin puolin, joka tuo summa <3. Katsotaanpa ajaa 10 kohdetta. Tällä kertaa se on 7, otamme johtava 3 ja 4. Tällä kertaa se on 8, ja saamme että ottamalla 1, 4 ja 3. Joten antaa sinulle intuitio siitä, miten voimme ratkaista tämän muuntaa ongelman, Katsotaanpa katsomaan tätä subarray. Olemme antaneet tämän tulon array, ja me tiedämme, vastaus on 8. Otamme 1, 4, ja 3. Mutta katsokaamme miten me loppujen lopuksi saimme vastauksesta. Katsokaamme maksimaalinen subarray päättyneen jokaisessa näistä indekseistä. Mikä on maksimaalinen subarray, joka on lopettaa ensimmäisessä asennossa? [Student] Zero. >> Zero. Kunhan et ota -5. Tässä se tulee olemaan 0 samoin. Niin? (Opiskelija, käsittämättömällä) [Yu] Anteeksi, se on -3. Joten tämä on 2, tämä on -3. Okei. Joten -4, mikä on maksimaalinen subarray lopettaa tähän asemaan missä -4 on? Zero. Yksi? 1, 5, 8. Nyt minun täytyy lopettaa siihen paikkaan, jossa -2 on. Joten 6, 5, 7, ja viimeinen on 4. Tietäen, että nämä ovat minun merkinnät varten muunnettava ongelma, jossa minun on päätyttävä Jokaiseen näistä indekseistä, sitten minun viimeinen vastaus on vain, ottaa lakaista koko, ja ottaa enimmäismäärä. Joten tässä tapauksessa se on 8. Tämä merkitsee sitä, että maksimaalinen subarray päättyy tämän indeksin, ja alkoi jonnekin ennen. Onko kaikki ymmärtävät tämän muuttaneet subarray? 

Okei. No, selvittää toistumisen tätä. Tarkastellaan vain muutaman ensimmäisen merkinnät. Joten tässä se oli 0, 0, 0, 1, 5, 8. Ja sitten oli -2 täällä, ja että toi se alas 6. Joten jos soitan maahantulo asennossa I subproblem (i), miten voin käyttää vastaus edelliseen subproblem vastata tähän subproblem? Jos katson, sanotaanko, tämä merkintä. Miten voin laskea vastauksen 6 katsomalla Yhdistelmä tämän array ja vastaukset edelliseen tutkimusongelmia tässä array? Kyllä? [Female student] Otat joukko summien asennossa juuri ennen sitä, joten 8, ja sitten lisäät nykyisen subproblem. [Yu] Joten hänen ehdotus on tarkastella nämä kaksi lukua, tämä numero ja tämä numero. Joten tämä 8 viittaa vastaus subproblem (i - 1). Ja kutsukaamme minun panos array A. Jotta löydettäisiin maksimaalisen subarray, joka päättyy asemassa i, Minulla on kaksi vaihtoehtoa: Voin joko jatkaa subarray päättyneen edellisen indeksin tai aloittaa uuden taulukon. Jos olisin jatkaa subarray alkanut edellisessä indeksi, Sitten enimmäismäärä voin saavuttaa on vastaus edelliseen subproblem plus nykyinen array merkintä. Mutta minulla on myös valita aloittaa uuden subarray, jolloin summa on 0. Joten vastaus on max 0, subproblem I - 1, sekä nykyinen array merkintä. Onko tämä toistumisen järkeä? Meidän toistumisen, kuten juuri löydetty, on subproblem i on yhtä suuri kuin suurin edellisen subproblem plus minun nykyinen array merkintä, mikä tarkoittaa sitä, jatkaa edellistä subarray, tai 0, aloita uusi subarray minun indeksin. Ja kun olemme rakentaneet tämän taulukon ratkaisuja, niin meidän lopullinen vastaus, vain tehdä lineaarisen lakaista koko subproblem array ja ottaa enimmäismäärä. Tämä on tarkka täytäntöönpano mitä juuri sanoin. Joten luomme uuden subproblem array, tutkimusongelmia. Ensimmäinen merkintä on joko 0 tai ensimmäisen maahantulon, enintään näiden kahden. Ja loput tutkimusongelmia käytämme tarkan toistumisen me juuri löytänyt. Nyt laskemme enintään meidän tutkimusongelmia array, ja se on meidän lopullinen vastaus. 

Joten kuinka paljon tilaa käytämme tässä algoritmissa? Jos olet vain ottanut CS50, niin et ehkä ole keskusteltu tilaa hyvin paljon. No, yksi asia huomata on, että pyysin malloc täällä koko n. Mitä se ehdottaa sinulle? Tämä algoritmi käyttää lineaarista tilaa. Me voisimme tehdä paremmin? Onko mitään, huomaat, että on tarpeen laskea lopullisen vastauksen? Oletan parempi kysymys on, mitä tietoja emme tarvitse kuljettaa aina loppuun asti? Nyt, jos me tarkastelemme näitä kahta riviä, me vain välitä edellisen subproblem, ja me vain välitä maksimi olemme koskaan nähneet tähän mennessä. Laske meidän lopullinen vastaus, emme tarvitse koko jono. Meidän tarvitsee vain viimeinen numero, kaksi viimeistä numeroa. Viime numero subproblem array, ja viimeinen numero maksimi. Niin, itse asiassa, voimme sulake nämä silmukat yhteen ja menevät lineaarisen avaruuden jatkuvasti avaruuteen. Nykyinen summa toistaiseksi täällä, korvaa rooli subproblem, meidän subproblem array. Joten nykyinen summa, toistaiseksi, on vastaus edelliseen subproblem. Ja että summa, tähän asti, otetaan paikka meidän max. Me lasketaan suurimman matkan varrella. Ja niin menemme lineaarisen avaruuden jatkuvasti tilaa, ja meillä on myös lineaarinen ratkaisu meidän subarray ongelma. 

Tällaiset kysymykset saat haastattelussa. Mikä on aika monimutkainen, mikä on avaruuden monimutkaisuus? Osaatko paremmin? Onko olemassa asioita, jotka ovat tarpeettomia pitää noin? Tein tämän korostaa analyyseihin, että sinun pitäisi ottaa oma koska olet työskennellyt läpi näitä ongelmia. Aina kysyä itseltäsi, "Voinko tehdä paremmin?" Itse me voisimme tehdä paremmin kuin tämä? Tavallaan temppu kysymys. Et voi, koska sinun täytyy ainakin lukea tulo ongelma. Niin että sinun täytyy ainakin lukea tulo ongelma tarkoittaa, että et voi tehdä paremmin kuin lineaarisen ajan, ja et voi tehdä paremmin kuin vakio tilaa. Joten tämä on, itse asiassa, paras ratkaisu tähän ongelmaan. Kysymyksiä? Okei. 

Osakemarkkinat ongelma: "Koska joukko N ​​kokonaislukuja, positiivinen, nolla tai negatiivinen, jotka edustavat hinta varastossa yli n päivää, kirjoita funktio laskea maksimaalisen voiton voit tehdä koska voit ostaa ja myydä tasan 1 varastosta näiden n päivää. " Pohjimmiltaan haluamme ostaa pieni, myydä korkea. Ja haluamme selvittää paras tulos voimme tehdä. Going takaisin minun kärki, mikä on heti selvä, yksinkertaisin vastaus, mutta se on hidasta? Kyllä? (Opiskelija, käsittämätön) >> Kyllä. >> Joten te vain mennä vaikka katsomaan pörssikursseja jokaisessa vaiheessa (käsittämätön). [Yu] Okei, joten hänen ratkaisu - hänen ehdotusta computing alin ja lasketaan korkeimman ei välttämättä toimi koska korkein saattaa tapahtua ennen alhaisin. Joten mikä on brute force ratkaisu tähän ongelmaan? Mitkä ovat kaksi asiaa, jotka minun täytyy yksiselitteisesti määrittää voitto teen? Oikea. Brute force ratkaisu on - ah, niin, George ehdotus on meidän tarvitsee vain kaksi päivä yksilöllisesti määritellä voiton näiden kahden päivän aikana. Joten me laskea jokaista paria, haluan ostaa / myydä, laskea tulos, joka voi olla negatiivinen tai positiivinen tai nolla. Laske suurin voitto, että teemme jälkeen iteroimalla kaikkien paria päivää. Se on meidän lopullinen vastaus. Ja että ratkaisu on O (n ^ 2), koska siellä on n valittava kaksi paria - päivän että voit valita loppu päivän. Okei, joten en aio mennä yli brute force ratkaisua. Aion kertoa teille, että on olemassa n log n ratkaisu. Mitä algoritmi sinä nyt tiedät että on n log n? Se ei ole temppu kysymys. 

Yhdistä lajitella. Yhdistä sort on n log n, ja itse asiassa yksi tapa ratkaista tämä ongelma on käyttää Yhdistämisen eräänlainen eräänlainen idea kutsutaan yleensä hajoita ja hallitse. Ja idea on seuraava. Haluat laskea parhaan osta / myy pari vasemmalla puolella. Löydä parhaat voittoa voit tehdä, pelkästään ensimmäiset n kahden päivän aikana. Sitten haluat oompute paras osta / myy pari oikealla puolella, niin, että viimeinen n kahden päivän aikana. Ja nyt kysymys on, miten voimme yhdistää nämä ratkaisut takaisin yhteen? Kyllä? (Opiskelija, käsittämättömällä) >> Okei. Joten haluan piirtää kuvan. Kyllä? (George, käsittämättömällä) >> Aivan. George ratkaisu on juuri oikea. Joten hänen ehdotuksestaan ​​on ensin laskea paras ostaa / myy pari, ja että esiintyy vasemmalla puolella, joten kutsukaamme että vasen, vasen. Best Buy / myydä pari joka esiintyy oikealla puolella. Mutta jos me vain verrataan nämä kaksi lukua, meiltä puuttuu asian jos ostamme täällä ja myydä jonnekin oikealla puolella. Ostamme vasemmalla puolella, myydä oikealla puolella. Ja paras tapa laskea parhaan Osta / myy pari joka kattaa molemmat puoliskot on laskea pienin tässä ja laskea maksimi tässä ja ottaa niiden erotus. Joten kaksi tapausta, joissa Osta / myy pari esiintyy vain täällä, Vain tässä, tai molemmat puoliskot on määritelty näitä kolme numeroa. Joten meidän algoritmi yhdistää ratkaisumme takaisin yhteen, haluamme laskea Best Buy / sell pari jos ostamme vasemmalla puoli ja myydä oikealla puoli. Ja paras tapa tehdä se on laskea alin hinta alkupuoliskolla, korkein hinta oikea puoli, ja ottavat eron. Tuloksena kolme voittoa, nämä kolme numeroa, otat enintään kolme, ja se on parasta voittoa voit tehdä näinä ensimmäinen ja pää vuorokautta. Täällä tärkeät linjat ovat punaisella. Tämä on rekursiivinen puhelun laskea vastaus vasemmalla puolella. Tämä on rekursiivinen puhelun laskea vastaus oikea puoli. Nämä kaksi silmukkaa laskea min ja max vasemmalla ja oikealla puoli, vastaavasti. Nyt olen laskea voitto, joka ulottuu molemmat puoliskot, ja lopullinen vastaus on suurin näistä kolmesta. Okei. 

Niin, että meillä on algoritmi, mutta isompi kysymys on, Mikä on aika monimutkainen? Ja syy miksi mainitsin Merge sort että tämä muoto jakaa vastaus kahteen ja sitten yhdistämällä ratkaisumme takaisin yhteen Juuri muoto merge sort. Joten anna minun mennä läpi kestoa. Jos me määritelty funktio t (n) olevan useita vaiheita N päivää, meidän kaksi rekursiivinen puhelut ovat kukin tulee maksamaan t (n / 2), ja siellä on kaksi puheluista. Nyt minun täytyy laskea vähintään vasen puoli, jonka voin tehdä N / 2 kertaa, sekä enintään oikea puoli. Joten tämä on vain N. Ja sitten plus joitakin jatkuvaa työtä. Ja tämä toistumisen yhtälö Juuri toistumisen yhtälö merge sort. Ja me kaikki tiedämme, että Merge sort on n log n aikaa. Näin ollen meidän algoritmi on myös N log N aikaa. Onko tämä iteraatio järkeä? Vain lyhyt kertaus tämän: T (n) on useita vaiheita laskea maksimi voitto aikana n päivän. Tapamme jakaa meidän rekursiivinen puhelut on soittamalla ratkaisun ensimmäiset n / 2 päivää, niin että yksi puhelu, ja sitten me kutsumme jälleen jälkipuoliskolla. Joten se kaksi puhelua. Ja sitten löydämme vähintään vasemmalla puoli, jonka voimme tehdä lineaarisessa ajassa, löytää enintään oikea puoli, jonka voimme tehdä lineaarisessa ajassa. Niin n / 2 + n / 2 on vain n. Sitten meillä on jatkuvaa työtä, joka on kuin tekee aritmeettinen. Tämä toistumisen yhtälö on täsmälleen toistumisen yhtälö merge sort. Siksi meidän shuffle algoritmi on myös N log N. Joten kuinka paljon tilaa käytämme? Mennään takaisin koodia. 

Parempi kysymys on, kuinka monta pino kehyksiä meillä koskaan ole joka hetki? Koska käytämme rekursio, määrä pinon kehysten määrää meidän tilankäytön. Tarkastellaan n = 8. Kehotamme shuffle päälle 8, jotka vaativat shufflen neljä ensimmäistä merkinnät, jotka vaativat shufflen ensimmäiset kaksi merkintää. Joten meidän pino on - tämä on meidän pino. Ja sitten me kutsumme shuffle jälleen 1, ja sitähän meidän tukikohta tapauksessa, joten palaamme välittömästi. Onko meillä koskaan yli tästä monet pino kehyksiä? No koska aina teemme vetoaminen, rekursiivinen vetoaminen sekoittaa, jaamme koko puoli. Joten maksimimäärä pino kehyksiä meillä koskaan on joka hetki on luokkaa log n pino kehyksiä. Jokaisella pinokehys on vakio tilaa, ja näin ollen tilan määrän, enimmäismäärä avaruuden koskaan käytä on O (log n) tilan jossa n on päivien määrä. 

Nyt, kysy itseltäsi, "me voisimme tehdä paremmin?" Ja erityisesti, voimme vähentää tätä ongelmaa olemme jo ratkaistu? Vihje: me vain keskustella kaksi muuta ongelmia ennen tätä, ja se ei tule olemaan sekoittaa. Voimme muuntaa tämän osakemarkkinoilla ongelma otetaan maksimaalinen subarray ongelma. Miten voimme tehdä tämän? Yksi teistä? Emmy? (Emmy, käsittämättömällä) [Yu] Aivan. Joten maksimaalinen subarray ongelma, Etsimme summan yli jatkuva subarray. Ja Emmy n ehdotus kantojen ongelma, harkita muutoksia tai delta. Ja kuva on - tämä on hinta varastossa, mutta jos otimme eron jokaisen peräkkäisen päivän - niin näemme, että enimmäishinta, suurin voitto voisimme tehdä on jos ostaa täällä ja myyvät täällä. Mutta katsokaamme jatkuvan - katsokaamme subarray ongelmaa. Joten tässä, voimme tehdä - menee tästä tänne, meillä on positiivinen muutos, ja sitten menee täällä meillä on tässä negatiivinen muutos. Mutta sitten, menee täällä meillä on tässä valtava positiivinen muutos. Ja nämä ovat muutoksia, jotka haluamme tiivistää saadaksemme lopullisen voiton. Sitten meillä on enemmän kielteisiä muutoksia täällä. Avain vähentää meidän varastossa ongelma meidän maksimaalinen subarray ongelma on tarkastella deltat päivien välillä. Joten luomme uuden array nimeltään delta- alustaa ensimmäinen merkintä on 0, ja sitten kunkin delta (i), anna sen olla ero minun tulo array (i), ja array (i - 1). Sitten me kutsumme rutiininomaisesti maksimaalisen subarray ohimennen Deltan array. Ja koska maksimaalinen subarray on lineaarinen aika, ja tämä vähennys, tämä luomassa tätä delta array, On myös lineaarisen ajan, sitten lopullinen ratkaisu kantojen O (n) työ plus O (n) työ on edelleen O (n) työhön. Joten meillä on lineaarisen ajan ratkaisu meidän ongelmaan. Onko kaikki ymmärtävät tämän muutoksen? 

Yleensä hyvä ajatus, että sinun pitäisi aina olla on pyrittävä vähentämään uusi ongelma, jonka te näette. Jos se näyttää tutulta vanha ongelma, yrittää vähentää sitä vanhaa ongelmaa. Ja jos voit käyttää kaikkia välineitä, jotka olet käyttänyt vanhan ongelman ratkaisemaan uuden ongelman. Joten kääriä, tekniset haastattelut ovat haastavia. Nämä ongelmat ovat todennäköisesti joitakin vaikeampia ongelmia että saatat nähdä haastattelussa, joten jos et ymmärrä kaikkia ongelmia, että olen juuri peittyy, se on okei. Nämä ovat joitakin haastavampia ongelmia. Harjoittele, harjoittele, harjoittele. Annoin paljon ongelmia moniste, joten ehdottomasti tarkistaa ne pois. Ja onnea teidän haastatteluihin. Kaikki minun resurssit löytyvät tästä linkistä, ja yksi minun vanhempi ystäviä on tarjoutunut tekemään pilkkaa teknisiä haastatteluja, joten jos olet kiinnostunut, sähköposti Yao tuohon sähköpostiosoitteeseen. Jos sinulla on kysyttävää, voit kysyä minulta. Onko teillä erityisiä kysymyksiä, jotka liittyvät tekniseen haastattelut tai ongelmia olemme nähneet tähän mennessä? Okei. No, onnea teidän haastatteluihin. [CS50.TV]