[Powered by Google Translate] [Seminar: Teknikal Panayam] [Kenny Yu, Harvard University] [Ito ay CS50.] [CS50.TV] Hi lahat, ako Kenny. Ako ay kasalukuyang isang junior pag-aaral computer science. Ako ng dating CS tf, at nais ko ako ay may ito kapag ako ay isang underclassman, at na kung bakit ako pagbibigay ito seminar. Kaya Umaasa ako na masisiyahan ka ito. Seminar na ito ay tungkol sa mga panteknikal na panayam, at sa lahat ng aking mga mapagkukunan ay maaaring matagpuan sa link na ito, ang link na ito dito mismo, ng ilang mga mapagkukunan. Kaya ko gumawa ng listahan ng mga problema, aktwal na, lubos ng ilang mga problema. Din ng pangkalahatang mga mapagkukunan ng pahina kung saan maaari naming mahanap ang mga tip sa kung paano upang maghanda para sa isang pakikipanayam, mga tip sa kung ano ang dapat mong gawin sa panahon ng isang aktwal na panayam, pati na rin kung paano lapitan ng mga problema at mga mapagkukunan para sa sanggunian sa hinaharap. Ang lahat ng ito online. At lang lagyan ng paunang salita ang seminar na ito, isang disclaimer, tulad ng ito ay dapat hindi - ang iyong paghahanda sa panayam hindi dapat limitado sa listahang ito. Lamang ito ay nilalayong maging isang gabay, at dapat mong tiyak ang lahat ng sinasabi ko na may isang butil ng asin, ngunit ring gamitin ang lahat ng ginamit ko upang makatulong sa iyo sa iyong paghahanda ng panayam. Pupunta ako upang mapabilis sa pamamagitan ng susunod na ilang mga slide upang maaari naming makapunta sa aktwal na mga pag-aaral ng kaso. Ang istraktura ng isang pakikipanayam para sa isang postion ng software engineering, ito ay karaniwang 30 sa 45 minuto, maramihang mga round, depende sa kumpanya. Madalas makikita mo ang coding sa isang puting board. Kaya isang puting board tulad nito, ngunit madalas sa isang mas maliit na scale. Kung nagkakaroon ka ng isang telepono pakikipanayam, malamang na gumagamit alinman collabedit o ng isang Google Doc sa gayon ay maaari nilang makita na Live coding habang ikaw ay kapanayamin sa telepono. Isang pakikipanayam mismo ay karaniwang 2 o 3 mga problema pagsubok ng kaalaman ng iyong computer science. At ito ay halos tiyak na sangkot sa coding. Ang mga uri ng mga katanungan na makikita mo ay karaniwang data istraktura at algorithm. At sa paggawa ng mga ganitong uri ng mga problema, sila tanungin mo, i, kung ano ang oras at pagiging kumplikado ng espasyo, malaki O? Madalas din nila magtanong ng mga mas mataas na antas na mga katanungan, ito, pagdidisenyo ng isang sistema, kung paano mo lay ang iyong code? Ano ang interface, kung ano ang klase, kung ano ang module mayroon ka sa iyong system, at paano ang mga nakikipag-ugnayan nang magkasama? Kaya data istraktura at algorithm pati na rin ang pagdidisenyo system. Ilang pangkalahatang mga tip bago namin sumisid sa sa aming mga pag-aaral ng kaso. Tingin ko ang pinaka-mahalagang panuntunan ay laging iniisip ang malakas. Pakikipanayam ay dapat na ang iyong pagkakataon upang ipakita ang iyong proseso sa pag-iisip. Ang punto ng pakikipanayam para sa tagapanayam upang masukat kung paano sa tingin mo at kung paano kang pumunta sa pamamagitan ng isang problema. Ang pinakamasama bagay na maaari mong gawin ay maging tahimik sa buong buong pakikipanayam. Na lang walang magandang. Kapag ikaw ay bibigyan ng isang katanungan, gusto mo ring upang tiyakin na nauunawaan mo ang tanong. Kaya ulitin ang tanong sa iyong sariling mga salita at pagtatangka upang gumana masinsinang ng ilang simpleng mga kaso ng pagsubok upang tiyakin na nauunawaan mo ang tanong. Paggawa sa pamamagitan ng ilang mga kaso ng pagsubok ay magbibigay sa iyo ng isang Swersey sa kung paano malutas ang problemang ito. Maaari mo ring matuklasan ng ilang mga pattern upang makatulong sa iyo na malutas ang problema. Ang kanilang malaking tip ay hindi bigo. Huwag bigo. Panayam ay mapaghamong, ngunit ang pinakamasama bagay na maaari mong gawin, sa karagdagan sa pagiging tahimik, ay nahahalata bigo. Hindi mo nais na magbigay na impression sa isang tagapanayam. Isang bagay na - ito, maraming mga tao, kapag sila ay pumunta sa isang pakikipanayam, tinangka nilang subukan upang mahanap ang pinakamahusay na solusyon sa unang, kapag talaga, may karaniwang isang nandidilat halata na solusyon. Maaaring maging mabagal, maaaring ito ay hindi mabisa, ngunit dapat mo lamang ihayag ito, lamang kaya mayroon kang isang panimulang punto kung saan ay mas mahusay. Gayundin, pagturo out ang solusyon ay mabagal, sa mga tuntunin ng malaking O oras kumplikado o pagiging kumplikado ng espasyo, ay nagpapakita sa tagapanayam na nauunawaan mo mga isyung ito kapag sumusulat code. Kaya huwag matakot upang makabuo ng ang pinakasimpleng algorithm unang at pagkatapos ay mas mahusay mula doon. Anumang mga katanungan sa ngayon? Okay. Kaya natin sumisid sa aming unang problema. "Dahil isang array ng mga integer n, magsulat ng isang function na shuffles ang array sa lugar tulad na ang lahat ng mga permutations ng integer n pantay malamang. " At angkinin mayroon kang makuha ang isang random generator integer na bumubuo ng isang integer sa isang hanay mula 0 hanggang i, kalahati hanay. Ba ang lahat maunawaan ang tanong na ito? Ako magbibigay sa iyo ng isang array ng mga integer n, at Gusto kong shuffle ito. Sa aking direktoryo, ako nagsulat ng ilang mga programa upang ipakita kung ano ang ibig sabihin ko. Pupunta ako sa shuffle isang array ng 20 mga elemento, mula sa -10 sa 9, at gusto kong mong output ng listahan tulad nito. Kaya ito ay aking pinagsunod-sunod input array, at Gusto kong shuffle ito. Susubukan naming gawin itong muli. Ba ang lahat maunawaan ang tanong? Okay. Kaya ito ay hanggang sa iyo. Ano ang ilang mga ideya? Maaari mong gawin ito bilang n ^ 2, n log n, n? Buksan sa mga mungkahi. Okay. Kaya isang ideya, na iminungkahi ng Emmy, compute muna ng random na numero, random ng integer, sa isang hanay mula 0 hanggang 20. Kaya ipagpalagay aming array ay may haba ng 20. Sa aming diagram ng 20 elemento, ito ang aming input array. At ngayon, ang kanyang mga mungkahi ay upang lumikha ng isang bagong array, kaya ito ay ang output ng array. At batay sa i ibinalik sa pamamagitan ng ribete - kaya kung i ay, sabihin nating, 17, kopyahin ang ika-17 na elemento sa unang posisyon. Ngayon ay kailangan naming tanggalin - kailangan namin upang ilipat ang lahat ng mga elemento dito sa paglipas ng sa gayon ay mayroon kaming isang agwat sa dulo at walang butas sa gitna. At ngayon namin ulitin ang proseso. Ngayon namin pumili ng isang bagong random integer sa pagitan ng 0 at 19. Mayroon kaming isang bagong i dito, at kopyahin namin ang elemento na ito sa posisyon na ito. Pagkatapos namin shift ang mga item sa paglipas at ulitin namin ang proseso hanggang mayroon namin ang aming buong bagong array. Ano ang run oras ng algorithm na ito? Well, sabihin isaalang-alang ang epekto ng mga ito. Paglilipat namin ang bawat elemento. Kapag naming alisin ang i, paglilipat namin ay ang lahat ng mga elemento matapos itong sa kaliwa. At iyon ay isang gastos ng O (n) dahil kung ano ang kung aalisin namin ang unang elemento? Kaya para sa bawat pag-alis, alisin namin ang - sa bawat pag-alis matatamo ng operasyon O (n), at dahil n pag-alis namin, ito ay humahantong sa isang shuffle O (n ^ 2). Okay. Kaya magandang simula. Magandang simula. Mungkahi ng isa pang ay upang gamitin ang isang bagay na kilala bilang shuffle Knuth, o ang Fisher-Yates shuffle. At ito ay talagang isang linear na oras shuffle. At ideya ay halos katulad na. Muli, mayroon kaming ang aming input array, ngunit sa halip ng paggamit ng dalawang array para sa aming input / output, ginagamit namin ang unang bahagi ng array upang subaybayan ang aming shuffled bahagi, at hindi na namin subaybayan, at pagkatapos namin iwanan ang natitira sa aming array para sa unshuffled bahagi. Kaya narito ang kung ano ang ibig sabihin ko. Simulan namin off ang may - pinili naming i, isang array mula 0 hanggang 20. Aming kasalukuyang pointer ay tumuturo sa unang index. Pinili namin ang ilang i dito at ngayon kami magpalitan. Kaya kung ito ay 5 at ito ay 4, nagreresulta array ay may 5 dito at 4 dito. At ngayon, tandaan namin ang isang marker dito. Lahat sa kaliwa ay shuffled, at lahat sa kanan ay unshuffled. At ngayon maaari naming ulitin ang proseso. Pinili namin ang isang random na index sa pagitan ng 1 at 20 ngayon. Kaya ipagpalagay ang aming bagong i dito. Ngayon swap namin ito i sa aming kasalukuyang bagong posisyon dito. Kaya namin pagpapalit pabalik-balik tulad nito. Hayaan akong ilabas ang code upang gawin itong mas kongkreto. Magsisimula kami sa aming pagpipilian ng i - simulan namin na may kasing-halaga i sa 0, namin pumili ng isang random na lokasyon j sa ang unshuffled bahagi ng array, i n-1. Kaya kung ako dito, pumili ng isang random na index sa pagitan ng dito at sa ibang bahagi ng array, at swap namin. Ito ay ang lahat ng mga code na kinakailangan upang shuffle iyong array. Anumang mga katanungan? Well, kailangan isa ang tanong ay, kung bakit ay ito tama? Bakit bawat permutasyon pantay malamang? At hindi ako ay pumunta sa pamamagitan ng katibayan ng ito, ngunit maraming mga problema sa computer science ay napatunayan sa pamamagitan ng pagtatalaga sa tungkulin. Paano marami sa inyo ang pamilyar sa induction? Okay. Cool. Sa gayon maaari mong patunayan ang kawastuhan ng ang algorithm na ito sa pamamagitan ng simpleng induction, kung saan ay ang iyong induction teorya, ipinapalagay na ang aking shuffle nagbabalik sa bawat permutasyon pantay malamang hanggang sa ang unang i elemento. Ngayon, isaalang-alang ang i + 1. At sa pamamagitan ng ang paraan na pinili namin sa aming index j sa swap, ito ay humahantong sa - at pagkatapos kang magtrabaho ang mga detalye, hindi bababa sa isang buong katibayan kung bakit algorithm na ito ay nagbabalik bawat permutasyon may pantay malamang na posibilidad. Lahat ng karapatan, sa tabi problema. Kaya "bibigyan ng isang array ng mga integer, postive, zero, negatibong, magsulat ng isang function na kinakalkula ang maximum na kabuuan ng anumang continueous subarray ng input array. " Isang halimbawa dito ay, sa kaso na kung saan ang lahat ng mga numero ay positibo, pagkatapos ay kasalukuyang ang pinakamahusay na pagpipilian ay upang gawin ang buong array. 1, 2, 3, 4, katumbas ng 10. Kapag mayroon kang ilang mga negatibo sa doon, sa kasong ito gusto lang namin ang unang dalawang dahil ang pagpili ng -1 at / o -3 ay dalhin ang aming kabuuan. Minsan maaari naming magsimula sa gitna ng array. Minsan gusto naming pumili ng wala sa lahat; pinakamahusay na hindi tumagal ng anumang. At kung minsan ito ay mas mahusay na upang gawin ang pagkahulog, dahil ang bagay na ito pagkatapos na ito ay sobrang malaki. Kaya ang anumang mga ideya? (Mag-aaral, hindi maintindihan) >> Oo. Ipagpalagay na hindi ko nagsasagawa ng -1. Pagkatapos alinman pinili ko ang 1,000 at 20,000, o ko lang piliin ang 3 bilyong. Well, ang pinakamahusay na pagpipilian ay upang gawin ang lahat ng mga numero. Ito -1, sa kabila ng pagiging negatibong, ang buong kabuuan ay mas mahusay kaysa sa ay hindi ko na kumuha -1. Kaya isa sa mga tip na nabanggit ko mas maaga ay upang ihayag ang malinaw halata at taong malupit na puwersa solusyon muna. Ano ang taong malupit na puwersa solusyon ang problemang ito? Oo? [Jane] Well, sa tingin ko ang mga taong malupit na puwersa solusyon ay upang magdagdag ng hanggang ang lahat ng posibleng mga kumbinasyon (hindi maintindihan). [Yu] Okay. Kaya Jane ng ideya gumawa ng bawat posibleng - Ako paraphrasing - ay upang gumawa ng bawat posibleng tuloy-tuloy na subarray, compute ang kabuuan nito, at pagkatapos ay ang pinakamataas na ng lahat ng mga posibleng tuloy-tuloy na subarrays. Ano ang natatanging nagpapakilala sa ng subarray sa aking input array? Tulad ng, kung ano ang dalawang bagay ang kailangan kong? Oo? (Mag-aaral, hindi maintindihan) >> Karapatan. Ang isang mas mababang sumunod sa index at upper bound index natatanging tumutukoy isang patuloy na subarray. [Babae mag-aaral] namin pagtantya ang isang hanay ng mga natatanging mga numero? [Yu] No Kaya kanyang tanong, kami ipagpalagay aming array - ang aming array lahat ng mga natatanging mga numero, at ang sagot ay hindi. Kung naming gamitin ang aming taong malupit na puwersa ng solusyon, pagkatapos ay ang mga indeks ng pagsisimula / pagtatapos natatanging tinutukoy ng aming tuloy-tuloy na subarray. Kaya kung umulit namin para sa lahat ng posibleng mga entry sa simula, at para sa lahat ng mga entry sa pagtatapos> o = upang magsimula, at > Zero. Lamang huwag gawin ang -5. Narito ito ay pagpunta sa 0 pati na rin. Oo? (Mag-aaral, hindi maintindihan) [Yu] Oh, paumanhin, ay isang -3. Kaya ito ay isang 2, ito ay isang -3. Okay. Kaya -4, ano ang pinakamalaki subarray upang tapusin na posisyon kung saan -4 sa? Zero. Isa? 1, 5, 8. Ngayon, kailangan kong magtapos sa lokasyon kung saan -2 sa. Kaya 6, 5, 7, at ang huling isa ay 4. Alam na ito ang aking mga entry para ang transformed na problema kung saan ako dapat magtapos sa bawat ng mga indeks ng, pagkatapos ay ang aking panghuling sagot lamang, isang sweep sa buong, at ang maximum na bilang. Kaya sa kasong ito ito ay 8. Nagpapahiwatig ito na ang pinakamalaki subarray ay nagtatapos sa index na ito, at nagsimulang isang lugar bago ito. Ba ang lahat maunawaan ang transformed subarray? Okay. Well, sabihin malaman kung ang pag-ulit para sa. Natin isaalang-alang ang mga unang ilang entry. Kaya dito ito ay 0, 0, 0, 1, 5, 8. At pagkatapos ay nagkaroon ng -2 dito, at dinala ito sa 6. Kaya kung tawagan ko ang entry sa posisyon i subproblem (i), kung paano ang maaari kong gamitin ang sagot sa isang nakaraang subproblem sagutin ang subproblem na ito? Kung titingnan ko sa, sabihin nating, ang entry na ito. Paano ko compute ang sagot 6 sa pamamagitan ng pagtingin sa ng isang kumbinasyon ng array na ito at ang mga sagot sa nakaraang subproblems sa array? Oo? [Babae mag-aaral] mo ang hanay ng mga sums sa posisyon tama bago ito, kaya ang 8, at pagkatapos mong idagdag ang kasalukuyang subproblem. [Yu] Kaya ang kanyang mungkahi ay upang tingnan ang dalawang numerong ito, ang numerong ito at ang numerong ito. Kaya ito 8 ay tumutukoy sa sagot para sa subproblem (i - 1). At sabihin tawagan ang aking input array A. Upang mahanap ang isang pinakamalaki subarray na nagtatapos sa posisyon i, Mayroon akong dalawang mga pagpipilian: Maaari ko bang ipagpatuloy ang subarray na natapos na sa nakaraang index, o magsimula ng isang bagong array. Kung ako ay upang ipagpatuloy ang subarray na nagsimula sa nakaraang index, pagkatapos ay ang maximum na kabuuan na maaari kong makamit ang sagot sa nakaraang subproblem pati na rin ang kasalukuyang array entry. Ngunit, ko rin ang pagpili ng simula ng isang bagong subarray, kung saan ang kabuuan ay 0. Kaya ang sagot ay max na 0, subproblem i - 1, pati na rin ang kasalukuyang array entry. Ba ang pag-ulit na ito ay may kabuluhan? Ang aming pag-ulit, namin natuklasan, ang subproblem i katumbas ng maximum ng nakaraang subproblem pati na ang aking kasalukuyang array entry, na nangangahulugan ipagpatuloy ang nakaraang subarray, o 0, magsimula ng isang bagong subarray sa aking kasalukuyang index. At sabay-sabay na binuo namin ang talahanayan na ito ng mga solusyon, at pagkatapos ay aming panghuling sagot, lamang gawin ang isang linear sweep sa buong array subproblem at ang maximum na bilang. Ito ay isang eksaktong pagpapatupad ng kung ano ang sinabi ko lang. Kaya kaming lumikha ng bagong array subproblem, subproblems. Ang unang entry ay alinman sa 0 o ang unang entry, ang maximum na mga dalawang. At para sa iba pang mga bahagi ng subproblems ginagamit namin ang eksaktong pag-ulit na lang namin natuklasan. Ngayon compute namin ang maximum ng aming mga subproblems array, at na ang aming panghuling sagot. Kaya kung magkano ang space ay namin ang paggamit sa algorithm? Kung mo lamang ang kinuha CS50, hindi mo maaaring tinalakay espasyo talaga. Well, isang bagay na dapat tandaan ay na tinatawag ko ang malloc dito sa n laki. Ano ang na iminumungkahi sa iyo? Algorithm na ito ay gumagamit ng linear espasyo. Maaari naming gawin mas mahusay? Mayroon bang anumang bagay na napansin mo na ay hindi kailangan upang makalkula ang panghuling sagot? Hulaan ko na ang isang mas mahusay na tanong ay, kung ano ang impormasyon hindi namin kailangan upang dalhin ang lahat ng mga paraan sa pamamagitan ng sa dulo? Ngayon, kung tiningnan namin sa mga dalawang linya, namin lamang pakialam tungkol sa nakaraang subproblem, at lamang namin pakialam tungkol sa maximum na nasaksihan namin sa ngayon. Upang makalkula ang aming panghuling sagot, hindi namin kailangan ang buong array. Kailangan lamang namin ang huling bilang, ang huling dalawang numero. Huling na numero para sa subproblem array, at ang huling bilang para sa maximum na. Kaya, sa katunayan, maaari naming pusible mga loop at pumunta mula sa linear espasyo sa pare-pareho ang espasyo. Kasalukuyang kabuuan sa ngayon, narito, pumapalit papel ng subproblem, ang aming subproblem array. Kaya kasalukuyang kabuuan, sa ngayon, ang sagot sa nakaraang subproblem. At kabuuan na, sa ngayon, tumatagal ang lugar ng aming mga max. Kino-compute namin ang maximum na bilang pumunta kami sa kahabaan. At kaya pumunta kami mula sa linear espasyo sa pare-pareho ang espasyo, at kami ay mayroon ding isang linear na solusyon sa aming subarray problema. Mga uri ng mga katanungan ay kang makakuha sa panahon ng isang pakikipanayam. Ano ang oras kumplikado, ano ang espasyo kumplikado? Maaari mong gawin mas mahusay? May mga bagay na hindi kinakailangang upang panatilihin sa paligid? Ginawa ko ito upang i-highlight ang mga pinag-aaralan na dapat mong gawin sa iyong sariling habang ikaw ay nagtatrabaho sa pamamagitan ng mga problemang ito. Laging humihiling sa iyong sarili, "Maaari ko bang gawin mas mahusay na?" Sa katunayan, maaari naming gawin mas mahusay kaysa sa ito? -Uri-uriin ng isang nanlilinlang tanong. Hindi ka maaari, dahil kailangan mo hindi bababa sa basahin ang input sa problema. Kaya ang katotohanan na kailangan mong hindi bababa sa basahin ang input sa problema nangangahulugan na hindi mo maaaring gawin mas mahusay kaysa sa linear oras, at hindi mo maaaring gawin mas mahusay kaysa sa pare-pareho ang espasyo. Kaya ito ay, sa katunayan, ang pinakamahusay na solusyon sa problemang ito. Mga tanong? Okay. Problema sa merkado ng stock: "Dahil isang array ng n integer, positibo, zero, o negatibong, na kumakatawan sa presyo ng stock sa n araw, magsulat ng isang function upang makalkula ang pinakamataas na kita maaari mong gawin ibinigay na kang bumili at magbenta ng eksaktong 1 stock sa loob ng mga n araw. " Mahalaga, gusto naming bumili mababa, magbenta ng mataas. At gusto naming malaman ang pinakamahusay na kita na maaari kaming magsagawa ng. Pagpunta pabalik sa aking tip, ano ang agad na malinaw, ang pinakasimpleng sagot, ngunit ito ay mabagal? Oo? (Mag-aaral, hindi maintindihan) >> Oo. >> Kaya gusto mong pumunta lamang bagaman at tumingin sa mga presyo ng stock sa bawat punto sa oras, (hindi maintindihan). [Yu] Okay, kaya ang kanyang solusyon - kanyang mungkahi ng computing ang pinakamababang at compute ang pinakamataas na ay hindi agad gumana dahil ang pinakamataas na maaaring maganap bago ang pinakamababang. Kaya kung ano ang taong malupit na puwersa solusyon sa problemang ito? Ano ang dalawang bagay na kailangan ko upang natatanging matukoy ang kita gumawa ako? Kanan. Ang taong malupit na puwersa solusyon - oh, kaya, George ng mungkahi kailangan lamang namin ng dalawang araw ng natatanging matukoy ang kita ng mga dalawang araw. Kaya compute namin ang bawat pares, i Bumibili / Nagpapalit, compute ang kita, na maaaring negatibong o positibong o zero. Compute ang maximum profit na ginawa namin pagkatapos iterating sa paglipas ng lahat ng mga pares ng mga araw. Na ang aming panghuling sagot. At ang solusyon na O (n ^ 2), dahil may n pumili ng dalawang pares - ng mga araw na maaari mong makapili sa mga araw ng pagtatapos. Okay, kaya hindi ako pagpunta sa pumunta sa ibabaw ng taong malupit na puwersa solusyon dito. Ako pagpunta sa sabihin sa iyo na may n solusyon log n. Ano algorithm ang kasalukuyan mong malaman na n log n? Hindi isang nanlilinlang tanong. Pagsamahin-uuri. Pagsamahin-uuri n log n at sa katunayan, ang isang paraan ng paglutas sa problemang ito ay upang gamitin ang isang uri ng pagsasama-uuri ng ideya na tinatawag na, sa pangkalahatan, hatiin at lupigin. At ideya ay ang mga sumusunod. Nais mong i-compute ang pinakamahusay na bumili / magbenta ng pares sa kaliwang kalahati. Hanapin ang pinakamahusay na kita na maaari mong gawin, sa mga unang n sa loob ng dalawang araw ng. Pagkatapos nais mong oompute ang pinakamahusay na bumili / magbenta ng pares sa kanang kalahati, kaya ang huling n sa loob ng dalawang araw ng. At ngayon ang tanong ay, kung paano namin sumanib pabalik ang mga solusyon na ito nang magkasama? Oo? (Mag-aaral, hindi maintindihan) >> Okay. Kaya ipaalam sa akin gumuhit ng larawan. Oo? (George, hindi maintindihan) >> Mismong. Akmang-akma ang George ng solusyon. Kaya ang kanyang mungkahi ay, compute muna ang pinakamahusay na bumili / magbenta ng pares, at na nangyayari sa kaliwang kalahati, kaya sabihin tumawag na kaliwa, ang natitira. Pinakamahusay na bumili / magbenta ng pares na nangyayari sa kanang kalahati. Ngunit kung lamang namin kumpara ang dalawang numerong ito, kami ay Kulang ang kaso kung saan kami bumili dito at magbenta ng isang lugar sa kanang kalahati. Bumili kami sa kaliwang kalahati, ibenta sa kanang kalahati. At ang pinakamahusay na paraan upang makalkula ang pinakamahusay Bumibili / Nagpapalit pares na sumasaklaw ng parehong halves upang makalkula ang minimum dito at compute ang maximum dito at dalhin ang kanilang mga pagkakaiba. Kaya ang dalawang mga kaso na kung saan ang Bumibili / Nagpapalit pares nangyayari lamang dito, lamang dito, o sa parehong halves ay tinukoy sa pamamagitan ng mga tatlong numero. Kaya ang aming algorithm upang sumanib ang aming mga solusyon pabalik sama-sama, gusto naming upang makalkula ang pinakamahusay na bumili / magbenta ng pares kung saan kami bumili sa kaliwang kalahati at magbenta sa tamang kalahati. At ang pinakamahusay na paraan upang gawin iyon ay upang makalkula ang pinakamababang presyo sa unang kalahati, ang pinakamataas na presyo sa kanang kalahati, at kanilang mga pagkakaiba. Ang resultang tatlong kita, ang tatlong numero, kukuha ka ng hanggang sa tatlong, at na ang pinakamahusay na kita maaari kang magsagawa ng sa mga unang at end na mga araw. Narito ang mga mahalagang linya ng pula. Ito ay isang recursive tawag upang makalkula ang sagot sa kaliwang kalahati. Ito ay isang recursive tawag upang makalkula ang sagot sa kanang kalahati. Ang dalawang para sa loop compute ang min at ang max sa kaliwa at kanang kalahati, ayon sa pagkakasunud-sunod. Ngayon ko compute ang kita na sumasaklaw sa parehong halves, at ang panghuling sagot ay ang maximum na ang tatlong. Okay. Kaya, sigurado, mayroon kaming isang algorithm, ngunit ang mas malaking tanong ay, ano ang oras ng pagiging kumplikado ng mga ito? At ang dahilan kung bakit nabanggit ko ang pagsasama-uuri ay na ang form na ito ng hatiin ang sagot sa dalawang at pagkatapos ay pinagsasama ang aming mga solusyon pabalik sama-sama ay eksaktong paraan ng pagsasama-uuri. Kaya hayaan mo akong pumunta sa pamamagitan ng tagal. Kung tinukoy na namin ang isang function t (n) na ang bilang ng mga hakbang para sa mga n araw, aming dalawang recursive tawag ang bawat gastos t (n / 2), at may dalawa sa mga tawag na ito. Ngayon ay kailangan ko upang makalkula ang minimum na kaliwang kalahati, na maaari kong gawin sa n / 2 oras, pati na rin ang maximum na ng tamang kalahati. Kaya ito ay lamang n. At pagkatapos plus ilang pare-pareho sa trabaho. At pag-ulit equation na ito ay eksakto ang pag-ulit ng equation para sa pagsasama-uuri. At namin ang lahat ng alam na ang pagsasama-uuri n log n oras. Samakatuwid, ang aming mga algorithm ay din n log n oras. Ba ang pag-ulit na ito ay may kabuluhan? Isang maikling pagbabalik-tanaw ng mga ito: T (n) ay ang bilang ng mga hakbang upang makalkula ang pinakamataas na kita sa ibabaw ng kurso ng n araw. Ang paraan namin hatiin aming mga recursive tawag sa pamamagitan ng pagtawag sa aming mga solusyon sa unang araw n / 2, kaya na isang tawag, at pagkatapos ay tinatawag naming muli sa ikalawang kalahati. Kaya na ang dalawang tawag. At pagkatapos ay nakita namin isang minimum na sa kaliwang kalahati, na maaari naming gawin sa linear oras, hanapin ang maximum ng kanang kalahati, na maaari naming gawin sa linear oras. Kaya n / 2 + n / 2 lamang n. Pagkatapos kami ay may ilang mga pare-pareho ang trabaho, na tulad ng ginagawa aritmetika. Ang pag-ulit equation na ito ay eksakto ang pag-ulit ng equation para sa pagsasama-uuri. Samakatuwid, ang aming algorithm sa shuffle din n log n. Kaya kung magkano ang space ay namin ginagamit? Natin bumalik sa code. Ang isang mas mahusay na tanong ay, kung gaano karaming mga stack frame namin sa anumang naibigay na sandali? Dahil kami ay gamit ng recursion, ang bilang ng mga frame ng stack ay tumutukoy sa paggamit ng aming espasyo. Natin isaalang-alang ang n = 8. Tinatawag namin ang shuffle sa 8, na tawagan ang shuffle sa unang apat na entry, na tumawag ng shuffle sa unang dalawang entry. Kaya ang aming stack ay - ito ang aming stack. At pagkatapos ay tinatawag naming shuffle muli sa 1, at iyon ang kung ano ang aming base kaso ay, kaya namin bumalik agad. Namin ay may higit pa kaysa sa mga ito maraming stack frame? No Dahil sa bawat oras na gawin namin ng pananalangin, isang recursive na pananalangin sa shuffle, hinati namin ang aming laki sa kalahati. Kaya ang maximum na bilang ng mga frame ng stack namin sa anumang naibigay na sandali sa pagkakasunud-sunod ng mga log n stack frame. Bawat stack frame ay may pare-pareho na espasyo, at samakatuwid ay ang kabuuang halaga ng espasyo, ang maximum na halaga ng puwang namin ginagamit O (log n) espasyo kung saan ang n ay ang bilang ng mga araw. Ngayon, palaging tanungin ang inyong sarili, "Maaari ba kaming gawin mas mahusay na?" At sa partikular, maaari naming bawasan ito sa isang problema na namin na malutas? Isang pahiwatig: lamang namin tinalakay ng dalawang iba pang mga problema bago ito, at hindi ito pagpunta sa shuffle. Maaari naming i-convert ito problema sa merkado ng stock sa ang pinakamalaki subarray problema. Paano namin gawin ito? Isa mo? Emmy? (Emmy, hindi maintindihan) [Yu] Mismong. Kaya ang pinakamalaki subarray problema, kaming naghahanap ng para sa isang kabuuan sa isang tuloy-tuloy na subarray. At Emmy mungkahi para sa mga problema ng mga stock, isaalang-alang ang mga pagbabago, o ang mga deltas. At ang isang larawan na ito ay - ito ay ang presyo ng stock, ngunit kung kinuha namin ang pagkakaiba sa pagitan ng bawat magkakasunod na araw - kaya namin makita na ang maximum na presyo, maximum profit kami maaaring magsagawa ng kung bumili kami dito at magbenta dito. Ngunit tingnan natin sa tuloy-tuloy na - tingnan natin sa problema subarray. Kaya dito, maaari kaming magsagawa ng - pagpunta mula dito sa dito, mayroon kami ng positibong pagbabago, at pagkatapos ng pagpunta mula dito dito kami ay may isang negatibong pagbabago. Ngunit pagkatapos, pagpunta mula dito sa dito mayroon kaming isang malaking positibong pagbabago. At ito ay ang mga pagbabago na gusto namin upang ipahayag sa ilang kataga upang makakuha ng ang aming panghuling kita. Pagkatapos kami ay may higit pang mga negatibong mga pagbabago dito. Ang susi sa pagbabawas ng aming stock problema sa aming mga problema sa pinakamalaki subarray ay upang isaalang-alang ang mga deltas sa pagitan ng mga araw. Kaya namin lumikha ng isang bagong array na tinatawag deltas, initialize ang unang entry na 0, at pagkatapos ay para sa bawat delta (i), sabihin na ang pagkakaiba ng aking input array (i), at array (i - 1). Pagkatapos tawagan namin ang aming nakagawiang pamamaraan para sa isang pinakamalaki subarray pagpasa sa isang delta ng array. At dahil ang pinakamalaki subarray linear oras, at ito pagbabawas, ang proseso ng paglikha ng ang delta array na ito, ding linear oras, pagkatapos ay ang panghuling solusyon para sa mga stock ay O (n) trabaho plus O (n) trabaho, pa rin ang O (n) na trabaho. Kaya mayroon kami ng linear oras solusyon sa aming problema. Ba ang lahat maunawaan ang pagbabago na ito? Sa pangkalahatan, ang isang magandang ideya na dapat palagi kang may ay subukan upang mabawasan ang isang bagong problema na nakakakita ka. Kung mukhang pamilyar sa isang lumang problema, subukang bawasan ito sa isang lumang problema. At kung maaari mong gamitin ang lahat ng mga tool na ginamit mo sa lumang problema upang malutas ang mga bagong problema. Kaya upang tapusin, teknikal na panayam ay hamon. Ang mga problemang ito ay marahil ilang ng mas mahirap na mga problema na maaari mong makita sa isang pakikipanayam, kaya kung hindi mo maunawaan ang lahat ng mga problema ko lang sakop, okay lang. Mga ito ay ilan sa ang mga mas mahirap na mga problema. Practice, kasanayan, kasanayan. Nagbigay ako ng maraming ng mga problema sa hand-awt, kaya tiyak na suriin ang mga out. At good luck sa iyong mga panayam. Lahat ng aking mga mapagkukunan ay nai-post sa link na ito, at isa ng aking mga kaibigan sa senior ay inaalok sa gawin ng mga kunwaring mga teknikal na panayam, kaya kung interesado ka, email Will Yao sa email address na iyon. Kung mayroon kang ilang mga katanungan, maaari mong hilingin sa akin. Ka ba guys may partikular na mga tanong na may kaugnayan sa mga teknikal na panayam o anumang mga problema na nasaksihan namin sa ngayon? Okay. Well, good luck sa iyong mga panayam. [CS50.TV]