[Powered by Google Translate] [Seminario: Teknika Intervjuoj]
[Kenny Yu, Harvard University]
[Jen CS50.] [CS50.TV]
Saluton ĉiuj, Mi estas Kenny. Mi estas aktuale junior studi komputiko.
Mi estas eks-CS TF, kaj mi deziras, ke mi havis tiun, kiam mi estis subklasulo,
kaj tial mi donas ĉi seminario.
Do mi esperas ke vi ĝuos ĝin.
Tiu seminario temas pri teknika intervjuoj,
kaj ĉiuj miaj rimedoj troveblas ĉe ĉi tiu ligilo,
ĉi ligilon ĉi tie, paro de rimedoj.
Tiam mi faris liston de problemoj, fakte, sufiĉe da problemoj.
Ankaŭ ĝenerala rimedoj paĝo kie ni povas trovi konsiloj
pri kiel pretigi por intervjuo,
konsiloj de kion vi devas fari dum reala intervjuo,
tiel kiel kiel alproksimigi problemoj kaj rimedoj por estonta referenco.
Estas ĉio ensalutintaj.
Kaj ĝuste al antaŭparolo ĉi seminario, oni disclaimer,
kiel tiu ne devus - via intervjuo preparado
ne devus esti limigita al tiu listo.
Tiu estas nur signifis esti gvidas,
kaj vi devas definitive preni ĉion, kion mi diras per greno de salo,
sed ankaŭ uzi ĉio Iam mi helpos vin en via intervjuo preparado.
>> Mi iros por akceli tra la venontaj diapozitivoj
tiel ni povos atingi al la reala kazo studoj.
La strukturo de intervjuo dum programado postion,
tipe ĝi estas 30 ĝis 45 minutoj,
multnombraj ĉirkaŭvojoj, depende de la kompanio.
Ofte vi estos kodigo sur blanka tabulo.
Do blankan tabulon kiel ĉi tiu, sed ofte sur pli malgranda skalo.
Se vi havas telefonon intervjuo, vi verŝajne uzas
ĉu collabedit aŭ Google Doc do ili povas vidi vin vivi kodigo
dum vi esti intervjuita pri la telefono.
Intervjuo mem estas tipe 2 aŭ 3 problemoj
provante vian komputiko scio.
Kaj estos preskaŭ certe engaĝi kodigo.
La tipoj de demandoj kiujn vi vidos kutime datumstrukturoj kaj algoritmoj.
Kaj por fari tiajn problemojn,
ili demandos vin, kiel, kio estas la tempo kaj spaca komplekseco, granda O?
Ili ofte ankaŭ peti pli alta-nivelo demandoj,
tiel, desegnante sistemo,
kiel vi jalonan via kodo?
Kio interfacoj, kion klasoj, kio moduloj vi havas en via sistemo,
kaj kion tiuj interagi kune?
Do datumstrukturoj kaj algoritmoj tiel kiel desegni sistemoj.
>> Iuj ĝeneralaj konsiloj antaŭ ol ni plonĝi en nia kazo studoj.
Mi kredas ke la plej grava regulo estas ĉiam pensas laŭte.
La intervjuo estas supozata esti via ŝanco por montri vian penson procezo.
La punkto de la intervjuo estas por la intervjuanto por taksi
kiel vi opinias kaj kiel vi iros tra problemo.
La plej malbona afero vi povas fari estas silenti tra la tuta intervjuo.
Tio estas nur nenio bona.
Kiam vi donas al demando, vi ankaŭ volas certigi vin kompreni la demandon.
Do ripeti la demandon reen en viaj propraj vortoj
kaj provi labori funda kelkaj simpla provo kazoj
certigi vi komprenas la demandon.
Laborante per kelkaj provoj kazoj ankaŭ doni al vi intuicio pri kiel solvi tiun problemon.
Vi eble eĉ malkovri kelkajn ŝablonoj por helpi vin solvi la problemon.
Ilia granda pinto estas ne get frustrita.
Ili ne frustrita.
Intervjuoj estas defia, sed la plej malbona afero vi povas fari,
krom esti silentaj, devas esti videble frustrita.
Vi ne volas doni tiun impreson al intervjuinto.
Unu afero, kiun vi - jes, multe da homoj, kiam ili iros en intervjuo,
ili provas provi trovi la plej bona solvo unua,
kiam vere, estas kutime glaringly evidenta solvo.
Povus esti malrapida, ĝi povus esti senutilaj, sed vi devas simple indiki gxin,
nur tiom vi havas deirpunkto de kiu funkcios pli bone.
Ankaŭ, markante la solvo estas malrapida, en terminoj de
granda a tempa komplekseco aŭ spaca komplekseco,
pruvos al la intervjuanto ke vi komprenas
tiuj temoj kiam skribante kodon.
Do ne timu veni supren kun la plej simpla algoritmo unua
kaj tiam funkcias pli bone de tie.
Demandojn ĝis nun? Okay.
>> Do estu la plonĝi en nia unua problemo.
"Donita aro de n entjeroj, skribi funkcio kiu ludkartaro la tabelo
en loko tia ke ĉiuj permutoj de la n entjeroj estas egale verŝajna. "
Kaj alpreni vi havas disponebla hazarda entjero generilo
kiu generas entjero en rango de 0 al mi, duono gamo.
Ĉu ĉiuj komprenas ĉi demando?
Mi donas al vi tabelo de n entjeroj, kaj mi volas ke vi barajar ĝin.
En mia dosierujo, mi skribis kelkajn programojn por pruvi kion mi volas diri.
Mi tuj barajar tabelo de 20 elementoj,
el -10 al +9,
kaj mi volas ke vi Eligu listo ŝatas tion.
Do ĉi tiu estas mia ordo enigo tabelo, kaj mi volas ke vi barajar ĝin.
Ni tion faros denove.
Ĉu ĉiuj komprenas la demandon? Okay.
Do ĝi estas ĝis vi.
Kio estas iuj ideoj? Ĉu vi povas fari tion kiel n ^ 2, n logo n, n?
Malfermu al sugestoj.
Okay. Do unu ideo, proponita de Emmy,
estas unue komputi hazarda nombro, hazarda entjero, en rango de 0 al 20.
Do supozi nia tabelo havas longitudon de 20.
En la diagramo de 20 elementoj,
tio estas nia eniro tabelo.
Kaj nun, ŝia sugesto estas krei novan tabelo,
tial ĉi tiu estos la eligo tabelo.
Kaj bazita sur la i revenis por rand -
do se i estis, diru, 17,
kopii la 17a elemento en la unua pozicio.
Nun ni bezonas forigi - ni bezonas ŝanĝi ĉiujn elementojn tie
super tiel ke ni havas truon en la fino kaj neniu truoj en la mezo.
Kaj nun ni ripetos la procezon.
Nun oni prenas novajn hazarda entjero inter 0 kaj 19.
Ni havas novan i tie, kaj ni kopias ĉi elemento en tiun pozicion.
Tiam ni ŝanĝi artikoloj super kaj ni ripeti la procezon ĝis ni havos niajn plena nova tabelo.
Kio estas la tempo de ekzekuto de ĉi tiu algoritmo?
Nu, ni konsideru la trafo de ĉi.
Ni sxangxigxantaj ĉiu elemento.
Kiam ni forpreni ĉi mi, ni estas sxangxigxantaj ĉiuj elementoj post ĝi al la maldekstra.
Kaj tio estas O (n) kosto
ĉar kion se ni forpreni la unuan elementon?
Do por ĉiu kopio, ni forigi -
ĉiu forigo falas al O (n) operacio,
kaj kiel ni n translokadoj, tio kondukas al O (n ^ 2) barajar.
Okay. Tiel bona komenco. Bona komenco.
>> Alia sugesto estas uzi iu konata kiel la Knuth barajar,
aŭ la Fiŝista-Jaktoj barajar.
Kaj estas vere lineara tempo barajar.
Kaj la ideo estas tre simila.
Denove, ni havas niajn enigo tabelo,
sed anstataŭ uzi du tabeloj por nia eniro / eligo,
ni uzas la unuan parton de la tabelo por kontroli kiu faras nia barajan parton,
kaj ni observu spuro, kaj poste ni lasos la resto de nia tabelo por la unshuffled parton.
Do jen kion mi volas diri. Ni dividas kun - ni elekti i,
tabelo de 0 al 20.
Nia nuna puntero estas indikante la unuan indicon.
Ni elektas iu mi tie
kaj nun ni interŝanĝi.
Do, se ĉi tio estis 5 kaj tio estis 4,
la rezultanta tabelo havos 5 tie kaj 4 tie.
Kaj nun ni rimarku markilo tie.
Ĉiu al la maldekstra estas barajadas,
kaj ĉiu al la dekstra unshuffled.
Kaj nun ni povas ripeti la procezon.
Ni elektas hazarda indekso inter 1 kaj 20 nun.
Do supozu nia nova i estas tie.
Nun ni interŝanĝi ĉi i kun nia nuna nova pozicio tie.
Do ni estas interŝanĝi tien kaj reen kiel ĉi tio.
Lasu min porti la kodon por fari ĝin pli konkreta.
Ni komencu per nia elekto de i -
ni starti kun i egalas al 0, oni prenas hazarda loko j
en la unshuffled parto de la tabelo, i al n-1.
Do, se mi estas ĉi tie, elektu hazarda indekso inter ĉi tie kaj la resto de la tabelo,
kaj ni interŝanĝi.
Tio estas la tuta kodo necese barajar vian tabelo.
Demandojn?
>> Nu, unu bezonis demando estas, kial tiu korekta?
Kial ĉiu permuto egale verŝajna?
Kaj mi ne iros tra la pruvo de ĉi tio,
sed multaj problemoj en komputiko povas esti pruvita per indukto.
Kiel multaj el vi estas familiara kun indukto?
Okay. Cool.
Do vi povas pruvi la praveco de ĉi tiu algoritmo per simpla indukto,
kie estas via indukta hipotezo estus, supozi ke
mia barajar revenas ĉiun permuto egale verŝajna
supren al la unua i elementoj.
Nun, konsideru mi + 1.
Kaj laux la vojo ni elekti nia indekso j por interŝanĝi,
tio kondukas al - kaj tiam vi laboras ekster la detaloj,
almenaŭ plenan pruvon pri tio, kial tiu algoritmo redonas
ĉiu permuto kun egale verŝajna probablo.
>> Bone, apud problemo.
Do "donita tabelo de entjeroj, postive, nula, negativa,
skribi funkcion kiu kalkulas la maksimuma sumo
de iu continueous subarray de la enigo tabelo. "
Ekzemplo jen, en la kazo kie ĉiuj nombroj estas pozitiva,
tiam nuntempe la plej bona elekto estas preni la tuta tabelo.
1, 2, 3, 4, egalas 10.
Kiam vi havas iujn negativaj en tie,
en ĉi tiu kazo ni volas nur la du unuaj
ĉar elekti -1 kaj / aŭ -3 venigos nia sumo sube.
Foje ni eble devus komenci en la mezo de la tabelo.
Kelkfoje ni volas elekti nenion, temas pli bone ne fari ion.
Kaj kelkfoje estas pli bone doni la falo,
ĉar la afero post ĝi estas super granda. Do neniu ideoj?
(Studento, nekomprenebla) >> Jes.
Supozu mi ne prenas -1.
Tiam ĉu mi elektu 1.000 kaj 20.000,
aŭ mi simple elektas la 3 miliardoj.
Nu, la plej bona elekto estas preni ĉiujn numerojn.
Ĉi -1, malgraŭ esti negativa,
la tuta sumo estas pli bona ol se mi ne preni -1.
Do unu el la pintoj mi menciis pli frue estis konstati la klare evidentaj
kaj la malpura forto solvon unue.
Kio estas la bruta forto solvon en ĉi tiu problemo? Yeah?
[Jane] Nu, mi kredas ke la malpura forto solvo
estus adicii ĉiujn eblajn kombinojn (nekomprenebla).
[Yu] Okay. Do Jane ideon estas preni ĉiun eblan -
Mi simpligas - estas preni ĉiun eblan kontinua subarray,
komputi lia sumo, kaj poste prenu la maksimumo de ĉiuj eblaj kontinua subarrays.
Kio unike identigas subarray en mia enigo tabelo?
Kiel, kio du aferojn mi bezonas? Yeah?
(Studento, nekomprenebla) >> Ĝuste.
Al suba baro sur la indekso kaj supera baro indekso
unike determinas kontinua subarray.
[Ina studento] Ĉu ni taksanta estas tabelo de solaj nombroj?
[Yu] No Do ŝi demando estas, ĉu ni supozante nia tabelo -
estas nia tabelo ĉiuj solaj nombroj, kaj la respondo estas ne.
>> Se ni uzi nian bruta forto solvon, tiam la komenco / fino indeksoj
unike determinas nian kontinua subarray.
Do, se ni persisti por ĉiuj eblaj komenco enskriboj,
por ĉiuj fino enskriboj> aŭ = komenci, kaj <n,
vi komputi la sumon, kaj tiam ni preni la maksimuman sumon ni vidis ĝis nun.
Ĉu ĉi tiu estas klara?
Kio estas la granda O de tiu solvo?
Timewise.
Ne tute n ^ 2.
Notu ke ni persisti de 0 al n,
do jen unu por buklo.
Ni persisti denove de preskaŭ la komenco ĝis la fino, alia por buklo.
Kaj nun, ene de tiu, ni devas sumigi ĉiu eniro,
do jen alia por buklo. Do ni havas tri anidado por bukloj, n ^ 3.
Okay. Ĉi tio iras kiel deirpunkto.
Nia solvo estas ne pli malbona, ol n ^ 3.
Ĉu ĉiuj komprenas la bruta forto solvo?
>> Okay. Pli bona solvo estas uzi ideo nomita dinamika programado.
Se vi prenos CS124, kiu estas Algoritmoj kaj Datumoj Strukturoj,
vi fariĝos tre konas ĉi tiun teknikon.
Kaj la ideo estas, provu konstrui solvojn al malgrandaj problemoj unue.
Kion mi celas per tio estas, ni aktuale devas maltrankviligi du aferoj: komenco kaj fino.
Kaj tio estas ĝena. Kio se ni povus forigi unu el tiuj parametroj?
Unu ideo estas - we're donita nia originala problemo,
trovi la maksimuma sumo de ajna subarray en rango [ho, n-1].
Kaj nun ni havas novan subproblem, kie ni scias, en nia nuna indekso i,
ni scias ke ni devas fini tie. Nia subarray devas finiĝi je la nuna indekso.
Do la ceteraj problemo estas, kie ni komencos nian subarray?
Ĉu ĉi sencon? Okay.
Do mi kodita ĉi, kaj ni rigardu kion tio signifas.
En la codirectory, ekzistas programo nomata subarray,
kaj ĝi portas numeron de artikoloj,
kaj denove la maksimuma subarray sumo en mia barajan listo.
Do ĉi-kaze, nia maksimuma subarray estas 3.
Kaj tio prenita de nur uzante 2 kaj 1.
Ni kuras ĝin denove. Estas ankaŭ 3.
Sed ĉi tiun fojon, rimarku kiom ni akiris la 3.
Ni prenis la - ni simple prenu la 3 sin
ĉar ĝi estas ĉirkaŭita de negativaj sur ambaŭ flankoj,
kiu alportos sumo <3.
Ni kuras je 10 eroj.
Ĉi-foje ĝi estas 7, ni prenu la ĉefan 3 kaj 4.
Ĉi-foje ĝi estas 8, kaj ni atingos ke per prenante 1, 4 kaj 3.
Por tiel doni al vi intuicio pri kiel ni povas solvi ĉi transformita problemo,
ni rigardu tiun subarray.
Ni donis ĉi enigo tabelo, kaj ni konas la respondo estas 8.
Ni prenu la 1, 4, kaj 3.
Sed ni rigardu kiom ni efektive havas tiun respondon.
Ni rigardu la maksimuma subarray kiu enfluis en ĉiu el tiuj indeksoj.
Kio estas la maksimuma subarray kiu havas por enflui en la unua pozicio?
[Studenta] Nulo. >> Nulo. Nur ne prenas la -5.
Tie okazas al esti 0 tiel. Yeah?
(Studento, nekomprenebla)
[Yu] Ho, pardonu, estas -3.
Do tiu estas 2, ĉi tiu estas -3.
Okay. Do -4, kio estas la maksimuma subarray fini tiun pozicion
kie -4 estas? Nulo.
Unu? 1, 5, 8.
Nun, mi devas fini je la loko kie -2 estas.
Do 6, 5, 7, kaj la lasta estas 4.
Sciante, ke tiuj estas miaj enskriboj
por la transformita problemo kie mi devas fini je ĉiu el tiuj indeksoj,
tiam mia fina respondo estas justa, preni sweep trans,
kaj prenu la maksimuma nombro.
Do en tiu kazo ĝi estas 8.
Ĉi tio implicas ke la maksimuma subarray finiĝas ĉe ĉi tiu indico,
kaj komencis ie antaŭ ĝi.
Ĉu ĉiuj komprenas ĉi transformita subarray?
>> Okay. Nu, ni kalkuli la rekursieca por ĉi tio.
Ni konsideru nur la unuaj kelkaj enskriboj.
Do jen tio estis 0, 0, 0, 1, 5, 8.
Kaj tiam estis -2 tie, kaj kiu alportis ĝin al 6.
Do se mi nomas la eniron en la pozicio i subproblem (i),
kiel mi povas uzi la respondo al antaŭa subproblem
respondi tiun subproblem?
Se mi rigardas, diru, ĉi eniro.
Kiel mi povas kalkuli la respondon 6 por rigardi
kombino de tablo kaj la respondoj al la antaŭaj subproblemo en ĉi tabelo? Jes?
[Ina studento] Vi prenu la tabelo de sumoj
en la pozicio ĝuste antaŭ ĝi, do la 8an,
kaj tiam vi aldonas la nunan subproblem.
[Yu] Do ŝi sugesto estas por rigardi tiujn du nombroj,
ĉi tiu numero kaj ĉi tiu numero.
Do tiu 8 raportas al la respondo de la subproblem (i - 1).
Kaj ni nomas mia enigo tabelo A.
Por trovi maksimuma subarray kiu enfluas en pozicio i,
Mi havas du eblojn: Mi povas aŭ daŭrigi la subarray
kiu enfluis en la antaŭa indekso, aŭ komenci novan tabelo.
Se mi estus por daŭrigi la subarray kiu komencis ĉe la antaŭa indico,
tiam la maksimuma sumo mi povas atingi estas la respondo al la antaŭa subproblem
plus la nuna tabelo eniro.
Sed, mi ankaux havas la elekton de komenci novan subarray,
en kiu kazo la sumo estas 0.
Do la respondo estas max de 0, subproblem i - 1, plus la nuna tabelo eniro.
Ĉu ĉi rekursieca sencon?
Nia rekursieca, kiel ni ĵus malkovris, estas subproblem i
estas egala al la maksimumo de la antaŭa subproblem plus miajn nuna tabelo eniro,
kio signifas daŭrigi la antaŭan subarray,
aŭ 0, komenci novan subarray en mia nuna indekso.
Kaj unufoje ni konstruis ĉi tabelo de solvoj, tiam nia fina respondo,
nur faru lineara balaita tra la subproblem tabelo
kaj prenu la maksimuma nombro.
Ĉi tiu estas ĝusta apliko de tio, kion mi ĵus diris.
Do ni kreu novan subproblem tabelo, subproblemo.
La unua ero estas ĉu 0 aŭ la unua eniro, la maksimumo de tiuj du.
Kaj dum la resto de la subproblemo
ni uzas la ĝustan rekursieca ni ĵus malkovrita.
Nun ni kalkulas la maksimumo de nia subproblemo tabelo, kaj tio estas nia fina respondo.
>> Do kiom spaco ni uzas en ĉi tiu algoritmo?
Se vi nur prenis CS50, tiam vi eble ne diskutis spaco tre multe.
Nu, unu afero noti estas, ke mi nomis malloc tie kun amplekso n.
Kion tio sugestas al vi?
Ĉi tiu algoritmo uzas lineara spaco.
Ĉu ni povas fari pli bone?
Ĉu estas io, kiun vi rimarkos ke estas nenecese komputi la fina respondo?
Mi supozas pli bonan demando estas, kio informo
ni ne bezonis portadi la tuta vojo tra la fino?
Nun, se ni rigardas tiujn du linioj,
ni nur zorgas pri la antaŭa subproblem,
kaj ni nur zorgas pri la maksimuma ni iam vidis ĝis nun.
Komputi nia fina respondo, ni ne bezonas la tutan aron.
Ni nur bezonas la lasta numero, du lastaj ciferoj.
Lasta numero por la subproblem tabelo, kaj lasta numero por la maksimumo.
Do, fakte, ni povas kunfandi tiujn maŝojn kune
kaj iru de lineara spaco al konstanta spaco.
Nuna sumo ĝis nun, ĉi tie, anstataŭas la rolo de subproblem, nia subproblem tabelo.
Do nuna sumo, ĝis nun, estas la respondo al la antaŭa subproblem.
Kaj tiu sumo, ĝis nun, prenas la lokon de nia max.
Ni kalkulas la maksimuma kiel ni iru kune.
Kaj tiel ni iros de lineara spaco al konstanta spaco,
kaj ni ankaux havas lineara solvon al niaj subarray problemo.
>> Tiuj specoj de demandoj vi ricevos dum intervjuo.
Kio estas la tempa komplekseco; kio estas la spaca komplekseco?
Ĉu vi povas fari pli bone? Ĉu ekzistas aĵoj kiuj estas nenecesa teni ĉirkaŭe?
Mi faris ĉi reliefigi analizoj kiujn vi devus preni sur via propra
kiel vi laboras tra tiuj problemoj.
Ĉiam petante vin, "Ĉu mi povas fari pli bone?"
Fakte, ĉu ni povas fari pli bone ol tio?
Ordigi de lertaĵo demando. Vi ne povas, ĉar vi bezonas
almenaŭ legis la eniro al la problemo.
Do la fakto, ke vi bezonas almenaŭ legis la eniro al la problemo
signifas ke vi ne povas fari pli bone ol lineara tempo,
kaj vi ne povas fari pli bone ol konstanta spaco.
Do tiu estas, fakte, la plej bona solvo por tiu problemo.
Demandoj? Okay.
>> Borso problemo:
"Donita aro de n entjeroj, pozitivaj, nulo, aŭ negativa,
kiuj reprezentas la prezo de la sako sur n tagoj,
skribi funkcion por kalkuli la maksimuman profiton vi povos fari
pro tio ke vi aĉeti kaj vendi ekzakte 1 stock ene tiuj n tagoj. "
Esence, ni volas aĉeti malalta, vendi altaj.
Kaj ni volas eltrovi la plej bona profito oni povas fari.
Reiros al mia bekon, kio estas la tuj klara, plej simpla respondo, sed ĝi estas malrapida?
Jes? (Studento, nekomprenebla) >> Jes.
>> Do vi simple iru kvankam kaj rigardi la stock prezoj
je ĉiu punkto en tempo, (nekomprenebla).
[Yu] Okay, do ŝi solvo - ŝia sugesto de komputado
la plej malalta kaj komputanta la plej alta ne nepre laboras
ĉar la plej alta povus okazi antaŭ la plej malalta.
Do kio estas la bruta forto solvo por tiu problemo?
Kio estas la du aĵoj kiuj mi bezonas por unike difini la utilo mi faru? Ĝuste.
La bruta forto solvo estas - ho, jes, Georgo sugesto estas ni nur bezonas du tagojn
por unike difini la profito de tiuj du tagoj.
Do ni komputi ĉiu paro, kiel aĉeti / vendi,
komputi la profito, kiu povus esti negativa aŭ pozitiva aŭ nula.
Komputi la maksimuma profito, ke ni faros post ripetanta super ĉiuj paroj de tagoj.
Tio estos nia fina respondo.
Kaj tiu solvo estos O (n ^ 2), ĉar tie estas n elekti du paroj -
de tempo, kiun vi povas elekti inter fino tagoj.
Okay, do mi ne tuj transiros malpura forto solvon ĉi tie.
Mi tuj diros al vi ke estas n logo n solvo.
Kio algoritmo vi aktuale scias ke estas n logo n?
Ne estas atuto demando.
>> Kunfandi varon. Kunfandi varo estas n logo n,
kaj fakte, unu maniero solvi tiun problemon estas uzi
a merge speco ia ideo nomas, en ĝenerala, dividi kaj venki.
Kaj la ideo estas kiel sekvas.
Vi volas komputi la plej bona buy / vendi paro en la maldekstra duono.
Trovu la bona profito oni povas fari, nur kun la unua n super du tagoj.
Tiam vi volas oompute la plej bona buy / vendi paron ĉe la dekstra duono,
do la lasta n super du tagoj.
Kaj nun la demando estas, kiel ni kunfandi tiujn solvojn reen kune?
Jes? (Studento, nekomprenebla)
>> Bone. Do mi desegnis bildon.
Jes? (George, nekomprenebla)
>> Ekzakte. Georgo solvo estas ĝuste dekstre.
Do lia sugesto estas, unue komputi la plej bona buy / vendas paro,
kaj tio okazas en la maldekstra duono, do ni nomas tio maldekstra, maldekstra.
Best aĉeti / vendi paro kiu okazas en la dekstra duono.
Sed se ni nur kompare tiuj du nombroj, ni mankis la kazo
kie ni aĉeti tie kaj vendi ie en la dekstra duono.
Ni aĉetas en la maldekstra duono, vendi en la dekstra duono.
Kaj la plej bona maniero por kalkuli la plej bona buy / vendas paro kiu ĉirkaŭprenas ambaŭ duonoj
estas al komputi la minimuma tie kaj kalkuli la maksimuman tie
kaj prenu lian diferencon.
Do la du kazoj kie la buy / vendas paro okazas nur ĉi tie,
nur ĉi tie, aŭ en ambaŭ duonoj estas difinita per ĉi tiuj tri nombroj.
Do nia algoritmo por kunfandi nian solvaĵoj reen kune,
ni volas kalkuli la plej bona buy / vendas paro
kie ni aĉetas en la maldekstra duono kaj vendi en la dekstra duono.
Kaj la plej bona maniero fari tion estas por kalkuli la plej malalta prezo en la unua duono,
la plej alta prezo en la dekstra duono, kaj prenu lian diferencon.
La rezultanta tri profitojn, tiuj tri numeroj, vi prenos la maksimumo de la tri,
kaj tio estas la plej bona profito vi povas fari sur tiuj unuaj kaj fino tagoj.
Jen la grava linioj estas en ruĝa.
Ĉi tiu estas rekursia alvoko al komputi la respondon en la maldekstra duono.
Ĉi tiu estas rekursia alvoko al komputi la respondon en la dekstra duono.
Tiuj du por maŝojn komputi la min kaj la max sur la maldekstra kaj dekstra duono, respektive.
Nun mi kalkulas la profiton, ke trairas ambaŭ duonoj,
kaj la fina respondo estas la maksimumo de tiuj tri.
Okay.
>> Do, certe, ni havas algoritmon, sed la granda demando estas,
kio estas la tempa komplekseco de tiu?
Kaj la kialo, kial mi menciis merge varo estas ke tiu formo de dividi la respondo
en du kaj poste kunfandi nian solvaĵoj dorso kune
Estas precize la formo de merge varon.
Do lasu min iri tra la daŭro.
Se ni difini funkcion t (n) por esti la nombro de paŝoj
por n tagoj,
niaj du rekursiaj alvokoj
estas ĉiu tuj kostos t (n / 2),
kaj tie estas du el tiuj alvokoj.
Nun mi bezonas por kalkuli la minimumo de la maldekstra duono,
kion mi povas fari en n / 2 horo, plus la maksimumo de la dekstra duono.
Do ĉi tiu estas nur n.
Kaj tiam pli iuj konstanta laboro.
Kaj tion rekursieca ekvacio
Estas ĝuste la rekursieca ekvacio por merge varon.
Kaj ni ĉiuj scias ke merge varo estas n logo n tempon.
Tial, nia algoritmo ankaŭ n logo n tempon.
Ĉu ĉi tiu ripeto sencon?
Nur mallongan recap de ĉi:
T (n) estas la nombro de paŝoj al komputi la maksimuma profito
Super la apartajxo de n tagoj.
La vojo ni disigis nian rekursie alvokoj
estas nomante nian solvon en la unua n / 2 tagoj,
do jen unu alvokon,
kaj tiam ni nomas denove en la dua duono.
Do jen du alvokoj.
Kaj tiam ni trovos minimumo en la maldekstra duono, kiun ni povas fari en lineara tempo,
trovi la maksimumo de la dekstra duono, kiun ni povas fari en lineara tempo.
Do n / 2 + n / 2 estas simple n.
Tiam ni havi iu konstanta laboro, kiu estas kiel fari aritmetiko.
Ĉi rekursieca ekvacio estas precize la rekursieca ekvacio por merge varon.
Tial, nia barajar algoritmo estas ankaŭ n log n.
Do kiom spaco ni uzas?
Ni reiru al la kodo.
>> Pli bona demando estas, kiom da pilo kadroj ni iam havos je ĉiu momento?
Ekde ni uzas rekursio,
la nombro de pilo kadroj determinas nian spacon uzado.
Ni konsideru n = 8.
Ni nomas barajar la 8,
kio vokos barajar en la unuaj kvar elementoj,
kio vokos al barajar en la unuaj du elementoj.
Do nia stako estas - tio estas nia stako.
Kaj tiam ni nomas barajar denove la 1,
kaj tio nia bazo kazo estas, ke ni revenu tuj.
Ĉu ni iam havos pli ol tio multaj stako kadroj?
Ne, ĉar ĉiufoje kiam ni alvoko,
rekursia alvoko al barajar,
ni dividas nian grandecon en duono.
Do la maksimuma nombro de pilo kadroj ni iam havos je ĉiu momento
estas de ordo de logo n pilo kadroj.
Ĉiu pilo kadro havas konstantan spaco,
kaj sekve la tuta kvanto de spaco,
la maksimuma kvanto da spaco ni iam uzas estas O (log n) spaco
kie n estas la nombro de tagoj.
>> Nun, ĉiam petas vin, "Ĉu ni povas fari pli bone?"
Kaj en aparta, ni povas redukti tiun al problemo ni jam solvita?
Al aludo: ni nur diskutas du aliaj problemoj antaŭ ĉi tio, kaj ĝi ne tuj estos barajar.
Ni povas konverti tiun sakon problemo en la maksimuma subarray problemo.
Kiel ni povas fari ĉi tion?
Unu el vi? Emmy?
(Emmy, nekomprenebla)
[Yu] Ekzakte.
Do la maksimuma subarray problemo,
ni serĉas sumo super kontinua subarray.
Kaj Emmy la sugesto por la akcioj problemo,
konsideri la ŝanĝojn, aŭ la deltas.
Kaj bildon de tio estas - tio estas prezo de la sako,
sed se ni prenas la diferenco inter ĉiu sinsekva tago -
do ni vidas, ke la maksimuma prezo, maksimuma profito ni povus fari
estas, se ni aĉetus ĉi tie kaj vendi tie.
Sed ni rigardu la kontinua - ni rigardu la subarray problemo.
Do jen, ni povas fari - irante de tie al tie,
ni havas pozitivan ŝanĝon, kaj tiam irante de tie al tie ni havas negativan ŝanĝon.
Sed tiam, irante de tie al tie ni havas grandegan pozitivan ŝanĝon.
Kaj jen estas la ŝanĝoj kiuj ni volas resumi por atingi nian finan profiton.
Tiam ni havas pli negativajn ŝanĝoj ĉi tie.
La ŝlosilo por redukti nian stock problemo en nia maksimuma subarray problemo
estas al konsideri la deltas inter la tagoj.
Do ni kreu novan tabelo nomis deltas,
pravalorizi la unua eniro al esti 0,
kaj tiam por ĉiu delta (i), lasu ke estu la diferenco
de miaj enigo array (i), kaj batalarangxis (i - 1).
Tiam ni nomas nian rutinon proceduro por maksimuma subarray
pasante en delto de tabelo.
Kaj ĉar maksimuma subarray estas lineara tempo,
kaj ĉi redukto, tiu ĉi procezo de kreado ĉi delto tabelo,
Ankaŭ estas lineara tempo,
tiam la fina solvo por akcioj estas O (n) laboro pli O (n) laboro, estas ankoraŭ O (n) laboro.
Do ni havas lineara tempo solvon al nia problemo.
Ĉu ĉiuj komprenas ĉi transformo?
>> En ĝenerala, bona ideo ke vi ĉiam devas
estas provi redukti novan problemon, kiun vi vidas.
Se ĝi aspektas familiaraj al malnova problemo,
provi redukti ĝin al malnova problemo.
Kaj se vi povas uzi ĉiujn ilojn kiuj vi uzas la malnovan problemon
solvi la nova problemo.
Do por kovri supren, teknika intervjuoj estas defiante.
Ĉi tiuj problemoj estas probable iuj de la plej malfacilaj problemoj
ke vi povus vidi en intervjuo,
do se vi ne komprenas ĉiujn problemojn ke mi nur kovrita, tio estas bone.
Ĉi tiuj estas kelkaj el la pli defia problemo.
Praktiko, praktiko, praktiko.
Mi donis multe da problemoj en la flugfolia, do definitive kontroli tiujn eksteren.
Kaj bonŝancon en via intervjuo. Ĉiuj miaj rimedoj estas eldonitaj en ĉi-ligilo,
kaj unu el miaj amikoj altranga proponis fari maketo teknika intervjuoj,
do se vi estas interesata, retpoŝto Will Yao en tiu retadreso.
Se vi havas iujn demandojn, vi povas peti mi.
Ĉu vi infanoj havas specifajn demandojn rilataj al teknikaj intervjuoj
aŭ ajna problemoj ni vidis ĝis nun?
Okay. Nu, bonan sorton en via intervjuo.
[CS50.TV]