1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Szeminárium: Technical Interjúk]

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

3
00:00:04,630 --> 00:00:08,910
[Ez a CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Szia mindenki, én vagyok Kenny. Én jelenleg a junior tanul számítástechnika.

5
00:00:12,420 --> 00:00:17,310
Én egy korábbi CS TF, és azt kívánom, bárcsak volna ezt, amikor voltam underclassman,

6
00:00:17,310 --> 00:00:19,380
és ezért adok ezen a szemináriumon.

7
00:00:19,380 --> 00:00:21,370
Szóval remélem, élvezni.

8
00:00:21,370 --> 00:00:23,470
A szeminárium a technikai interjúk,

9
00:00:23,470 --> 00:00:26,650
és minden erőforrás találhatók meg ezt a linket,

10
00:00:26,650 --> 00:00:32,350
meg ezt a linket itt, egy pár a források.

11
00:00:32,350 --> 00:00:36,550
Úgyhogy csináltam egy listát azokról a problémákról, valóban, jó néhány problémát.

12
00:00:36,550 --> 00:00:40,800
Szintén általános erőforrások oldalt, ahol találunk tippeket

13
00:00:40,800 --> 00:00:42,870
, hogyan kell felkészülni egy interjúra,

14
00:00:42,870 --> 00:00:46,470
tippeket, mit kell tennie során tényleges interjú

15
00:00:46,470 --> 00:00:51,910
valamint azt, hogyan kell megközelíteni problémák és források a jövőben is.

16
00:00:51,910 --> 00:00:53,980
Ez mind online.

17
00:00:53,980 --> 00:00:58,290
És csak bevezetést a szeminárium, a nyilatkozat,

18
00:00:58,290 --> 00:01:00,690
így nem szabad - az interjú elkészítése

19
00:01:00,690 --> 00:01:02,800
nem kell korlátozni ezt a listát.

20
00:01:02,800 --> 00:01:04,750
Ez csak azt jelenti, hogy egy útikönyv,

21
00:01:04,750 --> 00:01:08,890
és akkor feltétlenül tegyen mindent, amit mondok egy csipet só,

22
00:01:08,890 --> 00:01:14,620
hanem használja mindent, amit alkalmaznak, hogy segítsen Önnek az interjú előkészítése.

23
00:01:14,620 --> 00:01:16,400
>> Megyek, hogy gyorsítsa a következő néhány diák

24
00:01:16,400 --> 00:01:18,650
így juthatunk a valós esettanulmányok.

25
00:01:18,650 --> 00:01:23,630
A szerkezet egy interjút a szoftverfejlesztés pozícióját,

26
00:01:23,630 --> 00:01:26,320
Jellemzően 30 és 45 perc,

27
00:01:26,320 --> 00:01:29,810
Több fordulóban, attól függően, hogy a vállalat számára.

28
00:01:29,810 --> 00:01:33,090
Gyakran leszel kódoló egy fehér tábla.

29
00:01:33,090 --> 00:01:35,960
Tehát egy fehér tábla, mint ez, de gyakran kisebb léptékben.

30
00:01:35,960 --> 00:01:38,540
Ha nem egy telefon interjúban, akkor valószínűleg használni

31
00:01:38,540 --> 00:01:44,030
akár collabedit vagy a Google Doc így láthatja élsz kódoló

32
00:01:44,030 --> 00:01:46,500
közben interjút telefonon keresztül.

33
00:01:46,500 --> 00:01:48,490
Egy interjú maga általában 2 vagy 3 problémák

34
00:01:48,490 --> 00:01:50,620
tesztelése a számítástechnikai ismeretek.

35
00:01:50,620 --> 00:01:54,490
És ez szinte biztosan jár kódolás.

36
00:01:54,490 --> 00:01:59,540
A fajta kérdés, hogy látni fogod általában adatstruktúrák és algoritmusok.

37
00:01:59,540 --> 00:02:02,210
És ennek ilyen jellegű problémák,

38
00:02:02,210 --> 00:02:07,830
fogják kérdezni, tetszik, mi az idő és a tér bonyolult, nagy O?

39
00:02:07,830 --> 00:02:09,800
Gyakran ők is kérni magasabb szintű kérdések,

40
00:02:09,800 --> 00:02:12,530
így, tervezése a rendszer,

41
00:02:12,530 --> 00:02:14,770
hogyan kíván feküdt ki a kódot?

42
00:02:14,770 --> 00:02:18,370
Mi interfészek, milyen osztályok, mit modulok nem van a rendszerben,

43
00:02:18,370 --> 00:02:20,900
és hogyan hatnak ezek együtt?

44
00:02:20,900 --> 00:02:26,130
Szóval adatstruktúrák és algoritmusok, valamint a tervezés rendszerek.

45
00:02:26,130 --> 00:02:29,180
>> Néhány általános tipp, mielőtt merülni a mi esettanulmányok.

46
00:02:29,180 --> 00:02:32,300
Azt hiszem, a legfontosabb szabály mindig is hangosan gondolkodtam.

47
00:02:32,300 --> 00:02:36,980
Az interjú állítólag az alkalom, hogy megmutassák a gondolkodási folyamat.

48
00:02:36,980 --> 00:02:39,820
A lényeg az interjú a kérdező, hogy mérje

49
00:02:39,820 --> 00:02:42,660
mit gondol, és hogyan megy keresztül egy probléma.

50
00:02:42,660 --> 00:02:45,210
A legrosszabb dolog, amit tehetünk, csendben az egész interjú.

51
00:02:45,210 --> 00:02:50,090
Ez csak nem jó.

52
00:02:50,090 --> 00:02:53,230
Ha kap egy kérdést, akkor is szeretnénk, hogy győződjön meg róla, hogy megértette a kérdést.

53
00:02:53,230 --> 00:02:55,350
Tehát ismételjük meg a kérdést vissza a saját szavaiddal

54
00:02:55,350 --> 00:02:58,920
és megpróbálja a munka alapos néhány egyszerű vizsgálati esetek

55
00:02:58,920 --> 00:03:01,530
, hogy győződjön meg róla, hogy megértette a kérdést.

56
00:03:01,530 --> 00:03:05,510
Munka egy pár teszt esetek is kapsz egy intuíció, hogy hogyan oldja meg ezt a problémát.

57
00:03:05,510 --> 00:03:11,210
Lehet, hogy még felfedezni néhány mintát, hogy segítsen megoldani a problémát.

58
00:03:11,210 --> 00:03:14,500
A nagy tipp, hogy nem kap csalódott.

59
00:03:14,500 --> 00:03:17,060
Ne hagyd, hogy csalódott.

60
00:03:17,060 --> 00:03:19,060
Interjúk a kihívást, de a legrosszabb dolog, amit tehetünk,

61
00:03:19,060 --> 00:03:23,330
azon kívül, hogy csendes be kell láthatóan csalódott.

62
00:03:23,330 --> 00:03:27,410
Nem akarod, hogy ennek a benyomást kelti, hogy egy interjúban.

63
00:03:27,410 --> 00:03:33,960
Egy dolog, hogy te - így sok ember, amikor bemegy egy interjúban,

64
00:03:33,960 --> 00:03:37,150
megpróbálják, hogy megpróbálja megtalálni a legjobb megoldást az első,

65
00:03:37,150 --> 00:03:39,950
ha tényleg, ott általában nyilvánvalóvá megoldást.

66
00:03:39,950 --> 00:03:43,500
Lehet, hogy lassú, lehet, hogy nem jó, de akkor csak jelölni azt,

67
00:03:43,500 --> 00:03:46,210
Csak így van egy kiindulási pont, ahonnan jobban működnek.

68
00:03:46,210 --> 00:03:48,270
Is, rámutatva a megoldás lassú, tekintve

69
00:03:48,270 --> 00:03:52,160
big O idő összetettsége vagy térben összetettsége,

70
00:03:52,160 --> 00:03:54,450
bemutatja a kérdezőnek, hogy érti

71
00:03:54,450 --> 00:03:57,510
ezeket a kérdéseket, amikor kódot írni.

72
00:03:57,510 --> 00:04:01,440
Szóval ne félj, hogy dolgozzon ki a legegyszerűbb algoritmus először

73
00:04:01,440 --> 00:04:04,950
majd jobban működjön onnan.

74
00:04:04,950 --> 00:04:09,810
Van még kérdése eddig? Oké.

75
00:04:09,810 --> 00:04:11,650
>> Szóval belevetik magukat az első probléma.

76
00:04:11,650 --> 00:04:14,790
"Mivel egy sor n egészek, írj egy függvényt, amely összekeveri a tömb

77
00:04:14,790 --> 00:04:20,209
helyén oly módon, hogy valamennyi permutációi az n egész számok egyformán valószínű. "

78
00:04:20,209 --> 00:04:23,470
És feltételezzük, hogy van szabad véletlen egész szám generátor

79
00:04:23,470 --> 00:04:30,980
generáló egész szám egy 0-tól I, fél tartomány.

80
00:04:30,980 --> 00:04:32,970
Mindenki érti ezt a kérdést?

81
00:04:32,970 --> 00:04:39,660
Adok neked egy sor n egész számok, és azt akarom, hogy shuffle azt.

82
00:04:39,660 --> 00:04:46,050
Az én könyvtárban írtam néhány programot annak bizonyítására, mire gondolok.

83
00:04:46,050 --> 00:04:48,910
Megyek shuffle egy sor 20-elemek,

84
00:04:48,910 --> 00:04:52,490
-10 és +9,

85
00:04:52,490 --> 00:04:57,050
, és azt akarom, hogy kimenetet egy ilyen lista.

86
00:04:57,050 --> 00:05:02,890
Szóval ez az én rendezett input tömb, és azt akarom, hogy shuffle azt.

87
00:05:02,890 --> 00:05:07,070
Megcsináljuk újra.

88
00:05:07,070 --> 00:05:13,780
Mindenki érti a kérdést? Oké.

89
00:05:13,780 --> 00:05:16,730
Tehát rajtad múlik.

90
00:05:16,730 --> 00:05:21,220
Milyen ötlet? Meg tudod csinálni, mint n ^ 2-n log n, n?

91
00:05:21,220 --> 00:05:34,400
Nyissa meg a javaslatokat.

92
00:05:34,400 --> 00:05:37,730
Oké. Tehát az egyik ötlet által javasolt Emmy,

93
00:05:37,730 --> 00:05:45,300
először kiszámítása egy véletlen szám, véletlen egész szám, egy 0-tól 20-ig.

94
00:05:45,300 --> 00:05:49,840
Így vállalnak a tömb hossza 20.

95
00:05:49,840 --> 00:05:54,800
A mi diagram 20-elemek,

96
00:05:54,800 --> 00:05:58,560
ez a mi input tömb.

97
00:05:58,560 --> 00:06:04,590
És most, az ő javaslata az, hogy hozzon létre egy új tömböt,

98
00:06:04,590 --> 00:06:08,440
így ez lesz a kimeneti tömbben.

99
00:06:08,440 --> 00:06:12,880
Alapján, valamint az i által visszaadott rand -

100
00:06:12,880 --> 00:06:17,580
tehát ha én, mondjuk, 17,

101
00:06:17,580 --> 00:06:25,640
másolja a 17. elemet az első helyen.

102
00:06:25,640 --> 00:06:30,300
Most el kell törölni - meg kell váltani az összes elemet itt

103
00:06:30,300 --> 00:06:36,920
, úgy, hogy van egy rés a végén, és nem lyukak a közepén.

104
00:06:36,920 --> 00:06:39,860
És most ismételje meg a folyamatot.

105
00:06:39,860 --> 00:06:46,360
Most válasszon egy új véletlen egész szám 0 és 19.

106
00:06:46,360 --> 00:06:52,510
Van egy új vagyok itt, és másolja ezt az elemet ebbe a helyzetbe.

107
00:06:52,510 --> 00:07:00,960
Aztán műszak tételeket át, és megismételjük a folyamatot, amíg megvan a teljesen új tömb.

108
00:07:00,960 --> 00:07:05,890
Mi a futási idő ezen algoritmus?

109
00:07:05,890 --> 00:07:08,110
Nos, nézzük meg ennek hatását.

110
00:07:08,110 --> 00:07:10,380
Mi változik minden elemét.

111
00:07:10,380 --> 00:07:16,800
Amikor eltávolításához i, mi változik az összes elemet, miután a bal oldalon.

112
00:07:16,800 --> 00:07:21,600
És ez egy O (n) költség

113
00:07:21,600 --> 00:07:26,100
mert mi van, ha eltávolítja az első elem?

114
00:07:26,100 --> 00:07:29,670
Tehát minden eltávolítására, akkor távolítsa el -

115
00:07:29,670 --> 00:07:32,170
elszállításáról minden egyes alkalommal keletkezik O (n) üzemeltetés,

116
00:07:32,170 --> 00:07:41,520
és mivel már n költöztetés, ez ahhoz vezet, hogy O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Oké. Szóval jó kezdés. Jó kezdet.

118
00:07:49,550 --> 00:07:55,290
>> Egy másik javaslat az, hogy valami ismert, mint a Knuth shuffle,

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

120
00:07:57,540 --> 00:07:59,630
És ez valójában egy lineáris idő shuffle.

121
00:07:59,630 --> 00:08:02,200
És az ötlet nagyon hasonló.

122
00:08:02,200 --> 00:08:05,160
Ismét megvan a bemeneti tömb,

123
00:08:05,160 --> 00:08:08,580
de ahelyett, hogy a két tömb számára bemenet / kimenet,

124
00:08:08,580 --> 00:08:13,590
használjuk az első rész a tömb, hogy nyomon követhesse a mi csoszogott részt,

125
00:08:13,590 --> 00:08:18,400
és mi nyomon, majd hagyjuk a többi a mi tömb a unshuffled részét.

126
00:08:18,400 --> 00:08:24,330
Szóval, itt van, amit gondolok. Kezdjük le - mi válasszon i,

127
00:08:24,330 --> 00:08:30,910
tömb 0-20.

128
00:08:30,910 --> 00:08:36,150
A jelenlegi mutató mutat az első index.

129
00:08:36,150 --> 00:08:39,590
Mi választani néhány i itt

130
00:08:39,590 --> 00:08:42,740
és most cserélni.

131
00:08:42,740 --> 00:08:47,690
Szóval, ha ez 5 és ez 4,

132
00:08:47,690 --> 00:08:57,150
A kapott tömb lesz itt 5 és 4 itt.

133
00:08:57,150 --> 00:09:00,390
És most, vegye figyelembe a marker itt.

134
00:09:00,390 --> 00:09:05,770
Minden, ami a bal oldalon van csoszogott,

135
00:09:05,770 --> 00:09:15,160
és minden a jog unshuffled.

136
00:09:15,160 --> 00:09:17,260
És most mi is ismételje meg a folyamatot.

137
00:09:17,260 --> 00:09:25,210
Mi választjuk ki véletlenszerűen index 1 és 20 között van.

138
00:09:25,210 --> 00:09:30,650
Tehát tegyük fel, az új i itt van.

139
00:09:30,650 --> 00:09:39,370
Most cserélni ezt én a mi jelenlegi új helyzet van.

140
00:09:39,370 --> 00:09:44,790
Szóval mi a csere oda-vissza, mint ez.

141
00:09:44,790 --> 00:09:51,630
Hadd hívjam fel a kódot, hogy ez több beton.

142
00:09:51,630 --> 00:09:55,290
Kezdjük a mi választott i -

143
00:09:55,290 --> 00:09:58,370
kezdjük i értéke 0, akkor válasszon egy random helyre j

144
00:09:58,370 --> 00:10:02,420
a unshuffled részében a tömb, az i n-1.

145
00:10:02,420 --> 00:10:07,280
Szóval, ha itt vagyok, válasszon egy véletlenszerű index között, itt és a többi tömb,

146
00:10:07,280 --> 00:10:12,410
és mi cserélni.

147
00:10:12,410 --> 00:10:17,550
Ez mind a kód szükséges shuffle a tömb.

148
00:10:17,550 --> 00:10:21,670
Van még kérdése?

149
00:10:21,670 --> 00:10:25,530
>> Nos, az egyik szükséges, kérdés az, hogy miért van ez a helyes?

150
00:10:25,530 --> 00:10:28,360
Miért van minden permutáció egyformán valószínű?

151
00:10:28,360 --> 00:10:30,410
És nem megy át a bizonyíték erre,

152
00:10:30,410 --> 00:10:35,970
de sok probléma számítógép-tudomány bizonyítani lehet a indukció.

153
00:10:35,970 --> 00:10:38,520
Hányan ismerik indukciós?

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

155
00:10:40,590 --> 00:10:43,610
Így be lehet bizonyítani a helyességét ezen algoritmus egyszerű indukció,

156
00:10:43,610 --> 00:10:49,540
ahol az indukciós feltevés lenne, feltételezik, hogy

157
00:10:49,540 --> 00:10:53,290
my shuffle visszatér minden permutáció egyformán valószínű

158
00:10:53,290 --> 00:10:56,120
fel, hogy az első i elemeket.

159
00:10:56,120 --> 00:10:58,300
Nos, úgy i + 1.

160
00:10:58,300 --> 00:11:02,550
És hogy hogyan választjuk meg j index a swap,

161
00:11:02,550 --> 00:11:05,230
ez vezet - és akkor dolgozzanak ki a részleteket,

162
00:11:05,230 --> 00:11:07,390
legalább egy teljes bizonyítékot, hogy miért ez az algoritmus visszatér

163
00:11:07,390 --> 00:11:12,800
minden permutáció egyformán valószínű a valószínűsége.

164
00:11:12,800 --> 00:11:15,940
>> Rendben, következő probléma.

165
00:11:15,940 --> 00:11:19,170
Így "az adott tömb egész számok, Pozitív, nulla, negatív,

166
00:11:19,170 --> 00:11:21,290
írni egy függvényt, amely kiszámítja a maximális összeget

167
00:11:21,290 --> 00:11:24,720
bármely continueous subarray a bemeneti tömb. "

168
00:11:24,720 --> 00:11:28,370
Egy példa itt van, abban az esetben, ahol az összes pozitív szám,

169
00:11:28,370 --> 00:11:31,320
akkor jelenleg a legjobb választás az, hogy az egész tömb.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, egyenlő 10.

171
00:11:34,690 --> 00:11:36,780
Ha van néhány negatív ott,

172
00:11:36,780 --> 00:11:38,690
ebben az esetben csak azt az első két

173
00:11:38,690 --> 00:11:44,590
mert a választott -1 és / vagy -3 viszi a összeget le.

174
00:11:44,590 --> 00:11:48,120
Néha talán el kell kezdenünk a közepén a tömb.

175
00:11:48,120 --> 00:11:53,500
Néha szeretnénk választani semmit, ez a legjobb, hogy nem vesz semmit.

176
00:11:53,500 --> 00:11:56,490
És néha jobb, hogy a bukás,

177
00:11:56,490 --> 00:12:07,510
mert a dolog, miután az szuper nagy. Szóval valami ötleted?

178
00:12:07,510 --> 00:12:10,970
(Diák, érthetetlen) >> Igen.

179
00:12:10,970 --> 00:12:13,560
Tegyük fel, hogy nem veszem -1.

180
00:12:13,560 --> 00:12:16,170
Akkor sem úgy döntök, 1.000 és 20.000,

181
00:12:16,170 --> 00:12:18,630
vagy én csak válassza ki a 3 milliárd euró.

182
00:12:18,630 --> 00:12:20,760
Nos, a legjobb választás az, hogy az összes számot.

183
00:12:20,760 --> 00:12:24,350
Ez a -1, annak ellenére, hogy negatív,

184
00:12:24,350 --> 00:12:31,340
a teljes összeg jobb, mint volt, én nem, hogy -1.

185
00:12:31,340 --> 00:12:36,460
Tehát az egyik a tippeket már korábban említettem volt, hogy azt az egyértelműen nyilvánvaló

186
00:12:36,460 --> 00:12:40,540
és a brute force megoldás először.

187
00:12:40,540 --> 00:12:44,340
Mi a brute force megoldás erre a problémára? Igen?

188
00:12:44,340 --> 00:12:46,890
[Jane] Nos, azt hiszem, a brute force megoldás

189
00:12:46,890 --> 00:12:52,600
lenne, ha összeadja az összes lehetséges kombinációt (érthetetlen).

190
00:12:52,600 --> 00:12:58,250
[Yu] Oké. Tehát Jane ötlete az, hogy minden lehetséges -

191
00:12:58,250 --> 00:13:01,470
Én parafrázisa -, hogy tegyenek meg minden lehetséges folyamatos subarray,

192
00:13:01,470 --> 00:13:07,840
kiszámítása az összeg, majd megteszi a legnagyobb az összes lehetséges folyamatos subarrays.

193
00:13:07,840 --> 00:13:13,310
Mi az egyedileg azonosítja a subarray az én bemeneti tömb?

194
00:13:13,310 --> 00:13:17,380
Mint, milyen két dolgot kell tennem? Igen?

195
00:13:17,380 --> 00:13:19,970
(Diák, érthetetlen) >> Rendben.

196
00:13:19,970 --> 00:13:22,130
Az alsó korlátot az index és a felső kötött index

197
00:13:22,130 --> 00:13:28,300
egyértelműen meghatározza a folyamatos subarray.

198
00:13:28,300 --> 00:13:31,400
[Nő diák] vagyunk becslése, hogy ez egy sor egyedi számok?

199
00:13:31,400 --> 00:13:34,280
[Yu] Szóval ő kérdés az, hogy mi vagyunk feltételezve array -

200
00:13:34,280 --> 00:13:39,000
a mi tömb minden egyedi számokat, és a válasz nem.

201
00:13:39,000 --> 00:13:43,390
>> Ha használja a brute force megoldás, akkor a start / end indexek

202
00:13:43,390 --> 00:13:47,200
egyértelműen meghatározza a folyamatos subarray.

203
00:13:47,200 --> 00:13:51,680
Tehát ha navigálhat az összes lehetséges kezdő tétel,

204
00:13:51,680 --> 00:13:58,320
és minden bejegyzés végére> vagy = kezdeni, és <n,

205
00:13:58,320 --> 00:14:05,570
Ön kiszámítása az összeget, és akkor megteszi a legnagyobb pénzösszeget láttunk eddig.

206
00:14:05,570 --> 00:14:07,880
Érthető ez?

207
00:14:07,880 --> 00:14:12,230
Mi a nagy O e megoldás?

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

209
00:14:16,660 --> 00:14:18,860
Nem egészen n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Vegyük észre, hogy navigálhat 0-tól n,

211
00:14:25,250 --> 00:14:27,520
úgy, hogy az egyik a hurok.

212
00:14:27,520 --> 00:14:35,120
Mi ismételget újra szinte elejétől a végéig, a másik a hurok.

213
00:14:35,120 --> 00:14:37,640
És most, ezen belül is meg kell összegezni minden bejegyzést,

214
00:14:37,640 --> 00:14:43,810
annak érdekében, hogy egy másik a hurok. Tehát van három egymásba a hurok, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Oké. Ez megy, mint egy kiindulási pont.

216
00:14:46,560 --> 00:14:53,180
A megoldás nem rosszabb, mint n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Mindenki érti a brute force megoldás?

218
00:14:55,480 --> 00:14:59,950
>> Oké. Egy jobb megoldás segítségével egy ötlet nevű dinamikus programozás.

219
00:14:59,950 --> 00:15:03,040
Ha az előírtnál CS124, amely Algoritmusok és adatszerkezetek,

220
00:15:03,040 --> 00:15:05,680
akkor lesz nagyon ismerik ezt a technikát.

221
00:15:05,680 --> 00:15:12,190
És az ötlet, próbálja felépíteni megoldásokat a kisebb problémákat először.

222
00:15:12,190 --> 00:15:17,990
Mit jelent ez, jelenleg nem kell aggódnia, két dolgot: kezdetét és végét.

223
00:15:17,990 --> 00:15:29,340
És ez bosszantó. Mi lenne, ha tudnánk megszabadulni egy ilyen paraméterek?

224
00:15:29,340 --> 00:15:32,650
Az egyik elképzelés az, hogy - az adott we're az eredeti probléma,

225
00:15:32,650 --> 00:15:37,470
A maximálisan összege bármely subarray közötti tartományban [O-, n-1].

226
00:15:37,470 --> 00:15:47,400
És most van egy új subproblem, ha tudjuk, hogy a jelenlegi i index,

227
00:15:47,400 --> 00:15:52,520
tudjuk, hogy meg kell kötni ott. A subarray véget kell vetni az aktuális index.

228
00:15:52,520 --> 00:15:57,640
Tehát a probléma az, hol kezdjük subarray?

229
00:15:57,640 --> 00:16:05,160
Van ennek értelme? Oké.

230
00:16:05,160 --> 00:16:12,030
Szóval kódolt e fel, és nézzük meg, mit jelent ez.

231
00:16:12,030 --> 00:16:16,230
A codirectory van egy program neve subarray,

232
00:16:16,230 --> 00:16:19,470
és tart tételek száma,

233
00:16:19,470 --> 00:16:25,550
és visszaadja a maximális subarray összeg az én csoszogott listában.

234
00:16:25,550 --> 00:16:29,920
Tehát ebben az esetben, a maximális subarray 3 lehet.

235
00:16:29,920 --> 00:16:34,850
És ez által csak a 2 és az 1.

236
00:16:34,850 --> 00:16:38,050
Fussunk újra. Ez is 3.

237
00:16:38,050 --> 00:16:40,950
De ez alkalommal, vegye figyelembe, hogy megvan a 3.

238
00:16:40,950 --> 00:16:46,690
Mi volt a - mi csak vegye a 3 is

239
00:16:46,690 --> 00:16:49,980
mert ez körül negatívok mindkét oldalon,

240
00:16:49,980 --> 00:16:55,080
amely fog egy összeget <3.

241
00:16:55,080 --> 00:16:57,820
Fussunk a 10 darab.

242
00:16:57,820 --> 00:17:03,200
Ezúttal 7, vesszük a vezető 3 és 4.

243
00:17:03,200 --> 00:17:09,450
Ezúttal 8, és azt kapjuk, hogy azáltal, hogy 1, 4 és 3.

244
00:17:09,450 --> 00:17:16,310
Szóval, hogy ön egy intuíció, hogyan tudjuk megoldani ezt a problémát át,

245
00:17:16,310 --> 00:17:18,890
vessünk egy pillantást erre subarray.

246
00:17:18,890 --> 00:17:23,460
Mi tekintettel e input tömb, és tudjuk, hogy a válasz: 8.

247
00:17:23,460 --> 00:17:26,359
Vesszük a 1, 4, és 3.

248
00:17:26,359 --> 00:17:29,090
De nézzük meg, hogy hogyan van, hogy tényleg választ.

249
00:17:29,090 --> 00:17:34,160
Nézzük meg a maximális subarray végződő mindegyik ilyen indexek.

250
00:17:34,160 --> 00:17:40,780
Mi az a maximális subarray amely véget az első helyen?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. >> Zero. Csak ne szedje a -5.

252
00:17:46,310 --> 00:17:50,210
Itt lesz 0 is. Igen?

253
00:17:50,210 --> 00:17:56,470
(Diák, érthetetlen)

254
00:17:56,470 --> 00:17:58,960
[Yu] Ó, sajnálom, ez egy -3.

255
00:17:58,960 --> 00:18:03,220
Tehát ez egy 2, ez egy -3.

256
00:18:03,220 --> 00:18:08,690
Oké. Szóval -4, mi a maximális subarray véget ez az álláspont

257
00:18:08,690 --> 00:18:12,910
ahol -4 van? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Nos, véget kell vetni a helyen, ahol a -2 címen.

260
00:18:28,060 --> 00:18:39,330
Így 6, 5, 7, és az utolsó 4 lehet.

261
00:18:39,330 --> 00:18:43,480
Tudva, hogy ezek az én bejegyzések

262
00:18:43,480 --> 00:18:48,130
A transzformált probléma, ahol véget kell vetni ezen egyes indexek

263
00:18:48,130 --> 00:18:51,410
majd a végső válasz csak, hogy egy sweep-át,

264
00:18:51,410 --> 00:18:53,580
és megteszi a maximális számát.

265
00:18:53,580 --> 00:18:55,620
Tehát ebben az esetben ez a 8.

266
00:18:55,620 --> 00:19:00,010
Ez azt jelenti, hogy a maximális subarray ér véget ez a mutató,

267
00:19:00,010 --> 00:19:04,970
és elkezdte valahol előtte.

268
00:19:04,970 --> 00:19:09,630
Mindenki érti ezt át subarray?

269
00:19:09,630 --> 00:19:22,160
>> Oké. Nos, kitaláljuk, a kiújulás erre.

270
00:19:22,160 --> 00:19:27,990
Nézzük csak az első néhány bejegyzéseket.

271
00:19:27,990 --> 00:19:35,930
Így itt volt 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
És ott volt a -2 itt, és azt hozta le 6-ra.

273
00:19:39,790 --> 00:19:50,800
Tehát, ha hívom a belépési pozícióban i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
hogyan használhatom a választ egy korábbi subproblem

275
00:19:54,910 --> 00:19:59,360
válaszolni erre subproblem?

276
00:19:59,360 --> 00:20:04,550
Ha megnézzük, mondjuk, ezt a bejegyzést.

277
00:20:04,550 --> 00:20:09,190
Hogyan lehet kiszámítani a választ a 6 nézi most

278
00:20:09,190 --> 00:20:18,780
kombinációja a tömb, és a válaszokat az előző alproblémát ebben a tömbben? Igen?

279
00:20:18,780 --> 00:20:22,800
[Nő diák] Veszel a tömbben összegek

280
00:20:22,800 --> 00:20:25,430
abban a helyzetben, közvetlenül előtte, így a 8,

281
00:20:25,430 --> 00:20:32,170
és akkor hozzá az aktuális subproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] Szóval ő javaslata, hogy nézd meg a két szám,

283
00:20:36,460 --> 00:20:40,090
ezt a számot, és ezt a számot.

284
00:20:40,090 --> 00:20:50,130
Tehát ez 8 utal a választ a subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
És hívjuk a bemeneti tömb A.

286
00:20:57,300 --> 00:21:01,470
Annak érdekében, hogy a maximális subarray végződő pozícióban i,

287
00:21:01,470 --> 00:21:03,980
Van két lehetőség közül választhat: vagy tudom folytatni subarray

288
00:21:03,980 --> 00:21:09,790
hogy véget ért a korábbi index, vagy indítson új tömb.

289
00:21:09,790 --> 00:21:14,190
Ha én lennék, hogy folytassák a subarray indult az előző index,

290
00:21:14,190 --> 00:21:19,260
akkor a maximális összeg tudom elérni a válasz az előző subproblem

291
00:21:19,260 --> 00:21:24,120
és a folyó tömb bejegyzést.

292
00:21:24,120 --> 00:21:27,550
De, én is a választás a kezdő új subarray,

293
00:21:27,550 --> 00:21:30,830
amely esetben az összeg 0.

294
00:21:30,830 --> 00:21:42,860
Tehát a válasz: max 0, subproblem i - 1, valamint a jelenlegi tömb bejegyzést.

295
00:21:42,860 --> 00:21:46,150
Van ennek megismétlődése értelme?

296
00:21:46,150 --> 00:21:50,840
A kiújulás, ahogy most fedezem fel, nem subproblem i

297
00:21:50,840 --> 00:21:54,740
egyenlő a maximális az előző subproblem plusz mostani tömb bejegyzés,

298
00:21:54,740 --> 00:22:01,490
ami azt jelenti, továbbra is a korábbi subarray,

299
00:22:01,490 --> 00:22:07,250
vagy 0, indítson új subarray én aktuális index.

300
00:22:07,250 --> 00:22:10,060
És ha egyszer már épített ki ezt a táblázatot a megoldások, majd a végső választ,

301
00:22:10,060 --> 00:22:13,950
Csak nem egy lineáris sweep-szerte subproblem tömb

302
00:22:13,950 --> 00:22:19,890
és megteszi a maximális számát.

303
00:22:19,890 --> 00:22:23,330
Ez egy pontos megvalósítása, amit mondtam.

304
00:22:23,330 --> 00:22:27,320
Tehát egy új subproblem tömb, alproblémát.

305
00:22:27,320 --> 00:22:32,330
Az első bejegyzés 0 vagy az első bejegyzés, a legnagyobb e kettő.

306
00:22:32,330 --> 00:22:35,670
És a többi alproblémát

307
00:22:35,670 --> 00:22:39,810
használjuk a pontos ismétlődés már csak fel.

308
00:22:39,810 --> 00:22:49,960
Most kiszámítani a legnagyobb a mi alproblémát tömb, és ez a végső válasz.

309
00:22:49,960 --> 00:22:54,130
>> Szóval, mennyi hely vagyunk használ ez az algoritmus?

310
00:22:54,130 --> 00:23:01,470
Ha csak venni CS50, akkor lehet, hogy nem tárgyalt terület nagyon.

311
00:23:01,470 --> 00:23:07,750
Nos, az egyik dolog megjegyezni, hogy hívtam malloc itt méretű n.

312
00:23:07,750 --> 00:23:13,590
Mit javasol az Ön számára?

313
00:23:13,590 --> 00:23:17,450
Ez az algoritmus lineáris tér.

314
00:23:17,450 --> 00:23:21,030
Tehetünk a jobb?

315
00:23:21,030 --> 00:23:30,780
Van valami, azt tapasztalja, hogy nem szükséges, hogy kiszámolja a végleges válasz?

316
00:23:30,780 --> 00:23:33,290
Azt hiszem, egy jobb kérdés az, hogy milyen információk

317
00:23:33,290 --> 00:23:40,680
tudjuk nem kell folytatni végig a vége?

318
00:23:40,680 --> 00:23:44,280
Most, ha megnézzük a két vonal,

319
00:23:44,280 --> 00:23:47,720
csak érdekel az előző subproblem,

320
00:23:47,720 --> 00:23:50,910
és csak érdekel a legnagyobb, amit valaha láttunk eddig.

321
00:23:50,910 --> 00:23:53,610
Ahhoz, hogy kiszámításához a végső választ, akkor nem kell az egész tömb.

322
00:23:53,610 --> 00:23:57,450
Csak kell az utolsó szám, az elmúlt két szám.

323
00:23:57,450 --> 00:24:02,630
Utolsó szám a subproblem tömb, és az utolsó szám a maximum.

324
00:24:02,630 --> 00:24:07,380
Tehát, valójában, tudjuk biztosíték ezeket hurok együtt

325
00:24:07,380 --> 00:24:10,460
és menjen a lineáris tér állandó helyet.

326
00:24:10,460 --> 00:24:15,830
Jelenlegi összeget eddig itt, helyettesíti a szerepe subproblem, mi subproblem tömb.

327
00:24:15,830 --> 00:24:20,020
Tehát a jelenlegi összeget, eddig a válasz az előző subproblem.

328
00:24:20,020 --> 00:24:23,450
És ez az összeg, hogy eddig azon a helyen a mi max.

329
00:24:23,450 --> 00:24:28,100
Mi kiszámításához a maximális, ahogy megy végig.

330
00:24:28,100 --> 00:24:30,890
És így megy lineáris tér állandó hely,

331
00:24:30,890 --> 00:24:36,650
és mi is lineáris megoldás a subarray probléma.

332
00:24:36,650 --> 00:24:40,740
>> Az ilyen típusú kérdésekre kapsz egy interjú során.

333
00:24:40,740 --> 00:24:44,450
Mennyi idő komplexitás, mi a tér bonyolult?

334
00:24:44,450 --> 00:24:50,600
Tudsz jobbat? Vannak dolgok, amelyek felesleges, hogy itt van?

335
00:24:50,600 --> 00:24:55,270
Én ezt kiemelni elemzéseket, hogy meg kell venni a saját

336
00:24:55,270 --> 00:24:57,400
ahogy dolgozunk át ezeket a problémákat.

337
00:24:57,400 --> 00:25:01,710
Mindig kell, hogy megkérdeznéd magadtól: "Tudok jobbat?"

338
00:25:01,710 --> 00:25:07,800
Tény, hogy tudunk jobban, mint ez?

339
00:25:07,800 --> 00:25:10,730
Valahogy egy beugratós kérdés. Nem lehet, mert kell, hogy

340
00:25:10,730 --> 00:25:13,590
Legalább olvasd el a bemenetet a problémát.

341
00:25:13,590 --> 00:25:15,570
Így az a tény, hogy meg kell, hogy legalább olvasni a bemeneti a probléma

342
00:25:15,570 --> 00:25:19,580
azt jelenti, hogy nem jobb, mint a lineáris idő,

343
00:25:19,580 --> 00:25:22,870
és akkor nem jobb, mint az állandó helyet.

344
00:25:22,870 --> 00:25:27,060
Tehát ez, valójában, a legjobb megoldás erre a problémára.

345
00:25:27,060 --> 00:25:33,040
Kérdései vannak? Oké.

346
00:25:33,040 --> 00:25:35,190
>> Tőzsdei probléma:

347
00:25:35,190 --> 00:25:38,350
"Mivel egy sor n egész számok, pozitív, nulla, vagy negatív

348
00:25:38,350 --> 00:25:41,680
hogy képviselje az ára a készlet több mint n nap,

349
00:25:41,680 --> 00:25:44,080
levelet funkció kiszámolja a maximális profit megteheti

350
00:25:44,080 --> 00:25:49,350
tekintve, hogy vásárolni és eladni pontosan 1 stock ezekben n nap. "

351
00:25:49,350 --> 00:25:51,690
Lényegében szeretnénk vásárolni alacsony eladni magas.

352
00:25:51,690 --> 00:25:58,580
És azt akarjuk, hogy kitaláljuk, a legjobb eredmény tehetjük.

353
00:25:58,580 --> 00:26:11,500
Visszatérve az én tip, mi az azonnal világos, legegyszerűbb válasz, de ez lassú?

354
00:26:11,500 --> 00:26:17,690
Igen? (Diák, érthetetlen) >> Igen.

355
00:26:17,690 --> 00:26:21,470
>> Szóval akkor csak menj, bár, és nézd meg a tőzsdei árfolyamok

356
00:26:21,470 --> 00:26:30,550
minden egyes időpontban, (érthetetlen).

357
00:26:30,550 --> 00:26:33,990
[Yu] Oké, szóval neki megoldás - ő javaslatára számítástechnika

358
00:26:33,990 --> 00:26:37,380
a legalacsonyabb és a legmagasabb számítása nem feltétlenül működik

359
00:26:37,380 --> 00:26:42,470
mert a legmagasabb előfordulhat, mielőtt a legalacsonyabb.

360
00:26:42,470 --> 00:26:47,340
Tehát mi a brute force megoldás erre a problémára?

361
00:26:47,340 --> 00:26:53,150
Mi az a két dolog, amit meg kell egyértelműen meghatározni a profit teszek? Rendben.

362
00:26:53,150 --> 00:26:59,410
A brute force megoldás - Ó, igen, George javaslat az, hogy mindössze két nap alatt

363
00:26:59,410 --> 00:27:02,880
egyedileg meghatározni a profit e két nap alatt.

364
00:27:02,880 --> 00:27:06,660
Tehát számolni minden pár, mint vétel / eladás,

365
00:27:06,660 --> 00:27:12,850
kiszámítja a profit, ami lehet pozitív vagy negatív, vagy nulla.

366
00:27:12,850 --> 00:27:18,000
Számítsuk ki a maximális profit, hogy mi teszi után iterációjával egész pár nap.

367
00:27:18,000 --> 00:27:20,330
Ez lesz a végső válasz.

368
00:27:20,330 --> 00:27:25,730
És ez lesz a megoldás O (n ^ 2), mert n választani két pár -

369
00:27:25,730 --> 00:27:30,270
napok közül lehet választani end nap.

370
00:27:30,270 --> 00:27:32,580
Oké, én nem megyek át a brute force megoldás itt.

371
00:27:32,580 --> 00:27:37,420
Fogom mondani, hogy van egy n log n megoldás.

372
00:27:37,420 --> 00:27:45,550
Mi az algoritmus nem Ön jelenleg tudni, hogy n log n?

373
00:27:45,550 --> 00:27:50,730
Ez nem egy trükkös kérdés.

374
00:27:50,730 --> 00:27:54,790
>> Merge sort. Merge sort n log n,

375
00:27:54,790 --> 00:27:57,760
és valóban, az egyik módja a probléma megoldása az, hogy az

376
00:27:57,760 --> 00:28:04,400
összeolvasztás egyfajta egyfajta ötlet hívják, általában oszd meg és uralkodj.

377
00:28:04,400 --> 00:28:07,570
És az elképzelés a következő.

378
00:28:07,570 --> 00:28:12,400
Azt akarod, hogy kiszámolja a legjobb vétel / eladás pár a bal felét.

379
00:28:12,400 --> 00:28:16,480
Keresse meg a legjobb eredmény lehet, hogy, csak az első n két nap alatt.

380
00:28:16,480 --> 00:28:19,780
Ezután szeretnéd oompute legjobb vétel / eladás pár a jobb felét,

381
00:28:19,780 --> 00:28:23,930
így az utolsó n keresztül két nap.

382
00:28:23,930 --> 00:28:32,400
És most az a kérdés, hogyan egyesítik ezeket a megoldásokat újra együtt?

383
00:28:32,400 --> 00:28:36,320
Igen? (Diák, érthetetlen)

384
00:28:36,320 --> 00:28:49,890
>> Oké. Szóval hadd dolgozzon ki egy képet.

385
00:28:49,890 --> 00:29:03,870
Igen? (George, érthetetlen)

386
00:29:03,870 --> 00:29:06,450
>> Pontosan. George megoldás pontosan így van.

387
00:29:06,450 --> 00:29:10,040
Szóval ő javaslatára az első kiszámíthatjuk a legjobb vétel / eladás pár,

388
00:29:10,040 --> 00:29:16,050
és az fordul elő, hogy a bal oldalán, így hívjuk, hogy a bal, bal.

389
00:29:16,050 --> 00:29:20,790
A legjobb vétel / eladás pár fordul elő, hogy a jobb felét.

390
00:29:20,790 --> 00:29:25,180
De ha csak, mint a két szám, mi hiányzik az ügy

391
00:29:25,180 --> 00:29:30,460
ahol vásárolni és eladni itt valahol a jobb felét.

392
00:29:30,460 --> 00:29:33,810
Veszünk a bal fele, eladni a jobb felét.

393
00:29:33,810 --> 00:29:38,490
És a legjobb módja annak, hogy kiszámolja a legjobb vétel / eladás pár ível Mindkét félidőt

394
00:29:38,490 --> 00:29:43,480
van, hogy kiszámolja a minimális itt és kiszámítja a maximális ide

395
00:29:43,480 --> 00:29:45,580
és megteszi a különbséget.

396
00:29:45,580 --> 00:29:50,850
Így a két esetben, amikor a vásárlás / eladás pár fordul elő csak itt,

397
00:29:50,850 --> 00:30:01,910
csak itt, vagy mindkét fél határozza három számokat.

398
00:30:01,910 --> 00:30:06,450
Szóval mi algoritmus egyesítése megoldásaink újra együtt,

399
00:30:06,450 --> 00:30:08,350
szeretnénk, hogy kiszámolja a legjobb vétel / eladás pár

400
00:30:08,350 --> 00:30:13,120
ahol vásárolni a bal felét, és eladni a jobb felét.

401
00:30:13,120 --> 00:30:16,740
És a legjobb módja, hogy az, hogy kiszámolja a legalacsonyabb árat az első félévben,

402
00:30:16,740 --> 00:30:20,360
a legmagasabb ár a jobb felére, és megteszi a különbséget.

403
00:30:20,360 --> 00:30:25,390
A kapott 3 nyereséget, ez a három számot, akkor megteszi a legnagyobb a három,

404
00:30:25,390 --> 00:30:32,720
és ez a legjobb eredmény lehet, hogy át ezek az első és a végső napon.

405
00:30:32,720 --> 00:30:36,940
Itt a legfontosabb vonalak piros.

406
00:30:36,940 --> 00:30:41,160
Ez egy rekurzív hívás kiszámolja a választ a bal felét.

407
00:30:41,160 --> 00:30:44,760
Ez egy rekurzív hívás kiszámolja a választ a jobb felét.

408
00:30:44,760 --> 00:30:50,720
Ez a két hurok számára kiszámolja a min és a max szintjét a bal és jobb fele, illetve.

409
00:30:50,720 --> 00:30:54,970
Most kiszámítani a nyereség, amely felöleli mindkét felét,

410
00:30:54,970 --> 00:31:00,530
és a végső válasz a maximális e három.

411
00:31:00,530 --> 00:31:04,120
Oké.

412
00:31:04,120 --> 00:31:06,420
>> Szóval, biztos, hogy van egy algoritmust, de a nagyobb kérdés az,

413
00:31:06,420 --> 00:31:08,290
mi az idő összetettsége ez?

414
00:31:08,290 --> 00:31:16,190
És az ok, amiért említettem merge sort, hogy ez a formája osztani a válasz

415
00:31:16,190 --> 00:31:19,200
két, majd egyesülő megoldásaink újra együtt

416
00:31:19,200 --> 00:31:23,580
pontosan formában merge sort.

417
00:31:23,580 --> 00:31:33,360
Szóval hadd menjen végig az időtartamot.

418
00:31:33,360 --> 00:31:41,340
Ha definiált egy függvény t (n), hogy a lépések számát

419
00:31:41,340 --> 00:31:50,010
n nap,

420
00:31:50,010 --> 00:31:54,350
a két rekurzív hívás

421
00:31:54,350 --> 00:32:00,460
mindegyike fog kerülni t (n / 2),

422
00:32:00,460 --> 00:32:03,540
és van két ilyen hívások.

423
00:32:03,540 --> 00:32:10,020
Most ki kell számolnunk a legkisebb a bal fele,

424
00:32:10,020 --> 00:32:17,050
amit tehet n / 2 alkalommal, valamint a legnagyobb a jobb felét.

425
00:32:17,050 --> 00:32:20,820
Tehát ez éppen n.

426
00:32:20,820 --> 00:32:25,050
És akkor plusz néhány állandó munkát.

427
00:32:25,050 --> 00:32:27,770
És ez az ismétlődés egyenlet

428
00:32:27,770 --> 00:32:35,560
pontosan az ismétlődés egyenlet merge sort.

429
00:32:35,560 --> 00:32:39,170
És mindannyian tudjuk, hogy az egyesítés rendezés n log n idő.

430
00:32:39,170 --> 00:32:46,880
Ezért a mi algoritmus is n log n idő.

431
00:32:46,880 --> 00:32:52,220
Van ennek iterációs értelme?

432
00:32:52,220 --> 00:32:55,780
Csak egy rövid bedugni ebből:

433
00:32:55,780 --> 00:32:59,170
T (n) a lépések számát, hogy kiszámolja a maximális profit

434
00:32:59,170 --> 00:33:02,750
folyamán n nap.

435
00:33:02,750 --> 00:33:06,010
Ahogy mi különválnak a rekurzív hívások

436
00:33:06,010 --> 00:33:11,980
az hívja a megoldás az első n / 2 nap,

437
00:33:11,980 --> 00:33:14,490
így ez egy hívás,

438
00:33:14,490 --> 00:33:16,940
és akkor hívja újra a második felét.

439
00:33:16,940 --> 00:33:20,440
Szóval ez két hívást.

440
00:33:20,440 --> 00:33:25,310
Aztán találunk egy minimum a bal fele, amit tehetünk a lineáris idő,

441
00:33:25,310 --> 00:33:29,010
megtalálja a legnagyobb a jobb fele, amit tehetünk a lineáris időben.

442
00:33:29,010 --> 00:33:31,570
Így n / 2 + n / 2 csak n.

443
00:33:31,570 --> 00:33:36,020
Aztán van néhány állandó munka, ami olyan, mint csinál számtani.

444
00:33:36,020 --> 00:33:39,860
A visszatérő egyenlet pontosan az ismétlődés egyenlet merge sort.

445
00:33:39,860 --> 00:33:55,490
Ezért, a shuffle algoritmus is n log n.

446
00:33:55,490 --> 00:33:58,520
Szóval, mennyi hely vagyunk használ?

447
00:33:58,520 --> 00:34:04,910
Menjünk vissza a kódot.

448
00:34:04,910 --> 00:34:09,420
>> Egy jobb kérdés, hány stack frame tudjuk valaha is bármely adott pillanatban?

449
00:34:09,420 --> 00:34:11,449
Mivel mi vagyunk a rekurzió,

450
00:34:11,449 --> 00:34:23,530
száma stack frame meghatározza az űr használat.

451
00:34:23,530 --> 00:34:29,440
Vegyük n = 8.

452
00:34:29,440 --> 00:34:36,889
Felhívjuk shuffle 8-án,

453
00:34:36,889 --> 00:34:41,580
amely hívja shuffle az első négy bejegyzéseket,

454
00:34:41,580 --> 00:34:46,250
ami meg fogja hívni a shuffle az első két bejegyzés.

455
00:34:46,250 --> 00:34:51,550
Így a verem - ez a mi verem.

456
00:34:51,550 --> 00:34:54,980
És akkor hívjuk újra shuffle 1-jén,

457
00:34:54,980 --> 00:34:58,070
és ez az, amit mi alap eset, úgyhogy vissza azonnal.

458
00:34:58,070 --> 00:35:04,700
Vajon valaha több, mint ez a sok stack frame?

459
00:35:04,700 --> 00:35:08,880
No. Mivel minden egyes alkalommal, amikor csinál egy könyörgés,

460
00:35:08,880 --> 00:35:10,770
rekurzív hívása a shuffle,

461
00:35:10,770 --> 00:35:13,950
osztjuk a mérete a felére.

462
00:35:13,950 --> 00:35:17,020
Így a maximális számú köteg képkockák mi valaha bármely pillanatban

463
00:35:17,020 --> 00:35:28,460
van nagyságrendű log n stack kereteket.

464
00:35:28,460 --> 00:35:42,460
Minden stack frame van állandó hely,

465
00:35:42,460 --> 00:35:44,410
és ezért a teljes összegét terület,

466
00:35:44,410 --> 00:35:49,240
maximális összege hely amit valaha is használni O (log n) space

467
00:35:49,240 --> 00:36:03,040
ahol n jelentése a napok száma.

468
00:36:03,040 --> 00:36:07,230
>> Nos, mindig kérdezd meg magadtól: "Tudunk jobbat?"

469
00:36:07,230 --> 00:36:12,390
És különösen, tudjuk csökkenteni, hogy ez egy probléma, amit már megoldott?

470
00:36:12,390 --> 00:36:20,040
Egy tipp: csak tárgyalt két másik probléma, mielőtt ez, és ez nem lesz shuffle.

471
00:36:20,040 --> 00:36:26,200
Mi lehet konvertálni a tőzsde problémát a maximális subarray problémát.

472
00:36:26,200 --> 00:36:40,100
Hogyan tudjuk ezt megtenni?

473
00:36:40,100 --> 00:36:42,570
Az egyik te? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, érthetetlen)

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

476
00:36:53,860 --> 00:36:59,940
Tehát a maximális subarray problémát,

477
00:36:59,940 --> 00:37:10,610
keresünk összeget több mint egy folyamatos subarray.

478
00:37:10,610 --> 00:37:16,230
És Emmy javaslatot, a készletek probléma,

479
00:37:16,230 --> 00:37:30,720
fontolja meg a változásokat, vagy a delták.

480
00:37:30,720 --> 00:37:37,440
És egy képet ez - ez az ára a készlet,

481
00:37:37,440 --> 00:37:42,610
de ha volt a különbség az egymást követő nap -

482
00:37:42,610 --> 00:37:45,200
úgy látjuk, hogy a legmagasabb árat, maximális profit tudtuk, hogy

483
00:37:45,200 --> 00:37:50,070
, ha vásárolunk itt és eladni itt.

484
00:37:50,070 --> 00:37:54,240
De nézzük meg a folyamatos - nézzük a subarray problémát.

485
00:37:54,240 --> 00:38:02,510
Tehát itt van, tudjuk, hogy - haladva itt van,

486
00:38:02,510 --> 00:38:08,410
van egy pozitív változás, aztán megy innen, hogy itt van egy negatív változás.

487
00:38:08,410 --> 00:38:14,220
De aztán, megy innen, hogy itt van egy óriási pozitív változást.

488
00:38:14,220 --> 00:38:20,930
És ezek a változások, hogy szeretnénk összegezni, hogy a végső eredmény.

489
00:38:20,930 --> 00:38:25,160
Akkor már több negatív változások itt.

490
00:38:25,160 --> 00:38:29,990
A legfontosabb, hogy csökkentsük a Stock probléma a mi maximális subarray probléma

491
00:38:29,990 --> 00:38:36,630
hogy fontolja meg a delta nap között.

492
00:38:36,630 --> 00:38:40,630
Így létre egy új tömböt nevű delták,

493
00:38:40,630 --> 00:38:43,000
inicializálni az első bejegyzés a 0,

494
00:38:43,000 --> 00:38:46,380
, majd ezt követően minden egyes delta (i), legyen az a különbség

495
00:38:46,380 --> 00:38:52,830
az én input array (i) és array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Aztán hívja rutin eljárás a maximális subarray

497
00:38:55,530 --> 00:39:01,500
halad a delta a tömböt.

498
00:39:01,500 --> 00:39:06,440
És mivel a maximális subarray lineáris idő,

499
00:39:06,440 --> 00:39:09,370
és ez a csökkenés, ez a folyamat létrehozásának a delta tömb,

500
00:39:09,370 --> 00:39:11,780
szintén lineáris idő,

501
00:39:11,780 --> 00:39:19,060
majd a végső megoldás az állományok O (n) munkát plus O (n) a munka, még mindig O (n) munkát.

502
00:39:19,060 --> 00:39:23,900
Tehát van egy lineáris idő megoldás a problémára.

503
00:39:23,900 --> 00:39:29,610
Mindenki érti ezt az átalakulást?

504
00:39:29,610 --> 00:39:32,140
>> Általában egy jó ötlet, hogy meg kell mindig

505
00:39:32,140 --> 00:39:34,290
van próbálja csökkenteni egy új probléma, hogy látsz.

506
00:39:34,290 --> 00:39:37,700
Ha úgy néz ki, ismerős egy régi probléma,

507
00:39:37,700 --> 00:39:39,590
próbálja csökkenteni, hogy egy régi probléma.

508
00:39:39,590 --> 00:39:41,950
És ha tudod használni minden eszközt, amit használni a régi probléma

509
00:39:41,950 --> 00:39:46,450
, hogy megoldja az új problémát.

510
00:39:46,450 --> 00:39:49,010
Szóval, hogy lezárja a műszaki interjúk kihívást jelent.

511
00:39:49,010 --> 00:39:52,280
Ezek a problémák valószínűleg néhány a több nehéz problémákat

512
00:39:52,280 --> 00:39:54,700
hogy lehet látni egy interjúban,

513
00:39:54,700 --> 00:39:57,690
így ha nem érti a problémát, hogy én csak fedezni, ez rendben van.

514
00:39:57,690 --> 00:40:01,080
Ezek közül néhány a nagyobb kihívást jelentő problémákat.

515
00:40:01,080 --> 00:40:03,050
Gyakorlás, gyakorlás, gyakorlás.

516
00:40:03,050 --> 00:40:08,170
Adtam egy csomó probléma a tájékoztatót, ezért feltétlenül ellenőrizze e meg.

517
00:40:08,170 --> 00:40:11,690
És sok szerencsét a interjút. Minden az én források beírás most ezt a linket,

518
00:40:11,690 --> 00:40:15,220
és az egyik magas rangú társaság felajánlotta, hogy csinál mock műszaki interjúk,

519
00:40:15,220 --> 00:40:22,050
így ha érdekel, email Will Yao meg az e-mail címre.

520
00:40:22,050 --> 00:40:26,070
Ha van kérdése, akkor kérdezzen.

521
00:40:26,070 --> 00:40:28,780
Van srácok kapcsolatos speciális kérdésekre vonatkozó műszaki interjúk

522
00:40:28,780 --> 00:40:38,440
vagy bármilyen problémát láttunk eddig?

523
00:40:38,440 --> 00:40:49,910
Oké. Hát, sok szerencsét a interjút.

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