[Powered by Google Translate] [Semina: Ufundi Mahojiano] [Kenny Yu, Chuo Kikuu cha Harvard] [Hii ni CS50.] [CS50.TV] Hi kila mtu, mimi nina Kenny. I am sasa junior kusoma sayansi ya kompyuta. Mimi nina zamani CS TF, na mimi napenda alikuwa nilipokuwa underclassman, na kwamba sababu mimi nina kutoa semina hii. Hivyo Natumaini kufurahia. Semina hii ni kuhusu mahojiano ya kiufundi, na rasilimali yangu yote yanaweza kupatikana katika link hii, link hii hapa hapa, wanandoa wa rasilimali. Hivyo mimi alifanya orodha ya matatizo, kwa kweli, kabisa matatizo machache. Pia jumla ya rasilimali ukurasa ambapo tunaweza kupata tips juu ya jinsi ya kujiandaa kwa ajili ya mahojiano, vidokezo juu ya nini unatakiwa kufanya wakati wa mahojiano halisi, kama vile jinsi ya kukabili matatizo na rasilimali kwa ajili ya baadae. Ni wote online. Na tu kwa utangulizi semina hii, disclaimer, kama hii haipaswi - mahojiano yako maandalizi kusiishie tu kwa orodha hii. Hii ni tu maana ya kuwa kiongozi, na unapaswa dhahiri kuchukua kila kitu nasema pamoja na punje ya chumvi, lakini pia kutumia kila kitu mimi kutumika kukusaidia katika mahojiano maandalizi yako. 

Mimi nina kwenda kwa haraka kupitia slides michache ijayo ili tuweze kupata masomo halisi kesi. muundo wa mahojiano kwa postion uhandisi programu, kawaida ni dakika 30 hadi 45, nyingi raundi, kutegemea kampuni. Mara nyingi utasikia kuwa coding juu ya bodi nyeupe. Hivyo bodi nyeupe kama hii, lakini mara nyingi kwa kiwango kidogo. Kama wewe ni kuwa na mahojiano ya simu, pengine utasikia kutumia aidha collabedit au Doc Google ili waweze kuona mkiishi coding wakati wewe kuwa waliohojiwa juu ya simu. mahojiano yenyewe ni kawaida 2 au 3 matatizo kupima kompyuta yako sayansi maarifa. Na itakuwa karibu dhahiri kuhusisha coding. maswali ya aina hiyo utaona ni kawaida data miundo na algorithms. Na katika kufanya aina hii ya matatizo, watamwuliza wewe, kama, nini ni wakati na utata nafasi, kubwa O? Mara nyingi wao pia kuuliza maswali juu ya ngazi, hivyo, kubuni mfumo, jinsi gani unaweza kuweka nje code yako? Nini interfaces, kile madarasa, modules je, una katika mfumo wako, na jinsi gani haya kuingiliana pamoja? Hivyo data miundo na algorithms kama vile mifumo ya kubuni. 

Baadhi ya vidokezo ujumla kabla ya sisi kupiga mbizi katika kesi yetu masomo. Nadhani utawala muhimu zaidi ni daima kufikiri kwa sauti. mahojiano zinatakiwa kuwa nafasi yako ya kuonyesha mbali mawazo yako mchakato. hatua ya mahojiano ni kwa ajili ya mhojaji ili kupima jinsi wanafikiri na jinsi ya kwenda kwenye tatizo. Kitu mbaya unaweza kufanya ni kuwa kimya katika mahojiano nzima. Hiyo tu hakuna nzuri. Wakati wewe ni kupewa swali, wewe pia wanataka kuhakikisha unaelewa swali. Hivyo kurudia swali nyuma kwa maneno yako mwenyewe na jaribio la kazi ya uhakika chache kesi mtihani rahisi kuhakikisha unaelewa swali. Kufanya kazi kwa njia ya kesi chache mtihani pia kukupa Intuition juu ya jinsi ya kutatua tatizo hili. Unaweza hata kugundua ruwaza chache kukusaidia kutatua tatizo. Ncha yao kubwa ni si kupata frustrated. Je, si kupata frustrated. Mahojiano ni changamoto, lakini kitu mbaya unaweza kufanya, kwa kuongeza kuwa kimya, ni kuwa wazi imechanganyikiwa. Wewe hawataki kutoa hisia kwamba kwa mhojaji. Jambo moja kwamba - kwa hivyo, watu wengi, wakati wao kwenda katika mahojiano, wao kujaribu kujaribu kupata ufumbuzi bora ya kwanza, wakati kwa kweli, kuna kawaida ufumbuzi glaringly dhahiri. Inaweza kuwa polepole, inaweza kuwa ufanisi, lakini wewe lazima tu kueleza kuwa, hivyo tu una uhakika kuanzia ambayo kazi vizuri zaidi. Pia, akizungumzia nje ufumbuzi ni polepole, katika suala la kubwa O wakati utata au utata nafasi, itadhihirisha kwa mhojaji kwamba kuelewa masuala haya wakati wa kuandika code. Kwa hiyo msiwe na hofu ya kuja na algorithm rahisi kwanza na kisha kazi bora kutoka huko. Maswali yoyote hadi sasa? Sawa. 

Hivyo hebu kupiga mbizi katika tatizo letu kwanza. "Kutokana na safu ya integers n, kuandika kazi kwamba shuffles safu katika mahali vile kwamba permutations wote wa integers n wana uwezekano sawa. " Na kudhani kuwa inapatikana random integer jenereta kwamba inazalisha integer katika mbalimbali kutoka 0 kwa i, nusu mbalimbali. Je, kila mtu kuelewa swali hili? Mimi kukupa safu ya integers n, na Mimi nataka wewe shuffle yake. Katika orodha yangu, mimi aliandika programu chache kuonyesha namaanisha nini. Mimi naenda shuffle safu ya vipengele 20, kutoka -10 hadi 9, na mimi nataka wewe pato orodha kama hii. Hivyo hii ni pembejeo yangu sorted safu, na Mimi nataka wewe shuffle yake. Tutaweza kufanya hivyo tena. Je, kila mtu kuelewa swali? Sawa. Hivyo ni juu yako. Nini ni baadhi ya mawazo? Je, unaweza kufanya hivyo kama n ^ 2, n logi n, n? Fungua kwa mapendekezo. Sawa. Hivyo wazo moja, alipendekeza kwa Emmy, ni ya kwanza compute random idadi, random integer, katika mbalimbali 0-20. Hivyo kudhani safu yetu ina urefu wa 20. Katika mchoro wetu wa mambo ya 20, hii ni pembejeo yetu safu. Na sasa, pendekezo lake ni kujenga safu mpya, hivyo hii itakuwa safu pato. Na msingi i akarudi na rand - hivyo kama i alikuwa, hebu sema, 17, nakala ya kipengele 17 katika nafasi ya kwanza. Sasa sisi haja ya kufuta - tunahitaji kuhama vipengele vyote hapa juu ya hivyo kwamba tuna pengo mwishoni na mashimo hakuna katikati. Na sasa sisi kurudia utaratibu. Sasa sisi kuchukua mpya random integer kati ya 0 na 19. Tuna i mpya hapa, na sisi nakala hii ya kipengele katika nafasi hii. Kisha sisi kuhama vitu zaidi na sisi kurudia mchakato mpaka tuna mpya wetu kamili safu. Je, ni wakati wa kukimbia algorithm hii? Naam, hebu kuangalia matokeo ya. Sisi ni shifting kila kipengele. Wakati sisi kuondoa hii i, sisi ni shifting vipengele vyote baada ya upande wa kushoto. Na kwamba ni O (n) gharama kwa sababu nini kama sisi kuondoa kipengele kwanza? Hivyo kwa ajili ya kuondolewa kila, sisi kuondoa - kuondolewa kila incurs O (n) operesheni, na tangu tuna n removals, hii hupelekea shuffle O (n ^ 2). Sawa. Hivyo nzuri kuanza. Nzuri ya kuanza. 

Pendekezo lingine ni kutumia kitu inayojulikana kama shuffle Knuth, au shuffle Fisher-Yates. Na ni kweli linear wakati shuffle. Na wazo ni sawa sana. Tena, tuna mchango wetu safu, lakini badala ya kutumia arrays mbili kwa ajili ya pembejeo wetu / pato, sisi kutumia sehemu ya kwanza ya safu ya kuweka wimbo wa sehemu yetu huchanganywa, na sisi kuweka wimbo, na kisha sisi kuacha wengine wa safu yetu kwa ajili ya sehemu unshuffled. Hivyo hapa ni nini namaanisha. Sisi kuanza mbali na - sisi kuchagua i, safu 0-20. Pointer wetu wa sasa ni akizungumzia index kwanza. Sisi kuchagua baadhi hapa i na sasa sisi wabadilishane. Hivyo kama hii ilikuwa 5 na hii ilikuwa 4, safu kusababisha itakuwa na 5 hapa na 4 hapa. Na sasa tunaona marker hapa. Kila kitu kwa upande wa kushoto ni huchanganywa, na kila kitu kwa kulia unshuffled. Na sasa tunaweza kurudia utaratibu. Sisi kuchagua index random kati ya 1 na 20 sasa. Hivyo kudhani wetu mpya i ni hapa. Sasa sisi byta hii i na msimamo wetu wa sasa mpya hapa. Hivyo hatujui swapping na kurudi kama hii. Hebu kuleta code kufanya hivyo zaidi zege. Tunaweza kuanza na uchaguzi wetu wa i - sisi kuanza na i sawa na 0, tunachukua random mahali j katika sehemu unshuffled wa safu, i kwa n-1. Basi, ikiwa mimi niko hapa, kuchagua kati ya index random hapa na wengine wa safu, na sisi wabadilishane. Hii ni kanuni zote muhimu shuffle safu yako. Maswali yoyote? 

Naam, mmoja zinahitajika swali ni, kwa nini hili ni sahihi? Kwa nini ni kila permutation uwezekano sawa? Na mimi si kwenda kwa njia ya ushahidi wa hili, lakini matatizo mengi katika sayansi ya kompyuta inaweza kuthibitika kwa njia ya introduktionsutbildning. Jinsi wengi wewe ni ukoo na introduktionsutbildning? Sawa. Cool. Hivyo unaweza kuthibitisha usahihi wa algorithm hili kwa introduktionsutbildning rahisi, ambapo introduktionsutbildning yako hypothesis itakuwa, kudhani kuwa Shuffle yangu anarudi kila permutation uwezekano sawa hadi kwanza i vipengele. Sasa, fikiria i + 1. Na kwa njia ya sisi kuchagua index yetu j wabadilishane, hii husababisha - na kisha kazi nje maelezo, angalau ushahidi kamili ya nini algorithm hili hurejea kila permutation na uwezekano uwezekano sawa. 

Haki ya wote, karibu tatizo. Hivyo "kupewa safu ya integers, postive, sifuri, hasi, kuandika kazi ambayo inakokotoa Jumla upeo yoyote subarray continueous wa safu pembejeo. " mfano hapa ni, katika kesi ambapo wote idadi ni chanya, basi sasa chaguo bora ni kuchukua safu nzima. 1, 2, 3, 4, sawa na 10. Wakati una baadhi negatives huko, katika kesi hii sisi tu wanataka mbili kwanza kwa sababu kuchagua -1 na / au -3 ataleta Jumla yetu chini. Wakati mwingine sisi tupate kuwa na kuanza katikati ya safu. Wakati mwingine tunataka kuchagua kitu; ni bora si kuchukua kitu chochote. Na wakati mwingine ni bora kuchukua kuanguka, sababu jambo baada ya ni super kubwa. Hivyo mawazo yoyote? (Mwanafunzi, unintelligible) >> Yeah. Tuseme mimi wala kuchukua -1. Basi ama mimi kuchagua 1000 na 20,000, au mimi tu kuchagua bilioni 3. Naam, chaguo bora ni kuchukua namba zote. Hii -1, licha ya kuwa hasi, Jumla zima ni bora kuliko walikuwa mimi si kuchukua -1. Basi mmoja wa tips nilivyoeleza awali ilikuwa kueleza wazi wazi na nguvu brute ufumbuzi kwanza. Je, ni nguvu brute ufumbuzi katika tatizo hili? Yeah? [Jane] Vizuri, nadhani brute nguvu ufumbuzi itakuwa na kuongeza hadi mchanganyiko wote inawezekana (unintelligible). [Yu] Sawa. Hivyo wazo Jane ni kuchukua kila iwezekanavyo - Mimi nina kufafanua - ni kuchukua kila iwezekanavyo kuendelea subarray, compute Jumla yake, na kisha kuchukua upeo wa subarrays wote inawezekana kuendelea. Nini kipekee kubainisha subarray katika pembejeo safu yangu? Kama, nini mambo mawili Ninahitaji? Yeah? (Mwanafunzi, unintelligible) >> Haki. chini amefungwa juu ya index na juu amefungwa index kipekee huamua subarray kuendelea. [Kike mwanafunzi] Je, sisi kukadiria ni safu ya idadi ya kipekee? [Yu] No Hivyo swali lake, ni sisi kuchukua safu yetu - ni safu zetu zote idadi ya kipekee, na jibu ni hapana. 

Kama sisi kutumia nguvu zetu brute ufumbuzi, basi fahirisi kuanza / mwisho kipekee huamua subarray wetu kuendelea. Hivyo kama sisi iterate kwa entries wote inawezekana kuanza, na kwa entries mwisho wote> au = kuanza, na <n, wewe compute jumla, na kisha sisi kuchukua Jumla upeo tumeona mpaka sasa. Je, hii ni wazi? Nini ni O kubwa ya ufumbuzi huu? Timewise. Si kabisa n ^ 2. Kumbuka kwamba sisi iterate kutoka 0 kwa n, hivyo kwamba moja kwa kitanzi. Sisi iterate tena kutoka karibu mwanzo hadi mwisho, mwingine kwa kitanzi. Na sasa, ndani ya kwamba, tuna jumla juu ya kila kuingia, ili mwingine kwa kitanzi. Hivyo tuna tatu nested kwa tanzi, n ^ 3. Sawa. Hii inakwenda kama kianzio. Ufumbuzi yetu ni mbaya zaidi kuliko hakuna n ^ 3. Je, kila mtu kuelewa brute nguvu ufumbuzi? 

Sawa. ufumbuzi bora ni kutumia wazo kuitwa nguvu programu. Kama wewe kuchukua CS124, ambayo ni Algorithms na Miundo Data, utakuwa familiar sana na mbinu hii. Na wazo, kujaribu kujenga ufumbuzi wa matatizo madogo ya kwanza. Nini maana na hii ni, sisi sasa kuwa na wasiwasi juu ya mambo mawili: mwanzo na mwisho. Na kwamba ni annoying. Nini kama tunaweza kujikwamua moja ya vigezo wale? Moja wazo ni - we're aliyopewa tatizo yetu ya awali, Jumla kupata upeo wa yoyote katika subarray mbalimbali [O, n-1]. Na sasa tuna subproblem mpya, ambapo tunajua, katika ripoti yetu ya sasa i, tunajua lazima kuhitimisha huko. Subarray yetu lazima mwisho katika index sasa. Hivyo tatizo iliyobaki ni, ambapo tunapaswa kuanza subarray yetu? Je, hii mantiki? Sawa. Hivyo nimekuwa coded hii juu, na hebu tuangalie nini maana ya hii. Katika codirectory, kuna programu inayoitwa subarray, na inachukua idadi ya vitu, na kuirudisha maximal subarray Jumla katika orodha yangu huchanganywa. Hivyo katika kesi hii, subarray wetu maximal ni 3. Na hiyo kuchukuliwa na kutumia tu 2 na 1. Hebu kukimbia tena. Ni pia 3. Lakini wakati huu, tambua jinsi sisi got 3. Sisi alichukua - sisi tu kuchukua 3 yenyewe sababu ni kuzungukwa na negatives pande zote mbili, ambayo kuleta Jumla <3. Hebu kukimbia juu ya vitu 10. Wakati huu ni 7, sisi kuchukua 3 kuongoza na 4. Wakati huu ni 8, na sisi kupata kwamba kwa kuchukua 1, 4 na 3. Hivyo kukupa Intuition juu ya jinsi gani tunaweza kutatua tatizo hili kubadilishwa, hebu tuangalie subarray hii. Sisi ni kupewa hii safu ya pembejeo, na tunajua jibu ni 8. Sisi kuchukua 1, 4, na 3. Lakini hebu tuangalie jinsi sisi kweli got kuwa jibu. Hebu tuangalie subarray maximal kumalizika katika kila moja ya fahirisi hizi. Nini subarray maximal ambayo ina kumaliza katika nafasi ya kwanza? [Mwanafunzi] Sifuri. >> Zero. Tu wala kuchukua -5. Hapa ni kwenda kuwa 0 vilevile. Yeah? (Mwanafunzi, unintelligible) [Yu] Oh, sorry, ni -3. Hivyo hii ni 2, hii ni -3. Sawa. Hivyo -4, nini subarray maximal kukomesha kwamba nafasi ambapo -4 ni saa? Zero. Moja? 1, 5, 8. Sasa, mimi lazima mwisho katika eneo ambapo -2 ni saa. Hivyo 6, 5, 7, na moja ya mwisho ni 4. Kujua kwamba haya ni entries yangu kwa tatizo kubadilishwa ambapo mimi lazima mwisho katika kila moja ya fahirisi hizi, basi jibu langu la mwisho ni wa haki, kuchukua zoa hela, na kuchukua idadi ya juu. Hivyo katika kesi hii ni 8. Hii ina maana kwamba subarray maximal inaishia katika index hii, na kuanza mahali fulani mbele yake. Je, kila mtu kuelewa hili subarray kubadilishwa? 

Sawa. Naam, hebu takwimu nje upprepning kwa hili. Hebu fikiria tu kwanza entries chache. Hivyo hapa ilikuwa 0, 0, 0, 1, 5, 8. Na kisha kulikuwa -2 hapa, na kwamba kuletwa ni chini ya 6. Hivyo kama mimi wito kuingia katika nafasi i subproblem (i), jinsi gani naweza kutumia jibu subproblem uliopita kujibu hii subproblem? Kama mimi kuangalia, hebu sema, kuingia hii. Ninawezaje compute jibu 6 kwa kuangalia mchanganyiko wa safu hii na majibu ya subproblems uliopita katika safu hii? Ndiyo? [Kike mwanafunzi] Wewe kuchukua safu ya maswali katika nafasi ya haki mbele yake, hivyo 8, na kisha kuongeza subproblem sasa. [Yu] Basi pendekezo lake ni kuangalia namba hizi mbili, idadi hii na idadi hii. Hivyo hii 8 inahusu jibu kwa subproblem (i - 1). Na hebu piga pembejeo yangu safu A. Ili kupata subarray maximal kwamba mwisho katika msimamo i, Nina maamuzi mawili: Mimi wanaweza ama kuendelea subarray kwamba kumalizika saa index uliopita, au kuanza safu mpya. Kama ningekuwa na kuendelea subarray ambayo ilianza katika index uliopita, kisha Jumla upeo naweza kufikia ni jibu kwa subproblem uliopita plus sasa safu ya kuingia. Lakini, mimi pia kuwa na uchaguzi wa kuanzia subarray mpya, katika kesi ambayo Jumla ni 0. Hivyo jibu ni max ya 0, subproblem i - 1, plus sasa kuingia safu. Je upprepning hii mantiki? Upprepning yetu, kama sisi tu kugundua, ni subproblem i ni sawa na upeo wa subproblem uliopita plus kuingia yangu ya sasa safu, ambayo ina maana ya kuendelea subarray uliopita, au 0, kuanza subarray mpya katika index yangu ya sasa. Na mara moja tumejenga hii meza ya ufumbuzi, basi jibu wetu wa mwisho, tu kufanya zoa linear hela safu subproblem na kuchukua idadi ya juu. Hii ni utekelezaji kamili ya kile tu alisema. Hivyo sisi kujenga mpya subproblem safu, subproblems. kwanza kuingia ni aidha 0 au ya kwanza kuingia, upeo wa wale wawili. Na kwa ajili ya mapumziko ya subproblems sisi kutumia upprepning halisi sisi kirahisi tu. Sasa sisi compute upeo wa safu yetu subproblems, na kwamba jibu yetu ya mwisho. 

Hivyo muda kiasi gani ni sisi kutumia katika algorithm hii? Kama ve tu kuchukuliwa CS50, basi unaweza kuwa kujadiliwa nafasi sana. Naam, jambo moja kukumbuka ni kwamba mimi kuitwa malloc hapa na n kawaida. Gani zinaonyesha kwamba na wewe? Algorithm hii inatumia nafasi linear. Je, tunaweza kufanya vizuri zaidi? Je, kuna kitu utaona kwamba ni unnecessary kwa compute jibu la mwisho? Nadhani swali bora ni, nini habari je, sisi si haja ya kubeba njia yote hadi mwisho? Sasa, kama sisi kuangalia mistari hii miwili, sisi tu huduma ya juu subproblem uliopita, na sisi tu huduma kuhusu upeo tumekuwa milele kuona hadi sasa. Compute jibu letu la mwisho, sisi hatuhitaji safu nzima. Tunahitaji tu namba ya mwisho, mwisho namba mbili. Mwisho idadi kwa safu subproblem, na namba ya mwisho kwa upeo. Hivyo, kwa kweli, tunaweza Fuse matanzi hizi pamoja na kwenda kutoka nafasi linear nafasi ya mara kwa mara. Hali Jumla hadi sasa, hapa, nafasi nafasi ya subproblem, subproblem yetu safu. Hivyo sasa jumla, hadi sasa, ni jibu kwa subproblem uliopita. Jumla na kwamba, hadi sasa, unafanyika ya max yetu. Sisi compute upeo kama sisi kwenda pamoja. Na hivyo sisi kwenda kutoka nafasi linear nafasi ya mara kwa mara, na sisi pia kuwa na ufumbuzi linear subarray tatizo letu. 

Hizi aina ya maswali utapata wakati wa mahojiano. Je, ni utata wakati; ni nini utata nafasi? Je, unaweza kufanya vizuri? Je, kuna mambo ambayo ni lazima kuweka kote? Mimi alifanya hivyo kuonyesha kwamba uchambuzi unapaswa kuchukua juu yako mwenyewe kama wewe ni kufanya kazi kwa njia ya matatizo haya. Daima kuwa na kuuliza wewe mwenyewe, "Naweza kufanya vizuri?" Kwa kweli, tunaweza kufanya vizuri zaidi kuliko haya? Aina ya swali hila. Huwezi, kwa sababu unahitaji angalau kusoma pembejeo kwa tatizo. Hivyo ukweli kwamba unahitaji angalau kusoma pembejeo kwa tatizo ina maana kwamba huwezi kufanya vizuri zaidi kuliko wakati linear, na huwezi kufanya vizuri zaidi kuliko nafasi ya mara kwa mara. Hivyo hii ni, kwa kweli, ufumbuzi bora wa tatizo hili. Maswali? Sawa. 

Hisa soko tatizo: "Kutokana na safu ya integers n, chanya, sifuri, au hasi, kwamba kuwakilisha bei ya hisa zaidi ya siku n, kuandika kazi kwa compute faida upeo unaweza kufanya kutokana na kwamba unaweza kununua na kuuza hasa 1 hisa ndani ya siku hizi n. " Kimsingi, tunataka kununua chini, kuuza high. Na tunataka takwimu nje faida bora tunaweza kufanya. Tukirudi kwenye ncha wangu, ni nini mara moja wazi, rahisi jibu, lakini ni polepole? Ndiyo? (Mwanafunzi, unintelligible) >> Ndiyo. >> Hivyo ingekuwa tu kwenda ingawa na kuangalia bei ya hisa katika kila hatua katika wakati, (unintelligible). [Yu] Sawa, hivyo ufumbuzi wake - pendekezo yake ya kompyuta chini na kompyuta ya juu si lazima kazi kwa sababu ya juu ili kutokea kabla ya chini. Hiyo ni nini brute force ufumbuzi wa tatizo hili? Je, ni mambo mawili ambayo nahitaji kipekee kuamua faida mimi kufanya? Haki. brute force ufumbuzi ni - oh, hivyo, pendekezo George ni sisi tu haja ya siku mbili kwa kipekee kuamua faida ya siku hizo mbili. Hivyo sisi compute kila jozi, kama kununua / kuuza, compute faida, ambayo inaweza kuwa hasi au chanya au sifuri. Compute faida kubwa kwamba sisi kufanya baada ya iterating juu ya jozi wote wa siku. Hiyo itakuwa jibu yetu ya mwisho. Na ufumbuzi kwamba itakuwa O (n ^ 2), kwa sababu kuna n kuchagua jozi mbili - ya siku kwamba unaweza kuchagua kati ya siku za mwisho. Okay, hivyo nina si kwenda na kwenda juu ya ufumbuzi brute force hapa. Mimi naenda kukuambia kwamba kuna n logi n ufumbuzi. Nini algorithm gani sasa kujua kwamba ni n logi n? Siyo suala hila. 

Changanya aina. Changanya aina ni n logi n, na kwa kweli, njia moja ya kutatua tatizo hili ni kutumia aina kuunganisha aina ya wazo kuitwa, kwa ujumla, kugawanya na kushinda. Na wazo ni kama ifuatavyo. Unataka compute bora kununua / kuuza jozi katika nusu kushoto. Kupata faida bora unaweza kufanya, na tu n kwanza juu ya siku mbili. Kisha unataka oompute bora kununua / kuuza jozi kwenye nusu haki, hivyo n mwisho juu ya siku mbili. Na sasa swali ni jinsi gani sisi kuunganisha hawa ufumbuzi nyuma pamoja? Ndiyo? (Mwanafunzi, unintelligible) >> Sawa. Hivyo basi mimi kuchora picha. Ndiyo? (George, unintelligible) >> Hasa. George ufumbuzi ni sahihi kabisa. Hivyo maoni yake ni, kwanza compute bora kununua / kuuza jozi, na kwamba hutokea katika nusu kushoto, hivyo hebu wito kwamba kushoto, kushoto. Best kununua / kuuza jozi kwamba hutokea katika nusu ya haki. Lakini kama sisi tu ikilinganishwa namba hizi mbili, sisi ni kukosa kesi ambapo sisi kununua hapa na kuuza mahali fulani katika nusu ya haki. Sisi kununua katika nusu kushoto, kuuza katika nusu ya haki. Na njia bora ya compute bora kununua / kuuza jozi kwamba spans halves wote ni kwa compute kima cha chini hapa na compute upeo hapa na kuchukua tofauti zao. Hivyo kesi mbili ambapo jozi kununua / kuuza hutokea tu hapa, tu hapa, au juu ya wote halves hufafanuliwa kwa namba hizi tatu. Hivyo algorithm yetu kwa kuunganisha ufumbuzi yetu nyuma pamoja, tunataka compute bora kununua / kuuza jozi ambapo sisi kununua kwa nusu kushoto na kuuza nusu ya haki. Na njia bora ya kufanya hivyo ni kwa compute bei ya chini katika nusu ya kwanza, bei ya juu katika nusu haki, na kuchukua tofauti zao. kusababisha tatu faida, hizi idadi tatu, unaweza kuchukua upeo wa tatu, na kwamba ni faida bora unaweza kufanya zaidi ya siku hizi kwanza na wa mwisho. Hapa mistari muhimu ni katika nyekundu. Huu ni wito wa kujirudia kwa compute jibu katika nusu kushoto. Huu ni wito wa kujirudia kwa compute jibu katika nusu ya haki. Hizi mbili kwa matanzi compute min na max juu ya nusu ya kushoto na kulia, kwa mtiririko huo. Sasa mimi compute faida spans halves wote, na jibu la mwisho ni upeo wa tatu hizi. Sawa. 

Hivyo, uhakika, tuna algorithm, lakini swali kubwa ni, kile ni utata wakati wa hili? Na sababu mimi zilizotajwa kuunganisha aina ni kwamba aina hii ya kugawanya jibu katika mbili na kisha kuunganisha ufumbuzi yetu nyuma pamoja ni hasa aina ya aina kuunganisha. Hivyo basi mimi kwenda kwa njia ya muda. Kama sisi defined t kazi (n) kuwa idadi ya hatua kwa n siku, zetu mbili kujirudia wito ni kila kwenda gharama t (n / 2), na kuna mawili ya simu hizi. Sasa nahitaji compute chini ya nusu ya kushoto, ambayo naweza kufanya katika n / 2 wakati, pamoja na upeo wa nusu ya haki. Hivyo hii ni haki ya n. Na kisha pamoja na baadhi ya kazi mara kwa mara. Na hii equation upprepning ni hasa equation upprepning kwa aina kuunganisha. Na sisi wote tunajua kwamba kuunganisha aina ni n logi n wakati. Kwa hiyo, algorithm yetu pia n logi n wakati. Je iteration hii mantiki? Tu recap mafupi ya hili: T (n) ni Idadi ya hatua ya compute faida upeo juu ya mwendo wa siku n. njia ya sisi wameigawanya wetu wito kujirudia ni kwa wito ufumbuzi yetu juu ya siku ya kwanza n / 2, hivyo kwamba moja ya simu, na kisha sisi kuwaita tena juu ya nusu ya pili. Basi hiyo ni mbili wito. Na kisha sisi kupata chini ya nusu ya kushoto, ambayo tunaweza kufanya katika muda linear, kupata upeo wa nusu haki, ambayo tunaweza kufanya katika muda linear. Hivyo n / 2 + n / 2 ni tu n. Basi tuna baadhi ya kazi mara kwa mara, ambayo ni kama kufanya hesabu. Hii equation upprepning ni hasa equation upprepning kwa aina kuunganisha. Hivyo, shuffle wetu algorithm ni pia n logi n. Hivyo muda kiasi gani ni sisi kutumia? Turudi kwa kificho. 

swali ni bora, jinsi wengi stack muafaka gani sisi milele kuwa wakati wowote? Tangu sisi ni kutumia recursion, idadi ya muafaka stack huamua nafasi yetu ya matumizi. Hebu fikiria n = 8. Tunatoa wito shuffle juu ya 8, ambayo nitakuita shuffle juu entries kwanza nne, ambayo nitakuita shuffle juu entries mbili za kwanza. Hivyo stack yetu ni - hii ni stack yetu. Na kisha sisi kuwaita shuffle tena juu ya 1, na kwamba ni nini msingi wetu ni kesi, hivyo sisi kurudi mara moja. Je, sisi milele kuwa na zaidi ya muafaka hii wengi stack? No sababu kila wakati sisi kufanya sala, sala ya kujirudia kwa Shuffle, sisi kugawanya kawaida yetu katika nusu. Hivyo idadi ya juu ya muafaka stack sisi milele kuwa wakati wowote ni juu ya utaratibu wa muafaka logi n stack. Kila sura stack ina nafasi ya mara kwa mara, na kwa hiyo jumla ya kiasi cha nafasi, kiasi cha upeo wa nafasi sisi milele kutumia ni O (logi n) nafasi ambapo n ni idadi ya siku. 

Sasa, ujihoji, "Je, sisi kufanya vizuri?" Na hasa, tunaweza kupunguza tatizo tumekuwa tayari kutatuliwa? hint: sisi tu kujadiliwa mbili matatizo mengine kabla ya haya, na si kwenda kuwa shuffle. Tunaweza kubadilisha soko hili la hisa tatizo katika tatizo maximal subarray. Tunawezaje kufanya hivyo? Moja ya wewe? Emmy? (Emmy, unintelligible) [Yu] Hasa. Hivyo tatizo maximal subarray, sisi ni kuangalia kwa jumla juu ya subarray kuendelea. Na pendekezo Emmy kwa tatizo hifadhi, kuzingatia mabadiliko, au delta. Na picha ya hii ni - hii ni bei ya hisa, lakini kama sisi alichukua tofauti kati ya kila siku mfululizo - hivyo tunaona kwamba bei ya upeo, upeo faida tunaweza kufanya ni kama sisi kununua na kuuza hapa hapa. Lakini hebu angalia kuendelea - hebu tuangalie tatizo subarray. Hivyo hapa, tunaweza kufanya - yanaenda hapa na hapa, tuna mabadiliko chanya, na kisha kwenda kutoka hapa na hapa tuna mabadiliko hasi. Lakini basi, inaenda hapa na hapa tuna kubwa mabadiliko chanya. Na haya ni mabadiliko ambayo tunataka jumla juu ya kupata faida yetu ya mwisho. Basi tuna zaidi hasi mabadiliko hapa. muhimu kwa kupunguza hisa zetu tatizo ndani ya tatizo letu maximal subarray ni kuzingatia delta kati ya siku. Hivyo sisi kujenga safu mpya inayoitwa delta, initialize ya kwanza kuingia kwa kuwa 0, na kisha kwa kila delta (i), basi kwamba kuwa tofauti wa pembejeo yangu array (i), na safu (i - 1). Kisha sisi kuwaita utaratibu wetu wa kawaida kwa subarray maximal kupita katika safu ya delta. Na kwa sababu subarray maximal ni linear muda, na hii kupunguza, mchakato huu wa kujenga hii safu delta, pia ni linear muda, basi suluhisho la mwisho kwa ajili ya hifadhi ni O (n) kazi pamoja na O (n) kazi, bado ni O (n) kazi. Hivyo tuna linear wakati ufumbuzi wa tatizo letu. Je, kila mtu kuelewa mabadiliko haya? 

Kwa ujumla, wazo nzuri kwamba unapaswa daima kuwa ni kujaribu kupunguza tatizo mpya kwamba wewe ni kuona. Kama inaonekana familiar na tatizo zamani, kujaribu kupunguza kwa tatizo zamani. Na kama unaweza kutumia zana zote kwamba ve kutumika kwenye tatizo zamani kutatua tatizo mpya. Hivyo wa kufuta, mahojiano ya kiufundi ni changamoto. Matatizo haya pengine baadhi ya matatizo magumu zaidi kwamba unaweza kuona katika mahojiano, hivyo kama huelewi matatizo yote kwamba mimi tu kufunikwa, ni sawa. Hizi ni baadhi ya matatizo ya changamoto zaidi. Mazoezi, mazoezi, mazoezi. Mimi alitoa na matatizo mengi katika karatasi ya mazoezi, hivyo dhahiri kuangalia wale nje. Na bahati nzuri juu ya mahojiano yako. Rasilimali yangu yote ni posted katika link hii, na mmoja wa marafiki zangu mwandamizi imetoa kufanya mahojiano maskhara kiufundi, hivyo kama wewe ni nia, barua pepe Will Yao katika anuani kwamba barua pepe. Kama una baadhi ya maswali, unaweza kuuliza mimi. Je, wewe guys kuwa maswali maalum kuhusiana na mahojiano ya kiufundi au matatizo yoyote tumeona hadi sasa? Sawa. Naam, bahati nzuri na mahojiano yako. [CS50.TV]