[Powered by Google Translate] [Seminar: Intervisti Tekniċi]
[Kenny Yu, Università ta 'Harvard]
[Dan huwa CS50.] [CS50.TV]
Hi kulħadd, jien Kenny. Bħalissa jien xjenza junior kompjuter jistudjaw.
I'ma TF CS qabel, u nixtieq I kellha din meta I kien underclassman,
u hu għalhekk li jien tagħti dan is-seminar.
So I hope inti tgawdi minnha.
Dan is-seminar huwa dwar intervisti tekniċi,
u r-riżorsi kollha tiegħi tista 'tinstab fuq din ir-rabta,
din ir-rabta dritt hawn, ftit riżorsi.
So I għamel lista ta 'problemi, fil-fatt, pjuttost ftit problemi.
Wkoll paġna riżorsi ġenerali fejn nistgħu nsibu tips
dwar kif tipprepara għal intervista,
suġġerimenti dwar x'għandek tagħmel waqt intervista attwali,
kif ukoll kif l-approċċ il-problemi u r-riżorsi għal referenza futura.
Dan kollu online.
U biss għal prefazju dan is-seminar, dikjarazzjoni ta 'ċaħda,
bħal dan ma għandu - preparazzjoni intervista tiegħek
m'għandhiex tkun limitata għal din il-lista.
Dan huwa biss maħsub biex ikun gwida,
u inti għandek definittivament tieħu kollox I say bil-qamħ ta 'melħ,
iżda wkoll jużaw dak kollu I użati biex jgħinek fil-preparazzjoni intervista tiegħek.
>> Jien ser tħaffef permezz tal-pjastri li ġejjin
hekk aħna jistgħu jiksbu l-istudji ta 'każijiet attwali.
L-istruttura ta 'intervista għal postion inġinerija tas-softwer,
tipikament huwa 30 sa 45 minuta,
rawnds multipli, jiddependi fuq il-kumpanija.
Spiss inti ser tkun kodifikazzjoni fuq bord abjad.
Allura bord abjad bħal dan, iżda ħafna drabi fuq skala iżgħar.
Jekk int wara intervista telefon, inti probabilment tkun qed tuża
jew collabedit jew Dok Google sabiex ikunu jistgħu jaraw tgħix kodifikazzjoni
filwaqt li qed jiġi intervistat fuq it-telefon.
Intervista nnifisha hija tipikament 2 jew 3 problemi
ittestjar għarfien tiegħek xjenza tal-kompjuter.
U se kważi definittivament jinvolvi kodifikazzjoni.
It-tipi ta 'mistoqsijiet li inti ser tara huma normalment strutturi tad-data u algoritmi.
U meta tagħmel dawn it-tipi ta 'problemi,
dawn se jgħidlek, bħal, dak li huwa l-ħin u l-kumplessità ispazju, big O?
Ħafna drabi dawn jitolbu wkoll ta 'livell ogħla mistoqsijiet,
hekk, tfassil ta 'sistema,
kif tista jistabbilixxu kodiċi tiegħek?
Liema interfaces, liema klassijiet, liema moduli do għandek fis-sistema tiegħek,
u kif dawn jinteraġixxu flimkien?
Allura strutturi tad-data u algoritmi kif ukoll sistemi tfassil.
>> Xi tips ġenerali qabel we adsa fl għal studji ta 'każijiet tagħna.
Naħseb li l-istat l-aktar importanti huwa dejjem tkun ħsieb out loud.
L-intervista suppost tkun iċ-ċans tiegħek biex juru off proċess ta 'ħsieb tiegħek.
Il-punt ta 'l-intervista hija għall-intervistatur biex titkejjel
kif taħseb u kif inti tmur permezz ta 'problema.
L-agħar ħaġa li tista 'tagħmel huwa tkun siekta matul l-intervista sħiħa.
Li jinsab biss mhux tajba.
Meta inti tingħata mistoqsija, inti wkoll tixtieq tagħmel żgur li int tifhem il-kwistjoni.
Allura irrepeti l-kwistjoni lura fi kliem tiegħek
u l-attentat biex jaħdmu ftit każijiet bir-reqqa tat-test sempliċi
tagħmel żgur li int tifhem il-kwistjoni.
Ħidma permezz ta 'każijiet ta' eżaminazzjoni ftit se jagħtik ukoll intwizzjoni dwar kif issolvi din il-problema.
Inti tista 'anki jiskopru xi mudelli ftit biex jgħinuk issolvi l-problema.
Ponta kbira tagħhom huwa li ma jsibux frustrata.
Ma jsibux frustrata.
Intervisti huma sfida, iżda l-agħar ħaġa li tista 'tagħmel,
minbarra li jkunu siekta, għandu jiġi viżibbli frustrata.
Inti ma tridx tagħti l-impressjoni lill-intervistatur.
Ħaġa waħda li inti - hekk, ħafna nies, meta jmorru fi intervista,
jippruvaw biex jippruvaw isibu l-aħjar soluzzjoni 1,
meta verament, hemm normalment soluzzjoni waħda ovvja.
Jista 'jkun bil-mod, jista' jkun ineffiċjenti, iżda inti għandek biss tiddikjara dan,
biss hekk ikollok punt ta 'tluq minn fejn jaħdmu aħjar.
Ukoll, jinnota s-soluzzjoni hija bil-mod, f'termini ta '
big time O kumplessità jew il-kumplessità l-ispazju,
se juru lill-intervistatur li tifhem
dawn il-kwistjonijiet meta tikteb kodiċi.
Allura tibżgħux biex toħroġ bi l-algoritmu sempliċi 1
u mbagħad jaħdmu aħjar minn hemm.
Kwalunkwe mistoqsijiet s'issa? Okay.
>> Mela ejja adsa fis-ewwel problema tagħna.
"Minħabba l-firxa ta 'numri interi n, jiktbu funzjoni li shuffles-firxa
f'dak il-post li l permutazzjonijiet ta 'l-interi n huma ugwalment probabbli. "
U tassumi ikollok disponibbli ġeneratur numru sħiħ każwali
li jiġġenera numru sħiħ fil-firxa minn 0 sa i, firxa nofs.
Ma kulħadd jifhem din il-kwistjoni?
I jagħtuk firxa ta 'numri interi n, u nixtieq li shuffle dan.
Fil-direttorju tiegħi, I kiteb ftit programmi li juru dak li jfisser.
Jien ser shuffle firxa ta '20 elementi,
minn -10 sa 9,
u nixtieq li toħroġ lista bħal din.
Allura dan huwa firxa tiegħi input magħżula, u nixtieq li shuffle dan.
Aħna ser jagħmlu mill-ġdid.
Ma kulħadd jifhem il-kwistjoni? Okay.
Allura huwa sa inti.
Liema huma xi ideat? Tista 'tagħmel dan bħala n ^ 2, n log n, n?
Miftuħa għal suġġerimenti.
Okay. Allura wieħed idea, issuġġerit mill Emmy,
hija l-ewwel kkalkulata numru bl-addoċċ, sħiħ każwali, fi sensiela minn 0 sa 20.
Allura wieħed jassumi firxa tagħna għandha tul ta '20.
Fil dijagramma tagħna ta '20 elementi,
dan huwa firxa input tagħna.
U issa, suġġeriment tagħha huwa li toħloq firxa ġdida,
għalhekk dan se jkun l-firxa output.
U bbażata fuq l-i lura mill rand -
hekk jekk i kien, ejja ngħidu, 17,
kopja l-element 17 fil-pożizzjoni l-ewwel.
Issa għandna bżonn li titħassar - għandna bżonn li ċċaqlaq l-elementi kollha hawn
fuq hekk li għandna vojt fl-aħħar u l-ebda toqob fin-nofs.
U issa aħna irrepeti l-proċess.
Issa aħna pick numru sħiħ każwali ġdid bejn 0 u 19.
Għandna i ġdid hawn, u aħna kopja dan l-element f'din il-pożizzjoni.
Imbagħad aħna bidla oġġetti fuq u aħna irrepeti l-proċess sakemm ikollna firxa ġdida tagħna sħiħa.
X'inhu l-ħin ta 'tħaddim ta' dan algoritmu?
Ukoll, ejja tikkunsidra l-impatt ta 'dan.
Aħna qed iressqu kull element.
Meta aħna tneħħi din i, aħna qed iressqu l-elementi kollha wara li lejn ix-xellug.
U li huwa O (n) spejjeż
għaliex dak li jekk aħna tneħħi l-ewwel element?
Allura għal kull tneħħija, aħna neħħi -
kull tneħħija jeħel O (n) l-operazzjoni,
u peress li aħna n-tneħħija, dan iwassal għal O (n ^ 2) shuffle.
Okay. Allura tajjeb bidu. Tajba bidu.
>> Suġġeriment ieħor huwa l-użu xi ħaġa magħrufa bħala l-shuffle Knuth,
jew il-shuffle Fisher Yates.
U huwa attwalment shuffle ħin lineari.
U l-idea hija simili ħafna.
Għal darb'oħra, aħna għandna firxa input tagħna,
iżda minflok tuża żewġ arrays għall-input tagħna / output,
aħna nużaw l-ewwel porzjon tal-array biex iżommu kont ta 'porzjon shuffled tagħna,
u aħna jżommu rekord, u allura aħna tħalli l-bqija ta 'firxa tagħna għall-porzjon unshuffled.
Allura hawnhekk huwa dak li jfisser. Nibdew off mal - aħna jagħżlu i,
firxa 0-20.
Pointer attwali tagħna hija li tipponta lejn l-indiċi 1.
Aħna jagħżlu xi hawn i
u issa aħna tpartit.
Allura jekk dan kien 5 u dan kien 4,
l-array li jirriżulta se jkollha 5 hawn u 4 hawn.
U issa aħna ninnotaw markatur hawn.
Kollox fuq ix-xellug hija shuffled,
u dak kollu li d-dritt ikun unshuffled.
U issa aħna tista 'tirrepeti l-proċess.
Aħna jagħżlu indiċi każwali bejn l-1 u l-20 issa.
Allura jissoponi ġdida tagħna i huwa hawnhekk.
Issa aħna tpartit din i mal-pożizzjoni ġdida tagħna attwali hawn.
Allura aħna do a iskambji u lura bħal dan.
Let me iġibu l-kodiċi li jagħmilha aktar konkreti.
Nibdew bl-għażla tagħna ta 'i -
nibdew bil i ugwali għal 0, aħna pick j post każwali
fil-porzjon unshuffled tal-firxa, i għal n-1.
Mela jekk jien hawn, jagħżlu indiċi każwali bejn hawn u l-bqija tal-firxa,
u aħna tpartit.
Dan huwa l-kodiċi meħtieġa biex shuffle firxa tiegħek.
Kwalunkwe mistoqsijiet?
>> Ukoll, wieħed meħtieġa kwistjoni hija, għaliex huwa dan korretta?
Għaliex huwa kull permutation ugwalment probabbli?
U jien mhux ser jgħaddu mill-prova ta 'dan,
iżda ħafna problemi fix-xjenza tal-kompjuter jista 'jiġi ppruvat permezz ta' induzzjoni.
Kemm inti familjari ma 'induzzjoni?
Okay. Kessaħ.
Allura inti tista 'tipprova l-korrettezza ta' din algoritmu permezz ta 'induzzjoni sempliċi,
fejn ipoteżi induzzjoni tiegħek tkun, jassumi li
shuffle tiegħi lura kull permutation ugwalment probabbli
sa l-elementi i 1.
Issa, jikkunsidraw i + 1.
U mill-mod nagħżlu j indiċi tagħna li tpartit,
dan iwassal għal - u mbagħad inti taħdem id-dettalji,
mill-inqas prova sħiħa ta 'għaliex dan il-algoritmu prospetti
kull permutation bi probabbiltà ugwali probabbli.
>> Kull dritt, li jmiss il-problema.
Allura "minħabba firxa ta 'numri interi, postive, żero, negattiv,
jiktbu funzjoni li tikkalkula s-somma massima
ta 'kwalunkwe subarray continueous tal-firxa input. "
Eżempju hawnhekk huwa, fil-każ fejn numri kollha huma pożittivi,
allura bħalissa l-aħjar għażla hija li jieħdu l-firxa sħiħa.
1, 2, 3, 4, ugwali għal 10.
Meta inti għandek xi negattivi fil hemm,
f'dan il-każ aħna biss trid l-ewwel tnejn
għaliex jagħżlu -1 u / jew -3 se jġib somma tagħna isfel.
Kultant aħna jista 'jkollhom biex tibda fin-nofs tal-firxa.
Kultant irridu jagħżlu xejn; huwa aħjar li ma tieħu xejn.
U xi kultant huwa aħjar li tieħu l-waqgħa,
minħabba li l-ħaġa wara huwa super kbar. Allura xi ideat?
(Student, mhux intelliġibbli) >> Yeah.
Ejja ngħidu I ma tieħu -1.
Imbagħad waħda I jagħżlu 1,000 u 20,000,
jew I biss jagħżlu l-3 biljun.
Ukoll, l-aħjar għażla hija li jieħdu l-numri.
Dan -1, minkejja li negattiv,
is-somma sħiħa hija aħjar milli kienu I ma jieħdu -1.
Allura waħda mill-ponot semmejt qabel kien li tiddikjara l-ovvju b'mod ċar
u s-soluzzjoni forza brutali ewwel.
X'inhi s-soluzzjoni forza brutali fil din il-problema? Yeah?
[Jane] Well, I think-soluzzjoni forza brutali
tkun li żid sa l-kombinazzjonijiet possibbli (mhux intelliġibbli).
[Yu] Okay. Allura l-idea Jane huwa li jieħdu kull possibbli -
Jien jipparafraża - huwa li jieħdu kull subarray kontinwu possibbli,
jikkomputa somma tagħha, u imbagħad ħu l-massimu ta 'l-subarrays kontinwu possibbli.
What jidentifika b'mod uniku subarray fil array input tiegħi?
Bħal, liema żewġ affarijiet għandi bżonn? Yeah?
(Student, mhux intelliġibbli) >> Dritt.
A aktar baxx marbut fuq l-indiċi u l-indiċi marbuta fuq
unikament jiddetermina subarray kontinwu.
[Student Female] Are we stima huwa firxa ta 'numri uniċi?
[Yu] No Allura mistoqsija tagħha hija, aħna wieħed jassumi firxa tagħna -
huwa array tagħna kollha numri uniċi, u t-tweġiba hija le.
>> Jekk nużaw brute-seħħ tagħna soluzzjoni, imbagħad l-indiċijiet bidu / tmiem
unikament jiddetermina subarray kontinwu tagħna.
Allura jekk aħna jtenni għal daħliet kollha jibdew possibbli,
u għall-entrati kollha aħħarin> jew = tibda, u <n,
inti kkalkulata l-ammont, u allura aħna jieħdu s-somma massima Rajna s'issa.
Huwa dan ċar?
X'inhu l-O kbir ta 'din is-soluzzjoni?
Timewise.
Mhux pjuttost n ^ 2.
Innota li aħna jtenni minn 0 sa n,
b'tali mod li wieħed għal linja.
Aħna jtenni mill-ġdid minn kważi l-bidu sat-tmiem, ieħor għall-loop.
U issa, fi ħdan dak, għandna biex qosor kull dħul,
hekk li l-ieħor għall-loop. Allura għandna tliet nested għal-linji, n ^ 3.
Okay. Dan imur bħala punt tat-tluq.
Soluzzjoni tagħna huwa mhux agħar minn n ^ 3.
Ma kulħadd jifhem is-soluzzjoni forza brutali?
>> Okay. Soluzzjoni aħjar tkun qiegħda tuża idea imsejħa programmazzjoni dinamiku.
Jekk tieħu CS124, li huwa algoritmi u Strutturi tad-Data,
inti se jsiru familjari ħafna ma 'din it-teknika.
U l-idea hija, jippruvaw jibnu soluzzjonijiet għall-problemi iżgħar ewwel.
What I jfisser minn dan hija, għandna attwalment għalfejn tinkwieta dwar żewġ affarijiet: bidu u t-tmiem.
U li tedjanti. X'jiġri jekk nistgħu jeħles ta 'waħda minn dawk il-parametri?
Wieħed idea hija li - we're mogħtija problema oriġinali tagħna,
isibu s-somma massima ta 'kull subarray fil-firxa [O, n-1].
U issa għandna subproblem ġdid, fejn nafu, fl-indiċi attwali tagħna i,
nafu wieħed irid jikkonkludi hemmhekk. Subarray tagħna għandha tintemm fl-indiċi attwali.
Allura l-problema jibqa 'huwa, fejn għandhom nibdew subarray tagħna?
Ma dan jagħmel sens? Okay.
Allura stajt kodifikati dan up, u ejja nħarsu lejn dak li dan ifisser.
Fil-codirectory, hemm programm imsejjaħ subarray,
u li tieħu għadd ta 'oġġetti,
u dan jirritorna s-somma subarray massimu fil-lista shuffled tiegħi.
Allura f'dan il-każ, subarray massima tagħna huwa 3.
U li jittieħdu bi ftit użu 2 u 1.
Ejja run mill-ġdid. Huwa wkoll 3.
Iżda dan iż-żmien, innota kif aħna ltqajna l-3.
Aħna ħa l - aħna biss jieħdu l-3 innifsu
għaliex dan huwa mdawra mill-negattivi fuq iż-żewġ naħat,
li se jġib somma <3.
Ejja jimxu fuq 10 punti.
Din id-darba huwa 7, nieħdu l-3 ewlieni u 4.
Din id-darba huwa 8, u irridu jiksbu li billi tieħu 1, 4 u 3.
Allura biex jagħtuk intuwizzjoni dwar kif nistgħu issolvi din il-problema trasformati,
ejja tagħti ħarsa lejn din subarray.
Aħna jingħataw din array input, u nafu l-risposta hija 8.
Nieħdu l-1, 4, u 3.
Imma ejja nħarsu lejn kif għandna attwalment marret din ir-risposta.
Ejja nħarsu lejn l-subarray massima li ntemmet f'kull wieħed minn dawn l-indiċi.
X'hemm-subarray massima li għandha tintemm fil-pożizzjoni ewwel?
[Student] Zero. >> Zero. Just ma jieħdu l--5.
Hawnhekk huwa għaddej biex tkun 0 ukoll. Yeah?
(, Student mhux intelliġibbli)
[Yu] Oh, sorry, huwa -3.
Allura dan huwa ta '2, din hija -3.
Okay. Allura -4, x'inhu l-subarray massima li tintemm din il-pożizzjoni
fejn huwa -4 fi? Zero.
Wieħed? 1, 5, 8.
Issa, I għandu jintemm fil-post fejn ikun -2 fuq.
Allura 6, 5, 7, u l-aħħar wieħed huwa 4.
Jafu li dawn huma daħliet tiegħi
għall-problema trasformati I fejn għandhom jintemmu f'kull wieħed minn dawn l-indiċi,
allura tweġiba finali tiegħi huwa biss, tieħu jiknes madwar,
u tieħu l-għadd massimu.
Allura f'dan il-każ huwa 8.
Dan jimplika li l-subarray massima jispiċċa f'dan indiċi,
u beda x'imkien quddiemha.
Ma kulħadd jifhem dan subarray trasformat?
>> Okay. Ukoll, ejja insemmu l-rikorrenza għal dan.
Ejja jikkunsidraw biss l-iskrizzjonijiet ewwel ftit.
Allura hawnhekk kien 0, 0, 0, 1, 5, 8.
U mbagħad kien hemm -2 hawn, u li jinġiebu l-isfel sa 6.
Mela jekk jien sejħa-dħul fil-pożizzjoni i subproblem (i),
kif nista 'nuża l-risposta għal subproblem preċedenti
biex twieġeb din subproblem?
Jekk I tħares lejn, ejja ngħidu, dan id-dħul.
Kif nista 'tikkalkula l-risposta 6 billi tħares lejn
kombinazzjoni ta 'din il-firxa u t-tweġibiet għall subproblems preċedenti f'dan il-firxa? Iva?
[Student Female] Tieħu l-firxa ta 'somom
fil-pożizzjoni dritt qabel dan, hekk l-8,
u allura inti żid l-subproblem kurrenti.
[Yu] Mela suġġeriment tagħha hi li tħares lejn dawn iż-żewġ numri,
dan in-numru u dan in-numru.
Allura dan 8 jirreferi għar-risposta għall-subproblem (i - 1).
U ejja sejħa A. tiegħi firxa input
Sabiex issib subarray massima li jispiċċa fil-pożizzjoni i,
Għandi żewġ għażliet: I jistgħu jew ikomplu l-subarray
li ntemmet fil-indiċi ta 'qabel, jew jibdew firxa ġdida.
I Jekk kellhom ikomplu l-subarray li beda fl-indiċi ta 'qabel,
allura s-somma massima I jistgħu jiksbu hija t-tweġiba għall-subproblem preċedenti
flimkien mal-annotazzjoni firxa attwali.
Iżda, Għandi wkoll l-għażla ta 'bidu ta subarray ġdid,
f'liema każ it-total huwa 0.
Allura l-tweġiba hija max ta '0, subproblem i - 1, kif ukoll id-dħul firxa attwali.
Ma dan rikorrenza jagħmel sens?
Rikorrenza tagħna, kif aħna biss skoperti, huwa subproblem i
huwa ugwali għall-massimu ta 'l subproblem preċedenti flimkien ma' dħul tiegħi firxa attwali,
li jfisser tkompli l subarray ta 'qabel,
jew 0, jibdew subarray ġdid fil indiċi kurrenti tiegħi.
U ladarba aħna bnew din it-tabella ta 'soluzzjonijiet, allura tweġiba finali tagħna,
biss tagħmel mesħiet lineari madwar l-firxa subproblem
u tieħu l-għadd massimu.
Dan huwa ta 'implimentazzjoni eżatta ta' dak I biss qal.
Allura aħna joħolqu firxa subproblem ġdid, subproblems.
L-ewwel dħul huwa jew 0 jew l-ewwel dħul, il-massimu ta 'dawn iż-żewġ.
U għall-bqija tal-subproblems
aħna nużaw l-rikorrenza eżatt aħna biss skoperti.
Issa aħna kkalkulata l-massimu ta 'firxa subproblems tagħna, u li l-tweġiba finali tagħna.
>> Allura kemm l-ispazju huma aħna jużaw f'din algoritmu?
Jekk inti ħadthom biss jittieħdu CS50, allura inti jista 'ma jkollhomx diskussi spazju ħafna.
Ukoll, ħaġa waħda li wieħed jinnota li I imsejħa malloc hawn ma n daqs.
Xi jfisser li jissuġġerixxu li inti?
Dan algoritmu użi ispazju lineari.
Nistgħu nagħmlu aħjar?
Hemm xi ħaġa li tinnota li m'hemmx lok li jiġu kkalkulati l-risposta finali?
I raden mistoqsija aħjar hija, liema informazzjoni
għandna ma jeħtiġilhomx ikollhom it-triq kollha sa l-aħħar?
Issa, jekk inħarsu lejn dawn iż-żewġ linji,
aħna biss kura dwar il-subproblem ta 'qabel,
u aħna biss jimpurtahom-massimu aħna stajt qatt dehret sallum.
Biex tiġi kkalkulata tweġiba finali tagħna, aħna ma bżonn l-firxa sħiħa.
Aħna biss bżonn l-aħħar numru, l-aħħar żewġ numri.
Numru aħħar għall-firxa subproblem, u n-numru l-aħħar għall-massimu.
Għalhekk, fil-fatt, nistgħu fjus dawn loops flimkien
u jmorru mill-ispazju lineari għall-ispazju kostanti.
Somma kurrenti s'issa, hawn, jissostitwixxi l-irwol ta 'subproblem, array subproblem tagħna.
Somma hekk kurrenti, s'issa, hija t-tweġiba għall-subproblem preċedenti.
U din is-somma, s'issa, jieħu l-post ta 'max tagħna.
Aħna kkalkulata l-massimu kif aħna jmorru flimkien.
U hekk immorru mill-ispazju lineari għall-ispazju kostanti,
u aħna għandna wkoll soluzzjoni lineari għall-problema subarray tagħna.
>> Dawn it-tipi ta 'mistoqsijiet li inti se tikseb matul l-intervista.
X'inhu l-kumplessità żmien; x'inhi l-kumplessità ispazju?
Tista 'tagħmel aħjar? Hemm affarijiet li huma meħtieġa biex iżommu madwar?
Jien għamilt dan li jenfasizzaw l-analiżi li għandek tieħu fuq tiegħek
kif inti qed jaħdmu permezz ta 'dawn il-problemi.
Dejjem 'tistaqsi lilek innifsek, "Nista' nagħmel aħjar?"
Fil-fatt, nistgħu nagħmlu aħjar minn dan?
Sort ta 'kwistjoni trick. Inti ma tistax, għaliex ikollok bżonn li
inqas aqra l-input għall-problema.
Allura l-fatt li għandek bżonn mill-inqas taqra l-input għall-problema
ifisser li inti ma tistax tagħmel aħjar minn żmien lineari,
u inti ma tistax tagħmel aħjar minn spazju kostanti.
Allura dan huwa, fil-fatt, l-aħjar soluzzjoni għal din il-problema.
Mistoqsijiet? Okay.
>> Problema tas-suq Stock:
"Minħabba l-firxa ta 'numri interi n, pożittivi, żero, jew negattiva,
li jirrappreżentaw l-prezz ta 'stokk jgħaddi jiem n,
jiktbu funzjoni biex tiġi kkalkulata l-profitt massimu inti tista 'tagħmel
peress li inti tixtri u tbigħ eżattament 1-istokk fi żmien dawn il-jiem n. "
Essenzjalment, irridu li jixtru baxx, ibigħu għolja.
U rridu biex insemmu l-aqwa profitt nistgħu nagħmlu.
Tmur lura għall-ponta tiegħi, dak li huwa l-ewwel ċar, risposta sempliċi, iżda huwa bil-mod?
Iva? (Student, mhux intelliġibbli) >> Iva.
>> Allura inti biss tmur għalkemm u ħarsa lejn il-prezzijiet istokk
f'kull punt ta 'żmien, (mhux intelliġibbli).
[Yu] Okay, so soluzzjoni tagħha - suġġeriment tagħha tal-kompjuters
l-aktar baxx u l-komputazzjoni tal-ogħla ma neċessarjament xogħol
minħabba li l-ogħla jistgħu jseħħu qabel l-aktar baxx.
Allura dak li huwa s-soluzzjoni forza brutali biex din il-problema?
Liema huma l-żewġ affarijiet li għandi bżonn biex unikament jiddeterminaw il-profitt nagħmel? Dritt.
Is-soluzzjoni forza brutali huwa - oh, iva, suġġeriment George huwa għandna bżonn biss jumejn
sabiex unikament jiddeterminaw il-profitt ta 'dawk il-jumejn.
Allura aħna jikkomputa kull par, bħal xiri / bejgħ,
kkalkulata l-profitt, li jista 'jkun negattiv jew pożittiv jew żero.
Ikkalkola l-profitt massimu li nagħmlu wara iterazzjoni fuq kull par ta 'jiem.
Dak se jkun tweġiba finali tagħna.
U din is-soluzzjoni se tkun O (n ^ 2), minħabba li hemm n jagħżlu żewġ pari -
ta 'ġranet li inti tista' tagħżel fost jiem finali.
Okay, hekk jien mhux se jmorru fuq is-soluzzjoni forza brutali hawn.
Jien ser jgħidlek li hemm xi n log soluzzjoni n.
What do you algoritmu bħalissa taf li huwa n log n?
Mhuwiex kwistjoni trick.
>> Jingħaqdu tip. Jingħaqdu tip huwa n log n,
u fil-fatt, mod wieħed ta 'soluzzjoni ta' din il-problema huwa l-użu
tip tip ta 'idea jingħaqdu imsejħa, b'mod ġenerali, jaqsam u jirbħu.
U l-idea hija kif ġej.
Inti tixtieq biex tiġi kkalkulata l-aħjar jixtru / bejgħ par fil-nofs tax-xellug.
Sib l-aqwa profitt inti tista 'tagħmel, biss bl-n 1 fuq jumejn.
Imbagħad inti tixtieq li oompute l-aħjar jixtru / bejgħ par fuq il-nofs tal-lemin,
sabiex il-n-aħħar fuq jumejn.
U issa l-kwistjoni hija, kif nistgħu jingħaqdu dawn is-soluzzjonijiet lura flimkien?
Iva? (, Student mhux intelliġibbli)
Okay. >> So let me tfassal stampa.
Iva? (George, mhux intelliġibbli)
>> Eżattament. Soluzzjoni Ġorġ huwa eżattament id-dritt.
Allura suġġeriment tiegħu huwa, l-ewwel kkalkulata l-aħjar jixtru / jbiegħu par,
u li jseħħ fil-nofs tax-xellug, so ejja sejħa li xellug, xellug.
Best xiri / bejgħ par li jseħħ fil-nofs tal-lemin.
Imma jekk aħna biss meta mqabbel dawn iż-żewġ numri, aħna qed nieqsa l-każ
fejn nixtru hawn u jbiegħu x'imkien fil-nofs tal-lemin.
Nixtru fil-nofs tax-xellug, jbiegħu fil-nofs tal-lemin.
U l-aħjar mod biex tiġi kkalkulata l-aħjar jixtru / jbiegħu par li tifrex żewġ nofsijiet
hu li jiġu kkalkulati l-minimu hawn u kkalkulata l-massimu hawn
u jieħdu differenza tagħhom.
Allura l-żewġ każijiet fejn il-par xiri / bejgħ iseħħ biss hawn,
biss hawn, jew fuq iż-żewġ nofsijiet huwa definit minn dawn in-numri tlieta.
Allura algoritmu tagħna biex jingħaqdu soluzzjonijiet tagħna lura flimkien,
irridu biex tiġi kkalkulata l-aħjar jixtru / jbiegħu par
fejn nixtru fuq in-nofs tax-xellug u jbiegħu fuq l-nofs tal-lemin.
U l-aħjar mod biex tagħmel dan huwa li jiġu kkalkulati l-orħos prezz fl-ewwel nofs,
l-ogħla prezz fis-nofs tal-lemin, u jieħdu differenza tagħhom.
It-3 li jirriżultaw fi profitti, dawn in-numri 3, tieħu l-massimu tal-tlieta,
u dak l-profitt aħjar li tista 'tagħmel aktar dawn il-jiem ewwel u tmiem.
Hawn il-linji importanti huma bl-aħmar.
Din hija sejħa jirrikorri biex tiġi kkalkulata r-risposta fil-nofs tax-xellug.
Din hija sejħa jirrikorri biex tiġi kkalkulata r-risposta fil-nofs tal-lemin.
Dawn iż-żewġ linji għall kkalkulata l-min u l-mass fuq in-nofs tax-xellug u tal-lemin, rispettivament.
Now I kkalkulata l-profitt li tifrex żewġ nofsijiet,
u t-tweġiba finali huwa l-massimu ta 'dawn it-tliet.
Okay.
>> Allura, żgur, għandna algoritmu, iżda l-kwistjoni akbar huwa,
dak li huwa l-kumplessità żmien ta 'dan?
U r-raġuni għaliex semmejt sort jingħaqdu hija li din il-forma ta 'qasma-risposta
fis tnejn u mbagħad jingħaqdu soluzzjonijiet tagħna lura flimkien
huwa eżattament l-forma ta 'tip jingħaqdu.
So let me jgħaddu t-tul.
Jekk aħna iddefinixxa t-funzjoni (n) li jkun in-numru ta 'passi
għal ġranet n,
żewġ sejħiet tagħna rikursivi
huma kull va ispiża t (n / 2),
u hemm tnejn minn dawn is-sejħiet.
Issa għandi bżonn biex tiġi kkalkulata l-minimu tan-nofs tax-xellug,
li I tista 'tagħmel fil-n / 2 darba, flimkien mal-massimu ta' l-nofs tal-lemin.
Allura dan huwa biss n.
U mbagħad flimkien ma 'xi xogħol kostanti.
U din l-ekwazzjoni rikorrenza
huwa eżattament l-ekwazzjoni rikorrenza ta sort jingħaqdu.
U lkoll nafu li tip jingħaqdu huwa log n n żmien.
Għalhekk, algoritmu tagħna hija wkoll n log n-żmien.
Ma dan iterazzjoni jagħmel sens?
Just terġa qasira ta 'dan:
T (n) huwa n-numru ta 'passi biex tiġi kkalkulata l-profitt massimu
matul il-kors ta 'ġranet n.
Il-mod kif aħna maqsuma sejħiet jirrikorri tagħna
huwa billi ċċempel soluzzjoni tagħna fil-jiem n / 2 1,
b'tali mod li sejħa waħda,
u allura nitolbu għal darb'oħra fuq it-tieni nofs.
Allura dak żewġ sejħiet.
U allura insibu minimu fuq in-nofs tax-xellug, li nistgħu nagħmlu fil-ħin lineari,
isibu l-massimu tal-nofs tal-lemin, li nistgħu nagħmlu fil-ħin lineari.
Allura n / 2 + n / 2 hija biss n.
Imbagħad għandna xi xogħol kostanti, li hija bħal tagħmel aritmetika.
Dan ekwazzjoni rikorrenza huwa eżattament l-ekwazzjoni rikorrenza ta sort jingħaqdu.
Għalhekk, algoritmu shuffle tagħna huwa wkoll n log n.
Allura kemm l-ispazju huma aħna jużaw?
Ejja ħa mmorru lura għall-kodiċi.
>> A kwistjoni aħjar hija, kif ħafna frames munzell għandna qatt fi kwalunkwe mument?
Minħabba li aħna qed jużaw recursion,
in-numru ta 'frejms munzell jiddetermina użu spazjali tagħna.
Ejja jikkunsidraw n = 8.
Nappellaw shuffle fit-8,
li se ssejjaħ shuffle fuq l-ewwel erba entrati,
li se jsejjaħ shuffle fuq l-ewwel żewġ daħliet.
Allura munzell tagħna huwa - dan huwa munzell tagħna.
U allura nitolbu shuffle ġdid fl-1,
u dan huwa dak il-każ bażi tagħna hija, hekk aħna lura immedjatament.
Do we qatt aktar minn dan frejms munzell ħafna?
No Minħabba li kull darba li nagħmlu xi invokazzjoni,
a invokazzjoni rikursivi li shuffle,
aħna jaqsam daqs tagħna fil nofs.
Allura l-għadd massimu ta 'frejms munzell għandna qatt fi kwalunkwe mument
huwa fuq l-ordni ta 'frejms log n munzell.
Kull qafas munzell għandha spazju kostanti,
u għalhekk l-ammont totali ta 'l-ispazju,
l-ammont massimu ta 'spazju li aħna qatt tuża hija O (log n) l-ispazju
fejn n huwa n-numru ta 'ġranet.
>> Issa, dejjem staqsi lilek innifsek, "Nistgħu nagħmlu aħjar?"
U partikolarment, nistgħu tnaqqas dan għal problema konna diġà solvuti?
A ħjiel: aħna biss diskussi żewġ problemi oħra qabel dan, u mhuwiex ser ikun shuffle.
Nistgħu jikkonvertu din il-problema istokk tas-suq fil-problema subarray massimu.
Kif nistgħu nagħmlu dan?
Wieħed mill inti? Emmy?
(Emmy, mhux intelliġibbli)
[Yu] Eżattament.
Allura l-problema subarray massimu,
aħna qed infittxu somma fuq subarray kontinwu.
U suġġeriment Emmy għall-problema ħażniet,
jikkunsidraw il-bidliet, jew il-deltas.
U stampa ta 'dan huwa - dan huwa l-prezz ta' stokk,
iżda jekk aħna ħa d-differenza bejn kull jum konsekuttiv -
hekk naraw li l-prezz massimu, profitt massimu nistgħu jagħmlu
huwa jekk nixtru u jbiegħu hawn hawn.
Imma ejja nħarsu lejn il-kontinwu - ejja nħarsu lejn il-problema subarray.
Allura hawn, nistgħu nagħmlu - jmorru minn hawn hawn,
għandna bidla pożittiva, u mbagħad tmur minn hawn biex hawnhekk għandna bidla negattiva.
Iżda mbagħad, li jmorru minn hawn biex hawnhekk għandna bidla kbira u pożittiva.
U dawn huma l-bidliet li rridu qosor biex tikseb profitt finali tagħna.
Imbagħad għandna bidliet aktar negattivi hawn.
Il-qofol biex jitnaqqsu l-problema istokk tagħna fis-problema tagħna subarray massimu
huwa li tikkunsidra l-deltas bejn jiem.
Allura aħna toħloq firxa ġdida msejħa deltas,
initialize-ewwel dħul li jkun 0,
u allura għal kull delta (i), let li jkun id-differenza
ta 'input firxa tiegħi (i), u array (i - 1).
Imbagħad aħna sejħa proċedura ta 'rutina tagħna għal subarray massimu
tgħaddi fil-firxa ta 'delta s.
U minħabba subarray massimu huwa żmien lineari,
u dan it-tnaqqis, dan il-proċess ta 'ħolqien ta' din array delta,
huwa wkoll żmien lineari,
imbagħad is-soluzzjoni finali għall-istokkijiet huwa O (n) 'xogħol b'żieda O (n) ix-xogħol, għadu O (n) ix-xogħol.
Allura aħna għandna soluzzjoni ħin lineari għall-problema tagħna.
Ma kulħadd jifhem dan it-trasformazzjoni?
>> B'mod ġenerali, hija idea tajba li għandek dejjem ikollhom
huwa tipprova tnaqqas problema ġdida li int tara.
Jekk jidher familjari għal problema antika,
jippruvaw naqqsitu għal problema antika.
U jekk inti tista 'tuża l-għodda kollha li inti stajt użati fuq il-problema antika
biex isolvu l-problema ġdida.
Allura biex nagħlaq, intervisti tekniċi huma sfida.
Dawn il-problemi huma probabbilment xi wħud mill-problemi l-aktar diffiċli
li inti tista 'tara fl-intervista,
hekk jekk inti ma tifhimx il-problemi kollha li jien biss koperti, huwa okay.
Dawn huma wħud mill-problemi aktar ta 'sfida.
Prattika, il-prattika, il-prattika.
I taw ħafna ta 'problemi fil-volantin, hekk definittivament check out dawn.
U Xorti tajba fuq intervisti tiegħek. Ir-riżorsi kollha tiegħi huma stazzjonati fuq din ir-rabta,
u wieħed mill-ħbieb tiegħi anzjani offriet li tagħmel intervisti mock tekniċi,
hekk jekk int interessat, email Will Yao f'dak l-indirizz email.
Jekk għandek xi mistoqsijiet, inti tista 'titlob lili.
Do you guys jkollhom kwistjonijiet speċifiċi relatati mad-intervisti tekniċi
jew kwalunkwe problemi aħna stajt tidher s'issa?
Okay. Ukoll, Xorti tajba fuq intervisti tiegħek.
[CS50.TV]