1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminár: Technické Rozhovory]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Harvard University]

3
00:00:04,630 --> 00:00:08,910
[To je CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Ahoj všetci, ja som Kenny. V súčasnej dobe som junior študuje počítačové vedy.

5
00:00:12,420 --> 00:00:17,310
Som bývalý SK TF, a ja som si prial, aby som mal, keď som bol Underclassman,

6
00:00:17,310 --> 00:00:19,380
a to je dôvod, prečo dávam tohto seminára.

7
00:00:19,380 --> 00:00:21,370
Takže dúfam, že sa vám bude páčiť.

8
00:00:21,370 --> 00:00:23,470
Tento seminár je o technických rozhovorov,

9
00:00:23,470 --> 00:00:26,650
a všetky moje zdroje možno nájsť na tomto odkaze,

10
00:00:26,650 --> 00:00:32,350
tento odkaz tu, pár zdrojov.

11
00:00:32,350 --> 00:00:36,550
Tak som si urobil zoznam problémov, v skutočnosti, docela málo problémov.

12
00:00:36,550 --> 00:00:40,800
Tiež všeobecné zdroje stránky, kde môžeme nájsť tipy

13
00:00:40,800 --> 00:00:42,870
o tom, ako sa pripraviť na prijímací pohovor,

14
00:00:42,870 --> 00:00:46,470
tipy na to, čo by ste mali urobiť, pri skutočnom rozhovore,

15
00:00:46,470 --> 00:00:51,910
a ako pristupovať k problémom a zdroje pre budúce použitie.

16
00:00:51,910 --> 00:00:53,980
Je to všetko on-line.

17
00:00:53,980 --> 00:00:58,290
A len preto, aby predhovor tento seminár, zrieknutie,

18
00:00:58,290 --> 00:01:00,690
takhle by to - váš rozhovor príprava

19
00:01:00,690 --> 00:01:02,800
by nemal byť obmedzený v tomto zozname.

20
00:01:02,800 --> 00:01:04,750
To je možné len má byť sprievodca,

21
00:01:04,750 --> 00:01:08,890
a vy by ste mali určite vziať všetko, čo hovorím s trochou soli,

22
00:01:08,890 --> 00:01:14,620
ale tiež použiť všetko, čo som použil, aby vám pomôžu vo vašej rozhovor príprave.

23
00:01:14,620 --> 00:01:16,400
>> Idem do rýchlosti cez niekoľko ďalších snímok

24
00:01:16,400 --> 00:01:18,650
takže sa môžeme dostať do skutočných prípadových štúdií.

25
00:01:18,650 --> 00:01:23,630
Štruktúra rozhovore pre nachádza softvérového inžinierstva,

26
00:01:23,630 --> 00:01:26,320
obvykle je to 30 a 45 minút,

27
00:01:26,320 --> 00:01:29,810
viac kôl, v závislosti na spoločnosti.

28
00:01:29,810 --> 00:01:33,090
Často budete kódovanie na bielom podklade.

29
00:01:33,090 --> 00:01:35,960
Takže biele tabule, ako to, ale často v menšom meradle.

30
00:01:35,960 --> 00:01:38,540
Ak máte telefónny rozhovor, budete pravdepodobne používať

31
00:01:38,540 --> 00:01:44,030
buď collabedit alebo Google Doc, aby mohli vidieť v ktorom žijete, kódovanie

32
00:01:44,030 --> 00:01:46,500
keď ste bol rozhovor po telefóne.

33
00:01:46,500 --> 00:01:48,490
Rozhovor sám je typicky 2 až 3 problémy

34
00:01:48,490 --> 00:01:50,620
testovanie počítačovej vedy znalosti.

35
00:01:50,620 --> 00:01:54,490
A to bude takmer určite zahŕňať kódovanie.

36
00:01:54,490 --> 00:01:59,540
Typy otázok, ktoré uvidíte, sú zvyčajne dátové štruktúry a algoritmy.

37
00:01:59,540 --> 00:02:02,210
A v tom tieto druhy problémov,

38
00:02:02,210 --> 00:02:07,830
budú sa vás opýtať, páči, čo je časová a pamäťová zložitosť, veľký O?

39
00:02:07,830 --> 00:02:09,800
Často sa tiež spýtať na vyššej úrovni otázky,

40
00:02:09,800 --> 00:02:12,530
tak, navrhovanie systému,

41
00:02:12,530 --> 00:02:14,770
ako by ste rozvrhnúť svoj kód?

42
00:02:14,770 --> 00:02:18,370
Čo rozhranie, čo triedy, ktoré moduly máte vo vašom systéme,

43
00:02:18,370 --> 00:02:20,900
a ako tieto ovplyvňujú spolu?

44
00:02:20,900 --> 00:02:26,130
Takže dátové štruktúry a algoritmy, rovnako ako projekčné systémy.

45
00:02:26,130 --> 00:02:29,180
>> Niektoré všeobecné tipy, ako sa ponoríme do našich prípadových štúdií.

46
00:02:29,180 --> 00:02:32,300
Myslím, že najdôležitejšie pravidlo je vždy myslieť nahlas.

47
00:02:32,300 --> 00:02:36,980
Rozhovor by mal byť vaša šanca predviesť svoje myslenie proces.

48
00:02:36,980 --> 00:02:39,820
Bod rozhovore je pre anketára, aby zistili,

49
00:02:39,820 --> 00:02:42,660
ako si myslíte, a ako si prejsť problém.

50
00:02:42,660 --> 00:02:45,210
Najhoršie, čo môžete urobiť, je byť ticho celom rozhovore.

51
00:02:45,210 --> 00:02:50,090
To je proste k ničomu.

52
00:02:50,090 --> 00:02:53,230
Ak máte k dispozícii otázku, budete tiež chcieť, aby sa ubezpečil, aby ste pochopili otázku.

53
00:02:53,230 --> 00:02:55,350
Takže zopakovať otázku späť vlastnými slovami

54
00:02:55,350 --> 00:02:58,920
a pokus o prácu dôkladné niekoľko jednoduchých testovacích prípadov

55
00:02:58,920 --> 00:03:01,530
aby sa ubezpečil, aby ste pochopili otázku.

56
00:03:01,530 --> 00:03:05,510
Práca cez niekoľko testovacích prípadov bude aj vám intuícia o tom, ako tento problém vyriešiť.

57
00:03:05,510 --> 00:03:11,210
Dalo by sa dokonca objaviť niekoľko vzory, ktoré vám pomôžu problém vyriešiť.

58
00:03:11,210 --> 00:03:14,500
Ich veľkou tip je nie je frustrovaný.

59
00:03:14,500 --> 00:03:17,060
Nenechajte si frustrovaní.

60
00:03:17,060 --> 00:03:19,060
Rozhovory sú náročné, ale to najhoršie, čo môžete urobiť,

61
00:03:19,060 --> 00:03:23,330
Okrem toho, že tichý, je potrebné viditeľne frustrovaný.

62
00:03:23,330 --> 00:03:27,410
Nechcete, aby tento dojem na anketára.

63
00:03:27,410 --> 00:03:33,960
Jedna vec, ktorú - tak, veľa ľudí, keď idú do rozhovoru,

64
00:03:33,960 --> 00:03:37,150
sa pokúsi, aby sa pokúsili nájsť najlepšie riešenie prvej,

65
00:03:37,150 --> 00:03:39,950
keď v skutočnosti, tam je zvyčajne bije do očí riešenie.

66
00:03:39,950 --> 00:03:43,500
To môže byť pomalé, môže to byť neefektívne, ale mali by ste len uviesť to,

67
00:03:43,500 --> 00:03:46,210
Len tak máte východiskový bod, z ktorého sa lepšie pracovať.

68
00:03:46,210 --> 00:03:48,270
Tiež poukázal na riešenie je pomalý, pokiaľ ide o

69
00:03:48,270 --> 00:03:52,160
Veľký O časová zložitosť alebo pamäťová zložitosť,

70
00:03:52,160 --> 00:03:54,450
bude demonštrovať na anketára, že ste porozumeli

71
00:03:54,450 --> 00:03:57,510
Tieto problémy pri písaní kódu.

72
00:03:57,510 --> 00:04:01,440
Takže sa nebojte prísť s najjednoduchším algoritmom prvý

73
00:04:01,440 --> 00:04:04,950
a potom pracovať lepšie odtiaľ.

74
00:04:04,950 --> 00:04:09,810
Akékoľvek otázky tak ďaleko? Dobre.

75
00:04:09,810 --> 00:04:11,650
>> Takže poďme sa ponoriť do našej prvý problém.

76
00:04:11,650 --> 00:04:14,790
"Vzhľadom k tomu, pole celých čísel n, napísať funkciu, ktorá zamieša pole

77
00:04:14,790 --> 00:04:20,209
na mieste tak, že všetky permutácie celých čísel n sú rovnako pravdepodobné. "

78
00:04:20,209 --> 00:04:23,470
A predpokladáme, že máte k dispozícii náhodný generátor integer

79
00:04:23,470 --> 00:04:30,980
ktorý generuje celé číslo v rozmedzí od 0 do i, polovičná rozsah.

80
00:04:30,980 --> 00:04:32,970
Má každý pochopiť túto otázku?

81
00:04:32,970 --> 00:04:39,660
Dávam vám radu celých čísel n, a ja chcem, aby ste to náhodné.

82
00:04:39,660 --> 00:04:46,050
V mojom adresári, napísal som niekoľko programov, ktorými preukážu, čo mám na mysli.

83
00:04:46,050 --> 00:04:48,910
Chystám sa miešať pole 20 prvkov,

84
00:04:48,910 --> 00:04:52,490
-10 Až 9,

85
00:04:52,490 --> 00:04:57,050
a ja chcem, aby ste výstup zoznam, ako je tento.

86
00:04:57,050 --> 00:05:02,890
Tak toto je moja zoradená vstupné pole, a ja chcem, aby ste to náhodné.

87
00:05:02,890 --> 00:05:07,070
Urobíme to znova.

88
00:05:07,070 --> 00:05:13,780
Má každý pochopiť otázku? Dobre.

89
00:05:13,780 --> 00:05:16,730
Takže je to na vás.

90
00:05:16,730 --> 00:05:21,220
Aké sú niektoré nápady? Môžeš to urobiť ako n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Otvorte sa návrhy.

92
00:05:34,400 --> 00:05:37,730
Dobre. Takže jeden nápad, navrhol Emmy,

93
00:05:37,730 --> 00:05:45,300
je prvý vypočítať náhodné číslo, náhodné celé číslo, v rozsahu od 0 do 20 rokov.

94
00:05:45,300 --> 00:05:49,840
Takže predpokladať, naše polia má dĺžku 20.

95
00:05:49,840 --> 00:05:54,800
V našom schéme 20 prvkov,

96
00:05:54,800 --> 00:05:58,560
to je naše vstupné pole.

97
00:05:58,560 --> 00:06:04,590
A teraz, jej návrh je vytvoriť nové pole,

98
00:06:04,590 --> 00:06:08,440
takže to bude výstupné pole.

99
00:06:08,440 --> 00:06:12,880
A na základe aj vrátenej rand -

100
00:06:12,880 --> 00:06:17,580
takže ak som bol, povedzme, 17,

101
00:06:17,580 --> 00:06:25,640
skopírujte 17. prvok do prvej polohy.

102
00:06:25,640 --> 00:06:30,300
Teraz musíme odstrániť - musíme presunúť všetky prvky tu

103
00:06:30,300 --> 00:06:36,920
sa tak, že máme medzery na konci a žiadne diery v strede.

104
00:06:36,920 --> 00:06:39,860
A teraz sme proces opakovať.

105
00:06:39,860 --> 00:06:46,360
Teraz vyberáme nové náhodné číslo medzi 0 a 19.

106
00:06:46,360 --> 00:06:52,510
Máme novú aj tu, a my sme skopírujte tento prvok do tejto polohy.

107
00:06:52,510 --> 00:07:00,960
Potom sme posun položky za nami a my opakujeme, kým máme plnú novú radu.

108
00:07:00,960 --> 00:07:05,890
Čo je doba behu tohto algoritmu?

109
00:07:05,890 --> 00:07:08,110
Dobre, poďme zvážiť dopad tohto.

110
00:07:08,110 --> 00:07:10,380
Sme presúva každý prvok.

111
00:07:10,380 --> 00:07:16,800
Keď sme odstrániť túto ja, sme sa presúva všetky prvky po ňom doľava.

112
00:07:16,800 --> 00:07:21,600
A to je O (n) náklady

113
00:07:21,600 --> 00:07:26,100
pretože to, čo keby sme odstrániť prvý prvok?

114
00:07:26,100 --> 00:07:29,670
Takže pre každý odber, odstránime -

115
00:07:29,670 --> 00:07:32,170
Každý odstránenie nadobudne O (n) operácie,

116
00:07:32,170 --> 00:07:41,520
a pretože sme n sťahovanie, to vedie k O (n ^ 2) miešať.

117
00:07:41,520 --> 00:07:49,550
Dobre. Tak dobrý začiatok. Dobrý začiatok.

118
00:07:49,550 --> 00:07:55,290
>> Ďalšou možnosťou je použiť známy ako shuffle Knuth,

119
00:07:55,290 --> 00:07:57,540
alebo Fisher-Yates shuffle.

120
00:07:57,540 --> 00:07:59,630
A je to vlastne lineárny čas shuffle.

121
00:07:59,630 --> 00:08:02,200
A myšlienka je veľmi podobná.

122
00:08:02,200 --> 00:08:05,160
Opäť, máme vstupné pole,

123
00:08:05,160 --> 00:08:08,580
ale namiesto toho, aby pomocou dvoch polí pre náš vstup / výstup,

124
00:08:08,580 --> 00:08:13,590
používame prvú časť poľa sledovať našej zamiešané časti,

125
00:08:13,590 --> 00:08:18,400
a sledujeme, a potom nechať zvyšok našej pole pre unshuffled časti.

126
00:08:18,400 --> 00:08:24,330
Tak tu je to, čo mám na mysli. Začneme s - zvolíme si aj,

127
00:08:24,330 --> 00:08:30,910
poľa 0-20.

128
00:08:30,910 --> 00:08:36,150
Náš súčasný ukazovateľ ukazuje na prvý index.

129
00:08:36,150 --> 00:08:39,590
Vyberáme niektoré aj tu

130
00:08:39,590 --> 00:08:42,740
a teraz sme vymeniť.

131
00:08:42,740 --> 00:08:47,690
Takže v prípade, že bol 5 a to bolo 4,

132
00:08:47,690 --> 00:08:57,150
Výsledné pole bude mať 5 Tu a 4 tu.

133
00:08:57,150 --> 00:09:00,390
A teraz sme na vedomie, značku tu.

134
00:09:00,390 --> 00:09:05,770
Všetko k ľavici zamiešané,

135
00:09:05,770 --> 00:09:15,160
a všetko vpravo je unshuffled.

136
00:09:15,160 --> 00:09:17,260
A teraz môžeme proces opakovať.

137
00:09:17,260 --> 00:09:25,210
Sme si vybrať náhodný index medzi 1 a 20 teraz.

138
00:09:25,210 --> 00:09:30,650
Takže predpokladám, náš nový aj tu.

139
00:09:30,650 --> 00:09:39,370
Teraz vymeníme to som s našou súčasnou novú pozíciu tu.

140
00:09:39,370 --> 00:09:44,790
Tak sme sa vymieňať tam a späť, ako toto.

141
00:09:44,790 --> 00:09:51,630
Dovoľte mi, aby som vychovať kód, aby to viac konkrétny.

142
00:09:51,630 --> 00:09:55,290
Začneme s našou voľbou aj -

143
00:09:55,290 --> 00:09:58,370
začneme s i rovnať 0, vyberáme náhodné umiestnenie j

144
00:09:58,370 --> 00:10:02,420
v unshuffled časti poľa, aj do n-1.

145
00:10:02,420 --> 00:10:07,280
Takže ak som tu, skúste si vybrať náhodný index medzi tu a zvyšok poľa,

146
00:10:07,280 --> 00:10:12,410
a vymeníme.

147
00:10:12,410 --> 00:10:17,550
To všetko je kód nutné miešať vaše pole.

148
00:10:17,550 --> 00:10:21,670
Nejaké otázky?

149
00:10:21,670 --> 00:10:25,530
>> No, jeden potreboval otázka je, prečo je to správne?

150
00:10:25,530 --> 00:10:28,360
Prečo je každý permutácií rovnako pravdepodobné?

151
00:10:28,360 --> 00:10:30,410
A nebudem prechádzať dôkaz tohto,

152
00:10:30,410 --> 00:10:35,970
ale mnoho problémov v informatike možno dokázať indukciou.

153
00:10:35,970 --> 00:10:38,520
Ako mnohí z vás poznajú s indukciou?

154
00:10:38,520 --> 00:10:40,590
Dobre. Cool.

155
00:10:40,590 --> 00:10:43,610
Takže si môžete overiť správnosť tohto algoritmu jednoduchou indukciou,

156
00:10:43,610 --> 00:10:49,540
, Kde sa vaše indukčné hypotéza by, predpokladajme, že

157
00:10:49,540 --> 00:10:53,290
moje náhodné vracia každý permutácie rovnako pravdepodobné

158
00:10:53,290 --> 00:10:56,120
až prvý som prvkov.

159
00:10:56,120 --> 00:10:58,300
Teraz, zvážte i + 1.

160
00:10:58,300 --> 00:11:02,550
A mimochodom sme sa rozhodli náš index j vymeniť,

161
00:11:02,550 --> 00:11:05,230
to vedie k - a potom prísť na detaily,

162
00:11:05,230 --> 00:11:07,390
aspoň plný dôkaz, prečo tento algoritmus vracia

163
00:11:07,390 --> 00:11:12,800
Každý permutácie sa rovnako pravdepodobné pravdepodobnosťou.

164
00:11:12,800 --> 00:11:15,940
>> Dobre, ďalší problém.

165
00:11:15,940 --> 00:11:19,170
Takže "vzhľadom pole celých čísel, Postive, nula, záporná,

166
00:11:19,170 --> 00:11:21,290
napísať funkciu, ktorá vypočíta maximálnu sumu

167
00:11:21,290 --> 00:11:24,720
akékoľvek continueous subarray vstupné pole. "

168
00:11:24,720 --> 00:11:28,370
Príkladom tu je, v prípade, že všetky čísla sú pozitívne,

169
00:11:28,370 --> 00:11:31,320
potom v súčasnej dobe najlepšou voľbou je vziať celý rad.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, sa rovná 10.

171
00:11:34,690 --> 00:11:36,780
Ak máte nejaké negatívy tam,

172
00:11:36,780 --> 00:11:38,690
V tomto prípade chceme len prvé dva

173
00:11:38,690 --> 00:11:44,590
pretože výber -1 a / alebo -3 prinesie náš súčet dole.

174
00:11:44,590 --> 00:11:48,120
Niekedy sa môžu mať začať v polovici poľa.

175
00:11:48,120 --> 00:11:53,500
Niekedy chceme vybrať vôbec nič, je to najlepšie, aby nemali nič.

176
00:11:53,500 --> 00:11:56,490
A niekedy je lepšie padnúť,

177
00:11:56,490 --> 00:12:07,510
pretože vec po ňom je super veľká. Takže nejaké nápady?

178
00:12:07,510 --> 00:12:10,970
(Študent, nezrozumiteľné) >> Jo.

179
00:12:10,970 --> 00:12:13,560
Predpokladajme, že neberiem -1.

180
00:12:13,560 --> 00:12:16,170
Potom buď volím 1000 a 20000,

181
00:12:16,170 --> 00:12:18,630
alebo som len stačí vybrať 3000000000.

182
00:12:18,630 --> 00:12:20,760
No, najlepšou voľbou je vziať všetky čísla.

183
00:12:20,760 --> 00:12:24,350
Tento -1, napriek tomu, že je negatívny,

184
00:12:24,350 --> 00:12:31,340
Celá súčet je lepšia, než boli nemôžem vziať -1.

185
00:12:31,340 --> 00:12:36,460
Takže jeden z tipov, ktoré som spomenul predtým, bolo uviesť jasne zrejmé

186
00:12:36,460 --> 00:12:40,540
a hrubou silou riešenie ako prvý.

187
00:12:40,540 --> 00:12:44,340
Čo je brutálna sila riešenie tohto problému? Jo?

188
00:12:44,340 --> 00:12:46,890
[Jane] No, myslím, že brutálny sily roztok

189
00:12:46,890 --> 00:12:52,600
by bolo pridať až všetky možné kombinácie (nezrozumiteľný).

190
00:12:52,600 --> 00:12:58,250
[Yu] Dobre. Takže Jane nápad je vziať všetky možné -

191
00:12:58,250 --> 00:13:01,470
Som prerozprávať - ​​je vziať všetky možné kontinuálne subarray,

192
00:13:01,470 --> 00:13:07,840
vypočítať jej súčet, a potom mať maximálne všetkých možných priebežných subarrays.

193
00:13:07,840 --> 00:13:13,310
Čo jednoznačne identifikuje subarray v mojom vstupné pole?

194
00:13:13,310 --> 00:13:17,380
Rovnako ako to, čo dve veci potrebujem? Jo?

195
00:13:17,380 --> 00:13:19,970
(Študent, nezrozumiteľné) >> Právo.

196
00:13:19,970 --> 00:13:22,130
Dolná hranica indexu a hornú hranicu indexu

197
00:13:22,130 --> 00:13:28,300
jednoznačne určuje priebežné subarray.

198
00:13:28,300 --> 00:13:31,400
[Študentka] Už sme odhad, že je to rad unikátnych čísel?

199
00:13:31,400 --> 00:13:34,280
[Yu] No tak jej otázku je, sme za predpokladu, že našu ponuku -

200
00:13:34,280 --> 00:13:39,000
je naše pole všetky jedinečné čísla, a odpoveď je nie.

201
00:13:39,000 --> 00:13:43,390
>> Ak budeme používať náš silovú riešenie, potom na začiatok / koniec indexov

202
00:13:43,390 --> 00:13:47,200
jednoznačne určuje naše kontinuálne subarray.

203
00:13:47,200 --> 00:13:51,680
Takže keď sme iterácii pre všetky možný štart položky,

204
00:13:51,680 --> 00:13:58,320
a pre všetky koncové položky> alebo = začať, a <n,

205
00:13:58,320 --> 00:14:05,570
môžete spočítať súčet, a potom sme sa na maximálnu čiastku sme videli doteraz.

206
00:14:05,570 --> 00:14:07,880
Je to jasné?

207
00:14:07,880 --> 00:14:12,230
Čo je to veľký O tohto roztoku?

208
00:14:12,230 --> 00:14:16,660
TimeWise.

209
00:14:16,660 --> 00:14:18,860
Nie tak celkom n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Všimnite si, že sme iterácii od 0 do n,

211
00:14:25,250 --> 00:14:27,520
tak to je jeden pre sláčiky.

212
00:14:27,520 --> 00:14:35,120
Sme iterácii opäť od takmer začiatku až do konca, ďalšie pre sláčiky.

213
00:14:35,120 --> 00:14:37,640
A teraz, v to, že musíme sčítať všetky položky,

214
00:14:37,640 --> 00:14:43,810
tak to je iná pre sláčiky. Takže máme tri vnorené cykly for, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Dobre. To platí ako východiskový bod.

216
00:14:46,560 --> 00:14:53,180
Naše riešenie nie je o nič horší ako n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Má každý pochopiť silovú riešenie?

218
00:14:55,480 --> 00:14:59,950
>> Dobre. Lepším riešením je použitie predstavu názvom dynamické programovanie.

219
00:14:59,950 --> 00:15:03,040
Ak ste užili CS124, čo je Algoritmy a dátové štruktúry,

220
00:15:03,040 --> 00:15:05,680
stanete sa veľmi dobre oboznámení s touto technikou.

221
00:15:05,680 --> 00:15:12,190
A myšlienka je, pokúsiť sa vybudovať riešenie menších problémov ako prvý.

222
00:15:12,190 --> 00:15:17,990
Čo tým chcem povedať je to, v súčasnej dobe sa starať o dve veci: začiatok a koniec.

223
00:15:17,990 --> 00:15:29,340
A to je nepríjemné. Čo keby sme sa mohli zbaviť jedného z týchto parametrov?

224
00:15:29,340 --> 00:15:32,650
Jeden nápad je - Sme rovnako náš pôvodný problém,

225
00:15:32,650 --> 00:15:37,470
nájsť maximálny súčet všetkých subarray v rozmedzí [O, n-1].

226
00:15:37,470 --> 00:15:47,400
A teraz máme novú podproblém, kde vieme, v našom súčasnom indexu i,

227
00:15:47,400 --> 00:15:52,520
vieme, že musíme urobiť záver, že. Naša subarray musí skončiť v aktuálnom indexe.

228
00:15:52,520 --> 00:15:57,640
Takže zostávajúce problém je, mali kde sme začali našu subarray?

229
00:15:57,640 --> 00:16:05,160
Má to zmysel? Dobre.

230
00:16:05,160 --> 00:16:12,030
Takže som kódu hore, a poďme sa pozrieť na to, čo to znamená.

231
00:16:12,030 --> 00:16:16,230
V codirectory, je tu program s názvom subarray,

232
00:16:16,230 --> 00:16:19,470
a to trvá niekoľko položiek,

233
00:16:19,470 --> 00:16:25,550
a vráti maximálnu subarray sumu v mojom zamiešané zozname.

234
00:16:25,550 --> 00:16:29,920
Takže v tomto prípade, naša maximálna subarray je 3.

235
00:16:29,920 --> 00:16:34,850
A to zhotovená len pomocou 2 a 1.

236
00:16:34,850 --> 00:16:38,050
Poďme znova spustite. Je to tiež 3.

237
00:16:38,050 --> 00:16:40,950
Ale tentoraz, všimnite si, ako sme sa dostali 3.

238
00:16:40,950 --> 00:16:46,690
Vzali sme - sme jednoducho bralo 3 sám

239
00:16:46,690 --> 00:16:49,980
pretože je obklopený negatívov na oboch stranách,

240
00:16:49,980 --> 00:16:55,080
ktorá prinesie určitú čiastku <3.

241
00:16:55,080 --> 00:16:57,820
Poďme beží na 10 položiek.

242
00:16:57,820 --> 00:17:03,200
Tentoraz je to 7, vezmeme vedúci 3 a 4.

243
00:17:03,200 --> 00:17:09,450
Tento čas je 8, a získame že tým, že sa 1, 4 a 3.

244
00:17:09,450 --> 00:17:16,310
Takže vám intuícia o tom, ako môžeme vyriešiť tento transformovaný problém,

245
00:17:16,310 --> 00:17:18,890
Poďme sa pozrieť na tento subarray.

246
00:17:18,890 --> 00:17:23,460
Sme rovnako tento vstupné pole, a vieme, že odpoveď je 8.

247
00:17:23,460 --> 00:17:26,359
Berieme 1, 4, a 3.

248
00:17:26,359 --> 00:17:29,090
Ale poďme sa pozrieť na to, ako sme sa vlastne dostali túto odpoveď.

249
00:17:29,090 --> 00:17:34,160
Poďme sa pozrieť na maximálnu subarray, ktorá skončila na každý z týchto indexov.

250
00:17:34,160 --> 00:17:40,780
Aký je maximálny subarray, ktorý má skončiť na prvom mieste?

251
00:17:40,780 --> 00:17:46,310
[Študent] Zero. >> Zero. Len neberte -5.

252
00:17:46,310 --> 00:17:50,210
Tu to bude 0 rovnako. Jo?

253
00:17:50,210 --> 00:17:56,470
(Študent, nezrozumiteľným)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, ospravedlňujem sa, je to -3.

255
00:17:58,960 --> 00:18:03,220
Takže je 2, to je -3.

256
00:18:03,220 --> 00:18:08,690
Dobre. Takže -4, čo je maximálna subarray ukončiť túto pozíciu

257
00:18:08,690 --> 00:18:12,910
kde -4 je v? Zero.

258
00:18:12,910 --> 00:18:22,570
Jeden? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
Teraz, musím končiť v mieste, kde je v -2.

260
00:18:28,060 --> 00:18:39,330
Tak 6, 5, 7, a posledný je 4.

261
00:18:39,330 --> 00:18:43,480
S vedomím, že to sú moje záznamy

262
00:18:43,480 --> 00:18:48,130
pre transformované problém, kde musím skončiť v každom z týchto indexov,

263
00:18:48,130 --> 00:18:51,410
potom môj posledný odpoveď je len, vziať zákrutu cez,

264
00:18:51,410 --> 00:18:53,580
a pre maximálny celkový počet.

265
00:18:53,580 --> 00:18:55,620
Takže v tomto prípade je to 8.

266
00:18:55,620 --> 00:19:00,010
Z toho vyplýva, že maximálna subarray končí v tomto indexe,

267
00:19:00,010 --> 00:19:04,970
a začal niekde pred ním.

268
00:19:04,970 --> 00:19:09,630
Má každý pochopiť tento transformovaný subarray?

269
00:19:09,630 --> 00:19:22,160
>> Dobre. Dobre, poďme zistiť, opakovanie pre tento.

270
00:19:22,160 --> 00:19:27,990
Pozrime sa len prvých pár položiek.

271
00:19:27,990 --> 00:19:35,930
Tak tu je to 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
A potom tam bol -2 tu, a že priniesla to až do 6.

273
00:19:39,790 --> 00:19:50,800
Takže keď ti budem hovoriť položka na pozíciu aj podproblém (i),

274
00:19:50,800 --> 00:19:54,910
Ako môžem použiť odpoveď na predchádzajúcu podproblém

275
00:19:54,910 --> 00:19:59,360
odpoveď na túto podproblém?

276
00:19:59,360 --> 00:20:04,550
Keď sa pozriem na, povedzme, táto položka.

277
00:20:04,550 --> 00:20:09,190
Ako môžem spočítať odpoveď 6 pri pohľade na

278
00:20:09,190 --> 00:20:18,780
Kombinácia tohto poľa a odpovede na predchádzajúce subproblems v tomto poli? Áno?

279
00:20:18,780 --> 00:20:22,800
[Študentka] Tu sa pole súm

280
00:20:22,800 --> 00:20:25,430
v polohe, priamo pred ňou, takže 8,

281
00:20:25,430 --> 00:20:32,170
a potom pridáte aktuálne podproblém.

282
00:20:32,170 --> 00:20:36,460
[Yu] Takže jej návrh je pozrieť sa na týchto dvoch čísel,

283
00:20:36,460 --> 00:20:40,090
toto číslo a toto číslo.

284
00:20:40,090 --> 00:20:50,130
Takže táto 8 odkazuje na odpovede pre podproblém (i - 1).

285
00:20:50,130 --> 00:20:57,300
A hovorme môj vstupné pole A.

286
00:20:57,300 --> 00:21:01,470
S cieľom nájsť maximálnu subarray, ktorá končí v polohe I,

287
00:21:01,470 --> 00:21:03,980
Mám dve možnosti: môžem buď pokračovať v subarray

288
00:21:03,980 --> 00:21:09,790
, Ktorá skončila na predchádzajúcu index, alebo začať nové pole.

289
00:21:09,790 --> 00:21:14,190
Ak by som mal pokračovať v subarray, ktorá začala v predchádzajúcom indexu,

290
00:21:14,190 --> 00:21:19,260
potom maximálna suma môžem dosiahnuť, je odpoveď na predchádzajúcu podproblém

291
00:21:19,260 --> 00:21:24,120
plus aktuálne pole záznam.

292
00:21:24,120 --> 00:21:27,550
Ale tiež mám na výber spustenie novej subarray,

293
00:21:27,550 --> 00:21:30,830
v takom prípade je súčet je 0.

294
00:21:30,830 --> 00:21:42,860
Takže odpoveď je max 0, podproblém i - 1, plus aktuálne pole záznam.

295
00:21:42,860 --> 00:21:46,150
Znamená to opakovanie zmysel?

296
00:21:46,150 --> 00:21:50,840
Naše opakovanie, ako sme práve zistili, je podproblém aj

297
00:21:50,840 --> 00:21:54,740
sa rovná maximu predchádzajúceho podproblém navyše mojej súčasnej pole vstupu,

298
00:21:54,740 --> 00:22:01,490
čo znamená, že aj naďalej predchádzajúce subarray,

299
00:22:01,490 --> 00:22:07,250
alebo 0, začať nový subarray na mojom súčasnom indexe.

300
00:22:07,250 --> 00:22:10,060
A akonáhle sme vybudovali túto tabuľku riešenie, potom je naša konečná odpoveď,

301
00:22:10,060 --> 00:22:13,950
jednoducho lineárne ťahanie cez podproblém pole

302
00:22:13,950 --> 00:22:19,890
a pre maximálny celkový počet.

303
00:22:19,890 --> 00:22:23,330
To je presne realizácia toho, čo som práve povedal.

304
00:22:23,330 --> 00:22:27,320
Tak sme vytvoriť novú podproblém pole, podproblémy.

305
00:22:27,320 --> 00:22:32,330
Prvá položka je buď 0 alebo prvý vstup, maximálne tých dvoch.

306
00:22:32,330 --> 00:22:35,670
A pre zvyšok subproblems

307
00:22:35,670 --> 00:22:39,810
používame presný opakovanie sme práve objavili.

308
00:22:39,810 --> 00:22:49,960
Teraz určíme maximum našej podproblémy pole, a to je naša konečná odpoveď.

309
00:22:49,960 --> 00:22:54,130
>> Tak koľko miesta sme pomocou tohto algoritmu?

310
00:22:54,130 --> 00:23:01,470
Ak ste len vziať CS50, potom ste možno ešte prerokované priestor veľmi veľa.

311
00:23:01,470 --> 00:23:07,750
No, jedna vec k poznámke je, že som zavolal malloc tu veľkosti n

312
00:23:07,750 --> 00:23:13,590
Čo to naznačujú vás?

313
00:23:13,590 --> 00:23:17,450
Tento algoritmus používa lineárny priestor.

314
00:23:17,450 --> 00:23:21,030
Môžeme to urobiť lepšie?

315
00:23:21,030 --> 00:23:30,780
Je tam niečo, čo zistíte, že je zbytočné počítať konečnú odpoveď?

316
00:23:30,780 --> 00:23:33,290
Myslím, že lepšie otázka je, aké informácie

317
00:23:33,290 --> 00:23:40,680
my nie je potrebné vykonávať celú cestu až do konca?

318
00:23:40,680 --> 00:23:44,280
Teraz, keď sa pozrieme na tieto dva riadky,

319
00:23:44,280 --> 00:23:47,720
nás však zaujíma iba o predchádzajúcej podproblém,

320
00:23:47,720 --> 00:23:50,910
a my sme len o maximálne sme kedy videli doteraz.

321
00:23:50,910 --> 00:23:53,610
Pre výpočet našej konečnú odpoveď, nepotrebujeme celého poľa.

322
00:23:53,610 --> 00:23:57,450
Budeme potrebovať iba posledné číslo, posledné dve čísla.

323
00:23:57,450 --> 00:24:02,630
Posledné číslo pre podproblém pole, a posledné číslo pre maximum.

324
00:24:02,630 --> 00:24:07,380
Takže, v skutočnosti, môžeme zničiť tieto slučky spolu

325
00:24:07,380 --> 00:24:10,460
a ísť od lineárneho priestoru na konštantnú priestoru.

326
00:24:10,460 --> 00:24:15,830
Aktuálna suma tak ďaleko, tu, nahradí úlohu podproblém, naše podproblém poľa.

327
00:24:15,830 --> 00:24:20,020
Takže súčasná suma, tak ďaleko, je odpoveď na predchádzajúcu podproblém.

328
00:24:20,020 --> 00:24:23,450
A táto suma, tak ďaleko, zaberie miesto nášho max.

329
00:24:23,450 --> 00:24:28,100
Počítame maximálnu, ako sme ísť ďalej.

330
00:24:28,100 --> 00:24:30,890
A tak ideme od lineárneho priestoru do konštantnej priestoru,

331
00:24:30,890 --> 00:24:36,650
a tiež majú lineárne riešenie našej subarray problému.

332
00:24:36,650 --> 00:24:40,740
>> Tieto druhy otázok získate počas rozhovoru.

333
00:24:40,740 --> 00:24:44,450
Aká je časová zložitosť, čo je priestorová zložitosť?

334
00:24:44,450 --> 00:24:50,600
Môžeš to urobiť lepšie? Sú tam veci, ktoré sú zbytočné, aby okolo?

335
00:24:50,600 --> 00:24:55,270
Urobil som to zdôrazniť analýzy, ktoré by ste mali podniknúť na vlastnú päsť

336
00:24:55,270 --> 00:24:57,400
ako budete prechádzať týmito problémami.

337
00:24:57,400 --> 00:25:01,710
Vždy sa pýtať sami seba: "Môžem urobiť lepšie?"

338
00:25:01,710 --> 00:25:07,800
V skutočnosti, môžeme robiť lepšie, než toto?

339
00:25:07,800 --> 00:25:10,730
Druh chyták. Nemôžete, pretože je potrebné, aby

340
00:25:10,730 --> 00:25:13,590
aspoň čítať vstup do problému.

341
00:25:13,590 --> 00:25:15,570
Takže skutočnosť, že je potrebné, aby aspoň čítať vstup na problém

342
00:25:15,570 --> 00:25:19,580
znamená, že nemôžete urobiť lepšie, než lineárnom čase,

343
00:25:19,580 --> 00:25:22,870
a môžete to urobiť lepšie než neustále priestoru.

344
00:25:22,870 --> 00:25:27,060
Takže je to, v skutočnosti, že najlepšie riešenie tohto problému.

345
00:25:27,060 --> 00:25:33,040
Otázky? Dobre.

346
00:25:33,040 --> 00:25:35,190
>> Akciový trh problém:

347
00:25:35,190 --> 00:25:38,350
"Vzhľadom k tomu, pole celých čísel n, pozitívne, nula, alebo negatívne,

348
00:25:38,350 --> 00:25:41,680
ktoré predstavujú cenu populácie nad n dní,

349
00:25:41,680 --> 00:25:44,080
napísať funkciu pre výpočet maximálnej zisk si môžete urobiť

350
00:25:44,080 --> 00:25:49,350
vzhľadom k tomu, si kúpiť a predať presne 1 tovar do týchto n dní. "

351
00:25:49,350 --> 00:25:51,690
V podstate, chceme lacno kúpiť, draho predať.

352
00:25:51,690 --> 00:25:58,580
A my chceme prísť na to najlepšie zisk môžeme urobiť.

353
00:25:58,580 --> 00:26:11,500
Vráťme sa späť k môjmu tipu, čo je okamžite jasné, najjednoduchšie odpoveď, ale je to pomalé?

354
00:26:11,500 --> 00:26:17,690
Áno? (Študent, nezrozumiteľné) >> Áno.

355
00:26:17,690 --> 00:26:21,470
>> Takže by ste jednoducho ísť a keď sa pozrieť na ceny akcií

356
00:26:21,470 --> 00:26:30,550
na každý bod v čase, (nezrozumiteľné).

357
00:26:30,550 --> 00:26:33,990
[Yu] Dobre, takže jej riešenie - jej návrh výpočtovej

358
00:26:33,990 --> 00:26:37,380
Najnižšia a výpočtovej najvyššej nutne pracovať

359
00:26:37,380 --> 00:26:42,470
pretože najvyššia môže dôjsť pred najnižšia.

360
00:26:42,470 --> 00:26:47,340
Takže to, čo je brutálna sila riešenie tohto problému?

361
00:26:47,340 --> 00:26:53,150
Aké sú dve veci, ktoré musím jednoznačne určiť zisk urobím? Právo.

362
00:26:53,150 --> 00:26:59,410
Brute force riešenie je - ach, áno, George návrh ich budeme potrebovať iba dva dni

363
00:26:59,410 --> 00:27:02,880
jednoznačne určiť zisk týchto dvoch dní.

364
00:27:02,880 --> 00:27:06,660
Takže počítame každú dvojicu, ako buy / sell,

365
00:27:06,660 --> 00:27:12,850
vypočítať zisk, ktorý by mohol byť negatívne alebo pozitívne alebo nula.

366
00:27:12,850 --> 00:27:18,000
Vypočítajte maximálny zisk, ktorý vyrábame po iterácia cez všetky páry dní.

367
00:27:18,000 --> 00:27:20,330
To bude naša konečná odpoveď.

368
00:27:20,330 --> 00:27:25,730
A to riešenie bude O (n ^ 2), pretože tam je n zvoliť dva páry -

369
00:27:25,730 --> 00:27:30,270
dní, ktoré si môžete vybrať medzi koncovými dní.

370
00:27:30,270 --> 00:27:32,580
Dobre, tak som to ísť cez brute force riešenie tu.

371
00:27:32,580 --> 00:27:37,420
Chystám sa povedať, že je to n log n riešenia.

372
00:27:37,420 --> 00:27:45,550
Čo algoritmus sa v súčasnej dobe vieme, že je n log n?

373
00:27:45,550 --> 00:27:50,730
Nie je to chyták.

374
00:27:50,730 --> 00:27:54,790
>> Zlúčiť radenie. Zlúčiť druh je n log n,

375
00:27:54,790 --> 00:27:57,760
a v skutočnosti, jeden zo spôsobov riešenia tohto problému je použitie

376
00:27:57,760 --> 00:28:04,400
druh zlúčenie druh myšlienky tzv všeobecne, rozdeľ a panuj.

377
00:28:04,400 --> 00:28:07,570
A myšlienka je nasledovné.

378
00:28:07,570 --> 00:28:12,400
Ak chcete vypočítať najlepšie kúpiť / predať pár v ľavej polovici.

379
00:28:12,400 --> 00:28:16,480
Nájsť najlepšie zisk môžete urobiť, len s prvou n po dobu dvoch dní.

380
00:28:16,480 --> 00:28:19,780
Potom chcete oompute najlepšie kúpiť / predať pár v pravej polovici,

381
00:28:19,780 --> 00:28:23,930
takže posledný n do dvoch dní.

382
00:28:23,930 --> 00:28:32,400
A teraz je otázkou, ako sme zlúčiť tieto riešenia dohromady?

383
00:28:32,400 --> 00:28:36,320
Áno? (Študent, nezrozumiteľným)

384
00:28:36,320 --> 00:28:49,890
Dobre >>. Dovoľte mi teda nakresliť obrázok.

385
00:28:49,890 --> 00:29:03,870
Áno? (George, nezrozumiteľným)

386
00:29:03,870 --> 00:29:06,450
Presne >>. Jiří riešenie je presne to pravé.

387
00:29:06,450 --> 00:29:10,040
Takže jeho návrh je najprv spočítať najlepšie kúpiť / predať pár,

388
00:29:10,040 --> 00:29:16,050
a ktorý sa vyskytuje v ľavej polovici, takže povedzme, že vľavo, vľavo.

389
00:29:16,050 --> 00:29:20,790
Najlepší buy / sell pár, ktorý sa vyskytuje v pravej polovici.

390
00:29:20,790 --> 00:29:25,180
Ale ak máme len porovnaní týchto dvoch čísel, nám chýba prípad

391
00:29:25,180 --> 00:29:30,460
kde sme kúpiť tu a predávať niekde v pravej polovici.

392
00:29:30,460 --> 00:29:33,810
Nakupujeme v ľavej polovici, predávať v pravej polovici.

393
00:29:33,810 --> 00:29:38,490
A najlepší spôsob, ako spočítať najlepšie kúpiť / predať pár, ktorý pokrýva obe polovice

394
00:29:38,490 --> 00:29:43,480
je pre výpočet minimálnej sem a vypočítať maximálnu tu

395
00:29:43,480 --> 00:29:45,580
a vziať si ich rozdiel.

396
00:29:45,580 --> 00:29:50,850
Takže dvoch prípadoch buy / sell pár vyskytuje iba tu,

397
00:29:50,850 --> 00:30:01,910
iba tu, alebo na oboch poloviciach je definovaná v týchto troch čísel.

398
00:30:01,910 --> 00:30:06,450
Takže náš algoritmus zlúčiť naše riešenie zase dohromady,

399
00:30:06,450 --> 00:30:08,350
chceme spočítať najlepšie kúpiť / predať pár

400
00:30:08,350 --> 00:30:13,120
kde sme kúpiť na ľavej polovici a predávať na pravej polovici.

401
00:30:13,120 --> 00:30:16,740
A najlepší spôsob, ako to urobiť, je pre výpočet najnižšie ceny v prvej polovici,

402
00:30:16,740 --> 00:30:20,360
najvyššia cena v pravej polovici, a vziať si ich rozdiel.

403
00:30:20,360 --> 00:30:25,390
Vyplývání tri zisky, tieto tri čísla, budete mať maximálne tri,

404
00:30:25,390 --> 00:30:32,720
a to je najlepší výsledok si môžete urobiť cez tieto prvé a koniec dní.

405
00:30:32,720 --> 00:30:36,940
Tu dôležité linky sú v červenej farbe.

406
00:30:36,940 --> 00:30:41,160
To je rekurzívny volanie vypočítať odpoveď v ľavej polovici.

407
00:30:41,160 --> 00:30:44,760
To je rekurzívny volanie vypočítať odpoveď v pravej polovici.

408
00:30:44,760 --> 00:30:50,720
Tieto dva cykly for počítať min a max na ľavej a pravej polovici, resp.

409
00:30:50,720 --> 00:30:54,970
Teraz som vypočítať zisk, ktorý pokrýva obe polovice,

410
00:30:54,970 --> 00:31:00,530
a konečná odpoveď je maximálna z týchto troch.

411
00:31:00,530 --> 00:31:04,120
Dobre.

412
00:31:04,120 --> 00:31:06,420
>> Takže, samozrejme, máme algoritmus, ale väčšie otázkou je,

413
00:31:06,420 --> 00:31:08,290
čo je časová zložitosť tohto?

414
00:31:08,290 --> 00:31:16,190
A dôvod, prečo som sa zmienil zlučovacie druhu je, že táto forma delenie odpoveď

415
00:31:16,190 --> 00:31:19,200
do dvoch a potom zlučovať naše riešenie opäť dohromady

416
00:31:19,200 --> 00:31:23,580
je presne forma druhu zlúčenie.

417
00:31:23,580 --> 00:31:33,360
Tak nechaj ma ísť cez trvania.

418
00:31:33,360 --> 00:31:41,340
Ak sme definovali funkciu t (n) sa rovná počtu krokov

419
00:31:41,340 --> 00:31:50,010
pre n dní,

420
00:31:50,010 --> 00:31:54,350
naše dve rekurzívne volania

421
00:31:54,350 --> 00:32:00,460
sú každý bude stáť t (n / 2),

422
00:32:00,460 --> 00:32:03,540
a tam sú dva z týchto výziev.

423
00:32:03,540 --> 00:32:10,020
Teraz musím počítať minimálne v ľavej polovici,

424
00:32:10,020 --> 00:32:17,050
ktoré môžem robiť v n / 2 času, plus maximálne v pravej polovici.

425
00:32:17,050 --> 00:32:20,820
Takže je to len n

426
00:32:20,820 --> 00:32:25,050
A potom plus nejakú konštantu práce.

427
00:32:25,050 --> 00:32:27,770
A to opakovanie rovnice

428
00:32:27,770 --> 00:32:35,560
je presne opakovanie rovnice pre radiť zlúčenie.

429
00:32:35,560 --> 00:32:39,170
A všetci vieme, že zlúčenie sort n log n čas.

430
00:32:39,170 --> 00:32:46,880
Preto je náš algoritmus tiež n log n čas.

431
00:32:46,880 --> 00:32:52,220
Znamená to iterácie zmysel?

432
00:32:52,220 --> 00:32:55,780
Len stručný súhrn toho, toto:

433
00:32:55,780 --> 00:32:59,170
T (n) je počet krokov pre výpočet maximálnej zisk

434
00:32:59,170 --> 00:33:02,750
v priebehu roka n dňoch.

435
00:33:02,750 --> 00:33:06,010
Spôsob, akým sme sa rozišli naše rekurzívne volanie

436
00:33:06,010 --> 00:33:11,980
je tým, že volá naše riešenia na prvých n / 2 dni,

437
00:33:11,980 --> 00:33:14,490
tak to je jeden telefonát,

438
00:33:14,490 --> 00:33:16,940
a potom nazývame opäť na druhej polovici.

439
00:33:16,940 --> 00:33:20,440
Tak to je dva hovory.

440
00:33:20,440 --> 00:33:25,310
A potom sme nájsť minimum na ľavej polovici, ktorú môžeme urobiť v lineárnom čase,

441
00:33:25,310 --> 00:33:29,010
nájsť maximum v pravej polovici, ktorú môžeme urobiť v lineárnom čase.

442
00:33:29,010 --> 00:33:31,570
Takže n / 2 + n / 2 je len n

443
00:33:31,570 --> 00:33:36,020
Potom máme nejaké konštantné prácu, ktorá je ako robiť aritmetiku.

444
00:33:36,020 --> 00:33:39,860
Toto opakovanie rovnica je presne opakovanie rovnice pre radiť zlúčenie.

445
00:33:39,860 --> 00:33:55,490
Preto sme zamiešať algoritmus je tiež n log n

446
00:33:55,490 --> 00:33:58,520
Tak koľko miesta sme používate?

447
00:33:58,520 --> 00:34:04,910
Vráťme sa ku kódu.

448
00:34:04,910 --> 00:34:09,420
>> Lepšie otázka je, koľko zásobník snímok máme niekedy v danom okamihu?

449
00:34:09,420 --> 00:34:11,449
Vzhľadom k tomu, že sme s použitím rekurzia,

450
00:34:11,449 --> 00:34:23,530
počet komínových snímok určuje náš využitie priestoru.

451
00:34:23,530 --> 00:34:29,440
Uvažujme n = 8.

452
00:34:29,440 --> 00:34:36,889
Hovoríme náhodné prehrávanie 8,

453
00:34:36,889 --> 00:34:41,580
ktorá sa bude volať náhodné prehrávanie z prvých štyroch,

454
00:34:41,580 --> 00:34:46,250
ktorá sa bude volať Shuffle na prvých dvoch položiek.

455
00:34:46,250 --> 00:34:51,550
Takže naše stack je - to je náš stack.

456
00:34:51,550 --> 00:34:54,980
A potom hovoríme, náhodné prehrávanie opäť na 1,

457
00:34:54,980 --> 00:34:58,070
a to je to, čo naša základňa prípad je, a tak sme sa okamžite vráti.

458
00:34:58,070 --> 00:35:04,700
Máme stále viac než toľkých zásobníka snímok?

459
00:35:04,700 --> 00:35:08,880
Nie, pretože zakaždým, keď robíme invokace,

460
00:35:08,880 --> 00:35:10,770
rekurzívne vyvolanie miešať,

461
00:35:10,770 --> 00:35:13,950
delíme naše veľkosť na polovicu.

462
00:35:13,950 --> 00:35:17,020
Takže maximálny počet komínových snímok sme niekedy v danom okamihu

463
00:35:17,020 --> 00:35:28,460
je na poradí log n stack snímok.

464
00:35:28,460 --> 00:35:42,460
Každý zásobník má rámček konštantný priestor,

465
00:35:42,460 --> 00:35:44,410
a preto Celkové množstvo miesta,

466
00:35:44,410 --> 00:35:49,240
maximálne množstvo priestoru sa niekedy používajú, je O (log n) priestor

467
00:35:49,240 --> 00:36:03,040
, Kde n je počet dní.

468
00:36:03,040 --> 00:36:07,230
>> Teraz, vždy opýtajte sa sami seba, "Môžeme to urobiť lepšie?"

469
00:36:07,230 --> 00:36:12,390
A najmä, môžeme znížiť to problém sme už vyriešený?

470
00:36:12,390 --> 00:36:20,040
Tip: sme len diskutovali dva ďalšie problémy skôr, než to, a to nebude miešať.

471
00:36:20,040 --> 00:36:26,200
Môžeme previesť tento akciový problém do maximálnej subarray problému.

472
00:36:26,200 --> 00:36:40,100
Ako to môžeme urobiť?

473
00:36:40,100 --> 00:36:42,570
Jeden z vás? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, nezrozumiteľným)

475
00:36:47,680 --> 00:36:53,860
[Yu] Presne tak.

476
00:36:53,860 --> 00:36:59,940
Takže maximálnu subarray problému,

477
00:36:59,940 --> 00:37:10,610
hľadáme pre súčet cez kontinuálne subarray.

478
00:37:10,610 --> 00:37:16,230
A Emmy návrh pre populácie problému,

479
00:37:16,230 --> 00:37:30,720
zvážiť zmeny, alebo sa delty.

480
00:37:30,720 --> 00:37:37,440
A obraz je - to je cena akcií,

481
00:37:37,440 --> 00:37:42,610
ale ak sme sa rozdiel medzi jednotlivými nasledujúci pracovný deň -

482
00:37:42,610 --> 00:37:45,200
Vidíme teda, že maximálna cena, maximálny zisk by sme mohli

483
00:37:45,200 --> 00:37:50,070
ak je nám kúpiť tu a predávať tu.

484
00:37:50,070 --> 00:37:54,240
Ale poďme sa pozrieť na priebežné - poďme sa pozrieť na subarray problém.

485
00:37:54,240 --> 00:38:02,510
Takže tu, môžeme - ísť odtiaľto až sem,

486
00:38:02,510 --> 00:38:08,410
máme pozitívnu zmenu, a potom ísť odtiaľ až sem máme negatívne zmenu.

487
00:38:08,410 --> 00:38:14,220
Ale potom, bude odtiaľ až sem máme obrovskú pozitívnu zmenu.

488
00:38:14,220 --> 00:38:20,930
A to sú zmeny, ktoré chceme sčítať, aby boli naše posledné zisk.

489
00:38:20,930 --> 00:38:25,160
Potom máme viac negatívne zmeny tu.

490
00:38:25,160 --> 00:38:29,990
Kľúčom k zníženiu našej stock problém na našej maximálnej subarray problému

491
00:38:29,990 --> 00:38:36,630
je posúdiť delty medzi dní.

492
00:38:36,630 --> 00:38:40,630
Tak sme vytvoriť nové pole s názvom delty,

493
00:38:40,630 --> 00:38:43,000
inicializovať prvú položku, ktorú chcete 0,

494
00:38:43,000 --> 00:38:46,380
a potom sa pre každú delta (i), nech je to byť rozdiel

495
00:38:46,380 --> 00:38:52,830
z mojej vstupné pole (i), a array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Potom hovoríme, naše rutinné postup pre maximálnu subarray

497
00:38:55,530 --> 00:39:01,500
absolvovaní v poli delta je.

498
00:39:01,500 --> 00:39:06,440
A pretože maximálna subarray je lineárny čas,

499
00:39:06,440 --> 00:39:09,370
a toto zníženie, tento proces vytvorenia tohto delta poľa,

500
00:39:09,370 --> 00:39:11,780
je tiež lineárna čas,

501
00:39:11,780 --> 00:39:19,060
potom konečný roztok pre zásoby je O (n) práce a O (n) práce, je stále O (n) práce.

502
00:39:19,060 --> 00:39:23,900
Takže máme lineárne časovú riešenie nášho problému.

503
00:39:23,900 --> 00:39:29,610
Má každý pochopiť túto transformáciu?

504
00:39:29,610 --> 00:39:32,140
>> Všeobecne platí, že dobrý nápad, že by ste mali mať vždy

505
00:39:32,140 --> 00:39:34,290
je pokúsiť sa znížiť nový problém, že ste vidieť.

506
00:39:34,290 --> 00:39:37,700
Ak to vyzerá známe starého problému,

507
00:39:37,700 --> 00:39:39,590
skúste znížiť ju na starý problém.

508
00:39:39,590 --> 00:39:41,950
A ak môžete používať všetky nástroje, ktoré ste použili na starý problém

509
00:39:41,950 --> 00:39:46,450
riešiť nový problém.

510
00:39:46,450 --> 00:39:49,010
Takže zabaliť, technické rozhovory sú náročné.

511
00:39:49,010 --> 00:39:52,280
Tieto problémy sú pravdepodobne niektoré z ťažkých problémov

512
00:39:52,280 --> 00:39:54,700
ktoré ste mohli vidieť v rozhovore,

513
00:39:54,700 --> 00:39:57,690
takže ak nechcete pochopiť všetky problémy, ktoré som na ktoré sa vzťahuje, je to v poriadku.

514
00:39:57,690 --> 00:40:01,080
To sú niektoré z viac náročných problémov.

515
00:40:01,080 --> 00:40:03,050
Prax, prax, prax.

516
00:40:03,050 --> 00:40:08,170
Dal som veľa problémov v letáku, tak rozhodne kontrolovať tie von.

517
00:40:08,170 --> 00:40:11,690
A veľa šťastia na vašich rozhovorov. Všetky moje zdroje sú zverejnené na tomto odkaze,

518
00:40:11,690 --> 00:40:15,220
a jeden z mojich starších priateľov ponúkol robiť falošné technické rozhovory,

519
00:40:15,220 --> 00:40:22,050
takže ak máte záujem, Will email Yao na tejto e-mailovej adrese.

520
00:40:22,050 --> 00:40:26,070
Ak máte nejaké otázky, môžete sa ma pýtate.

521
00:40:26,070 --> 00:40:28,780
Myslíte si, chlapci majú špecifické otázky týkajúce sa technických rozhovorov

522
00:40:28,780 --> 00:40:38,440
alebo nejaké problémy sme videli tak ďaleko?

523
00:40:38,440 --> 00:40:49,910
Dobre. No, veľa šťastia na vašich rozhovorov.

524
00:40:49,910 --> 00:40:52,910
[CS50.TV]