[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 <n,
compute mo ang kabuuan, at pagkatapos namin ang maximum na kabuuan na nasaksihan namin sa ngayon.
Ba itong malinaw?
Ano ang malaking O na ito solusyon?
Timewise.
Hindi pa n ^ 2.
Tandaan na umulit namin mula 0 hanggang n,
sa gayon ay ang isa para sa loop.
Namin umulit muli mula sa halos simula sa dulo, isa pang para sa loop.
At ngayon, sa loob na, mayroon kaming upang ipahayag sa ilang kataga bawat entry,
kaya na ang isa pang para sa loop. Kaya mayroon kaming tatlong Nested para sa mga loop, n ^ 3.
Okay. Pupunta ito bilang isang panimulang punto.
Ang aming solusyon ay walang mas masahol pa kaysa sa n ^ 3.
Ba ang lahat maunawaan ang taong malupit na puwersa solusyon?
>> Okay. Ang isang mas mahusay na solusyon ay ang paggamit ng ideya na tinatawag na dynamic programming.
Kung magdadala sa iyo CS124, na algorithm at Data istraktura,
mong maging pamilyar sa diskarteng ito.
At ideya, subukan upang bumuo ng mga solusyon sa mas maliliit na problema sa unang.
Ano ang ibig sabihin ko sa pamamagitan ng ito, kasalukuyan kaming mag-alala tungkol sa dalawang bagay: pagsisimula at pagtatapos.
At na ang nakakainis. Paano kung kami makakuha ng mapupuksa ng isa sa mga parameter?
Ang isang ideya ay sa - lubos na binigyan ng aming orihinal na problema,
mahanap ang maximum na kabuuan ng anumang subarray sa isang hanay [O, n-1].
At ngayon kami ay may isang bagong subproblem, kung saan alam namin, sa aming kasalukuyang index i,
alam namin dapat namin pagtibayin may. Ang aming subarray dapat magtapos sa kasalukuyang index.
Kaya ang natitirang problema ay, kung saan dapat namin simulan aming subarray?
Ba ito magkaroon ng kahulugan? Okay.
Kaya ko ang code up na ito, at tingnan natin kung ano ang ibig sabihin nito.
Sa ang codirectory, isang programa na tinatawag na subarray,
at ito ay tumatagal ng bilang ng mga item,
at nagbabalik ang pinakamalaki subarray kabuuan sa aking shuffled listahan.
Kaya sa kasong ito, ang aming pinakamalaki subarray ay 3.
At na kinuha sa pamamagitan ng lamang gamit ang 2 at 1.
Natin patakbuhin itong muli. Rin 3.
Ngunit ang oras na ito, tandaan kung paano namin nakuha ang 3.
Kinuha namin ang - lang ang dadalhin namin ang 3 mismo
dahil ito ay napapalibutan ng negatibo sa magkabilang panig,
na dalhin ang isang kabuuan <3.
Natin patakbuhin sa 10 mga item.
Oras na ito ito ay 7, namin ang nangungunang 3 at 4.
Oras na ito ito ay 8, at makuha namin na sa pamamagitan ng pagkuha ng 1, 4 at 3.
Kaya upang mabigyan ka ng Swersey sa kung paano maaari naming malutas ang ito transformed problema,
sabihin tingnan sa subarray.
Kami ay ibinigay ang input array, at alam namin ang sagot ay 8.
Isinasaalang-alang namin ang 1, 4, at 3.
Ngunit ipaalam sa tumingin sa kung paano aktwal na nakuha namin na sagot.
Tingnan natin sa pinakamalaki subarray na natapos sa bawat ng mga indeks ng.
Ano ang pinakamalaki subarray na may magtapos sa unang posisyon?
[Mag-aaral] Zero. >> 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]