1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminář: 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šichni, já jsem Kenny. V současné době jsem junior studuje počítačové vědy.

5
00:00:12,420 --> 00:00:17,310
Jsem bývalý CS TF, a já jsem si přál, abych měl, když jsem byl underclassman,

6
00:00:17,310 --> 00:00:19,380
a to je důvod, proč dávám tohoto semináře.

7
00:00:19,380 --> 00:00:21,370
Takže doufám, že se vám bude líbit.

8
00:00:21,370 --> 00:00:23,470
Tento seminář je o technických rozhovorů,

9
00:00:23,470 --> 00:00:26,650
a všechny mé zdroje lze nalézt na tomto odkazu,

10
00:00:26,650 --> 00:00:32,350
tento odkaz tady, pár zdrojů.

11
00:00:32,350 --> 00:00:36,550
Tak jsem si udělal seznam problémů, ve skutečnosti, docela málo problémů.

12
00:00:36,550 --> 00:00:40,800
Také obecné zdroje stránky, kde můžeme najít tipy

13
00:00:40,800 --> 00:00:42,870
o tom, jak se připravit na přijímací pohovor,

14
00:00:42,870 --> 00:00:46,470
tipy na to, co byste měli udělat, při skutečném rozhovoru,

15
00:00:46,470 --> 00:00:51,910
a jak přistupovat k problémům a zdroje pro budoucí použití.

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

17
00:00:53,980 --> 00:00:58,290
A jen proto, aby předmluva tento seminář, zřeknutí,

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

19
00:01:00,690 --> 00:01:02,800
by neměl být omezen v tomto seznamu.

20
00:01:02,800 --> 00:01:04,750
To je možné pouze má být průvodce,

21
00:01:04,750 --> 00:01:08,890
a vy byste měli určitě vzít všechno, co říkám s trochou soli,

22
00:01:08,890 --> 00:01:14,620
ale také použít vše, co jsem použil, aby vám pomohou ve vaší rozhovor přípravě.

23
00:01:14,620 --> 00:01:16,400
>> Jdu do rychlosti přes několik dalších snímků

24
00:01:16,400 --> 00:01:18,650
takže se můžeme dostat do skutečných případových studií.

25
00:01:18,650 --> 00:01:23,630
Struktura rozhovoru pro nalézá softwarového inženýrství,

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

27
00:01:26,320 --> 00:01:29,810
více kol, v závislosti na společnosti.

28
00:01:29,810 --> 00:01:33,090
Často budete kódování na bílém podkladu.

29
00:01:33,090 --> 00:01:35,960
Takže bílé tabule, jako to, ale často v menším měřítku.

30
00:01:35,960 --> 00:01:38,540
Pokud máte telefonní rozhovor, budete pravděpodobně používat

31
00:01:38,540 --> 00:01:44,030
buď collabedit nebo Google Doc, aby mohli vidět ve kterém žijete, kódování

32
00:01:44,030 --> 00:01:46,500
když jste byl rozhovor po telefonu.

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
testování počítačové vědy znalosti.

35
00:01:50,620 --> 00:01:54,490
A to bude téměř určitě zahrnovat kódování.

36
00:01:54,490 --> 00:01:59,540
Typy otázek, které uvidíte, jsou obvykle datové struktury a algoritmy.

37
00:01:59,540 --> 00:02:02,210
A v tom tyto druhy problémů,

38
00:02:02,210 --> 00:02:07,830
budou se vás zeptat, líbí, co je časová a paměťová složitost, velký O?

39
00:02:07,830 --> 00:02:09,800
Často se také zeptat na vyšší úrovni otázky,

40
00:02:09,800 --> 00:02:12,530
tak, navrhování systému,

41
00:02:12,530 --> 00:02:14,770
jak byste rozvrhnout svůj kód?

42
00:02:14,770 --> 00:02:18,370
Co rozhraní, co třídy, které moduly máte ve vašem systému,

43
00:02:18,370 --> 00:02:20,900
a jak tyto ovlivňují spolu?

44
00:02:20,900 --> 00:02:26,130
Takže datové struktury a algoritmy, stejně jako projekční systémy.

45
00:02:26,130 --> 00:02:29,180
>> Některé obecné tipy, než se ponoříme do našich případových studií.

46
00:02:29,180 --> 00:02:32,300
Myslím, že nejdůležitější pravidlo je vždy myslet nahlas.

47
00:02:32,300 --> 00:02:36,980
Rozhovor by měl být vaše šance předvést své myšlení proces.

48
00:02:36,980 --> 00:02:39,820
Bod rozhovoru je pro tazatele, aby zjistily,

49
00:02:39,820 --> 00:02:42,660
jak si myslíte, a jak si projít problém.

50
00:02:42,660 --> 00:02:45,210
Nejhorší, co můžete udělat, je být zticha celém rozhovoru.

51
00:02:45,210 --> 00:02:50,090
To je prostě k ničemu.

52
00:02:50,090 --> 00:02:53,230
Pokud máte k dispozici otázku, budete také chtít, aby se ujistil, abyste pochopili otázku.

53
00:02:53,230 --> 00:02:55,350
Takže zopakovat otázku zpět vlastními slovy

54
00:02:55,350 --> 00:02:58,920
a pokus o práci důkladné několik jednoduchých testovacích případů

55
00:02:58,920 --> 00:03:01,530
aby se ujistil, abyste pochopili otázku.

56
00:03:01,530 --> 00:03:05,510
Práce přes několik testovacích případů bude také vám intuice o tom, jak tento problém vyřešit.

57
00:03:05,510 --> 00:03:11,210
Dalo by se dokonce objevit několik vzory, které vám pomohou problém vyřešit.

58
00:03:11,210 --> 00:03:14,500
Jejich velkou tip je není frustrovaný.

59
00:03:14,500 --> 00:03:17,060
Nenechte si frustrovaný.

60
00:03:17,060 --> 00:03:19,060
Rozhovory jsou náročné, ale to nejhorší věc, kterou můžete udělat,

61
00:03:19,060 --> 00:03:23,330
Kromě toho, že tichý, je třeba viditelně frustrovaný.

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

63
00:03:27,410 --> 00:03:33,960
Jedna věc, kterou - tak, mnoho lidí, když jdou do rozhovoru,

64
00:03:33,960 --> 00:03:37,150
se pokusí, aby se pokusili najít nejlepší řešení první,

65
00:03:37,150 --> 00:03:39,950
když ve skutečnosti, tam je obvykle bije do očí řešení.

66
00:03:39,950 --> 00:03:43,500
To může být pomalé, může to být neefektivní, ale měli byste jen uvést to,

67
00:03:43,500 --> 00:03:46,210
Jen tak máte výchozí bod, ze kterého se lépe pracovat.

68
00:03:46,210 --> 00:03:48,270
Také poukázal na řešení je pomalý, pokud jde o

69
00:03:48,270 --> 00:03:52,160
Velký O časová složitost nebo paměťová složitost,

70
00:03:52,160 --> 00:03:54,450
bude demonstrovat na tazatele, že jste porozuměli

71
00:03:54,450 --> 00:03:57,510
Tyto problémy při psaní kódu.

72
00:03:57,510 --> 00:04:01,440
Takže se nebojte přijít s nejjednodušším algoritmem první

73
00:04:01,440 --> 00:04:04,950
a pak pracovat lépe odtamtud.

74
00:04:04,950 --> 00:04:09,810
Jakékoliv otázky tak daleko? Dobře.

75
00:04:09,810 --> 00:04:11,650
>> Takže pojďme se ponořit do naší první problém.

76
00:04:11,650 --> 00:04:14,790
"Vzhledem k tomu, pole celých čísel n, napsat funkci, která zamíchá pole

77
00:04:14,790 --> 00:04:20,209
na místě tak, že všechny permutace celých čísel n jsou stejně pravděpodobné. "

78
00:04:20,209 --> 00:04:23,470
A předpokládáme, že máte k dispozici náhodný generátor integer

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

80
00:04:30,980 --> 00:04:32,970
Má každý pochopit tuto otázku?

81
00:04:32,970 --> 00:04:39,660
Dávám vám řadu celých čísel n, a já chci, abyste to náhodné.

82
00:04:39,660 --> 00:04:46,050
V mém adresáři, napsal jsem několik programů, kterými prokáží, co mám na mysli.

83
00:04:46,050 --> 00:04:48,910
Chystám se míchat pole 20 prvků,

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

85
00:04:52,490 --> 00:04:57,050
a já chci, abyste výstup seznam, jako je tento.

86
00:04:57,050 --> 00:05:02,890
Tak tohle je moje seřazena vstupní pole, a já chci, abyste to náhodné.

87
00:05:02,890 --> 00:05:07,070
Uděláme to znovu.

88
00:05:07,070 --> 00:05:13,780
Má každý pochopit otázku? Dobře.

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
Jaké jsou některé nápady? Můžeš to udělat jako n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Otevřete se návrhy.

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

93
00:05:37,730 --> 00:05:45,300
je první vypočítat náhodné číslo, náhodné celé číslo, v rozsahu od 0 do 20 let.

94
00:05:45,300 --> 00:05:49,840
Takže předpokládat, naše pole má délku 20.

95
00:05:49,840 --> 00:05:54,800
V našem schématu 20 prvků,

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 teď, její návrh je vytvořit 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ákladě i vrácené rand -

100
00:06:12,880 --> 00:06:17,580
takže pokud jsem byl, řekněme, 17,

101
00:06:17,580 --> 00:06:25,640
zkopírujte 17. prvek do první polohy.

102
00:06:25,640 --> 00:06:30,300
Nyní musíme odstranit - musíme přesunout všechny prvky zde

103
00:06:30,300 --> 00:06:36,920
se tak, že máme mezery na konci a žádné díry ve středu.

104
00:06:36,920 --> 00:06:39,860
A teď jsme proces opakovat.

105
00:06:39,860 --> 00:06:46,360
Nyní vybíráme nové náhodné číslo mezi 0 a 19.

106
00:06:46,360 --> 00:06:52,510
Máme novou i tady, a my jsme zkopírujte tento prvek do této polohy.

107
00:06:52,510 --> 00:07:00,960
Pak jsme posun položky za námi a my opakujeme, dokud máme plnou novou řadu.

108
00:07:00,960 --> 00:07:05,890
Co je doba běhu tohoto algoritmu?

109
00:07:05,890 --> 00:07:08,110
Dobře, pojďme zvážit dopad tohoto.

110
00:07:08,110 --> 00:07:10,380
Jsme přesouvá každý prvek.

111
00:07:10,380 --> 00:07:16,800
Když jsme odstranit tuto já, jsme se přesouvá všechny prvky po něm doleva.

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
protože to, co kdybychom odstranit první prvek?

114
00:07:26,100 --> 00:07:29,670
Takže pro každý odběr, odstraníme -

115
00:07:29,670 --> 00:07:32,170
Každý odstranění nabude O (n) operace,

116
00:07:32,170 --> 00:07:41,520
a protože jsme n stěhování, to vede k O (n ^ 2) míchat.

117
00:07:41,520 --> 00:07:49,550
Dobře. Tak dobrý začátek. Dobrý začátek.

118
00:07:49,550 --> 00:07:55,290
>> Další možností je použít známý jako shuffle Knuth,

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

120
00:07:57,540 --> 00:07:59,630
A je to vlastně lineární čas shuffle.

121
00:07:59,630 --> 00:08:02,200
A myšlenka je velmi podobná.

122
00:08:02,200 --> 00:08:05,160
Opět, máme vstupní pole,

123
00:08:05,160 --> 00:08:08,580
ale místo toho, aby pomocí dvou polí pro náš vstup / výstup,

124
00:08:08,580 --> 00:08:13,590
používáme první část pole sledovat naší zamíchány části,

125
00:08:13,590 --> 00:08:18,400
a sledujeme, a pak nechat zbytek naší pole pro unshuffled části.

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

127
00:08:24,330 --> 00:08:30,910
pole 0-20.

128
00:08:30,910 --> 00:08:36,150
Náš současný ukazatel ukazuje na první index.

129
00:08:36,150 --> 00:08:39,590
Vybíráme některé i zde

130
00:08:39,590 --> 00:08:42,740
a teď jsme vyměnit.

131
00:08:42,740 --> 00:08:47,690
Takže v případě, že byl 5 a to bylo 4,

132
00:08:47,690 --> 00:08:57,150
Výsledné pole bude mít 5 Tady a 4 zde.

133
00:08:57,150 --> 00:09:00,390
A teď jsme na vědomí, značku zde.

134
00:09:00,390 --> 00:09:05,770
Vše k levici zamíchány,

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

136
00:09:15,160 --> 00:09:17,260
A nyní můžeme proces opakovat.

137
00:09:17,260 --> 00:09:25,210
Jsme si vybrat náhodný index mezi 1 a 20 teď.

138
00:09:25,210 --> 00:09:30,650
Takže předpokládám, náš nový i zde.

139
00:09:30,650 --> 00:09:39,370
Nyní vyměníme to jsem s naší současnou novou pozici zde.

140
00:09:39,370 --> 00:09:44,790
Tak jsme se vyměňovat tam a zpět, jako tohle.

141
00:09:44,790 --> 00:09:51,630
Dovolte mi, abych vychovat kód, aby to více konkrétní.

142
00:09:51,630 --> 00:09:55,290
Začneme s naší volbou i -

143
00:09:55,290 --> 00:09:58,370
začneme s i rovnat 0, vybíráme náhodné umístění j

144
00:09:58,370 --> 00:10:02,420
v unshuffled části pole, i do n-1.

145
00:10:02,420 --> 00:10:07,280
Takže pokud jsem tady, zkuste si vybrat náhodný index mezi tady a zbytek pole,

146
00:10:07,280 --> 00:10:12,410
a vyměníme.

147
00:10:12,410 --> 00:10:17,550
To vše je kód nutné míchat vaše pole.

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

149
00:10:21,670 --> 00:10:25,530
>> No, jeden potřeboval otázka je, proč je to správné?

150
00:10:25,530 --> 00:10:28,360
Proč je každý permutací stejně pravděpodobné?

151
00:10:28,360 --> 00:10:30,410
A nebudu procházet důkaz tohoto,

152
00:10:30,410 --> 00:10:35,970
ale mnoho problémů v informatice lze dokázat indukcí.

153
00:10:35,970 --> 00:10:38,520
Jak mnozí z vás znají s indukcí?

154
00:10:38,520 --> 00:10:40,590
Dobře. Cool.

155
00:10:40,590 --> 00:10:43,610
Takže si můžete ověřit správnost tohoto algoritmu prostou indukcí,

156
00:10:43,610 --> 00:10:49,540
, kde se vaše indukční hypotéza by, předpokládejme, že

157
00:10:49,540 --> 00:10:53,290
moje náhodné vrací každý permutace stejně pravděpodobné

158
00:10:53,290 --> 00:10:56,120
až první jsem prvků.

159
00:10:56,120 --> 00:10:58,300
Nyní, zvažte i + 1.

160
00:10:58,300 --> 00:11:02,550
A mimochodem jsme se rozhodli náš index j vyměnit,

161
00:11:02,550 --> 00:11:05,230
to vede k - a pak přijít na detaily,

162
00:11:05,230 --> 00:11:07,390
alespoň plný důkaz, proč tento algoritmus vrací

163
00:11:07,390 --> 00:11:12,800
Každý permutace se stejně pravděpodobné pravděpodobností.

164
00:11:12,800 --> 00:11:15,940
>> Dobře, další problém.

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

166
00:11:19,170 --> 00:11:21,290
napsat funkci, která vypočítá maximální částku

167
00:11:21,290 --> 00:11:24,720
jakékoli continueous subarray vstupní pole. "

168
00:11:24,720 --> 00:11:28,370
Příkladem zde je, v případě, že všechna čísla jsou pozitivní,

169
00:11:28,370 --> 00:11:31,320
pak v současné době nejlepší volbou je vzít celou řadu.

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

171
00:11:34,690 --> 00:11:36,780
Pokud máte nějaké negativy tam,

172
00:11:36,780 --> 00:11:38,690
V tomto případě chceme jen první dva

173
00:11:38,690 --> 00:11:44,590
protože výběr -1 a / nebo -3 přinese náš součet dolů.

174
00:11:44,590 --> 00:11:48,120
Někdy se mohou mít začít v polovině pole.

175
00:11:48,120 --> 00:11:53,500
Někdy chceme vybrat vůbec nic, je to nejlepší, aby neměli nic.

176
00:11:53,500 --> 00:11:56,490
A někdy je lepší padnout,

177
00:11:56,490 --> 00:12:07,510
protože věc po něm je super velká. Takže nějaké nápady?

178
00:12:07,510 --> 00:12:10,970
(Student, nesrozumitelné) >> Jo.

179
00:12:10,970 --> 00:12:13,560
Předpokládejme, že neberu -1.

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

181
00:12:16,170 --> 00:12:18,630
nebo jsem jen stačí vybrat 3000000000.

182
00:12:18,630 --> 00:12:20,760
No, nejlepší volbou je vzít všechny čísla.

183
00:12:20,760 --> 00:12:24,350
Tento -1, přesto, že je negativní,

184
00:12:24,350 --> 00:12:31,340
Celá součet je lepší, než byly nemohu vzít -1.

185
00:12:31,340 --> 00:12:36,460
Takže jeden z tipů, které jsem zmínil dříve, bylo uvést jasně zřejmé

186
00:12:36,460 --> 00:12:40,540
a hrubou silou řešení jako první.

187
00:12:40,540 --> 00:12:44,340
Co je brutální síla řešení tohoto problému? Jo?

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

189
00:12:46,890 --> 00:12:52,600
by bylo přidat až všechny možné kombinace (nesrozumitelný).

190
00:12:52,600 --> 00:12:58,250
[Yu] Dobře. Takže Jane nápad je vzít všechny možné -

191
00:12:58,250 --> 00:13:01,470
Jsem parafrázovat - je vzít všechny možné kontinuální subarray,

192
00:13:01,470 --> 00:13:07,840
vypočítat její součet, a pak mít maximálně všech možných průběžných subarrays.

193
00:13:07,840 --> 00:13:13,310
Co jednoznačně identifikuje subarray v mém vstupní pole?

194
00:13:13,310 --> 00:13:17,380
Stejně jako to, co dvě věci potřebuji? Jo?

195
00:13:17,380 --> 00:13:19,970
(Student, nesrozumitelné) >> Právo.

196
00:13:19,970 --> 00:13:22,130
Dolní mez indexu a horní hranici indexu

197
00:13:22,130 --> 00:13:28,300
jednoznačně určuje průběžné subarray.

198
00:13:28,300 --> 00:13:31,400
[Studentka] Už jsme odhad, že je to řada unikátních čísel?

199
00:13:31,400 --> 00:13:34,280
[Yu] No tak její otázku je, jsme za předpokladu, že naší nabídku -

200
00:13:34,280 --> 00:13:39,000
je naše pole všechny jedinečné čísla, a odpověď je ne.

201
00:13:39,000 --> 00:13:43,390
>> Pokud budeme používat náš silovou řešení, pak na začátek / konec indexů

202
00:13:43,390 --> 00:13:47,200
jednoznačně určuje naše kontinuální subarray.

203
00:13:47,200 --> 00:13:51,680
Takže když jsme iteraci pro všechny možný start položky,

204
00:13:51,680 --> 00:13:58,320
a pro všechny koncové položky> nebo = začít, a <n,

205
00:13:58,320 --> 00:14:05,570
můžete spočítat součet, a pak jsme se na maximální částku jsme viděli doposud.

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

207
00:14:07,880 --> 00:14:12,230
Co je to velký O tohoto roztoku?

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

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

210
00:14:18,860 --> 00:14:25,250
Všimněte si, že jsme iteraci od 0 do n,

211
00:14:25,250 --> 00:14:27,520
tak to je jeden pro smyčce.

212
00:14:27,520 --> 00:14:35,120
Jsme iteraci opět od téměř počátku až do konce, další pro smyčce.

213
00:14:35,120 --> 00:14:37,640
A nyní, v to, že musíme sečíst všechny položky,

214
00:14:37,640 --> 00:14:43,810
tak to je jiná pro smyčce. Takže máme tři vnořené cykly for, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Dobře. To platí jako výchozí bod.

216
00:14:46,560 --> 00:14:53,180
Naše řešení není o nic horší než n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Má každý pochopit silovou řešení?

218
00:14:55,480 --> 00:14:59,950
>> Dobře. Lepším řešením je použití představu názvem dynamické programování.

219
00:14:59,950 --> 00:15:03,040
Jestliže jste užil CS124, což je Algoritmy a datové struktury,

220
00:15:03,040 --> 00:15:05,680
stanete se velmi dobře obeznámeni s touto technikou.

221
00:15:05,680 --> 00:15:12,190
A myšlenka je, pokusit se vybudovat řešení menších problémů jako první.

222
00:15:12,190 --> 00:15:17,990
Co tím chci říct je to, v současné době se starat o dvě věci: začátek a konec.

223
00:15:17,990 --> 00:15:29,340
A to je nepříjemné. Co kdybychom se mohli zbavit jednoho z těchto parametrů?

224
00:15:29,340 --> 00:15:32,650
Jeden nápad je - Jsme stejně náš původní problém,

225
00:15:32,650 --> 00:15:37,470
najít maximální součet všech subarray v rozmezí [O, n-1].

226
00:15:37,470 --> 00:15:47,400
A teď máme novou podproblém, kde víme, v našem současném indexu i,

227
00:15:47,400 --> 00:15:52,520
víme, že musíme učinit závěr, že. Naše subarray musí skončit v aktuálním indexu.

228
00:15:52,520 --> 00:15:57,640
Takže zbývající problém je, měli kde jsme začali naši subarray?

229
00:15:57,640 --> 00:16:05,160
Má to smysl? Dobře.

230
00:16:05,160 --> 00:16:12,030
Takže jsem Kódujete nahoru, a pojďme se podívat na to, co to znamená.

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

232
00:16:16,230 --> 00:16:19,470
a to trvá několik položek,

233
00:16:19,470 --> 00:16:25,550
a vrátí maximální subarray částku v mém zamíchány seznamu.

234
00:16:25,550 --> 00:16:29,920
Takže v tomto případě, naše maximální subarray je 3.

235
00:16:29,920 --> 00:16:34,850
A to pořízena jen pomocí 2 a 1.

236
00:16:34,850 --> 00:16:38,050
Pojďme znovu spusťte. Je to také 3.

237
00:16:38,050 --> 00:16:40,950
Ale tentokrát, všimněte si, jak jsme se dostali 3.

238
00:16:40,950 --> 00:16:46,690
Vzali jsme - jsme prostě bralo 3 sám

239
00:16:46,690 --> 00:16:49,980
protože je obklopen negativů na obou stranách,

240
00:16:49,980 --> 00:16:55,080
která přinese určitou částku <3.

241
00:16:55,080 --> 00:16:57,820
Pojďme běží na 10 položek.

242
00:16:57,820 --> 00:17:03,200
Tentokrát je to 7, vezmeme vedoucí 3 a 4.

243
00:17:03,200 --> 00:17:09,450
Tento čas je 8, a získáme že tím, že se 1, 4 a 3.

244
00:17:09,450 --> 00:17:16,310
Takže vám intuice o tom, jak můžeme vyřešit tento transformovaný problém,

245
00:17:16,310 --> 00:17:18,890
Pojďme se podívat na tento subarray.

246
00:17:18,890 --> 00:17:23,460
Jsme stejně tento vstupní pole, a víme, že odpověď je 8.

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

248
00:17:26,359 --> 00:17:29,090
Ale pojďme se podívat na to, jak jsme se vlastně dostali tuto odpověď.

249
00:17:29,090 --> 00:17:34,160
Pojďme se podívat na maximální subarray, která skončila na každý z těchto indexů.

250
00:17:34,160 --> 00:17:40,780
Jaký je maximální subarray, který má skončit na prvním místě?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. >> Zero. Jen neberte -5.

252
00:17:46,310 --> 00:17:50,210
Tady to bude 0 stejně. Jo?

253
00:17:50,210 --> 00:17:56,470
(Student, nesrozumitelným)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, omlouvám se, 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
Dobře. Takže -4, jaký je maximální subarray ukončit tuto pozici

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
Teď, musím končit v místě, 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 vědomím, že to jsou mé záznamy

262
00:18:43,480 --> 00:18:48,130
pro transformované problém, kde musím skončit v každém z těchto indexů,

263
00:18:48,130 --> 00:18:51,410
pak můj poslední odpověď je jen, vzít zatáčku přes,

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

265
00:18:53,580 --> 00:18:55,620
Takže v tomto případě je to 8.

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

267
00:19:00,010 --> 00:19:04,970
a začal někde před ním.

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

269
00:19:09,630 --> 00:19:22,160
>> Dobře. Dobře, pojďme zjistit, opakování pro tento.

270
00:19:22,160 --> 00:19:27,990
Podívejme se jen prvních pár položek.

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

272
00:19:35,930 --> 00:19:39,790
A pak tam byl -2 zde, a že přinesla to až do 6.

273
00:19:39,790 --> 00:19:50,800
Takže když ti budu říkat položka na pozici i podproblém (i),

274
00:19:50,800 --> 00:19:54,910
Jak mohu použít odpověď na předchozí podproblém

275
00:19:54,910 --> 00:19:59,360
odpověď na tuto podproblém?

276
00:19:59,360 --> 00:20:04,550
Když se podívám na, řekněme, tato položka.

277
00:20:04,550 --> 00:20:09,190
Jak mohu spočítat odpověď 6 při pohledu na

278
00:20:09,190 --> 00:20:18,780
Kombinace tohoto pole a odpovědi na předchozí subproblems v tomto poli? Ano?

279
00:20:18,780 --> 00:20:22,800
[Studentka] Zde se pole částek

280
00:20:22,800 --> 00:20:25,430
v poloze, přímo před ní, takže 8,

281
00:20:25,430 --> 00:20:32,170
a pak přidáte aktuální podproblém.

282
00:20:32,170 --> 00:20:36,460
[Yu] Takže její návrh je podívat se na těchto dvou čí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 tato 8 odkazuje na odpovědi pro podproblém (i - 1).

285
00:20:50,130 --> 00:20:57,300
A říkejme můj vstupní pole A.

286
00:20:57,300 --> 00:21:01,470
Za účelem nalezení maximální subarray, která končí v poloze I,

287
00:21:01,470 --> 00:21:03,980
Mám dvě možnosti: mohu buď pokračovat v subarray

288
00:21:03,980 --> 00:21:09,790
, která skončila na předchozí index, nebo začít nové pole.

289
00:21:09,790 --> 00:21:14,190
Pokud bych měl pokračovat v subarray, která začala v předchozím indexu,

290
00:21:14,190 --> 00:21:19,260
pak maximální částka mohu dosáhnout, je odpověď na předchozí podproblém

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

292
00:21:24,120 --> 00:21:27,550
Ale také mám na výběr spuštění nové subarray,

293
00:21:27,550 --> 00:21:30,830
v takovém případě je součet je 0.

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

295
00:21:42,860 --> 00:21:46,150
Znamená to opakování smysl?

296
00:21:46,150 --> 00:21:50,840
Naše opakování, jak jsme právě zjistili, je podproblém i

297
00:21:50,840 --> 00:21:54,740
se rovná maximu předchozího podproblém navíc mé současné pole vstupu,

298
00:21:54,740 --> 00:22:01,490
což znamená, že i nadále předchozí subarray,

299
00:22:01,490 --> 00:22:07,250
nebo 0, začít nový subarray na mém současném indexu.

300
00:22:07,250 --> 00:22:10,060
A jakmile jsme vybudovali tuto tabulku řešení, pak je naše konečná odpověď,

301
00:22:10,060 --> 00:22:13,950
prostě lineární tažení přes podproblém pole

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

303
00:22:19,890 --> 00:22:23,330
To je přesně realizace toho, co jsem právě řekl.

304
00:22:23,330 --> 00:22:27,320
Tak jsme vytvořit novou podproblém pole, podproblémy.

305
00:22:27,320 --> 00:22:32,330
První položka je buď 0 nebo první vstup, maximálně těch dvou.

306
00:22:32,330 --> 00:22:35,670
A pro zbytek subproblems

307
00:22:35,670 --> 00:22:39,810
používáme přesný opakování jsme právě objevili.

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

309
00:22:49,960 --> 00:22:54,130
>> Tak kolik místa jsme pomocí tohoto algoritmu?

310
00:22:54,130 --> 00:23:01,470
Pokud jste jen vzít CS50, pak jste možná ještě projednány prostor velmi mnoho.

311
00:23:01,470 --> 00:23:07,750
No, jedna věc k poznámce je, že jsem zavolal malloc zde velikosti n.

312
00:23:07,750 --> 00:23:13,590
Co to naznačují vás?

313
00:23:13,590 --> 00:23:17,450
Tento algoritmus používá lineární prostor.

314
00:23:17,450 --> 00:23:21,030
Můžeme to udělat lépe?

315
00:23:21,030 --> 00:23:30,780
Je tam něco, co zjistíte, že je zbytečné počítat konečnou odpověď?

316
00:23:30,780 --> 00:23:33,290
Myslím, že lepší otázka je, jaké informace

317
00:23:33,290 --> 00:23:40,680
my není třeba provádět celou cestu až do konce?

318
00:23:40,680 --> 00:23:44,280
Teď, když se podíváme na tyto dva řádky,

319
00:23:44,280 --> 00:23:47,720
nás však zajímá pouze o předchozí podproblém,

320
00:23:47,720 --> 00:23:50,910
a my jsme jen o maximálně jsme kdy viděli doposud.

321
00:23:50,910 --> 00:23:53,610
Pro výpočet naší konečnou odpověď, nepotřebujeme celého pole.

322
00:23:53,610 --> 00:23:57,450
Budeme potřebovat pouze poslední číslo, poslední dvě čísla.

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

324
00:24:02,630 --> 00:24:07,380
Takže, ve skutečnosti, můžeme zničit tyto smyčky spolu

325
00:24:07,380 --> 00:24:10,460
a jít od lineárního prostoru na konstantní prostoru.

326
00:24:10,460 --> 00:24:15,830
Aktuální částka tak daleko, tady, nahradí roli podproblém, naše podproblém pole.

327
00:24:15,830 --> 00:24:20,020
Takže současná suma, tak daleko, je odpověď na předchozí podproblém.

328
00:24:20,020 --> 00:24:23,450
A tato částka, tak daleko, zabere místo našeho max..

329
00:24:23,450 --> 00:24:28,100
Počítáme maximální, jak jsme jít dál.

330
00:24:28,100 --> 00:24:30,890
A tak jdeme od lineárního prostoru do konstantní prostoru,

331
00:24:30,890 --> 00:24:36,650
a také mají lineární řešení naší subarray problému.

332
00:24:36,650 --> 00:24:40,740
>> Tyto druhy otázek získáte během rozhovoru.

333
00:24:40,740 --> 00:24:44,450
Jaká je časová složitost, co je prostorová složitost?

334
00:24:44,450 --> 00:24:50,600
Můžeš to udělat lépe? Jsou tam věci, které jsou zbytečné, aby kolem?

335
00:24:50,600 --> 00:24:55,270
Udělal jsem to zdůraznit analýzy, které byste měli podniknout na vlastní pěst

336
00:24:55,270 --> 00:24:57,400
jak budete procházet těmito problémy.

337
00:24:57,400 --> 00:25:01,710
Vždy se ptát sami sebe: "Můžu udělat lépe?"

338
00:25:01,710 --> 00:25:07,800
Ve skutečnosti, můžeme dělat lépe, než tohle?

339
00:25:07,800 --> 00:25:10,730
Druh chyták. Nemůžete, protože je třeba, aby

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

341
00:25:13,590 --> 00:25:15,570
Takže skutečnost, že je třeba alespoň číst vstup problému

342
00:25:15,570 --> 00:25:19,580
znamená, že nemůžete udělat lépe, než lineárním čase,

343
00:25:19,580 --> 00:25:22,870
a můžete to udělat lépe než neustálé prostoru.

344
00:25:22,870 --> 00:25:27,060
Takže je to, ve skutečnosti, že nejlepší řešení tohoto problému.

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

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

347
00:25:35,190 --> 00:25:38,350
"Vzhledem k tomu, pole celých čísel n, pozitivní, nula, nebo negativní,

348
00:25:38,350 --> 00:25:41,680
které představují cenu populace nad n dnů,

349
00:25:41,680 --> 00:25:44,080
napsat funkci pro výpočet maximální zisk si můžete udělat

350
00:25:44,080 --> 00:25:49,350
vzhledem k tomu, si koupit a prodat přesně 1 zboží do těchto n dnů. "

351
00:25:49,350 --> 00:25:51,690
V podstatě, chceme levně koupit, draze prodat.

352
00:25:51,690 --> 00:25:58,580
A my chceme přijít na to nejlepší zisk můžeme udělat.

353
00:25:58,580 --> 00:26:11,500
Vraťme se zpět k mému tipu, co je okamžitě jasné, nejjednodušší odpověď, ale je to pomalé?

354
00:26:11,500 --> 00:26:17,690
Ano? (Student, nesrozumitelné) >> Ano.

355
00:26:17,690 --> 00:26:21,470
>> Takže byste prostě jít a když se podívat na ceny akcií

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

357
00:26:30,550 --> 00:26:33,990
[Yu] Dobře, takže její řešení - její návrh výpočetní

358
00:26:33,990 --> 00:26:37,380
Nejnižší a výpočetní nejvyšší nutně pracovat

359
00:26:37,380 --> 00:26:42,470
protože nejvyšší může dojít před nejnižší.

360
00:26:42,470 --> 00:26:47,340
Takže to, co je brutální síla řešení tohoto problému?

361
00:26:47,340 --> 00:26:53,150
Jaké jsou dvě věci, které musím jednoznačně určit zisk udělám? Právo.

362
00:26:53,150 --> 00:26:59,410
Brute force řešení je - ach, ano, George návrh je budeme potřebovat pouze dva dny

363
00:26:59,410 --> 00:27:02,880
jednoznačně určit zisk těchto dvou dnů.

364
00:27:02,880 --> 00:27:06,660
Takže počítáme každou dvojici, jako buy / sell,

365
00:27:06,660 --> 00:27:12,850
vypočítat zisk, který by mohl být negativní nebo pozitivní nebo nula.

366
00:27:12,850 --> 00:27:18,000
Vypočítejte maximální zisk, který vyrábíme po iterace přes všechny páry dnů.

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

368
00:27:20,330 --> 00:27:25,730
A to řešení bude O (n ^ 2), protože tam je n zvolit dva páry -

369
00:27:25,730 --> 00:27:30,270
dnů, které si můžete vybrat mezi koncovými dnů.

370
00:27:30,270 --> 00:27:32,580
Dobře, tak jsem to jít přes brute force řešení zde.

371
00:27:32,580 --> 00:27:37,420
Chystám se říct, že je to n log n řešení.

372
00:27:37,420 --> 00:27:45,550
Co algoritmus se v současné době víme, že je n log n?

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

374
00:27:50,730 --> 00:27:54,790
>> Sloučit řazení. Sloučit druh je n log n,

375
00:27:54,790 --> 00:27:57,760
a ve skutečnosti, jeden ze způsobů řešení tohoto problému je použití

376
00:27:57,760 --> 00:28:04,400
druh sloučení druh myšlenky tzv. obecně, rozděl a panuj.

377
00:28:04,400 --> 00:28:07,570
A tato myšlenka je následující.

378
00:28:07,570 --> 00:28:12,400
Chcete-li vypočítat nejlepší koupit / prodat pár v levé polovině.

379
00:28:12,400 --> 00:28:16,480
Najít ty nejlepší zisk můžete udělat, jen s první n po dobu dvou dnů.

380
00:28:16,480 --> 00:28:19,780
Pak chcete oompute nejlepší koupit / prodat pár v pravé polovině,

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

382
00:28:23,930 --> 00:28:32,400
A teď je otázkou, jak jsme sloučit tato řešení dohromady?

383
00:28:32,400 --> 00:28:36,320
Ano? (Student, nesrozumitelným)

384
00:28:36,320 --> 00:28:49,890
Dobře >>. Dovolte mi tedy nakreslit obrázek.

385
00:28:49,890 --> 00:29:03,870
Ano? (George, nesrozumitelným)

386
00:29:03,870 --> 00:29:06,450
Přesně >>. Jiří řešení je přesně to pravé.

387
00:29:06,450 --> 00:29:10,040
Takže jeho návrh je nejprve spočítat nejlepší koupit / prodat pár,

388
00:29:10,040 --> 00:29:16,050
a který se vyskytuje v levé polovině, takže řekněme, že vlevo, vlevo.

389
00:29:16,050 --> 00:29:20,790
Nejlepší buy / sell pár, který se vyskytuje v pravé polovině.

390
00:29:20,790 --> 00:29:25,180
Ale pokud máme jen srovnání těchto dvou čísel, nám chybí případ

391
00:29:25,180 --> 00:29:30,460
kde jsme koupit zde a prodávat někde v pravé polovině.

392
00:29:30,460 --> 00:29:33,810
Nakupujeme v levé polovině, prodávat v pravé polovině.

393
00:29:33,810 --> 00:29:38,490
A nejlepší způsob, jak spočítat nejlepší koupit / prodat pár, který pokrývá obě poloviny

394
00:29:38,490 --> 00:29:43,480
je pro výpočet minimální sem a vypočítat maximální zde

395
00:29:43,480 --> 00:29:45,580
a vzít si jejich rozdíl.

396
00:29:45,580 --> 00:29:50,850
Takže dvou případech buy / sell pár vyskytuje pouze zde,

397
00:29:50,850 --> 00:30:01,910
pouze zde, nebo na obou polovinách je definována v těchto třech čísel.

398
00:30:01,910 --> 00:30:06,450
Takže náš algoritmus sloučit naše řešení zase dohromady,

399
00:30:06,450 --> 00:30:08,350
chceme spočítat nejlepší koupit / prodat pár

400
00:30:08,350 --> 00:30:13,120
kde jsme se koupit na levé polovině a prodávat na pravé polovině.

401
00:30:13,120 --> 00:30:16,740
A nejlepší způsob, jak to udělat, je pro výpočet nejnižší ceny v první polovině,

402
00:30:16,740 --> 00:30:20,360
nejvyšší cena v pravé polovině, a vzít si jejich rozdíl.

403
00:30:20,360 --> 00:30:25,390
Vyplývání tři zisky, tyto tři čísla, budete mít maximálně tři,

404
00:30:25,390 --> 00:30:32,720
a to je nejlepší výsledek si můžete udělat přes tyto první a konec dnů.

405
00:30:32,720 --> 00:30:36,940
Zde důležité linky jsou v červené barvě.

406
00:30:36,940 --> 00:30:41,160
To je rekurzivní volání pro výpočet odpověď v levé polovině.

407
00:30:41,160 --> 00:30:44,760
To je rekurzivní volání vypočítat odpověď v pravé polovině.

408
00:30:44,760 --> 00:30:50,720
Tyto dva cykly for počítat min a max na levé a pravé polovině, resp.

409
00:30:50,720 --> 00:30:54,970
Teď jsem vypočítat zisk, který pokrývá obě poloviny,

410
00:30:54,970 --> 00:31:00,530
a konečná odpověď je maximální z těchto tří.

411
00:31:00,530 --> 00:31:04,120
Dobře.

412
00:31:04,120 --> 00:31:06,420
>> Takže, samozřejmě, máme algoritmus, ale větší otázkou je,

413
00:31:06,420 --> 00:31:08,290
co je časová složitost tohoto?

414
00:31:08,290 --> 00:31:16,190
A důvod, proč jsem se zmínil slučovací druhu je, že tato forma dělení odpověď

415
00:31:16,190 --> 00:31:19,200
do dvou a pak slučovat naše řešení opět dohromady

416
00:31:19,200 --> 00:31:23,580
je přesně forma druhu sloučení.

417
00:31:23,580 --> 00:31:33,360
Tak nech mě jít přes trvání.

418
00:31:33,360 --> 00:31:41,340
Pokud jsme definovali funkci t (n) se rovná počtu kroků

419
00:31:41,340 --> 00:31:50,010
pro n dnů,

420
00:31:50,010 --> 00:31:54,350
naše dvě rekurzivní volání

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

422
00:32:00,460 --> 00:32:03,540
a tam jsou dva z těchto výzev.

423
00:32:03,540 --> 00:32:10,020
Teď musím počítat minimálně v levé polovině,

424
00:32:10,020 --> 00:32:17,050
které mohu dělat v n / 2 času, plus maximálně v pravé polovině.

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

426
00:32:20,820 --> 00:32:25,050
A pak plus nějakou konstantu práce.

427
00:32:25,050 --> 00:32:27,770
A to opakování rovnice

428
00:32:27,770 --> 00:32:35,560
je přesně opakování rovnice pro řadit sloučení.

429
00:32:35,560 --> 00:32:39,170
A všichni víme, že sloučení sort n log n čas.

430
00:32:39,170 --> 00:32:46,880
Proto je náš algoritmus také n log n čas.

431
00:32:46,880 --> 00:32:52,220
Znamená to iterace smysl?

432
00:32:52,220 --> 00:32:55,780
Jen stručný souhrn toho, toto:

433
00:32:55,780 --> 00:32:59,170
T (n) je počet kroků pro výpočet maximální zisk

434
00:32:59,170 --> 00:33:02,750
v průběhu roku n dnech.

435
00:33:02,750 --> 00:33:06,010
Způsob, jakým jsme se rozešli naše rekurzivní volání

436
00:33:06,010 --> 00:33:11,980
je tím, že volá naše řešení na prvních n / 2 dny,

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 pak nazýváme opět na druhé polovině.

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

440
00:33:20,440 --> 00:33:25,310
A pak jsme najít minimum na levé polovině, kterou můžeme udělat v lineárním čase,

441
00:33:25,310 --> 00:33:29,010
najít maximum v pravé polovině, kterou můžeme udělat v lineárním čase.

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

443
00:33:31,570 --> 00:33:36,020
Pak máme nějaké konstantní práci, která je jako dělat aritmetiku.

444
00:33:36,020 --> 00:33:39,860
Toto opakování rovnice je přesně opakování rovnice pro řadit sloučení.

445
00:33:39,860 --> 00:33:55,490
Proto jsme zamíchat algoritmus je také n log n.

446
00:33:55,490 --> 00:33:58,520
Tak kolik místa jsme používáte?

447
00:33:58,520 --> 00:34:04,910
Vraťme se ke kódu.

448
00:34:04,910 --> 00:34:09,420
>> Lepší otázka je, kolik zásobník snímků máme někdy v daném okamžiku?

449
00:34:09,420 --> 00:34:11,449
Vzhledem k tomu, že jsme s použitím rekurze,

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

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

452
00:34:29,440 --> 00:34:36,889
Říkáme náhodné přehrávání 8,

453
00:34:36,889 --> 00:34:41,580
která se bude volat náhodné přehrávání z prvních čtyř,

454
00:34:41,580 --> 00:34:46,250
která se bude volat Shuffle na prvních dvou položek.

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 pak říkáme, náhodné přehrávání opět na 1,

457
00:34:54,980 --> 00:34:58,070
a to je to, co naše základna případ je, a tak jsme se okamžitě vrátí.

458
00:34:58,070 --> 00:35:04,700
Máme stále více než tolika zásobníku snímků?

459
00:35:04,700 --> 00:35:08,880
Ne, protože pokaždé, když děláme invokace,

460
00:35:08,880 --> 00:35:10,770
rekurzivní vyvolání míchat,

461
00:35:10,770 --> 00:35:13,950
dělíme naše velikost na polovinu.

462
00:35:13,950 --> 00:35:17,020
Takže maximální počet komínových snímků jsme někdy v daném okamžiku

463
00:35:17,020 --> 00:35:28,460
je na pořadí log n stack snímků.

464
00:35:28,460 --> 00:35:42,460
Každý zásobník má rámeček konstantní prostor,

465
00:35:42,460 --> 00:35:44,410
a proto Celkové množství místa,

466
00:35:44,410 --> 00:35:49,240
maximální množství prostoru se někdy používají, je O (log n) prostor

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

468
00:36:03,040 --> 00:36:07,230
>> Nyní, vždy zeptejte se sami sebe, "Můžeme to udělat lépe?"

469
00:36:07,230 --> 00:36:12,390
A zejména, můžeme snížit to problém jsme již vyřešen?

470
00:36:12,390 --> 00:36:20,040
Tip: jsme jen diskutovali dva další problémy dříve, než to, a to nebude míchat.

471
00:36:20,040 --> 00:36:26,200
Můžeme převést tento akciový problém do maximální subarray problému.

472
00:36:26,200 --> 00:36:40,100
Jak to můžeme udělat?

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

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

475
00:36:47,680 --> 00:36:53,860
[Yu] Přesně tak.

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

477
00:36:59,940 --> 00:37:10,610
hledáme pro součet přes kontinuální subarray.

478
00:37:10,610 --> 00:37:16,230
A Emmy návrh pro populace problému,

479
00:37:16,230 --> 00:37:30,720
zvážit změny, nebo 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 pokud jsme se rozdíl mezi jednotlivými následující pracovní den -

482
00:37:42,610 --> 00:37:45,200
Vidíme tedy, že maximální cena, maximální zisk bychom mohli

483
00:37:45,200 --> 00:37:50,070
je-li nám koupit zde a prodávat zde.

484
00:37:50,070 --> 00:37:54,240
Ale pojďme se podívat na průběžné - pojďme se podívat na subarray problém.

485
00:37:54,240 --> 00:38:02,510
Takže tady, můžeme - jít odsud až sem,

486
00:38:02,510 --> 00:38:08,410
máme pozitivní změnu, a pak jít odtud až sem máme negativní změnu.

487
00:38:08,410 --> 00:38:14,220
Ale pak, bude odtud až sem máme obrovskou pozitivní změnu.

488
00:38:14,220 --> 00:38:20,930
A to jsou změny, které chceme sečíst, aby byly naše poslední zisk.

489
00:38:20,930 --> 00:38:25,160
Pak máme více negativní změny zde.

490
00:38:25,160 --> 00:38:29,990
Klíčem ke snížení naší stock problém na naší maximální subarray problému

491
00:38:29,990 --> 00:38:36,630
je posoudit delty mezi dní.

492
00:38:36,630 --> 00:38:40,630
Tak jsme vytvořit nové pole s názvem delty,

493
00:38:40,630 --> 00:38:43,000
inicializovat první položku, kterou chcete 0,

494
00:38:43,000 --> 00:38:46,380
a pak se pro každou delta (i), ať je to být rozdíl

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

496
00:38:52,830 --> 00:38:55,530
Pak říkáme, naše rutinní postup pro maximální subarray

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

498
00:39:01,500 --> 00:39:06,440
A protože maximální subarray je lineární čas,

499
00:39:06,440 --> 00:39:09,370
a toto snížení, tento proces vytvoření tohoto delta pole,

500
00:39:09,370 --> 00:39:11,780
je také lineární čas,

501
00:39:11,780 --> 00:39:19,060
pak konečný roztok pro 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ární časovou řešení našeho problému.

503
00:39:23,900 --> 00:39:29,610
Má každý pochopit tuto transformaci?

504
00:39:29,610 --> 00:39:32,140
>> Obecně platí, že dobrý nápad, že byste měli mít vždy

505
00:39:32,140 --> 00:39:34,290
je pokusit se snížit nový problém, že jste vidět.

506
00:39:34,290 --> 00:39:37,700
Pokud to vypadá známé starého problému,

507
00:39:37,700 --> 00:39:39,590
zkuste snížit ji na starý problém.

508
00:39:39,590 --> 00:39:41,950
A pokud můžete používat všechny nástroje, které jste použili na starý problém

509
00:39:41,950 --> 00:39:46,450
řešit nový problém.

510
00:39:46,450 --> 00:39:49,010
Takže zabalit, technické rozhovory jsou náročné.

511
00:39:49,010 --> 00:39:52,280
Tyto problémy jsou pravděpodobně některé z obtížných problémů

512
00:39:52,280 --> 00:39:54,700
které jste mohli vidět v rozhovoru,

513
00:39:54,700 --> 00:39:57,690
takže pokud nechcete pochopit všechny problémy, které jsem na něž se vztahuje, je to v pořádku.

514
00:39:57,690 --> 00:40:01,080
To jsou některé z více náročných problémů.

515
00:40:01,080 --> 00:40:03,050
Praxe, praxe, praxe.

516
00:40:03,050 --> 00:40:08,170
Dal jsem spoustu problémů v letáku, tak rozhodně kontrolovat ty ven.

517
00:40:08,170 --> 00:40:11,690
A hodně štěstí na vašich rozhovorů. Všechny mé zdroje jsou zveřejněny na tomto odkazu,

518
00:40:11,690 --> 00:40:15,220
a jeden z mých starších přátel nabídl dělat falešné technické rozhovory,

519
00:40:15,220 --> 00:40:22,050
takže pokud máte zájem, Will email Yao na této e-mailové adrese.

520
00:40:22,050 --> 00:40:26,070
Pokud máte nějaké otázky, můžete se mě ptáte.

521
00:40:26,070 --> 00:40:28,780
Myslíte si, kluci mají specifické otázky týkající se technických rozhovorů

522
00:40:28,780 --> 00:40:38,440
nebo nějaké problémy jsme viděli tak daleko?

523
00:40:38,440 --> 00:40:49,910
Dobře. No, hodně štěstí na vašich rozhovorů.

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