[Powered by Google Translate] [Seminar: Cyfweliadau Technegol]
[Kenny Yu, Prifysgol Harvard]
[Mae hyn yn CS50.] [CS50.TV]
Hi pawb, rwy'n Kenny. Hyn o bryd rwy'n gwyddoniaeth gyfrifiadurol iau yn astudio.
Rwy'n gyn-CS TF, a dymunaf gen i hyn pan oeddwn yn underclassman,
a dyna pam yr wyf i'n rhoi seminar hwn.
Felly, yr wyf yn gobeithio y byddwch yn ei fwynhau.
Mae'r seminar yn ymwneud â chyfweliadau technegol,
a gall fy holl adnoddau ar gael yn y cyswllt hwn,
y ddolen hon i'r dde yma, ychydig o adnoddau.
Felly yr wyf yn gwneud rhestr o broblemau, mewn gwirionedd, yn eithaf ychydig o broblemau.
Hefyd, adnoddau tudalen cyffredinol lle y gallwn ddod o hyd i awgrymiadau
ar sut i baratoi ar gyfer cyfweliad,
awgrymiadau ar yr hyn y dylech ei wneud yn ystod cyfweliad go iawn,
yn ogystal â sut i ddelio â phroblemau ac adnoddau ar gyfer y dyfodol.
Mae hyn i gyd ar-lein.
A dim ond i ragflaenu hyn seminar, ymwadiad,
Nid fel hyn ddylai - eich paratoi ar gyfer cyfweliad
ni ddylid eu cyfyngu at y rhestr hon.
Mae hyn yn golygu dim ond i fod yn ganllaw,
a dylech yn sicr yn cymryd popeth yr wyf yn dweud gyda gronyn o halen,
ond hefyd yn defnyddio popeth wyf yn ei ddefnyddio i'ch helpu chi yn eich paratoi ar gyfer cyfweliad.
>> Rydw i'n mynd i gyflymu'r drwy'r sleidiau nesaf
er mwyn i ni gyrraedd yr astudiaethau achos go iawn.
Mae strwythur y cyfweliad ar gyfer peirianneg meddalwedd postion,
fel arfer ei fod yn 30 i 45 munud,
rowndiau lluosog, yn dibynnu ar y cwmni.
Yn aml byddwch yn codio ar fwrdd gwyn.
Felly, bwrdd gwyn fel hyn, ond yn aml ar raddfa lai.
Os ydych yn cael cyfweliad ffôn, mae'n debyg y byddwch yn eu defnyddio
naill ai collabedit neu Doc Google fel y gallant weld rydych chi'n byw codio
tra byddwch chi'n cael eich cyfweld dros y ffôn.
Mae cyfweliad ei hun fel arfer 2 neu 3 broblemau
brofi eich cyfrifiadur gwybodaeth wyddonol.
A bydd yn bron yn bendant yn cynnwys codio.
Mae'r mathau o gwestiynau y byddwch yn gweld fel arfer yn strwythurau data ac algorithmau.
Ac wrth wneud y mathau hyn o broblemau,
byddant yn gofyn i chi, fel, beth yw'r amser ac, cymhlethdod gofod mawr O?
Yn aml, maent hefyd yn gofyn i lefel uwch gwestiynau,
felly, dylunio system,
sut fyddech chi'n gosod eich cod?
Pa rhyngwynebau, pa ddosbarthiadau, pa fodiwlau sydd gennych yn eich system,
a sut mae'r rhain yn rhyngweithio â'i gilydd?
Felly, strwythurau data ac algorithmau yn ogystal â systemau dylunio.
>> Rhai awgrymiadau cyffredinol cyn i ni plymio i mewn i ein hastudiaethau achos.
Rwy'n meddwl bod y rheol pwysicaf yw bob amser yn meddwl yn uchel.
Mae'r cyfweliad yn dybiedig i fod yn eich cyfle i ddangos eich proses meddwl.
Y pwynt y cyfweliad yw i'r cyfwelydd i fesur
sut rydych yn meddwl a sut rydych yn mynd drwy problem.
Y peth gwaethaf y gallwch chi ei wneud yw fod yn dawel drwy gydol y cyfweliad cyfan.
Dyna dim ond dda i ddim.
Pan fyddwch yn cael cwestiwn, byddwch hefyd yn dymuno gwneud yn siŵr eich bod yn deall y cwestiwn.
Felly, ailadrodd y cwestiwn yn ôl yn eich geiriau eich hun
a cheisio gweithio trylwyr o achosion prawf syml ychydig
i wneud yn siŵr eich bod yn deall y cwestiwn.
Bydd gweithio drwy achosion prawf rhai hefyd yn rhoi i chi greddf ar sut i ddatrys y broblem hon.
Efallai y byddwch hyd yn oed ddarganfod patrymau ychydig i'ch helpu chi i ddatrys y broblem.
Mae eu tip mawr yw peidio â mynd yn rhwystredig.
Peidiwch â mynd yn rhwystredig.
Cyfweliadau yn heriol, ond y peth gwaethaf y gallwch ei wneud,
yn ogystal â bod yn dawel, yn cael ei rhwystredig yn amlwg.
Nid ydych am i roi'r argraff i'r cyfwelydd.
Un peth sydd chi - felly, mae llawer o bobl, pan fyddant yn mynd i mewn i gyfweliad,
maent yn ymdrechu i geisio dod o hyd i'r ateb gorau yn gyntaf,
pan mewn gwirionedd, mae fel arfer yn ateb glaringly amlwg.
Gallai fod yn araf, gallai fod yn aneffeithlon, ond dylech dim ond nodi ei,
yn unig fel bod gennych man cychwyn i weithio'n well.
Hefyd, dynnu sylw at yr ateb yn araf, o ran
cymhlethdod amser mawr O neu gymhlethdod gofod,
Bydd ddangos i'r cyfwelydd eich bod yn deall
y materion hyn wrth ysgrifennu cod.
Felly peidiwch â bod ofn i ddod o hyd i'r algorithm symlaf 1
ac yna yn gweithio'n well oddi yno.
Unrhyw gwestiynau hyd yn hyn? Iawn.
>> Felly gadewch i ni neidio i mewn i'n problem cyntaf.
"O ystyried amrywiaeth o gyfanrifau n, ysgrifennwch swyddogaeth sy'n cymysgu'r yr amrywiaeth
yn eu lle fel bod yr holl gyfnewidiadau o'r cyfanrif n yr un mor debygol. "
Ac yn tybio sydd ar gael gennych generadur cyfanrif ar hap
sy'n cynhyrchu cyfanrif mewn amryw o 0 i i, ystod hanner.
Ydy pawb yn deall y cwestiwn hwn?
Yr wyf yn rhoi i chi amrywiaeth o gyfanrifau n, ac yr wyf am i chi siffrwd iddo.
Yn fy cyfeiriadur, ysgrifennais ychydig o raglenni i ddangos yr hyn rwy'n ei olygu.
Rydw i'n mynd i siffrwd amrywiaeth o 20 elfen,
o -10 i +9,
ac yr wyf am i chi allbynnu rhestr fel hyn.
Felly mae hyn yn fy amrywiaeth mewnbwn didoli, ac yr wyf am i chi siffrwd iddo.
Byddwn yn gwneud hynny eto.
Ydy pawb yn deall y cwestiwn? Iawn.
Felly, mae i fyny i chi.
Beth yw rhai syniadau? Allwch chi ei wneud fel n ^ 2, n log n, n?
Yn agored i awgrymiadau.
Iawn. Felly, un syniad, a awgrymwyd gan Emmy,
yn gyntaf gyfrifo rhif ar hap, cyfanrif ar hap, mewn amrywio o 0 i 20.
Felly, cymryd yn ganiataol ein casgliad mae cyfweliadau i 20.
Yn ein diagram o 20 elfen,
mae hyn yn ein amrywiaeth mewnbwn.
Ac yn awr, ei awgrym yw creu amrywiaeth newydd,
felly bydd hyn yn yr amrywiaeth allbwn.
Ac yn seiliedig ar y ff dychwelyd erbyn rand -
felly os fi oedd, gadewch i ni ddweud, 17,
copïo'r elfen 17 i mewn i'r swydd gyntaf.
Nawr mae angen i ddileu - mae angen i ni symud yr holl elfennau yma
drosodd fel bod gennym fwlch ar y diwedd a dim tyllau yn y canol.
Ac yn awr rydym yn ailadrodd y broses.
Nawr rydym yn dewis cyfanrif newydd ar hap rhwng 0 a 19 oed.
Mae gennym i newydd yma, ac rydym yn copïo yr elfen hon yn y sefyllfa hon.
Yna, rydym yn symud eitemau drosodd ac rydym yn ailadrodd y broses nes inni gael ein amrywiaeth llawn newydd.
Beth yw'r amser yn rhedeg y algorithm?
Wel, gadewch i ni ystyried effaith hyn.
Rydym yn symud pob elfen.
Pan fyddwn yn cael gwared hyn i, yr ydym yn symud yr holl elfennau ar ôl iddo ar y chwith.
A dyna yw (n) O cost
oherwydd yr hyn os ydym yn cael gwared ar y elfen gyntaf?
Felly, ar gyfer pob dileu, byddwn yn cael gwared -
pob symud tynnu yn (n) O gweithrediad,
ac ers i ni wedi symud n, mae hyn yn arwain at (n ^ 2) O siffrwd.
Iawn. Felly dechrau da. Dechrau da.
>> Awgrym arall yw defnyddio rhywbeth a elwir yn siffrwd Knuth,
neu 'r siffrwd Fisher-Yates.
Ac mewn gwirionedd mae'n shuffle amser llinol.
Ac mae'r syniad yn debyg iawn.
Unwaith eto, rydym wedi ein amrywiaeth mewnbwn,
ond yn hytrach na defnyddio ddau arae ar gyfer ein mewnbwn / allbwn,
rydym yn defnyddio y rhan gyntaf o'r amrywiaeth i gadw golwg ar ein rhan cymysgu,
ac rydym yn cadw trac, ac yna rydym yn gadael y gweddill ein amrywiaeth ar gyfer y rhan unshuffled.
Felly dyma beth rwy'n ei olygu. Rydym yn dechrau i ffwrdd gyda - rydym yn dewis i,
arae 0-20.
Mae ein pwyntydd ar hyn o bryd yn pwyntio at y mynegai cyntaf.
Rydym yn dewis rhai yma i
ac yn awr rydym yn cyfnewid.
Felly os yw hyn oedd 5 ac roedd hyn yn 4,
Bydd yr amrywiaeth o ganlyniad gael 5 yma a 4 yma.
Ac yn awr rydym yn nodi marciwr yma.
Mae popeth ar y chwith yn cael ei gymysgu,
a phopeth ar y dde yn cael ei unshuffled.
Ac yn awr y gallwn ailadrodd y broses.
Rydym yn dewis mynegai ar hap rhwng 1 a 20 awr.
Felly mae'n debyg ein newydd i yma.
Nawr rydym yn gyfnewid hon i gyda ein sefyllfa bresennol newydd yma.
Felly rydym yn yn cyfnewid yn ôl ac ymlaen fel hyn.
Gadewch i mi ddod i fyny y cod i'w wneud yn fwy cadarn.
Rydym yn dechrau gyda ein dewis o i -
rydym yn dechrau gyda i gyfartal i 0, rydym yn dewis j lleoliad ar hap
yn y rhan unshuffled y rhesi, i i n-1.
Felly os dwi yma, dewiswch mynegai ar hap rhwng y fan hon a gweddill y rhesi,
ac rydym yn gyfnewid.
Mae hyn i gyd y cod angenrheidiol i siffrwd eich casgliad.
Unrhyw gwestiynau?
>> Wel, un angen cwestiwn yw, pam fod hyn yn gywir?
Pam mae pob permutation yr un mor debygol?
Ac ni fyddaf yn mynd drwy'r dystiolaeth o hyn,
ond gall llawer o broblemau mewn gwyddoniaeth gyfrifiadurol yn cael ei brofi trwy sefydlu.
Faint ydych yn gyfarwydd â sefydlu?
Iawn. Cool.
Felly, gallwch chi brofi cywirdeb yr algorithm syml gan ddefnyddio anwythiad,
lle y byddai eich ddamcaniaeth sefydlu yn, cymryd yn ganiataol bod
fy siffrwd yn dychwelyd bob permutation yr un mor debygol
hyd at yr elfennau i gyntaf.
Yn awr, ystyriwch i + 1.
A thrwy y ffordd yr ydym yn dewis ein j mynegai i gyfnewid,
hyn yn arwain at - ac yna rydych yn gweithio allan y manylion,
o leiaf prawf llawn pam y algorithm yn dychwelyd
bob permutation gyda thebygolrwydd yr un mor debygol.
>> Mae pob hawl, problem nesaf.
Felly "rhoi amrywiaeth o gyfanrifau, chadaranhaol, sero, negyddol,
ysgrifennu swyddogaeth sy'n cyfrifo y swm uchaf
o unrhyw subarray continueous y rhesi mewnbwn. "
Un enghraifft yma, yn yr achos lle mae'r holl rifau yn gadarnhaol,
Yna, ar hyn o bryd y dewis gorau yw cymryd y casgliad cyfan.
1, 2, 3, 4, yn hafal i 10.
Pan fydd gennych rhai pethau negyddol i mewn 'na,
yn yr achos hwn rydym yn unig am y ddau gyntaf
oherwydd bydd dewis -1 a / neu -3 ddod â'n swm i lawr.
Weithiau gallai fod yn rhaid i ddechrau yng nghanol y rhesi.
Weithiau, rydym am i ddewis dim byd o gwbl; mae'n well i beidio â chymryd unrhyw beth.
Ac weithiau mae'n well i gymryd y cwymp,
oherwydd y peth ar ôl ei super mawr. Felly unrhyw syniadau?
(Myfyrwyr, annealladwy) >> Yeah.
Gadewch i ni dybio Nid wyf yn cymryd -1.
Yna naill ai Rwy'n dewis 1,000 a 20,000,
neu Fi jyst dewis y 3 biliwn.
Wel, y dewis gorau yw i gymryd yr holl rifau.
Mae hyn yn -1, er gwaethaf y ffaith bod yn negyddol,
y swm cyfan yn well nag oedd I beidio â chymryd -1.
Felly un o'r awgrymiadau y soniais yn gynharach oedd i ddatgan yr hyn sy'n amlwg yn glir
a'r ateb 'n ysgrublaidd dreisio yn gyntaf.
Beth yw'r ateb 'n ysgrublaidd dreisio yn y broblem? Yeah?
[Jane] Wel, yr wyf yn meddwl yr ateb 'n ysgrublaidd dreisio
fyddai ychwanegu yr holl gyfuniadau posibl (annealladwy).
[Yu] Iawn. Felly, Jane syniad yw i fanteisio ar bob bosibl -
Rwy'n aralleirio - yw manteisio ar bob subarray parhaus posibl,
gyfrifo ei swm, ac yna cymryd yr uchafswm yr holl subarrays posibl parhaus.
Beth unigryw yn nodi subarray yn fy amrywiaeth mewnbwn?
Fel, pa ddau beth sydd ei angen arnaf? Yeah?
(Myfyrwyr, annealladwy) Hawl >>.
Mae is rhwymo ar y mynegai a mynegai rhwymo uchaf
unigryw yn gyfrifol am y subarray parhaus.
[Myfyrwraig] A ydym yn amcangyfrif ei fod yn amrywiaeth o rifau unigryw?
[Yu] Rhif Felly, ei gwestiwn yn cael ei, rydym yn cymryd ein amrywiaeth -
yw ein amrywiaeth holl rifau unigryw, a'r ateb yw na.
>> Os ydym yn defnyddio ein ateb 'n ysgrublaidd dreisio, yna bydd y mynegeion dechrau / diwedd
unigryw yn pennu ein subarray barhaus.
Felly, os ydym yn ailadrodd ar gyfer pob cais cychwyn posibl,
ac ar gyfer pob cofnod diwedd> neu = i ddechrau, a <n,
chi gyfrifo swm, ac yna rydym yn cymryd y swm uchaf y byddwn wedi gweld hyd yn hyn.
A yw hyn yn glir?
Beth yw O fawr o'r ateb hwn?
Timewise.
Heb n eithaf ^ 2.
Sylwer ein bod yn ailadrodd o 0 i n,
felly dyna un ar gyfer dolen.
Rydym yn ailadrodd eto o bron dechrau i'r diwedd, un arall ar gyfer dolen.
Ac yn awr, o fewn hynny, mae'n rhaid i ni grynhoi bob cofnod,
felly dyna un arall ar gyfer dolen. Felly, mae gennym dri nythu ar gyfer dolenni, n ^ 3.
Iawn. Mae hyn yn mynd fel man cychwyn.
Mae ein ateb yn ddim gwaeth na n ^ 3.
Ydy pawb yn deall yr ateb 'n ysgrublaidd dreisio?
>> Iawn. Ateb gwell yn defnyddio syniad a elwir yn rhaglennu deinamig.
Os ydych yn cymryd CS124, sef Algorithmau a Strwythurau Data,
byddwch yn dod yn gyfarwydd iawn gyda'r dechneg hon.
Ac y syniad yw, ceisio adeiladu i fyny atebion i broblemau llai yn gyntaf.
Beth a olygaf wrth hyn yw, yr ydym ar hyn o bryd rhaid i chi boeni am ddau beth: dechrau a diwedd.
Ac mae hynny'n blino. Beth pe gallem gael gwared o un o'r paramedrau?
Un syniad yw - we're o ystyried ein problem gwreiddiol,
ddod o hyd i'r swm mwyaf o unrhyw subarray mewn ystod [O, n-1].
Ac yn awr mae gennym subproblem newydd, lle y gwyddom, yn ein mynegai ar hyn o bryd i,
rydym yn gwybod mae'n rhaid i ni ddod i'r casgliad yno. Rhaid i'n subarray dod i ben ar y mynegai ar hyn o bryd.
Felly, y broblem sydd ar ôl yw, ble y dylem ddechrau ein subarray?
A yw hyn yn gwneud synnwyr? Iawn.
Felly, yr wyf wedi eu codio hyn i fyny, a gadewch i ni edrych ar beth mae hyn yn ei olygu.
Yn y codirectory, mae 'na raglen o'r enw subarray,
ac mae'n cymryd nifer o eitemau,
ac yn dychwelyd y swm mwyaf posibl subarray yn fy rhestr cymysgu.
Felly, yn yr achos hwn, mae ein subarray mwyaf posibl yw 3.
A bod wedi cymryd gan ddefnyddio dim ond 2 ac 1.
Gadewch i ni ei gynnal eto. Mae hefyd yn 3.
Ond y tro hwn, yn nodi sut rydym yn cael y 3.
Rydym yn cymryd y - rydym yn unig yn cymryd y 3 ei hun
oherwydd ei fod yn amgylchynu gan negyddol ar y ddwy ochr,
fydd yn dod â swm <3.
Gadewch i ni redeg ar 10 eitem.
Y tro hwn mae'n 7, rydym yn cymryd y 3 blaenllaw a 4.
Y tro hwn mae'n 8, ac rydym yn cael bod drwy gymryd 1, 4 a 3.
Felly, er mwyn rhoi i chi greddf ar sut y gallwn ddatrys y broblem hon trawsnewid,
gadewch i ni edrych ar y subarray.
Rydym yn rhoi y array mewnbwn, ac rydym yn gwybod yr ateb yw 8.
Rydym yn cymryd y 1, 4, a 3.
Ond gadewch i ni edrych ar sut yr ydym mewn gwirionedd yn cael yr ateb hwnnw.
Gadewch i ni edrych ar y subarray mwyaf posibl a ddaeth i ben ym mhob un o'r mynegeion hyn.
Beth yw'r subarray mwyaf posibl sydd wedi dod i ben ar y sefyllfa cyntaf?
[Myfyrwyr] Zero. >> Zero. Nid yn unig yn cymryd y -5.
Yma, mae'n mynd i fod yn 0 yn ogystal. Yeah?
(Myfyrwyr, annealladwy)
[Yu] O, mae'n ddrwg gennyf, a -3.
Felly, mae hyn yn 2, mae hyn yn -3.
Iawn. Felly -4, beth yw'r subarray mwyaf posibl i roi terfyn ar y sefyllfa honno
lle -4 ar? Zero.
Un? 1, 5, 8.
Yn awr, rhaid i mi orffen yn y lleoliad lle -2 ar.
Felly 6, 5, 7, ac mae'r un olaf yn 4.
Mae gwybod bod y rhain yn fy cofnodion
am y broblem trawsnewid lle mae'n rhaid imi orffen ym mhob un o'r mynegeion hyn,
yna fy ateb terfynol yn unig, yn cymryd ysgubo ar draws,
ac yn cymryd y nifer mwyaf posibl.
Felly, yn yr achos hwn mae'n 8.
Mae hyn yn awgrymu bod y subarray mwyaf posibl yn dod i ben ar y mynegai,
a dechrau rhywle ger ei fron.
Ydy pawb yn deall y subarray trawsnewid?
>> Iawn. Wel, gadewch i chyfrif i maes y digwydd eto ar gyfer hyn.
Gadewch i ni ystyried dim ond y cofnodion cyntaf.
Felly dyma ei fod yn 0, 0, 0, 1, 5, 8.
Ac yna roedd -2 yma, ac a ddaeth ag ef i lawr i 6.
Felly, os galwaf y cofnod yn safle i subproblem (i),
sut y gallaf ddefnyddio'r ateb i subproblem blaenorol
i ateb y subproblem?
Os byddaf yn edrych ar, gadewch i ni ddweud, y cofnod hwn.
Sut alla i gyfrifo yr ateb 6 drwy edrych ar
cyfuniad o'r amrywiaeth a'r atebion i subproblems blaenorol yn y casgliad? Ydw?
[Myfyrwraig] i chi gymryd y casgliad o symiau
yn y safle cywir cyn hynny, felly yr 8,
ac yna i chi ychwanegu'r subproblem ar hyn o bryd.
[Yu] Felly, ei awgrym yw edrych ar y ddau rif,
rhif hwn a rhif hwn.
Felly, mae hyn 8 yn cyfeirio at yr ateb yn y subproblem (i - 1).
A gadewch i ni alw fy mewnbwn A. amrywiaeth
Er mwyn dod o hyd i subarray mwyaf posibl sy'n dod i ben yn safle i,
Mae gen i ddau ddewis: gallaf naill ai barhau â'r subarray
a ddaeth i ben ar y mynegai blaenorol, neu ddechrau casgliad newydd.
Pe bawn i barhau â'r subarray a ddechreuodd ar y mynegai blaenorol,
yna bydd y swm uchaf y gallaf ei gyflawni yw'r ateb i'r subproblem blaenorol
yn ogystal â'r cofnod amrywiaeth ar hyn o bryd.
Ond, yr wyf hefyd yn cael y dewis o ddechrau subarray newydd,
yn yr achos hwnnw y swm yw 0.
Felly yr ateb yw uchafswm o 0, subproblem i - 1, yn ogystal â'r cofnod amrywiaeth presennol.
A yw hyn yn digwydd eto yn gwneud synnwyr?
Mae ein eto, fel yr ydym yn unig darganfod, yn subproblem i
yn hafal i uchafswm y subproblem flaenorol ynghyd fy nghofnod array ar hyn o bryd,
sy'n golygu parhau â'r subarray blaenorol,
neu 0, dechrau subarray newydd yn fy mynegai ar hyn o bryd.
Ac unwaith y byddwn wedi adeiladu i fyny y tabl hwn o atebion, yna mae ein ateb terfynol,
dim ond gwneud ysgubo llinol ar draws y llu subproblem
ac yn cymryd y nifer mwyaf posibl.
Mae hwn yn gweithredu union yr hyn yr wyf newydd ei ddweud.
Felly, rydym yn creu amrywiaeth subproblem newydd, subproblems.
Y cofnod cyntaf yw naill ai 0 neu y cofnod cyntaf, yr uchafswm o'r ddau.
Ac ar gyfer gweddill y subproblems
byddwn yn defnyddio'r digwydd eto yn union yr ydym yn unig darganfod.
Nawr rydym gyfrifo uchafswm ein subproblems array, a dyna ein hateb terfynol.
>> Felly, faint o le yr ydym yn defnyddio yn y algorithm?
Os ydych wedi cymryd dim ond CS50, yna efallai nad ydych wedi trafod o le yn fawr iawn.
Wel, un peth i'w nodi yw fy mod wedi galw malloc yma gyda n maint.
Beth mae hynny'n awgrymu i chi?
Mae'r algorithm yn defnyddio gofod llinol.
Allwn ni wneud yn well?
A oes unrhyw beth y byddwch yn sylwi bod yn ddiangen i gyfrifo yr ateb terfynol?
Amcana gwestiwn gwell yw, pa wybodaeth
Nid oes angen i ni yr holl ffordd drwodd i'r diwedd?
Yn awr, os ydym yn edrych ar y ddwy linell,
byddwn ond yn gofalu am y subproblem blaenorol,
a dim ond gofalu am yr uchafswm ydym wedi gweld erioed hyd yn hyn.
I gyfrifo ein hateb terfynol, nid oes angen yr amrywiaeth gyfan.
Dim ond angen y rhif olaf, yn para dau rif.
Rhif olaf ar gyfer, array subproblem a rhif olaf ar gyfer yr uchafswm.
Felly, mewn gwirionedd, gallwn ffiws hyn dolenni at ei gilydd
ac yn mynd o le i le llinol yn gyson.
Swm ar hyn o bryd hyd yn hyn, dyma, yn disodli'r rôl subproblem, ein amrywiaeth subproblem.
Swm Felly ar hyn o bryd, hyd yma, yw'r ateb i'r subproblem blaenorol.
Ac y swm hwnnw, hyd yn hyn, yn cymryd lle ein max.
Rydym gyfrifo uchafswm wrth i ni fynd ymlaen.
Ac felly rydym yn mynd o le llinol i ofod gyson,
ac mae gennym hefyd ateb llinol i'n problem subarray.
>> Mae'r mathau hyn o gwestiynau y byddwch yn ei gael yn ystod cyfweliad.
Beth yw cymhlethdod amser; beth yw'r cymhlethdod gofod?
Allwch chi wneud yn well? Oes yna bethau sy'n ddiangen i'w cadw?
Fe wnes i hyn i dynnu sylw at ddadansoddiadau y dylech eu cymryd ar eich pen eich hun
wrth i chi weithio drwy'r problemau hyn.
Bob amser yn gofyn i chi eich hun, "Alla i wneud yn well?"
Yn wir, a allwn ni wneud yn well na hyn?
Fath o gwestiwn tric. Nid ydych yn gallu, oherwydd mae angen i chi
o leiaf yn darllen y mewnbwn i'r broblem.
Felly, y ffaith bod angen i chi o leiaf ddarllen y mewnbwn i'r broblem
yn golygu na allwch chi wneud yn well nag amser llinol,
ac ni allwch wneud yn well na ofod gyson.
Felly, mae hyn, mewn gwirionedd, yr ateb gorau i'r broblem hon.
Cwestiynau? Iawn.
>> Problem farchnad Stoc:
"O ystyried amrywiaeth o gyfanrifau n, cadarnhaol, sero, neu negyddol,
sy'n cynrychioli'r pris stoc dros gyfnod o ddyddiau n,
ysgrifennu swyddogaeth i gyfrifo yr elw mwyaf y gallwch ei wneud
ystyried eich bod yn prynu a gwerthu yn union 1 Stoc o fewn y dyddiau n. "
Yn y bôn, rydym yn awyddus i brynu isel, gwerthu uchel.
Ac rydym am i chyfrif i maes y elw gorau y gallwn ei wneud.
Fynd yn ôl at fy tip, beth yw'r amlwg ar unwaith, ateb symlaf, ond mae'n araf?
Ydw? (Myfyrwyr, annealladwy) >> Ydy.
>> Felly byddech yn unig yn mynd er bod ac edrych ar y prisiau stoc
ar bob pwynt mewn amser, (annealladwy).
[Yu] Iawn, felly mae ei ateb - mae ei awgrym o gyfrifiadura
nad yr isaf a chyfrifiadurol yr uchaf o reidrwydd yn gweithio
oherwydd gallai'r uchaf yn digwydd cyn yr isaf.
Felly beth yw'r ateb 'n ysgrublaidd dreisio i'r broblem hon?
Beth yw'r ddau beth sydd angen i mi benderfynu unigryw yr elw i'n gwneud? Hawl.
Yr ateb yw 'n ysgrublaidd dreisio - oh, felly, George awgrym yw ein bod dim ond angen dau ddiwrnod
i bennu unigryw yr elw o'r ddau ddiwrnod.
Felly, rydym yn cyfrifo bob pâr, fel prynu / gwerthu,
gyfrifo elw, a allai fod yn negyddol neu'n gadarnhaol neu sero.
Gyfrifo elw mwyaf yr ydym yn gwneud ar ôl ailadrodd dros yr holl barau o ddyddiau.
Bydd hynny'n ein hateb terfynol.
A bydd yr ateb hwnnw yn O (n ^ 2), oherwydd bod n dewis dau bâr -
y dyddiau y gallwch ddewis ymhlith ddyddiau diwedd.
Iawn, felly nid wyf ddim yn mynd i fynd dros yr ateb 'n ysgrublaidd dreisio yma.
Rydw i'n mynd i ddweud wrthych fod yna ateb n log n.
Pa algorithm ydych chi'n gwybod bod ar hyn o bryd yw n log n?
Nid yw'n gwestiwn castia.
>> Cyfuno fath. Cyfuno fath yw n log n,
ac yn wir, un ffordd o ddatrys y broblem hon yw defnyddio
math fath o syniad uno a elwir, yn gyffredinol, rhannu a goncro.
Ac y syniad yw fel a ganlyn.
Rydych am i gyfrifo y prynu gorau / gwerthu pâr yn yr hanner chwith.
Dod o hyd yr elw gorau y gallwch ei wneud, yn unig â'r n gyntaf dros ddau ddiwrnod.
Yna byddwch eisiau oompute y prynu gorau / gwerthu pâr ar yr hanner dde,
felly mae'r n ddiwethaf dros ddau ddiwrnod.
Ac yn awr y cwestiwn yw, sut rydym yn cyfuno'r atebion ôl at ei gilydd?
Ydw? (Myfyrwyr, annealladwy)
>> Iawn. Felly, gadewch i mi dynnu llun.
Ydw? (George, annealladwy)
>> Yn union. George ateb yn union gywir.
Felly ei awgrym yw, yn gyntaf gyfrifo y gorau prynu / gwerthu pâr,
ac sy'n digwydd yn yr hanner chwith, felly gadewch i ni alw y chwith, ar ôl.
Gorau prynu / gwerthu pâr sy'n digwydd yn yr hanner cywir.
Ond os ydym yn cymharu dim ond y ddau rif hyn, rydym yn colli achos
lle rydym yn prynu ac yn gwerthu yma yn rhywle yn yr hanner cywir.
Rydym yn prynu yn yr hanner chwith, gwerthu yn yr hanner cywir.
A'r ffordd orau i gyfrifo y gorau prynu / gwerthu pâr sy'n rhychwantu dau hanner
yw i gyfrifo isafswm yma ac gyfrifo uchafswm yma
ac yn cymryd eu gwahaniaeth.
Felly, y ddau achos lle mae'r pâr prynu / gwerthu yn digwydd yn unig yma,
yn unig yma, neu ar y ddau hanner yn cael ei ddiffinio gan y tri rhif.
Felly mae ein algorithm i uno ein datrysiadau ôl at ei gilydd,
rydym am i gyfrifo y gorau prynu / gwerthu pâr
lle rydym yn prynu ar yr hanner chwith a gwerthu ar yr hanner dde.
A'r ffordd orau o wneud hynny yw i gyfrifo y pris isaf yn yr hanner cyntaf,
y pris uchaf yn yr hanner iawn, ac yn cymryd eu gwahaniaeth.
Mae'r tri deillio o elw, mae'r rhain yn dri rhif, byddwch yn cymryd yr uchafswm o'r tri,
a dyna yr elw gorau y gallwch ei wneud dros y diwrnod cyntaf a diwrnod diwedd.
Yma, mae'r llinellau pwysig yn goch.
Mae hyn yn galw recursive i gyfrifo yr ateb yn yr hanner chwith.
Mae hyn yn galw recursive i gyfrifo yr ateb yn hanner cywir.
Mae'r rhain dau ar gyfer dolenni gyfrifo min a'r uchafswm ar yr hanner chwith a dde, yn y drefn honno.
Nawr rwy'n gyfrifo elw sy'n rhychwantu dau hanner,
a'r ateb terfynol yw'r mwyaf o'r tri hyn.
Iawn.
>> Felly, yn sicr, mae gennym algorithm, ond y cwestiwn mwy yw,
beth yw cymhlethdod amser o hyn?
A'r rheswm pam y crybwyllais uno fath yw bod y math hwn o rannu yr ateb
yn ddau ac yna uno ein datrysiadau ôl at ei gilydd
yn union y math o uno fath.
Felly, gadewch i mi fynd drwy gydol.
Os byddwn yn diffinio swyddogaeth (n) t i fod yn nifer o gamau
am ddyddiau n,
ein dwy alwad recursive
yn cael eu pob un yn mynd i gostio t (n / 2),
ac mae dau o'r galwadau hyn.
Nawr mae angen i gyfrifo isafswm o hanner chwith,
y gallaf ei wneud yn n / 2 amser, yn ogystal â'r uchafswm o hanner cywir.
Felly, mae hyn yn n unig.
Ac yna yn ogystal â rhywfaint o waith cyson.
Ac mae hyn yn digwydd eto hafaliad
yn union yr hafaliad eto ar gyfer uno fath.
Ac rydym i gyd yn gwybod bod uno fath yw n log n amser.
Felly, mae ein algorithm yn n hefyd log n amser.
A yw hyn yn fersiwn yn gwneud synnwyr?
Dim ond ailadrodd byr o'r hyn:
T (n) yw nifer o gamau i gyfrifo yr elw mwyaf
dros gyfnod o ddyddiau n.
Mae'r ffordd yr ydym gwahanu ein galwadau recursive
yw drwy ffonio ein ateb ar y dyddiau n / 2 gyntaf,
felly dyna un alwad,
ac yna rydym yn galw unwaith eto ar yr ail hanner.
Felly dyna dwy alwad.
Ac yna rydym yn dod o hyd o leiaf ar yr hanner chwith, y gallwn ei wneud mewn pryd llinol,
ddod o hyd i'r uchafswm o hanner iawn, y gallwn ei wneud mewn amser llinol.
Felly n / 2 + n / 2 yn unig n.
Yna, mae gennym rywfaint o waith cyson, sydd fel gwneud rhifyddeg.
Mae'r hafaliad digwydd eto yn union yr hafaliad eto ar gyfer uno fath.
Felly, mae ein algorithm siffrwd hefyd logio n n.
Felly, faint o le yr ydym yn ei ddefnyddio?
Gadewch i ni fynd yn ôl at y cod.
>> Cwestiwn gwell yw, faint o fframiau stac ydym byth ar unrhyw adeg benodol?
Ers i ni yn defnyddio dychweliad,
nifer y fframiau a stac yn pennu ein defnydd o le.
Gadewch i ni ystyried n = 8.
Rydym yn galw ar 8 siffrwd,
a fydd yn galw siffrwd ar y pedwar cyntaf cofnodion,
a fydd yn galw shuffle ar y ddau gyntaf cofnodion.
Felly mae ein stac yw - mae hyn yn ein pentwr.
Ac yna rydym yn galw siffrwd eto ar 1,
a dyna beth yw ein sylfaen yn achos, felly byddwn yn dychwelyd ar unwaith.
A oes gennym erioed wedi mwy na hyn fframiau stac lawer?
Rhif Gan fod pob tro y byddwn yn gwneud invocation,
a invocation recursive i siffrwd,
rydym yn rhannu ein maint yn ei hanner.
Felly, y nifer uchaf o fframiau stac ni byth ar unrhyw adeg benodol
ar y drefn fframiau log n simnai.
Mae gan bob ffrâm pentwr o ofod gyson,
ac felly cyfanswm y gofod,
y swm uchaf o le fyddwn byth yn defnyddio yw O (log n) lle
lle mae n yw nifer y dyddiau.
>> Nawr, gofynnwch bob amser i chi'ch hun, "Allwn ni wneud yn well?"
Ac yn arbennig, rydym yn lleihau hyn i broblem yr ydym wedi ei datrys yn barod?
Mae awgrym: dim ond trafod dwy broblem eraill cyn hyn, ac nid yw'n mynd i fod yn siffrwd.
Gallwn newid y stoc problem farchnad i mewn i'r broblem subarray mwyaf posibl.
Sut allwn ni wneud hyn?
Un ohonoch chi? Emmy?
(Emmy, annealladwy)
[Yu] Yn union.
Felly mae'r broblem subarray mwyaf posibl,
rydym yn chwilio am swm dros subarray parhaus.
Ac Emmy awgrym am y broblem stociau,
ystyried y newidiadau, neu y deltâu.
A llun o hyn yw - mae hyn yn y pris stoc,
ond os ydym yn cymryd y gwahaniaeth rhwng pob diwrnod yn olynol -
felly rydym yn gweld bod y pris uchaf, elw mwyaf posibl y gallem eu gwneud
yw os ydym yn prynu ac yn gwerthu yma yma.
Ond gadewch i ni edrych ar y barhaus - gadewch i ni edrych ar y broblem subarray.
Felly yma, y ​​gallwn wneud - mynd oddi yma i yma,
gennym newid cadarnhaol, ac yna yn mynd oddi yma i yma mae gennym wedi newid er gwaeth.
Ond yna, yn mynd oddi yma i yma mae gennym newid cadarnhaol enfawr.
Ac mae'r rhain yn newidiadau yr ydym eisiau i grynhoi i gael ein elw terfynol.
Yna, mae gennym newidiadau mwy negyddol yma.
Yr allwedd i leihau ein problem stoc i mewn i'n problem subarray mwyaf posibl
yw ystyried y deltâu rhwng diwrnodau.
Felly, rydym yn creu amrywiaeth newydd o'r enw deltâu,
ymgychwyn y cofnod cyntaf i fod yn 0,
ac yna ar gyfer pob delta (i), gadael i hynny fod y gwahaniaeth
o fy (i) array mewnbwn, a array (i - 1).
Yna, rydym yn galw ein trefn arferol ar gyfer subarray mwyaf posibl
pasio mewn delta o amrywiaeth.
Ac oherwydd subarray mwyaf posibl o amser llinol,
ac y gostyngiad hwn, mae'r broses o greu'r amrywiaeth delta,
Mae hefyd yn amser llinol,
yna yr ateb terfynol ar gyfer stociau yw O (n) yn gweithio yn ogystal O (n) yn gweithio, yn dal O (n) yn gweithio.
Felly mae gennym ateb amser llinol i'n problem.
Ydy pawb yn deall y trawsnewid?
>> Yn gyffredinol, yn syniad da y dylech bob amser
yn ceisio lleihau'r broblem newydd yr ydych yn gweld.
Os yw'n edrych yn gyfarwydd i hen broblem,
ceisiwch leihau i hen broblem.
Ac os allwch chi ddefnyddio'r holl offer yr ydych wedi eu defnyddio ar y hen broblem
i ddatrys y broblem newydd.
Felly, i lapio fyny, cyfweliadau technegol yn heriol.
Mae'r problemau hyn yn debyg bod rhai o'r problemau mwyaf anodd
y gallech eu gweld mewn cyfweliad,
felly os nad ydych yn deall yr holl broblemau a grybwyllais yn unig, ei fod yn iawn.
Mae'r rhain yn rhai o'r problemau yn fwy heriol.
Ymarfer, ymarfer, ymarfer.
Rhoddais llawer o broblemau yn y daflen, felly yn sicr wirio y rhai allan.
A phob lwc ar eich cyfweliad. Mae pob fy adnoddau yn cael eu postio ar y ddolen hon,
ac un o fy ffrindiau uwch wedi cynnig i wneud cyfweliadau ffug technegol,
felly os oes gennych ddiddordeb, e-bost Will Yao yn y cyfeiriad e-bost.
Os oes gennych gwestiynau, gallwch ofyn i mi.
Ydych chi'n guys gennych gwestiynau penodol yn ymwneud â chyfweliadau technegol
neu unrhyw broblemau yr ydym wedi ei weld hyd yn hyn?
Iawn. Wel, pob lwc ar eich cyfweliad.
[CS50.TV]