[Powered by Google Translate] [Seminārs: Tehniskie Intervijas]
[Kenny Yu, Hārvarda universitātes]
[Tas ir CS50.] [CS50.TV]
Sveiki visiem, es esmu Kenny. Es šobrīd jaunākais studē datorzinātnes.
Es esmu bijušais CS TF, un es vēlos man bija tas, kad man bija underclassman,
un tas ir iemesls, kāpēc es esmu sniedzot šo semināru.
Tāpēc es ceru, ka jums baudīt to.
Šis seminārs ir par tehniskās intervijas,
un visi mani resursi var atrast šo saiti,
šo saiti šeit, pāris resursu.
Tāpēc es problēmu sarakstu, patiesībā, diezgan dažas problēmas.
Arī vispārējā resursu lapu, kur mēs varam atrast padomus
par to, kā sagatavoties intervijai,
padomus par to, ko jums vajadzētu darīt laikā faktisko interviju,
kā arī to, kā pieeja problēmas un resursus nākotnē.
Tas viss tiešsaistē.
Un tikai, lai priekšvārds šo semināru, atruna,
kā šis nevajadzētu - savu interviju sagatavošana
nedrīkst ierobežot šajā sarakstā.
Tas ir tikai domāts, lai būtu ceļvedis,
un jums noteikti vajadzētu ņemt visu, ko es saku ar graudu sāls,
bet arī izmantot visu, es izmantoti, lai palīdzētu jums jūsu interviju sagatavošanā.
>> Es esmu gatavojas paātrināt, izmantojot tuvāko slaidiem
lai mēs varētu nokļūt uz faktisko gadījumu izpētes.
Struktūru intervijā programmatūras inženierijas norādītajai vietai,
parasti tas ir 30 līdz 45 minūtes,
vairākas kārtās, atkarībā no uzņēmuma.
Bieži jums tiks kodēšanas uz balta kuģa.
Tāpēc baltā tāfele kā šis, bet bieži mazākā mērogā.
Ja jums ir telefona intervijā, jūs, iespējams, izmantojot
nu collabedit vai Google dokuments, lai viņi varētu redzēt jūs dzīvojat kodēšanas
kamēr jūs tiek intervēti pa tālruni.
Intervija pati parasti 2 vai 3 problēmas
testēšanas savu datorzinātnes zināšanas.
Un tas gandrīz noteikti ietver kodēšanas.
Jautājumu veidi, ka jūs redzēsiet parasti datu struktūras un algoritmi.
Un, to darot šāda veida problēmām,
viņi lūgs jūs, piemēram, kāds ir laiks un telpa sarežģītība, Big O?
Bieži viņi arī lūgt augstāka līmeņa jautājumiem,
tāpēc, izstrādājot sistēmu,
kā jūs noteikt savu kodu?
Kas saskarnes, kas klasēm, ko moduļi Vai jums ir jūsu sistēmā,
un kā tie mijiedarbojas kopā?
Tātad datu struktūras un algoritmi, kā arī projektēšanas sistēmas.
>> Daži vispārīgi padomi, pirms mēs nirt mūsu gadījumu izpētes.
Es domāju, ka vissvarīgākais noteikums ir vienmēr domāt skaļi.
Intervija ir vajadzētu būt jūsu iespēja parādīt savu domāšanas procesu.
Intervijas punkts ir intervētājs novērtēt
kā jūs domājat, un kā jūs iet caur problēmu.
Sliktākais jūs varat darīt, ir klusēt visā interviju.
Tas ir tikai nav labi.
Ja jums tiek dota jautājumu, jūs arī vēlaties, lai pārliecinātos, ka Jums saprast jautājumu.
Tāpēc atkārto jautājumu atpakaļ saviem vārdiem
un mēģinājums darbu novērošanu dažus vienkāršus testpiemēru
lai pārliecinātos, jūs saprotat jautājumu.
Darbs caur pāris testa gadījumos arī dos jums intuīcija par to, kā atrisināt šo problēmu.
Jūs pat varētu atklāt dažas modeļus, lai palīdzētu jums atrisināt šo problēmu.
Viņu liels gals ir ne saņemt neapmierinātas.
Nesaņem neapmierinātas.
Intervijas ir grūti, bet sliktākais, ko jūs varat darīt,
papildus tam, ka kluss, ir redzami neapmierināti.
Jūs nevēlaties, lai dotu, ka iespaidu uz intervētāju.
Viena lieta, ka jūs - tik daudzi cilvēki, kad viņi iet uz interviju,
viņi cenšas, lai mēģinātu rast labāko risinājumu, pirmkārt,
ja tiešām, tur parasti glaringly skaidrs risinājums.
Tas varētu būt lēna, tas varētu būt neefektīva, bet jums vajadzētu vienkārši norādīt to,
vienkārši tāpēc jums ir sākuma punkts, no kura strādāt labāk.
Arī norādot risinājums ir lēns, runājot par
Big O laiks sarežģītība vai kosmosa sarežģītība,
demonstrēs uz intervētāju, ka jūs saprotat
šie jautājumi rakstot kodu.
Tāpēc nav jābaidās nākt klajā ar vienkāršāko algoritmu 1.
un pēc tam strādāt labāk no turienes.
Kādi jautājumi līdz šim? Labi.
>> Tātad, pieņemsim pikējošais mūsu pirmā problēma.
"Ņemot vērā masīvs n integers, uzrakstīt funkciju, kas shuffles masīvs
vietā tādā veidā, ka visi n integers permutācijas ir vienlīdz iespējams. "
Un pieņemu, jums ir pieejams izlases skaitlim ģenerators
kas ģenerē veselu skaitli diapazonā no 0 līdz i, puse diapazons.
Vai visi saprot šo jautājumu?
Es jums masīvs n integers, un es gribu, lai jūs shuffle to.
Manā direktorijā, es uzrakstīju dažas programmas, lai parādītu, ko es domāju.
Es esmu gatavojas, lai sajauktu masīvs 20 elementiem,
no -10 līdz +9,
un es gribu, lai jūs ar rezultātu sarakstu, kā šis.
Tātad šis ir mans sakārtoti ieejas masīvs, un es gribu, lai jūs shuffle to.
Mēs darīsim to vēlreiz.
Vai visi saprot šo jautājumu? Labi.
Tātad tas ir atkarīgs no jums.
Kas ir dažas idejas? Vai jūs varat darīt to par n ^ 2, n log n, n?
Atvērta ierosinājumus.
Labi. Tātad viena ideja, ierosināja Emmy,
ir pirmais aprēķināt izlases numuru, izlases skaitlim, tādā robežās no 0 līdz 20.
Tātad uzņemties mūsu masīvs garums ir 20.
Mūsu diagrammā 20 elementiem,
Tas ir mūsu ieguldījums masīvs.
Un tagad, viņas ieteikums ir izveidot jaunu masīvu,
tāpēc šī būs izejas masīvs.
Un, pamatojoties uz i atgriezās ar rand -
Tātad, ja man bija, teiksim, 17,
kopēt 17 elementu uz pirmo pozīciju.
Tagad mums ir nepieciešams, lai dzēstu - mums ir jāmaina visi elementi šeit
virs tā, ka mums ir beigās plaisu un nav pa vidu caurumiem.
Un tagad mēs atkārtojiet procesu.
Tagad mēs izvēlētos jaunu izlases veselam skaitlim no 0 līdz 19.
Mums ir jauna es šeit, un mēs kopēt šo elementu šajā pozīcijā.
Tad mēs pāreju priekšmetus virs un mēs atkārtojiet procesu, kamēr mums ir mūsu pilnīgu jaunu bloku.
Kāds ir palaist laiks šo algoritmu?
Nu, pieņemsim apsvērt ietekmi uz šo.
Mēs novirzot katru elementu.
Kad mēs noņemt šo es, mēs novirzot visus elementus pēc tam pa kreisi.
Un tas ir O (n) izmaksas
jo ko tad mēs noņemtu pirmo elementu?
Tātad uz katru pārvietošanu, mēs noņemam -
Katru izņemšanas rodas O (n) darbību,
un, jo mēs esam n izraidīšanu, tas noved pie O (n ^ 2) shuffle.
Labi. Tik labs sākums. Labs sākums.
>> Vēl viens ieteikums ir izmantot kaut ko sauc par Knuth shuffle,
vai Fisher-Yates dīdīties.
Un tas tiešām lineārs laiks dīdīties.
Un ideja ir ļoti līdzīga.
Atkal, mums ir mūsu ieejas masīvs,
bet tā vietā izmantojot divus masīvus mūsu ievades / izvades,
mēs izmantojam pirmo daļu masīva, lai sekotu mūsu iegrozījās daļu,
un mēs sekot līdzi, un tad mēs atstāt visu mūsu masīva par unshuffled daļu.
Tātad, šeit ir tas, ko es domāju. Mēs sākt ar - mēs izvēlamies kādu I,
masīvs 0-20.
Mūsu pašreizējā rādītājs ir vērsta uz pirmo indeksu.
Mēs izvēlēties kādu es šeit
un tagad mēs swap.
Tātad, ja tas bija 5 un tas bija 4,
iegūtais masīvs būs 5 Šeit un 4 šeit.
Un tagad mēs atzīmējam marķieri šeit.
Viss pa kreisi ir iegrozījās,
un viss pa labi tiek unshuffled.
Un tagad mēs varam atkārtot šo procesu.
Mēs izvēlamies izlases indeksu starp 1 un 20 tagad.
Tātad pieņemsim, ka mūsu jaunais man ir šeit.
Tagad mēs swap šo es ar mūsu pašreizējo jaunajā amatā šeit.
Tāpēc mēs pārnešana uz priekšu un atpakaļ, kā šis.
Ļaujiet man audzināt kodu, lai padarītu to konkretizēt.
Sākam ar mūsu izvēli i -
sākam ar I vienāds ar 0, mēs izvēlēties izlases atrašanās J
kas unshuffled daļu masīva, es līdz n-1.
Tātad, ja es esmu šeit, izvēlēties izlases indeksu starp šeit un masīva pārējo,
un mēs swap.
Tas ir viss kods nepieciešams, lai sajauktu savu masīvs.
Kādi jautājumi?
>> Nu, viena vajadzīga jautājums ir, kāpēc tas ir pareizi?
Kāpēc ir katru permutāciju tikpat iespējams?
Un es neiešu cauri pierādījums tam,
bet daudzi problēmas datorzinātnēs var pierādīt, izmantojot indukcijas.
Cik daudzi no jums ir iepazinušies ar indukciju?
Labi. Atdzist.
Tātad jūs varat pierādīt pareizību šo algoritmu ar vienkāršu indukcijas,
kur jūsu indukcijas hipotēze būtu, pieņemsim, ka
mans shuffle atgriež katru permutation tikpat iespējams
līdz pirmajiem i elementiem.
Tagad, uzskata i + 1.
Un kā mēs izvēlamies mūsu indekss j swap,
tas noved pie - un tad jūs izstrādāt detaļas,
vismaz pilns pierādījumu par to, kāpēc šis algoritms atgriež
Katru permutāciju ar tikpat iespējams varbūtību.
>> Labi, nākamā problēma.
Tāpēc "ņemot vērā masīvs integers, postive, nulle, negatīvs,
uzrakstīt funkciju, kas aprēķina maksimālo summu
Jebkura continueous subarray no ieejas bloku. "
Piemērs šeit ir, gadījumā, ja visi skaitļi ir pozitīvi,
tad šobrīd labākā izvēle ir veikt visai masīvs.
1, 2, 3, 4, veido 10.
Ja jums ir daži negatīvi tur,
šajā gadījumā mēs vienkārši vēlamies pirmās divas
jo izvēloties -1 un / vai -3 nesīs mūsu summu leju.
Dažreiz mēs varētu būt jāsāk vidū masīva.
Dažreiz mēs vēlamies, lai izvēlētos neko, tas ir labākais, lai neņem neko.
Un dažreiz tas ir labāk, lai kritums,
jo pēc tā lieta ir super liels. Tātad jebkuras idejas?
(Students, nesaprotami) >> Jā.
Pieņemsim, ka es nelietojiet -1.
Tad nu es izvēlos 1000 un 20000,
vai es vienkārši izvēlēties 3 miljardus.
Nu, labākā izvēle ir veikt visus numurus.
Tas -1, neskatoties negatīva,
visa summa ir labāka nekā bija man nav jāņem -1.
Tātad viens no padomiem es minēju iepriekš, bija norādīt skaidri redzams
un brutālu spēku risinājums pirmās.
Kāds ir brutālu spēku risinājums šai problēmai? Yeah?
[Jane] Nu, es domāju, Brute Force šķīdums
būtu saskaitīt visas iespējamās kombinācijas (nesaprotami).
[Yu] Labi. Tāpēc Džeinas ideja ir veikt visus iespējamos -
Es esmu pārfrazējot - ir veikt visus iespējamos nepārtrauktu subarray,
aprēķināt summu, un tad maksimāli visu iespējamo nepārtraukto subarrays.
Kas unikāli identificē subarray manā ieejas masīvā?
Piemēram, kāda divas lietas man ir nepieciešams? Yeah?
(Students, nesaprotami) >> Tiesības.
Apakšējā robeža indeksu un augšējo robežu indekss
unikāli nosaka nepārtrauktu subarray.
[Studente] Vai mēs aplēšot tas masīvs unikālu numuriem?
[Yu] Nē Tātad viņas jautājums ir, vai mēs pieņemot mūsu masīvs -
Mūsu masīvs visi unikālie numuri, un atbilde ir nē.
>> Ja mēs izmantojam mūsu brutālu spēku risinājumu, tad sākuma / beigu indeksi
unikāli nosaka mūsu nepārtrauktu subarray.
Tātad, ja mēs pārietu uz visiem iespējamiem starta ierakstus,
un visiem tiešajiem ierakstus> vai = sākt, un <n,
jūs aprēķināt summu, un tad mēs maksimālo summu mēs esam redzējuši līdz šim.
Vai tas skaidrs?
Kas ir liels O šo šķīdumu?
Timewise.
Ne gluži n ^ 2.
Ievērojiet, ka mēs atkārtot no 0 līdz n,
tā ka ir viens cilpa.
Mēs atkārtot vēlreiz no gandrīz sākuma līdz beigām, otru cilpu.
Un tagad, laikā, mums ir Rezumējot katru ierakstu,
tā ka cits uz cilpas. Tāpēc mums ir trīs ligzdotu uz cilpas, n ^ 3.
Labi. Tas ir kā sākuma punktu.
Mūsu risinājums ir ne sliktāks nekā n ^ 3.
Vai visi saprastu brutālu spēku risinājums?
>> Labi. Labāks risinājums ir izmantot priekšstatu par dinamisko programmēšana.
Ja esat lietojis CS124, kas ir algoritmi un datu struktūras,
Jums būs ļoti pazīstams ar šo tehniku.
Un ideja ir, mēģināt veidot risinājumus mazākiem problēmu pirmās.
Ko es domāju ar šo ir, mums šobrīd ir jāuztraucas par divām lietām: sākuma un beigu.
Un tas ir kaitinošas. Ko darīt, ja mēs varētu atbrīvoties no viena no šiem parametriem?
Viena ideja ir - mēs ņemot vērā mūsu sākotnējā problēma,
atrast maksimālo summu jebkurā subarray diapazons ir [O, n-1].
Un tagad mums ir jauns subproblem, kur mēs zinām, mūsu pašreizējā indeksa i,
mēs zinām, jāsecina tur. Mūsu subarray jābeidz pie pašreizējā indeksa.
Tāpēc atlikusī problēma ir, kur mums būtu jāsāk mūsu subarray?
Vai tas ir jēga? Labi.
Tāpēc es esmu kodēti šo augšu, un aplūkosim, ko tas nozīmē.
Jo codirectory, tur programma, ko sauc subarray,
un tas aizņem vairākus priekšmetus,
un tas atgriež maksimālo subarray summu manā iegrozījās sarakstā.
Tātad šajā gadījumā, mūsu maksimālā subarray ir 3.
Un tas ir pieņemts, tikai izmantojot 2 un 1.
Pieņemsim palaist vēlreiz. Tas ir arī 3.
Bet šoreiz, ņemiet kā mēs saņēmām 3.
Mēs ņēmām - mēs vienkārši ņemt 3 pati
jo tas ir ieskauj negatīviem abās pusēs,
kas dos lielu summu <3.
Pieņemsim palaist uz 10 jautājumiem.
Šoreiz tas ir 7, mēs uzņemties vadošo 3 un 4.
Šoreiz tas ir 8, un mēs iegūstam, ka, ņemot 1, 4 un 3.
Tātad, lai dotu jums intuīciju, kā mēs varam atrisināt šo pārveidots problēmu,
pieņemsim apskatīt šo subarray.
Mēs esam ņemot šo ievades masīvs, un mēs zinām, ka atbilde ir 8.
Mēs ņemam 1, 4, un 3.
Bet pieņemsim apskatīt to, kā mēs faktiski ieguva šo atbildi.
Apskatīsim augstāko subarray kas beidzās katrā no šiem rādītājiem.
Kas ir maksimālais subarray ka ir jābeidzas pirmajā pozīcijā?
[Studentu] Zero. >> Zero. Vienkārši nav uzņemties -5.
Šeit tas būs 0 un labi. Yeah?
(Students, nesaprotami)
[Yu] Ak, piedodiet, tas ir -3.
Tātad tas ir 2, tas ir -3.
Labi. Tātad -4, kas ir maksimālais subarray izbeigt šo nostāju
kur -4 ir? Nulle.
Vienu? 1, 5, 8.
Tagad, man jābeidz tajā vietā, kur -2 ir.
Tātad 6, 5, 7, un pēdējais ir 4.
Zinot, ka tās ir manas ieraksti
par transformēta problēmas, ja man jāizbeidz katrā no šiem rādītājiem,
tad mans gala atbilde ir tikai, veikt slaucīšana pāri,
un veikt maksimālo skaitu.
Tātad šajā gadījumā tas ir 8.
Tas nozīmē, ka maksimālā subarray beidzas šo indeksu,
un sāka kaut kur pirms tā.
Vai visi saprot šo pārveidots subarray?
>> Labi. Nu, pieņemsim izdomāt atkārtošanās par to.
Apskatīsim tikai dažus pirmos ierakstus.
Tātad šeit tas bija 0, 0, 0, 1, 5, 8.
Un tad tur bija -2 šeit, un tas nesa to uz leju līdz 6.
Tātad, ja es aicinu ierakstu pie pozīcijai i subproblem (i),
kā es varu izmantot atbildi uz iepriekšējo subproblem
atbildēt uz šo subproblem?
Ja es skatos uz, teiksim, šis ieraksts.
Kā es varu aprēķināt atbildi 6, apskatot
kombinācija šī masīva un atbildes uz iepriekšējiem subproblems šajā masīvā? Jā?
[Studente] Tu ņem masīvs summas
stāvoklī tieši pirms tā, lai 8,
un tad jūs pievienot pašreizējo subproblem.
[Yu] Tātad viņas ieteikums ir skatīties uz šiem diviem numuriem,
šis skaitlis un šis skaitlis.
Tātad šis 8 attiecas uz atbildi par subproblem (i - 1).
Un sauksim mana ieejas bloku A.
Lai atrastu maksimālu subarray kas beidzas stāvoklī i,
Man ir divas iespējas: Es var vai nu turpināt subarray
kas beidzās pie iepriekšējā indeksu, vai sākt jaunu masīvu.
Ja es būtu turpināt subarray kas sākās pēc iepriekšējā indeksa,
tad maksimālais summa es varētu sasniegt, ir atbilde uz iepriekšējo subproblem
plus pašreizējais masīvs ieraksts.
Bet, es arī ir izvēle, sākot jaunu subarray,
tādā gadījumā summa ir 0.
Tātad atbilde ir max 0, subproblem i - 1, plus pašreizējais masīvs ieraksts.
Vai tas atkārtosies jēga?
Mūsu atkārtošanās, kā mēs tikko atklāju, ir subproblem es
ir vienāda ar iepriekšējā subproblem maksimāli plus manu pašreizējo masīvs ierakstu,
kas nozīmē turpināt iepriekšējo subarray,
vai 0, sākt jaunu subarray pie mana pašreizējā indeksa.
Un kad mēs esam izveidojuši šo tabulu risinājumu, tad mūsu gala atbilde,
vienkārši darīt lineāru vēziens pāri subproblem masīvs
un veikt maksimālo skaitu.
Tas ir precīzs īstenošana, ko es tikko teicu.
Tātad mēs izveidot jaunu subproblem masīvu, subproblems.
Pirmais ieraksts ir vai nu 0 vai pirmais ieraksts, maksimālais šiem diviem.
Un par pārējo subproblems
mēs izmantojam precīzu atkārtošanos mēs vienkārši atklāts.
Tagad mēs aprēķināt maksimāli mūsu subproblems masīvs, un tas ir mūsu gala atbilde.
>> Tātad, cik daudz vietas mēs izmantot šo algoritmu?
Ja jūs esat tikai veikti CS50, tad jums varētu būt apspriesti telpu ļoti daudz.
Nu, viena lieta ir tas, ka es sauc malloc šeit ar izmēru n.
Ko tas liecina par jums?
Šis algoritms izmanto lineāru telpu.
Mēs varam darīt labāk?
Vai ir kaut kas jūs ievērosiet, ka ir nepieciešama, lai aprēķinātu galīgo atbildi?
Es domāju, labāk jautājums ir, kāda informācija
mums nav nepieciešams veikt visu ceļu līdz beigām?
Tagad, ja mēs skatāmies uz šīm divām līnijām,
mēs tikai rūpējamies par iepriekšējo subproblem,
un mēs tikai rūp maksimāli mēs jebkad esam redzējuši līdz šim.
Lai aprēķinātu savu galīgo atbildi, mums nav nepieciešams visu masīvs.
Mums ir nepieciešams tikai pēdējo numuru, pēdējie divi cipari.
Pēdējais numurs, subproblem masīvs, un pēdējo numuru par maksimāli.
Tātad, patiesībā, mēs varam drošinātāju šie cilpas kopā
un aiziet no lineāru telpu ar pastāvīgu vietu.
Pašreizējais summa šim, šeit, aizvieto lomu subproblem, mūsu subproblem masīvs.
Tātad pašreizējā summa, līdz šim, ir atbilde uz iepriekšējo subproblem.
Un šī summa, līdz šim, veic vietu mūsu maks.
Tiek aprēķināta maksimāli kā mums iet līdzi.
Un tā mēs aiziet no lineāru telpu pastāvīgi telpu,
un mums ir arī lineārs risinājumu mūsu subarray problēmu.
>> Šie jautājumi veida jūs saņemsiet intervijas laikā.
Kāds ir laika sarežģītība, kāda ir telpa sarežģītību?
Vai jūs varat darīt labāk? Vai ir lietas, kas ir lieki turēt ap?
I did this uzsvērt analīzi, ka jums vajadzētu ņemt par savu
kā jūs strādājat ar šīm problēmām.
Vienmēr būt jautā sev: "Vai es darīt labāk?"
Patiesībā, mēs varam darīt labāk, nekā tas?
Kārtot āķīgs jautājums. Jūs nevarat, jo jums ir nepieciešams, lai
vismaz lasīt pievade problēmas.
Tātad fakts, ka jums ir nepieciešams, lai vismaz lasīt ieguldījumu problēmas
nozīmē, ka jums nevar darīt labāk nekā lineārā laika,
un jūs nevar darīt labāk nekā pastāvīgu telpu.
Tātad tas ir, faktiski, labākais risinājums šai problēmai.
Jautājumi? Labi.
>> Akciju tirgus problēma:
"Ņemot vērā masīvs n integers, pozitīvs, nulle vai negatīvs,
kas pārstāv cena par uzkrājumu n dienām,
uzrakstīt funkciju, lai aprēķinātu maksimālo peļņu, jūs varat veikt
ņemot vērā, ka jūs pirkt un pārdot tieši 1 noliktavas šajās n dienām. "
Būtībā, mēs vēlamies pirkt zemi, pārdot augstas.
Un mēs gribam, lai noskaidrotu vislabāko peļņu, mēs varam sniegt.
Dodas atpakaļ uz manu galu, kas ir uzreiz skaidrs, Vienkāršākā atbilde, bet tas ir lēns?
Jā? (Students, nesaprotami) >> Jā.
>> Tātad jūs vēlētos doties gan, un apskatīt akciju cenām
pie katra brīdis, (nesaprotams).
[Yu] Labi, tāpēc viņas risinājums - viņas ierosinājums skaitļošanas
zemāko un skaitļošanas augstākais ne vienmēr strādā
jo augstākā varētu notikt pirms viszemākais.
Tātad, kāda ir brutālu spēku šīs problēmas risinājums?
Kādas ir divas lietas, kas man ir nepieciešams, lai unikāli noteikt peļņu man darīt? Tiesības.
Brutālu spēku risinājums ir - ak, jā, Jura ieteikums ir, mēs tikai nepieciešams divas dienas
unikāli noteiktu peļņu šajās divās dienās.
Tātad mēs aprēķināt ik pāris, patīk pirkt / pārdot,
aprēķināt peļņu, kas varētu būt negatīva vai pozitīva vai nulles.
Aprēķināt maksimālo peļņu, ka mēs pēc atkārtojot pār visiem dienu pāriem.
Tas būs mūsu galīgā atbilde.
Un šis risinājums būs O (n ^ 2), jo tur ir n izvēlēties divus pārus -
Dienu, ka jūs varat izvēlēties starp gala dienām.
Labi, tāpēc es neesmu gatavojas iet pa brutālu spēku risinājumu šeit.
Es esmu gatavojas pateikt, ka tur ir n log n šķīdums.
Ko algoritms jūs šobrīd zināt, ka ir n log n?
Tas nav āķīgs jautājums.
>> Sapludināt šķirot. Sapludināt kārtošanas ir n log n,
un patiesībā, viens no veidiem, kā atrisināt šo problēmu, ir izmantot
sapludināšana veida idejas veida sauc, vispār, skaldi un valdi.
Un ideja ir šāda.
Jūs vēlaties, lai aprēķinātu labāko pirkt / pārdot pāra kreisajā pusē.
Atrastu vislabāko peļņu jūs varat darīt, tikai ar pirmo n uz divām dienām.
Tad jūs vēlaties, lai oompute labāko pirkt / pārdot pāri labajā pusē,
tā pēdējā n divas dienas.
Un tagad jautājums ir, kā mēs apvienot šos risinājumus atpakaļ kopā?
Jā? (Students, nesaprotami)
>> Labi. Tāpēc ļaujiet man pievērst attēlu.
Jā? (George, nesaprotami)
>> Tieši tā. Jura risinājums ir tieši labi.
Tāpēc viņa ierosinājums ir, vispirms aprēķināt labāko pirkt / pārdot pāri,
un kas notiek kreisajā pusē, tāpēc sauksim ka kreisi, pa kreisi.
Labākais pirkt / pārdot pāris, kas notiek pareizajā pusē.
Bet, ja mēs tikai salīdzinot šos divus skaitļus, mēs esam trūkst lietu
kur mēs pirkt šeit un pārdot kaut kur labajā pusē.
Pērkam kreisajā pusē, pārdot pareizajā pusē.
Un labākais veids, lai aprēķinātu labāko pirkt / pārdot pāris, kas aptver abas pusītes
ir aprēķināt minimālo šeit un aprēķināt maksimālo šeit
un uzņemties savu atšķirību.
Tātad abos gadījumos, kad pirkt / pārdot pāri notiek tikai šeit,
tikai šeit, vai abām pusēm ir noteikts šiem trim numuriem.
Tāpēc mūsu algoritms apvienot mūsu risinājumus atpakaļ kopā,
Mēs vēlamies, lai aprēķinātu labāko pirkt / pārdot pāri
kur mēs nopirkt kreisajā pusē un pārdot labajā pusē.
Un labākais veids, kā to darīt, ir aprēķināt zemāko cenu pirmajā pusē,
augstāko cenu pareizajā pusē, un uzņemties savu atšķirību.
Rezultātā bija 3 peļņa, šie trīs skaitļi, jums veikt maksimāli trīs,
un tas ir labākais peļņas varat veikt pa šo pirmo un beigu dienu.
Šeit svarīgi līnijas ir sarkanā krāsā.
Tas ir rekursīvs zvanu, lai aprēķinātu atbildi kreisajā pusē.
Tas ir rekursīvs zvanu, lai aprēķinātu atbildi pareizajā pusē.
Šie uz cilpas 2 aprēķināt min un max uz kreisās un labās pusi, attiecīgi.
Tagad es aprēķināt peļņu, kas aptver abas pusītes,
un galīgā atbilde ir maksimālais no šiem trim.
Labi.
>> Tātad, pārliecinieties, mums ir algoritms, bet lielāks jautājums ir,
Kāds ir laika sarežģītība šo?
Un iemesls, kāpēc es teicu sapludināšanas kādas ir tā, ka šī forma sadalīt atbildi
divās un pēc tam apvienojot mūsu risinājumus atkal kopā
ir tieši forma sapludināšanas veida.
Tāpēc ļaujiet man iet cauri laiku.
Ja mēs noteikti funkciju t (N), lai būtu vairāki pasākumi
par n dienām,
abi mūsu rekursīvas zvani
ir katra maksās t (N / 2),
un tur ir divi no šiem zvaniem.
Tagad man ir nepieciešams, lai aprēķinātu minimumu kreisajā pusē,
ko es varētu darīt, n / 2 laiks, plus labajā pusē maksimums.
Tātad tas ir tikai n.
Un tad arī kādu pastāvīgu darbu.
Un šī atkārtošanās vienādojums
ir tieši atkārtošanās vienādojums sapludināšanas kārtošanas.
Un mēs visi zinām, ka sapludināšanas kārtošanas ir n log n laika.
Tāpēc mūsu algoritms ir arī n log n laika.
Vai šī atkārtojuma jēga?
Tikai īss kopsavilkums par šo:
T (n) ir virkne pasākumu, lai aprēķinātu maksimālo peļņu
gaitā n dienām.
Tas, kā mēs sadalīt mūsu rekursīvas zvanu
ir zvanot mūsu risinājumu par pirmajiem n / 2 dienas,
tā ka viens zvans,
un tad mēs saucam atkal otrajā pusē.
Tā ka ir divi zvani.
Un tad mēs atrastu vismaz kreisajā pusē, ko mēs varam darīt, lineārā laika,
atrast maksimāli labajā pusē, ko mēs varam darīt lineārā laika.
Tātad n / 2 + n / 2 ir tikai n.
Tad mums ir dažas pastāvīgu darbu, kas patīk darīt aritmētika.
Šo atkārtošanās vienādojums ir tieši atkārtošanās vienādojums sapludināšanas kārtošanas.
Tādēļ mūsu shuffle algoritms ir arī n log n.
Tātad, cik daudz vietas mēs izmanto?
Iesim atpakaļ uz kodu.
>> Labāks jautājums ir, cik daudz kaudze rāmji mums kādreiz ir jebkurā brīdī?
Tā kā mēs esam izmantojot rekursija,
gada kaudze kadru skaits nosaka mūsu vietas izmantošanu.
Apskatīsim n = 8.
Mēs saucam shuffle gada 8,
kas aicinās shuffle par pirmajiem četriem ierakstiem,
kas būs zvanīt shuffle par pirmajiem diviem ierakstiem.
Tātad mūsu kaudze ir - tas ir mūsu kaudze.
Un tad mēs saucam shuffle atkal uz 1,
un tas, ko mūsu bāzes scenārijs ir, lai mēs atgrieztos uzreiz.
Vai mēs kādreiz ir vairāk nekā šo daudzas kaudze rāmji?
Nr jo katru reizi mēs darām piesaukšana,
rekursīva piesaukšana, lai sajauktu,
Mēs sadalīt mūsu izmēra uz pusi.
Tātad maksimālais skaits kaudze kadru mums kādreiz ir jebkurā brīdī
ir par kārtību log n kaudze rāmjiem.
Katrs kaudze rāmis ir nemainīga telpu,
un tāpēc kopējā summa telpas,
maksimālais apjoms telpā mēs kādreiz izmantot ir O (log n) kosmosa
kur n ir dienu skaits.
>> Tagad, vienmēr jautāt sev: "Vai mēs labāk?"
Un jo īpaši, mēs varam samazināt to problēmu, mēs esam jau atrisinātas?
Mājiens: mēs tikai apsprieda divus citas problēmas pirms tam, un tas nav būs dīdīties.
Mēs varam pārvērst šo akciju tirgus problēmu uz maksimālu subarray problēmu.
Kā mēs varam darīt?
Viens no jums? Emmy?
(Emmy, nesaprotami)
[Yu] Tieši tā.
Tātad maksimālā subarray problēmas,
mēs meklējam summu virs nepārtrauktu subarray.
Un Emmy ieteikums par krājumu problēmas,
apsvērt izmaiņām vai deltas.
Un no šī aina - tas ir cena par akciju,
bet, ja mēs ņēmām atšķirību starp katru kārtas dienā -
tāpēc mēs redzam, ka maksimālā cena, maksimālais peļņas mēs varētu darīt
ir, ja mēs pirkt šeit un pārdot šeit.
Bet pieņemsim apskatīt nepārtraukta - pieņemsim apskatīt subarray problēmu.
Tātad šeit mēs varam darīt - iet no šejienes šeit,
mums ir pozitīvas pārmaiņas, un tad iet no šejienes uz vietas mums ir negatīva izmaiņas.
Bet tad, pārejot no šeit šeit mums ir milzīgs pozitīvas pārmaiņas.
Un šie ir izmaiņas, ko mēs vēlamies apkopot, lai saņemtu mūsu gala peļņu.
Tad mums ir vairāk negatīvas izmaiņas šeit.
Galvenais, lai samazinātu mūsu krājumu problēma mūsu maksimālā subarray problēmu
ir apsvērt delta koeficientus starp dienu.
Tāpēc mēs izveidojam jaunu masīvu sauc deltas,
inicializēt pirmo ierakstu uz 0,
un tad katras deltas (i), nemaz ka ir starpība
gada mana ieejas masīvs (i), un masīvs (i - 1).
Tad mēs saucam par mūsu ikdienas procedūra maksimālajam subarray
pārvietojoties Delta masīvs.
Un tāpēc maksimālā subarray ir lineāra laika,
un šis samazinājums, šis process, veidojot šo delta masīvs,
Ir arī lineārs laiks,
tad gala risinājums krājumiem ir O (n) darbs plus O (n) darbs, joprojām ir O (n) darbu.
Tātad mums ir lineārā laika risinājumu mūsu problēmai.
Vai visi saprot šo transformāciju?
>> Vispār, laba ideja, ka jums vienmēr ir
ir mēģināt samazināt jaunu problēmu, ka jūs redzēt.
Ja tas izskatās pazīstams ar veco problēmu,
mēģināt samazināt to uz vecā problēma.
Un, ja jūs varat izmantot visus instrumentus, kas jūs esat, ko izmanto par veco problēmu
lai atrisinātu jaunu problēmu.
Tātad, lai satīt, tehniskās intervijas grūti.
Šīs problēmas ir iespējams, daži no vairāk sarežģītu problēmu
ka jūs varētu redzēt intervijā,
tādēļ, ja jūs nesaprotat visas problēmas, kas man tikko kuriem, tas ir labi.
Šie ir daži no sarežģītākajiem problēmām.
Prakse, prakse, prakse.
Man bija daudz problēmu izdales materiāliem, tāpēc noteikti pārbaudiet tos out.
Un labu veiksmi jūsu intervijām. Visas manas resursi tiek publicēts šīs saites,
un viens no maniem vecākajiem draugiem piedāvāja darīt izspēles tehniskās intervijas,
tādēļ, ja jūs interesē, e-pastu tiks Yao šajā e-pasta adresi.
Ja jums ir kādi jautājumi, jūs varat uzdot man.
Vai jums puiši ir konkrēti jautājumi, kas saistīti ar tehniskās intervijas
vai kādas problēmas, mēs esam redzējuši līdz šim?
Labi. Nu, veiksmi jūsu intervijām.
[CS50.TV]