1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminarium: Tekniska Intervjuer]

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

3
00:00:04,630 --> 00:00:08,910
[Detta är CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hej alla, jag Kenny. Jag är för närvarande en junior studerar datavetenskap.

5
00:00:12,420 --> 00:00:17,310
Jag är en före detta CS TF, och jag önskar att jag hade det när jag var underclassman,

6
00:00:17,310 --> 00:00:19,380
och det är därför jag ger detta seminarium.

7
00:00:19,380 --> 00:00:21,370
Så jag hoppas att ni uppskattar det.

8
00:00:21,370 --> 00:00:23,470
Seminariet handlar om tekniska intervjuer,

9
00:00:23,470 --> 00:00:26,650
och alla mina resurser kan hittas på den här länken,

10
00:00:26,650 --> 00:00:32,350
den här länken här, ett par resurser.

11
00:00:32,350 --> 00:00:36,550
Så jag gjorde en lista över problem, faktiskt, en hel del problem.

12
00:00:36,550 --> 00:00:40,800
Också en generell resurser där vi kan hitta tips

13
00:00:40,800 --> 00:00:42,870
om hur man förbereder för en intervju,

14
00:00:42,870 --> 00:00:46,470
tips om vad du ska göra under en verklig intervju,

15
00:00:46,470 --> 00:00:51,910
liksom hur man skall närma problem och resurser för framtida referens.

16
00:00:51,910 --> 00:00:53,980
Det är allt på nätet.

17
00:00:53,980 --> 00:00:58,290
Och bara för att inleda seminariet en ansvarsfriskrivning,

18
00:00:58,290 --> 00:01:00,690
så här ska inte - din intervju förberedelse

19
00:01:00,690 --> 00:01:02,800
bör inte begränsas till denna lista.

20
00:01:02,800 --> 00:01:04,750
Detta är bara tänkt att vara en guide,

21
00:01:04,750 --> 00:01:08,890
och du bör definitivt ta allt jag säger med en nypa salt,

22
00:01:08,890 --> 00:01:14,620
men även använda allt jag använde för att hjälpa dig i din intervju förberedelse.

23
00:01:14,620 --> 00:01:16,400
>> Jag ska skynda igenom de närmaste bilder

24
00:01:16,400 --> 00:01:18,650
så vi kan få de faktiska fallstudier.

25
00:01:18,650 --> 00:01:23,630
Strukturen för en intervju för en software engineering fältbrytning,

26
00:01:23,630 --> 00:01:26,320
typiskt är det 30 till 45 minuter,

27
00:01:26,320 --> 00:01:29,810
flera omgångar, beroende på företaget.

28
00:01:29,810 --> 00:01:33,090
Ofta du kommer att kodning på en whiteboard.

29
00:01:33,090 --> 00:01:35,960
Så en whiteboard som denna, men ofta i mindre skala.

30
00:01:35,960 --> 00:01:38,540
Om du har en telefon intervju, kommer du antagligen att använda

31
00:01:38,540 --> 00:01:44,030
antingen collabedit eller en Google Doc, så att de kan se du bor kodning

32
00:01:44,030 --> 00:01:46,500
medan du intervjuas över telefon.

33
00:01:46,500 --> 00:01:48,490
En intervju själv är typiskt 2 eller 3 problem

34
00:01:48,490 --> 00:01:50,620
testa dina kunskaper datavetenskap.

35
00:01:50,620 --> 00:01:54,490
Och det kommer nästan definitivt innebära kodning.

36
00:01:54,490 --> 00:01:59,540
De typer av frågor som du ser är oftast datastrukturer och algoritmer.

37
00:01:59,540 --> 00:02:02,210
Och att göra den här typen av problem,

38
00:02:02,210 --> 00:02:07,830
De kommer att fråga dig, liksom, är vad tid och rum komplexitet, Big O?

39
00:02:07,830 --> 00:02:09,800
Ofta också be högre nivå frågor,

40
00:02:09,800 --> 00:02:12,530
så utforma ett system,

41
00:02:12,530 --> 00:02:14,770
hur skulle du lägga ut din kod?

42
00:02:14,770 --> 00:02:18,370
Vilka gränssnitt, vilka klasser, vad moduler du har i ditt system,

43
00:02:18,370 --> 00:02:20,900
och hur dessa interagerar med varandra?

44
00:02:20,900 --> 00:02:26,130
Så datastrukturer och algoritmer samt utforma system.

45
00:02:26,130 --> 00:02:29,180
>> Några allmänna tips innan vi dyker in i våra fallstudier.

46
00:02:29,180 --> 00:02:32,300
Jag tror att den viktigaste regeln alltid tänka högt.

47
00:02:32,300 --> 00:02:36,980
Intervjun är tänkt att vara din chans att visa upp din tankeprocess.

48
00:02:36,980 --> 00:02:39,820
Poängen med intervjun är att intervjuaren att bedöma

49
00:02:39,820 --> 00:02:42,660
hur du tänker och hur du går igenom ett problem.

50
00:02:42,660 --> 00:02:45,210
Det värsta du kan göra är att vara tyst under hela intervjun.

51
00:02:45,210 --> 00:02:50,090
Det är bara inte bra.

52
00:02:50,090 --> 00:02:53,230
När du får en fråga, vill du också se till att du förstår frågan.

53
00:02:53,230 --> 00:02:55,350
Så upprepa frågan tillbaka med egna ord

54
00:02:55,350 --> 00:02:58,920
och försök att arbeta grundligt några enkla testfall

55
00:02:58,920 --> 00:03:01,530
se till att du förstår frågan.

56
00:03:01,530 --> 00:03:05,510
Arbeta igenom några testfall kan också ge dig en intuition om hur man kan lösa detta problem.

57
00:03:05,510 --> 00:03:11,210
Du kan även upptäcka några mönster för att hjälpa dig att lösa problemet.

58
00:03:11,210 --> 00:03:14,500
Deras stora tips är att inte bli frustrerad.

59
00:03:14,500 --> 00:03:17,060
Bli inte frustrerad.

60
00:03:17,060 --> 00:03:19,060
Intervjuer är utmanande, men det värsta du kan göra,

61
00:03:19,060 --> 00:03:23,330
förutom att vara tyst, är att vara synligt frustrerad.

62
00:03:23,330 --> 00:03:27,410
Du vill inte ge det intrycket att en intervjuare.

63
00:03:27,410 --> 00:03:33,960
En sak som du - så många människor, när de går in i en intervju,

64
00:03:33,960 --> 00:03:37,150
de försöker att försöka hitta den bästa lösningen först,

65
00:03:37,150 --> 00:03:39,950
när det verkligen, det finns oftast en alldeles uppenbart lösning.

66
00:03:39,950 --> 00:03:43,500
Det kan vara långsam, kan det vara ineffektivt, men du bör bara ange det,

67
00:03:43,500 --> 00:03:46,210
bara så att du har en utgångspunkt för att fungera bättre.

68
00:03:46,210 --> 00:03:48,270
Dessutom pekar ut lösningen är långsam, i termer av

69
00:03:48,270 --> 00:03:52,160
Big O tid komplexitet eller utrymme komplexitet,

70
00:03:52,160 --> 00:03:54,450
kommer att visa att intervjuaren att du förstår

71
00:03:54,450 --> 00:03:57,510
dessa frågor när du skriver kod.

72
00:03:57,510 --> 00:04:01,440
Så var inte rädd att komma med den enklaste algoritmen 1.

73
00:04:01,440 --> 00:04:04,950
och sedan arbeta bättre därifrån.

74
00:04:04,950 --> 00:04:09,810
Eventuella frågor hittills? Okej.

75
00:04:09,810 --> 00:04:11,650
>> Så låt oss dyka in vår första problemet.

76
00:04:11,650 --> 00:04:14,790
"Givet en rad n heltal, skriva en funktion som blandar arrayen

77
00:04:14,790 --> 00:04:20,209
på plats så att alla permutationer av de n heltalen är lika sannolika. "

78
00:04:20,209 --> 00:04:23,470
Och antar att du har tillgång till en slumpmässigt heltal generator

79
00:04:23,470 --> 00:04:30,980
som genererar ett heltal inom ett intervall från 0 till i, halv intervall.

80
00:04:30,980 --> 00:04:32,970
Förstår alla denna fråga?

81
00:04:32,970 --> 00:04:39,660
Jag ger dig en rad n heltal, och jag vill att du blanda det.

82
00:04:39,660 --> 00:04:46,050
I min katalog, skrev jag några program att visa vad jag menar.

83
00:04:46,050 --> 00:04:48,910
Jag ska blanda en mängd 20 element,

84
00:04:48,910 --> 00:04:52,490
från -10 till +9,

85
00:04:52,490 --> 00:04:57,050
och jag vill att du ska mata en lista som denna.

86
00:04:57,050 --> 00:05:02,890
Så det här är min sorterade inputuppställningen, och jag vill att du ska blanda det.

87
00:05:02,890 --> 00:05:07,070
Vi ska göra det igen.

88
00:05:07,070 --> 00:05:13,780
Förstår alla frågan? Okej.

89
00:05:13,780 --> 00:05:16,730
Så det är upp till dig.

90
00:05:16,730 --> 00:05:21,220
Vad är några idéer? Kan du göra det som n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Öppen för förslag.

92
00:05:34,400 --> 00:05:37,730
Okej. Så en idé, som föreslagits av Emmy,

93
00:05:37,730 --> 00:05:45,300
först beräkna ett slumptal, slumpmässigt heltal, i ett område från 0 till 20.

94
00:05:45,300 --> 00:05:49,840
Så antar vår grupp har en längd av 20.

95
00:05:49,840 --> 00:05:54,800
I vår diagram av 20 element,

96
00:05:54,800 --> 00:05:58,560
Detta är vårt bidrag array.

97
00:05:58,560 --> 00:06:04,590
Och nu är hennes förslag att skapa en ny array,

98
00:06:04,590 --> 00:06:08,440
så kommer detta att vara den utgående matrisen.

99
00:06:08,440 --> 00:06:12,880
Och baseras på den jag återvände från rand -

100
00:06:12,880 --> 00:06:17,580
så om jag var, låt oss säga, 17,

101
00:06:17,580 --> 00:06:25,640
kopiera den 17 elementet i det första läget.

102
00:06:25,640 --> 00:06:30,300
Nu måste vi ta bort - vi måste flytta alla element här

103
00:06:30,300 --> 00:06:36,920
över så att vi har en lucka i slutet och inga hål i mitten.

104
00:06:36,920 --> 00:06:39,860
Och nu har vi upprepa processen.

105
00:06:39,860 --> 00:06:46,360
Nu väljer vi en ny slumpmässigt heltal mellan 0 och 19.

106
00:06:46,360 --> 00:06:52,510
Vi har en ny jag här, och vi kopierar detta element i denna position.

107
00:06:52,510 --> 00:07:00,960
Då vi flytta objekt över och vi upprepar processen tills vi har vår fulla ny array.

108
00:07:00,960 --> 00:07:05,890
Vad är körtiden för denna algoritm?

109
00:07:05,890 --> 00:07:08,110
Nåväl, låt oss betrakta effekterna av detta.

110
00:07:08,110 --> 00:07:10,380
Vi skiftar varje element.

111
00:07:10,380 --> 00:07:16,800
När vi tar bort detta jag, vi flytta alla element efter det till vänster.

112
00:07:16,800 --> 00:07:21,600
Och det är en O (n) kostnad

113
00:07:21,600 --> 00:07:26,100
eftersom vad händer om vi tar bort det första elementet?

114
00:07:26,100 --> 00:07:29,670
Så för varje uttag, tar vi bort -

115
00:07:29,670 --> 00:07:32,170
varje uttag medför en O (n) drift,

116
00:07:32,170 --> 00:07:41,520
och eftersom vi har n flyttning leder detta till en O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Okej. Så bra start. Bra start.

118
00:07:49,550 --> 00:07:55,290
>> Ett annat förslag är att använda något som kallas Knuth shuffle,

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

120
00:07:57,540 --> 00:07:59,630
Och det är faktiskt en linjär tid shuffle.

121
00:07:59,630 --> 00:08:02,200
Och tanken är mycket lika.

122
00:08:02,200 --> 00:08:05,160
Återigen har vi vår inputuppställningen,

123
00:08:05,160 --> 00:08:08,580
men i stället för att använda två uppsättningar för vår ingång / utgång,

124
00:08:08,580 --> 00:08:13,590
vi använder den första delen av matrisen för att hålla reda på vår skyfflade del,

125
00:08:13,590 --> 00:08:18,400
och vi håller koll, och då lämnar vi resten av vår grupp för unshuffled delen.

126
00:08:18,400 --> 00:08:24,330
Så här är vad jag menar. Vi börjar med - vi väljer en i,

127
00:08:24,330 --> 00:08:30,910
en array från 0 till 20.

128
00:08:30,910 --> 00:08:36,150
Vår nuvarande pekare pekar på första indexet.

129
00:08:36,150 --> 00:08:39,590
Vi väljer några jag här

130
00:08:39,590 --> 00:08:42,740
och nu har vi byter.

131
00:08:42,740 --> 00:08:47,690
Så om detta var 5 och detta var 4,

132
00:08:47,690 --> 00:08:57,150
den resulterande matrisen har 5 här och 4 här.

133
00:08:57,150 --> 00:09:00,390
Och nu har vi notera en markör här.

134
00:09:00,390 --> 00:09:05,770
Allt till vänster är blandade,

135
00:09:05,770 --> 00:09:15,160
och allt till höger unshuffled.

136
00:09:15,160 --> 00:09:17,260
Och nu kan vi upprepa processen.

137
00:09:17,260 --> 00:09:25,210
Vi väljer en slumpmässig index mellan 1 och 20 nu.

138
00:09:25,210 --> 00:09:30,650
Så antar vår nya jag är här.

139
00:09:30,650 --> 00:09:39,370
Nu har vi byta detta jag med vår nuvarande ny position här.

140
00:09:39,370 --> 00:09:44,790
Så vi en byta fram och tillbaka så här.

141
00:09:44,790 --> 00:09:51,630
Låt mig ta upp koden för att göra det mer konkret.

142
00:09:51,630 --> 00:09:55,290
Vi börjar med vårt val av i -

143
00:09:55,290 --> 00:09:58,370
vi börjar med i lika med 0, plocka vi ett slumpmässigt läge j

144
00:09:58,370 --> 00:10:02,420
i unshuffled delen av matrisen, till i n-1.

145
00:10:02,420 --> 00:10:07,280
Så om jag är här, välj en slumpmässig index mellan här och resten av arrayen,

146
00:10:07,280 --> 00:10:12,410
och vi byter.

147
00:10:12,410 --> 00:10:17,550
Detta är koden som krävs för att blanda din array.

148
00:10:17,550 --> 00:10:21,670
Några frågor?

149
00:10:21,670 --> 00:10:25,530
>> Tja, en behövde fråga, varför är detta korrekt?

150
00:10:25,530 --> 00:10:28,360
Varför är varje permutation lika troligt?

151
00:10:28,360 --> 00:10:30,410
Och jag kommer inte att gå igenom bevis på detta,

152
00:10:30,410 --> 00:10:35,970
men många problem i datavetenskap kan bevisas genom induktion.

153
00:10:35,970 --> 00:10:38,520
Hur många av er känner till induktion?

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

155
00:10:40,590 --> 00:10:43,610
Så du kan bevisa riktigheten av denna algoritm genom enkel induktion,

156
00:10:43,610 --> 00:10:49,540
där din induktion hypotes skulle vara, antar att

157
00:10:49,540 --> 00:10:53,290
min Shuffle tillbaka varje permutation lika sannolika

158
00:10:53,290 --> 00:10:56,120
upp till det första jag elementen.

159
00:10:56,120 --> 00:10:58,300
Nu anser jag + 1.

160
00:10:58,300 --> 00:11:02,550
Och genom det sätt vi väljer vårt index j för att byta,

161
00:11:02,550 --> 00:11:05,230
detta leder till - och sedan utarbeta detaljerna,

162
00:11:05,230 --> 00:11:07,390
åtminstone en fullt bevis för varför detta Algoritmen återgår

163
00:11:07,390 --> 00:11:12,800
Varje permutation med lika sannolika sannolikhet.

164
00:11:12,800 --> 00:11:15,940
>> Okej, nästa problem.

165
00:11:15,940 --> 00:11:19,170
Så "ges en rad av heltal, positiv, noll, negativ,

166
00:11:19,170 --> 00:11:21,290
skriva en funktion som beräknar den maximala summan

167
00:11:21,290 --> 00:11:24,720
varje continueous subanordningen av inputuppställningen. "

168
00:11:24,720 --> 00:11:28,370
Ett exempel här är, i det fall där alla siffror är positiva,

169
00:11:28,370 --> 00:11:31,320
då närvarande det bästa valet är att ta hela uppsättningen.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, är lika med 10.

171
00:11:34,690 --> 00:11:36,780
När du har vissa negativa där,

172
00:11:36,780 --> 00:11:38,690
I det här fallet vill vi bara de två första

173
00:11:38,690 --> 00:11:44,590
eftersom valet -1 och / eller -3 kommer att föra vår summa ner.

174
00:11:44,590 --> 00:11:48,120
Ibland har vi kanske måste starta i mitten av fältet.

175
00:11:48,120 --> 00:11:53,500
Ibland vill vi välja någonting alls, det är bäst att inte ta något.

176
00:11:53,500 --> 00:11:56,490
Och ibland är det bättre att ta fallet,

177
00:11:56,490 --> 00:12:07,510
eftersom sak efter det är super stort. Så några idéer?

178
00:12:07,510 --> 00:12:10,970
(Elev, obegripligt) >> Ja.

179
00:12:10,970 --> 00:12:13,560
Anta att jag inte tar -1.

180
00:12:13,560 --> 00:12:16,170
Sedan antingen väljer jag 1.000 och 20.000,

181
00:12:16,170 --> 00:12:18,630
eller jag väljer bara 3 miljarder.

182
00:12:18,630 --> 00:12:20,760
Tja, är det bästa valet för att ta alla nummer.

183
00:12:20,760 --> 00:12:24,350
Detta -1, trots att negativ,

184
00:12:24,350 --> 00:12:31,340
hela summan är bättre än var jag inte ta -1.

185
00:12:31,340 --> 00:12:36,460
Så en av de tips jag nämnde tidigare var att ange tydligt uppenbara

186
00:12:36,460 --> 00:12:40,540
och den brute force lösningen först.

187
00:12:40,540 --> 00:12:44,340
Vilken är den brute force lösningen i detta problem? Ja?

188
00:12:44,340 --> 00:12:46,890
[Jane] Jag tror det brute force lösningen

189
00:12:46,890 --> 00:12:52,600
skulle vara att lägga upp alla möjliga kombinationer (obegripliga).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okej. Så Jane idé är att ta alla möjliga -

191
00:12:58,250 --> 00:13:01,470
Jag är parafras - är att ta alla möjliga kontinuerlig subsystemet,

192
00:13:01,470 --> 00:13:07,840
beräkna sin summa, och sedan ta högst alla möjliga kontinuerliga subanordningar.

193
00:13:07,840 --> 00:13:13,310
Vad identifierar en subarray i min inputuppställningen?

194
00:13:13,310 --> 00:13:17,380
Liksom, vad två saker behöver jag? Ja?

195
00:13:17,380 --> 00:13:19,970
(Elev, obegripligt) >> höger.

196
00:13:19,970 --> 00:13:22,130
En lägre gräns för index och en övre gräns index

197
00:13:22,130 --> 00:13:28,300
unikt bestämmer en kontinuerlig undersystem.

198
00:13:28,300 --> 00:13:31,400
[Kvinnlig student] Är vi uppskatta att det är en rad unika nummer?

199
00:13:31,400 --> 00:13:34,280
[Yu] Nej Så hennes fråga, vi antar vår array -

200
00:13:34,280 --> 00:13:39,000
är vår matris alla unika nummer, och svaret är nej.

201
00:13:39,000 --> 00:13:43,390
>> Om vi ​​använder vår brute force-lösning, då start / slut index

202
00:13:43,390 --> 00:13:47,200
unikt avgör vår ständiga subsystemet.

203
00:13:47,200 --> 00:13:51,680
Så om vi upprepa för alla möjliga start poster,

204
00:13:51,680 --> 00:13:58,320
och för alla slut poster> eller = för att starta, och <n,

205
00:13:58,320 --> 00:14:05,570
du beräkna summan, och sedan tar vi det högsta belopp vi har sett hittills.

206
00:14:05,570 --> 00:14:07,880
Är det klart?

207
00:14:07,880 --> 00:14:12,230
Vad är den stora O av denna lösning?

208
00:14:12,230 --> 00:14:16,660
Tidsmässigt.

209
00:14:16,660 --> 00:14:18,860
Inte helt n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Notera att vi itererar från 0 till n,

211
00:14:25,250 --> 00:14:27,520
så det är en för slinga.

212
00:14:27,520 --> 00:14:35,120
Vi iterera igen från nästan början till slut, en annan för slinga.

213
00:14:35,120 --> 00:14:37,640
Och nu, inom denna måste vi summera varje post,

214
00:14:37,640 --> 00:14:43,810
så det är en annan för slinga. Så vi har tre nästlade loopar, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okej. Detta går som en startpunkt.

216
00:14:46,560 --> 00:14:53,180
Vår lösning är inte värre än n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Förstår alla de brute force lösningen?

218
00:14:55,480 --> 00:14:59,950
>> Okej. En bättre lösning är att använda en idé som kallas dynamisk programmering.

219
00:14:59,950 --> 00:15:03,040
Om du tar CS124, vilket Algoritmer och datastrukturer,

220
00:15:03,040 --> 00:15:05,680
du kommer att bli väl förtrogen med denna teknik.

221
00:15:05,680 --> 00:15:12,190
Och tanken är att försöka att bygga upp lösningar till mindre problem först.

222
00:15:12,190 --> 00:15:17,990
Vad jag menar med detta är, har vi för närvarande att oroa två saker: start och slut.

223
00:15:17,990 --> 00:15:29,340
Och det är irriterande. Tänk om vi kunde bli av med en av dessa parametrar?

224
00:15:29,340 --> 00:15:32,650
En idé är att - vi med tanke på vår ursprungliga problemet,

225
00:15:32,650 --> 00:15:37,470
hitta den maximala summan av alla subsystemet i intervallet [O, N-1].

226
00:15:37,470 --> 00:15:47,400
Och nu har vi en ny delproblem, där vi vet, i vår nuvarande index i,

227
00:15:47,400 --> 00:15:52,520
Vi vet att vi måste sluta där. Vår subarray måste sluta på det aktuella indexet.

228
00:15:52,520 --> 00:15:57,640
Så den återstående problemet är, bör där vi börjar vår subarray?

229
00:15:57,640 --> 00:16:05,160
Verkar denna mening? Okej.

230
00:16:05,160 --> 00:16:12,030
Så jag har kodat upp detta, och låt oss titta på vad detta innebär.

231
00:16:12,030 --> 00:16:16,230
I codirectory finns det ett program som heter undersystem,

232
00:16:16,230 --> 00:16:19,470
och det tar flera poster,

233
00:16:19,470 --> 00:16:25,550
och den returnerar den maximala subarray summan i min blandade lista.

234
00:16:25,550 --> 00:16:29,920
Så i detta fall är vår maximala undersystemet 3.

235
00:16:29,920 --> 00:16:34,850
Och det har tagit genom att bara använda 2 och 1.

236
00:16:34,850 --> 00:16:38,050
Vi kör det igen. Det är också 3.

237
00:16:38,050 --> 00:16:40,950
Men den här gången, notera hur vi fick 3.

238
00:16:40,950 --> 00:16:46,690
Vi tog - vi bara ta 3 själv

239
00:16:46,690 --> 00:16:49,980
eftersom det är omgivet av negativ på båda sidor,

240
00:16:49,980 --> 00:16:55,080
vilket kommer att medföra en summa <3.

241
00:16:55,080 --> 00:16:57,820
Låt oss köra på 10 punkter.

242
00:16:57,820 --> 00:17:03,200
Den här gången är det 7 tar vi den ledande 3 och 4.

243
00:17:03,200 --> 00:17:09,450
Den här gången är det 8, och vi får att genom att ta 1, 4 och 3.

244
00:17:09,450 --> 00:17:16,310
Så för att ge dig en intuition om hur vi kan lösa detta omvandlas problemet,

245
00:17:16,310 --> 00:17:18,890
låt oss ta en titt på denna subarray.

246
00:17:18,890 --> 00:17:23,460
Vi ges denna ingång array, och vi vet att svaret är 8.

247
00:17:23,460 --> 00:17:26,359
Vi tar 1, 4 och 3.

248
00:17:26,359 --> 00:17:29,090
Men låt oss titta på hur vi faktiskt fick det svaret.

249
00:17:29,090 --> 00:17:34,160
Låt oss titta på den maximala subarray som slutade på alla dessa index.

250
00:17:34,160 --> 00:17:40,780
Vad är den maximala subarray som måste sluta på den första positionen?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. >> Zero. Bara tar inte -5.

252
00:17:46,310 --> 00:17:50,210
Här kommer att bli 0 också. Ja?

253
00:17:50,210 --> 00:17:56,470
(Elev, obegripligt)

254
00:17:56,470 --> 00:17:58,960
[Yu] Åh, förlåt, det är en -3.

255
00:17:58,960 --> 00:18:03,220
Så detta är en 2, är detta en -3.

256
00:18:03,220 --> 00:18:08,690
Okej. Så -4, vad är den maximala subarray att avsluta den positionen

257
00:18:08,690 --> 00:18:12,910
där -4 är? Noll.

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

259
00:18:22,570 --> 00:18:28,060
Nu måste jag sluta vid den plats där -2 är.

260
00:18:28,060 --> 00:18:39,330
Så 6, 5, 7, och den sista är 4.

261
00:18:39,330 --> 00:18:43,480
Att veta att dessa är mina inlägg

262
00:18:43,480 --> 00:18:48,130
för den transformerade problemet där jag måste sluta på alla dessa index,

263
00:18:48,130 --> 00:18:51,410
då min sista svaret är bara, ta ett svep över,

264
00:18:51,410 --> 00:18:53,580
och ta det maximala antalet.

265
00:18:53,580 --> 00:18:55,620
Så i det här fallet är det 8.

266
00:18:55,620 --> 00:19:00,010
Detta innebär att den maximala subanordningen slutar vid detta index,

267
00:19:00,010 --> 00:19:04,970
och började någonstans innan.

268
00:19:04,970 --> 00:19:09,630
Förstår alla detta transformerade subarray?

269
00:19:09,630 --> 00:19:22,160
>> Okej. Nåväl, låt oss räkna ut återfall för detta.

270
00:19:22,160 --> 00:19:27,990
Låt oss betrakta bara de första posterna.

271
00:19:27,990 --> 00:19:35,930
Så här var 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Och då var det en -2 här, och som förde det ner till 6.

273
00:19:39,790 --> 00:19:50,800
Så om jag ringer posten i position i delproblem (i),

274
00:19:50,800 --> 00:19:54,910
Hur kan jag använda svaret på en tidigare delproblem

275
00:19:54,910 --> 00:19:59,360
att besvara denna delproblem?

276
00:19:59,360 --> 00:20:04,550
Om jag tittar på, låt oss säga, den här posten.

277
00:20:04,550 --> 00:20:09,190
Hur kan jag beräkna svaret 6 genom att titta på

278
00:20:09,190 --> 00:20:18,780
en kombination av denna array och svaren på tidigare delproblem i denna array? Ja?

279
00:20:18,780 --> 00:20:22,800
[Kvinnlig student] Du tar rad summor

280
00:20:22,800 --> 00:20:25,430
i positionen precis innan det, så det 8,

281
00:20:25,430 --> 00:20:32,170
och sedan lägga till den aktuella subproblemet.

282
00:20:32,170 --> 00:20:36,460
[Yu] Så hennes förslag är att titta på dessa två siffror,

283
00:20:36,460 --> 00:20:40,090
detta antal och detta antal.

284
00:20:40,090 --> 00:20:50,130
Så detta 8 hänvisar till svaret på subproblemet (i - 1).

285
00:20:50,130 --> 00:20:57,300
Och låt oss kalla min A. inputuppställningen

286
00:20:57,300 --> 00:21:01,470
För att hitta en maximal undersystem som slutar vid position i,

287
00:21:01,470 --> 00:21:03,980
Jag har två val: Jag kan antingen fortsätta subarray

288
00:21:03,980 --> 00:21:09,790
som slutade på föregående index, eller starta en ny array.

289
00:21:09,790 --> 00:21:14,190
Om jag skulle fortsätta subarray som började i föregående index,

290
00:21:14,190 --> 00:21:19,260
då det högsta belopp jag kan uppnå är svaret på den föregående subproblemet

291
00:21:19,260 --> 00:21:24,120
plus aktuella arrayen posten.

292
00:21:24,120 --> 00:21:27,550
Men har jag också valet att starta ett nytt undersystem,

293
00:21:27,550 --> 00:21:30,830
i vilket fall summan är 0.

294
00:21:30,830 --> 00:21:42,860
Så svaret är max 0, delproblem i - 1, plus den aktuella matrisen posten.

295
00:21:42,860 --> 00:21:46,150
Gör denna återkommande mening?

296
00:21:46,150 --> 00:21:50,840
Vår återkommande, som vi just upptäckt är delproblem i

297
00:21:50,840 --> 00:21:54,740
är lika med den högsta av föregående subproblemet plus min nuvarande uppsättning inträde,

298
00:21:54,740 --> 00:22:01,490
vilket betyder att fortsätta den tidigare subsystemet,

299
00:22:01,490 --> 00:22:07,250
eller 0, starta en ny undergrupp på min nuvarande index.

300
00:22:07,250 --> 00:22:10,060
Och när vi byggt upp denna tabell av lösningar, då vårt slutgiltiga svar,

301
00:22:10,060 --> 00:22:13,950
bara göra en linjär sveper över subproblemet array

302
00:22:13,950 --> 00:22:19,890
och ta det maximala antalet.

303
00:22:19,890 --> 00:22:23,330
Detta är en exakt tillämpning av det jag just sa.

304
00:22:23,330 --> 00:22:27,320
Så vi skapar en ny delproblem array, delproblem.

305
00:22:27,320 --> 00:22:32,330
Den första posten är antingen 0 eller den första posten, den högsta av dessa två.

306
00:22:32,330 --> 00:22:35,670
Och för resten av delproblem

307
00:22:35,670 --> 00:22:39,810
Vi använder exakt upprepning vi just upptäckt.

308
00:22:39,810 --> 00:22:49,960
Nu har vi beräkna maximalt våra delproblem array, och det är vårt slutgiltiga svar.

309
00:22:49,960 --> 00:22:54,130
>> Så hur mycket utrymme vi använder i denna algoritm?

310
00:22:54,130 --> 00:23:01,470
Om du bara har tagit CS50, då du kanske inte har diskuterat utrymme mycket.

311
00:23:01,470 --> 00:23:07,750
Tja, är en sak att konstatera att jag ringde malloc här med storlek N.

312
00:23:07,750 --> 00:23:13,590
Vad tyder på att för dig?

313
00:23:13,590 --> 00:23:17,450
Denna algoritm använder linjär utrymme.

314
00:23:17,450 --> 00:23:21,030
Kan vi göra bättre?

315
00:23:21,030 --> 00:23:30,780
Finns det något som du märker att är onödigt att beräkna det slutliga svaret?

316
00:23:30,780 --> 00:23:33,290
Jag antar att en bättre fråga är, vilken information

317
00:23:33,290 --> 00:23:40,680
behöver vi inte bära hela vägen till slutet?

318
00:23:40,680 --> 00:23:44,280
Om vi ​​nu tittar på dessa två linjer,

319
00:23:44,280 --> 00:23:47,720
Vi bryr sig bara om den tidigare subproblemet,

320
00:23:47,720 --> 00:23:50,910
och vi bryr sig bara om det maximala som vi någonsin har sett hittills.

321
00:23:50,910 --> 00:23:53,610
För att beräkna vårt slutgiltiga svar, behöver vi inte hela uppsättningen.

322
00:23:53,610 --> 00:23:57,450
Vi behöver bara den sista siffran två sista siffrorna.

323
00:23:57,450 --> 00:24:02,630
Senaste numret för subproblemet array, och sista numret för maximal.

324
00:24:02,630 --> 00:24:07,380
Så i själva verket kan vi smälta dessa slingor tillsammans

325
00:24:07,380 --> 00:24:10,460
och gå från linjär utrymme till konstant utrymme.

326
00:24:10,460 --> 00:24:15,830
Aktuell summa hittills, här ersätter roll subproblemet, vår subproblemet array.

327
00:24:15,830 --> 00:24:20,020
Så nuvarande summa, hittills, är svaret på den föregående subproblemet.

328
00:24:20,020 --> 00:24:23,450
Och den summan hittills ersätter vår max.

329
00:24:23,450 --> 00:24:28,100
Vi beräknar den maximala som vi går tillsammans.

330
00:24:28,100 --> 00:24:30,890
Och så går vi från linjär utrymme till konstant utrymme,

331
00:24:30,890 --> 00:24:36,650
och vi har också en linjär lösning för vår subarray problem.

332
00:24:36,650 --> 00:24:40,740
>> Dessa typer av frågor du kommer att få under en intervju.

333
00:24:40,740 --> 00:24:44,450
Vad är klockan komplexitet, vad är det utrymme komplexitet?

334
00:24:44,450 --> 00:24:50,600
Kan du göra det bättre? Finns det saker som är onödigt att hålla runt?

335
00:24:50,600 --> 00:24:55,270
Jag gjorde detta för att markera analyser som du bör ta på egen hand

336
00:24:55,270 --> 00:24:57,400
som du går igenom dessa problem.

337
00:24:57,400 --> 00:25:01,710
Alltid fråga dig själv: "Kan jag göra bättre?"

338
00:25:01,710 --> 00:25:07,800
I själva verket kan vi göra bättre än så här?

339
00:25:07,800 --> 00:25:10,730
Sortera på en kuggfråga. Du kan inte, eftersom du måste

340
00:25:10,730 --> 00:25:13,590
åtminstone läsa ingången till problemet.

341
00:25:13,590 --> 00:25:15,570
Så det faktum att du måste åtminstone läsa ingången till problemet

342
00:25:15,570 --> 00:25:19,580
innebär att du inte kan göra bättre än linjär tid,

343
00:25:19,580 --> 00:25:22,870
och du kan inte göra bättre än konstant utrymme.

344
00:25:22,870 --> 00:25:27,060
Så detta är i själva verket den bästa lösningen på detta problem.

345
00:25:27,060 --> 00:25:33,040
Frågor? Okej.

346
00:25:33,040 --> 00:25:35,190
>> Aktiemarknaden problem:

347
00:25:35,190 --> 00:25:38,350
"Givet en rad n heltal, positiv, noll eller negativ,

348
00:25:38,350 --> 00:25:41,680
som representerar priset på en aktie under n dagar,

349
00:25:41,680 --> 00:25:44,080
skriva en funktion för att beräkna den maximala vinsten du kan göra

350
00:25:44,080 --> 00:25:49,350
med tanke på att du köper och säljer exakt 1 lager inom dessa n dag. "

351
00:25:49,350 --> 00:25:51,690
I huvudsak vill vi köpa billigt, sälj dyrt.

352
00:25:51,690 --> 00:25:58,580
Och vi vill räkna ut det bästa resultatet vi kan göra.

353
00:25:58,580 --> 00:26:11,500
Att gå tillbaka till mitt tips, vad är omedelbart klar, enklaste svaret, men det är långsam?

354
00:26:11,500 --> 00:26:17,690
Ja? (Elev, obegripligt) >> Ja.

355
00:26:17,690 --> 00:26:21,470
>> Så du skulle bara gå igenom och titta på aktiekurserna

356
00:26:21,470 --> 00:26:30,550
vid varje tidpunkt, (ohörbart).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okej, så hennes lösning - hennes förslag av datorer

358
00:26:33,990 --> 00:26:37,380
det lägsta och beräkna den högsta fungerar inte nödvändigtvis

359
00:26:37,380 --> 00:26:42,470
eftersom den högsta kan inträffa innan den lägsta.

360
00:26:42,470 --> 00:26:47,340
Så vad är brute force lösningen på detta problem?

361
00:26:47,340 --> 00:26:53,150
Vilka är de två saker som jag behöver för att unikt fastställa vinsten jag gör? Rätt.

362
00:26:53,150 --> 00:26:59,410
Den brute force lösningen är - Åh, så är George förslag vi behöver bara två dagar

363
00:26:59,410 --> 00:27:02,880
att entydigt fastställa vinsten på dessa två dagar.

364
00:27:02,880 --> 00:27:06,660
Så vi beräkna varje par, vilja köpa / sälja,

365
00:27:06,660 --> 00:27:12,850
beräkna den vinst, som kan vara negativt eller positivt eller noll.

366
00:27:12,850 --> 00:27:18,000
Beräkna den maximala vinst som vi gör efter iteration över alla par dagar.

367
00:27:18,000 --> 00:27:20,330
Det kommer att vara vårt slutgiltiga svar.

368
00:27:20,330 --> 00:27:25,730
Och denna lösning blir O (n ^ 2), eftersom det är n välja två par -

369
00:27:25,730 --> 00:27:30,270
dagar som du kan välja mellan sista dagarna.

370
00:27:30,270 --> 00:27:32,580
Okej, så jag tänker inte gå över brute force lösningen här.

371
00:27:32,580 --> 00:27:37,420
Jag ska berätta för er att det finns en n log n-lösning.

372
00:27:37,420 --> 00:27:45,550
Vilken algoritm vet du nu det är n log n?

373
00:27:45,550 --> 00:27:50,730
Det är inte en kuggfråga.

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

375
00:27:54,790 --> 00:27:57,760
och i själva verket är ett sätt att lösa detta problem att använda

376
00:27:57,760 --> 00:28:04,400
en sammanslagning slags slags idé som kallas i allmänhet söndra och härska.

377
00:28:04,400 --> 00:28:07,570
Och tanken är som följer.

378
00:28:07,570 --> 00:28:12,400
Du vill beräkna den bästa köp / sälj par i den vänstra halvan.

379
00:28:12,400 --> 00:28:16,480
Hitta det bästa resultatet du kan göra, bara med den första n under två dagar.

380
00:28:16,480 --> 00:28:19,780
Då du vill oompute bästa köp / sälj par på den högra halvan,

381
00:28:19,780 --> 00:28:23,930
så att den sista n över två dagar.

382
00:28:23,930 --> 00:28:32,400
Och nu är frågan, hur ska vi slå ihop dessa lösningar tillsammans igen?

383
00:28:32,400 --> 00:28:36,320
Ja? (Elev, obegripligt)

384
00:28:36,320 --> 00:28:49,890
>> Okej. Så låt mig rita en bild.

385
00:28:49,890 --> 00:29:03,870
Ja? (George, obegripligt)

386
00:29:03,870 --> 00:29:06,450
>> Exakt. Georges lösning är exakt rätt.

387
00:29:06,450 --> 00:29:10,040
Så hans förslag är först beräkna den bästa köp / sälj-par,

388
00:29:10,040 --> 00:29:16,050
och som förekommer i den vänstra halvan, så låt oss kalla det vänster, vänster.

389
00:29:16,050 --> 00:29:20,790
Bästa köp / sälj par som sker i den högra halvan.

390
00:29:20,790 --> 00:29:25,180
Men om vi bara jämfört dessa två siffror, vi missar målet

391
00:29:25,180 --> 00:29:30,460
där vi köper här och säljer någonstans i den högra halvan.

392
00:29:30,460 --> 00:29:33,810
Vi köper i den vänstra halvan, sälja i den högra halvan.

393
00:29:33,810 --> 00:29:38,490
Och det bästa sättet att beräkna den bästa köp / sälj-par som sträcker sig över båda halvorna

394
00:29:38,490 --> 00:29:43,480
är att beräkna det minsta här och beräkna maximala här

395
00:29:43,480 --> 00:29:45,580
och ta deras skillnad.

396
00:29:45,580 --> 00:29:50,850
Så två fall där köp / sälj par förekommer bara här,

397
00:29:50,850 --> 00:30:01,910
bara här, eller på båda halvorna definieras av dessa tre nummer.

398
00:30:01,910 --> 00:30:06,450
Så vår algoritm för att slå ihop våra lösningar tillsammans igen,

399
00:30:06,450 --> 00:30:08,350
Vi vill beräkna den bästa köp / sälj-par

400
00:30:08,350 --> 00:30:13,120
där vi köper på den vänstra halvan och sälja på den högra halvan.

401
00:30:13,120 --> 00:30:16,740
Och det bästa sättet att göra det är att beräkna det lägsta priset under första halvåret,

402
00:30:16,740 --> 00:30:20,360
det högsta priset i den högra halvan, och ta deras skillnad.

403
00:30:20,360 --> 00:30:25,390
De resulterande tre vinster dessa tre siffror, tar du högst tre,

404
00:30:25,390 --> 00:30:32,720
och det är det bästa resultatet du kan göra över dessa första och sista dagarna.

405
00:30:32,720 --> 00:30:36,940
Här de viktiga linjerna i rött.

406
00:30:36,940 --> 00:30:41,160
Detta är ett rekursivt anrop till beräkna svaret i den vänstra halvan.

407
00:30:41,160 --> 00:30:44,760
Detta är ett rekursivt anrop till beräkna svaret i den högra halvan.

408
00:30:44,760 --> 00:30:50,720
Dessa två för slingor beräkna min och max på vänster och höger halv, respektive.

409
00:30:50,720 --> 00:30:54,970
Nu har jag beräkna den vinst som sträcker sig över båda halvorna,

410
00:30:54,970 --> 00:31:00,530
och det slutliga svaret är maximalt av dessa tre.

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

412
00:31:04,120 --> 00:31:06,420
>> Så, visst, vi har en algoritm, men den större frågan är,

413
00:31:06,420 --> 00:31:08,290
Vad är klockan komplexiteten i denna?

414
00:31:08,290 --> 00:31:16,190
Och anledningen till att jag nämnde merge sort är att denna form av delar svaret

415
00:31:16,190 --> 00:31:19,200
i två och sedan slå ihop våra lösningar tillsammans igen

416
00:31:19,200 --> 00:31:23,580
är exakt den form av sammanslagning slag.

417
00:31:23,580 --> 00:31:33,360
Så låt mig gå igenom varaktighet.

418
00:31:33,360 --> 00:31:41,340
Om vi ​​definierat en funktion t (n) vara antalet steg

419
00:31:41,340 --> 00:31:50,010
för n dagar,

420
00:31:50,010 --> 00:31:54,350
våra två rekursiva anrop

421
00:31:54,350 --> 00:32:00,460
vardera kommer att kosta t (n / 2),

422
00:32:00,460 --> 00:32:03,540
och det finns två av dessa samtal.

423
00:32:03,540 --> 00:32:10,020
Nu måste jag beräkna minimum den vänstra halvan,

424
00:32:10,020 --> 00:32:17,050
som jag kan göra i N / 2 tid, plus maximalt den högra halvan.

425
00:32:17,050 --> 00:32:20,820
Så detta är bara n.

426
00:32:20,820 --> 00:32:25,050
Och sedan plus någon konstant arbete.

427
00:32:25,050 --> 00:32:27,770
Och denna återkommande ekvation

428
00:32:27,770 --> 00:32:35,560
är exakt upprepning ekvationen för sammanfogningen sorteringen.

429
00:32:35,560 --> 00:32:39,170
Och vi vet alla att merge sort är n log n tid.

430
00:32:39,170 --> 00:32:46,880
Därför är vår algoritm även n log n tid.

431
00:32:46,880 --> 00:32:52,220
Gör denna iteration mening?

432
00:32:52,220 --> 00:32:55,780
Bara en kort resumé av detta:

433
00:32:55,780 --> 00:32:59,170
T (n) är antalet steg för att beräkna maximal vinst

434
00:32:59,170 --> 00:33:02,750
under loppet av n dagar.

435
00:33:02,750 --> 00:33:06,010
Det sätt vi dela upp våra rekursiva anrop

436
00:33:06,010 --> 00:33:11,980
är genom att ringa vår lösning på de första n / 2 dagar,

437
00:33:11,980 --> 00:33:14,490
så det är ett samtal,

438
00:33:14,490 --> 00:33:16,940
och då kallar vi igen på den andra halvan.

439
00:33:16,940 --> 00:33:20,440
Så det är två samtal.

440
00:33:20,440 --> 00:33:25,310
Och då finner vi ett minimum på den vänstra halvan, som vi kan göra i linjär tid,

441
00:33:25,310 --> 00:33:29,010
hitta maximalt den högra halvan, som vi kan göra i linjär tid.

442
00:33:29,010 --> 00:33:31,570
Så n / 2 + n / 2 är enbart n.

443
00:33:31,570 --> 00:33:36,020
Sedan har vi någon konstant arbete, vilket är som att göra aritmetik.

444
00:33:36,020 --> 00:33:39,860
Denna återkommande ekvation är exakt upprepning ekvationen för sammanfogningen sorteringen.

445
00:33:39,860 --> 00:33:55,490
Därför är vår shuffle algoritm också n log n.

446
00:33:55,490 --> 00:33:58,520
Så hur mycket utrymme använder vi?

447
00:33:58,520 --> 00:34:04,910
Låt oss gå tillbaka till koden.

448
00:34:04,910 --> 00:34:09,420
>> En bättre fråga är, hur många stack ramar vi någonsin vid en given tidpunkt?

449
00:34:09,420 --> 00:34:11,449
Eftersom vi använder rekursion,

450
00:34:11,449 --> 00:34:23,530
Antalet stack ramar avgör vårt utrymme användning.

451
00:34:23,530 --> 00:34:29,440
Låt oss betrakta n = 8.

452
00:34:29,440 --> 00:34:36,889
Vi kallar Blandning på 8,

453
00:34:36,889 --> 00:34:41,580
som kommer att kräva Blanda de första fyra posterna,

454
00:34:41,580 --> 00:34:46,250
som kommer att kräva en shuffle på de första två posterna.

455
00:34:46,250 --> 00:34:51,550
Så vår stack är - det är vår stack.

456
00:34:51,550 --> 00:34:54,980
Och då kallar vi blanda igen på 1,

457
00:34:54,980 --> 00:34:58,070
och det är vad vår bas fall är, så vi omedelbart återvända.

458
00:34:58,070 --> 00:35:04,700
Har vi någonsin har mer än så här många stack ramar?

459
00:35:04,700 --> 00:35:08,880
Nej Eftersom varje gång vi gör en åkallan,

460
00:35:08,880 --> 00:35:10,770
en rekursiv åkallan att blanda,

461
00:35:10,770 --> 00:35:13,950
Vi delar vår storlek i halv.

462
00:35:13,950 --> 00:35:17,020
Så det maximala antalet stack ramar vi någonsin vid en given tidpunkt

463
00:35:17,020 --> 00:35:28,460
är i storleksordningen av log n stack ramar.

464
00:35:28,460 --> 00:35:42,460
Varje stapel ram har konstant utrymme,

465
00:35:42,460 --> 00:35:44,410
och därför den totala utrymme,

466
00:35:44,410 --> 00:35:49,240
det maximala utrymme vi någonsin använder är O (log n) plats

467
00:35:49,240 --> 00:36:03,040
där n är antalet dagar.

468
00:36:03,040 --> 00:36:07,230
>> Nu, alltid fråga dig själv, "Kan vi göra bättre?"

469
00:36:07,230 --> 00:36:12,390
Och i synnerhet, kan vi minska detta ett problem som vi redan har löst?

470
00:36:12,390 --> 00:36:20,040
Ett tips: vi bara diskuterat två andra problem inför detta, och det kommer inte att bli shuffle.

471
00:36:20,040 --> 00:36:26,200
Vi kan omvandla detta problem aktiemarknaden i den maximala subarray problemet.

472
00:36:26,200 --> 00:36:40,100
Hur kan vi göra det?

473
00:36:40,100 --> 00:36:42,570
En av er? Emmy?

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

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

476
00:36:53,860 --> 00:36:59,940
Så maximala subsystemet problemet,

477
00:36:59,940 --> 00:37:10,610
Vi letar efter en summa under en sammanhängande undersystem.

478
00:37:10,610 --> 00:37:16,230
Och Emmy förslag för bestånden problemet,

479
00:37:16,230 --> 00:37:30,720
överväga förändringar eller deltan.

480
00:37:30,720 --> 00:37:37,440
Och en bild av detta är - detta är priset på en aktie,

481
00:37:37,440 --> 00:37:42,610
men om vi tog skillnaden mellan varje rad dag -

482
00:37:42,610 --> 00:37:45,200
så ser vi att det högsta priset, maximal vinst vi skulle kunna göra

483
00:37:45,200 --> 00:37:50,070
är om vi köper här och säljer här.

484
00:37:50,070 --> 00:37:54,240
Men låt oss titta på den kontinuerliga - låt oss titta på subarray problemet.

485
00:37:54,240 --> 00:38:02,510
Så här kan vi göra - gå härifrån till hit,

486
00:38:02,510 --> 00:38:08,410
Vi har en positiv förändring, och sedan gå härifrån till hit har vi en negativ förändring.

487
00:38:08,410 --> 00:38:14,220
Men sedan, går härifrån till hit har vi en enorm positiv förändring.

488
00:38:14,220 --> 00:38:20,930
Och det är dessa förändringar som vi vill summera för att få vår slutliga resultatet.

489
00:38:20,930 --> 00:38:25,160
Sedan har vi mer negativa förändringar här.

490
00:38:25,160 --> 00:38:29,990
Nyckeln till att minska vårt lager problem i vår maximala subarray problem

491
00:38:29,990 --> 00:38:36,630
är att betrakta deltan mellan dagarna.

492
00:38:36,630 --> 00:38:40,630
Så vi skapar en ny array med namnet deltan,

493
00:38:40,630 --> 00:38:43,000
initiera den första posten som 0,

494
00:38:43,000 --> 00:38:46,380
och sedan för varje delta (i), låt det vara skillnaden

495
00:38:46,380 --> 00:38:52,830
min inputuppställningen (i), och matrisen (i - 1).

496
00:38:52,830 --> 00:38:55,530
Sedan kallar vi vår rutin för en maximal undersystem

497
00:38:55,530 --> 00:39:01,500
passerar i en Deltas array.

498
00:39:01,500 --> 00:39:06,440
Och eftersom maximal subarray är linjär tid,

499
00:39:06,440 --> 00:39:09,370
och denna minskning, denna process för att skapa denna delta array,

500
00:39:09,370 --> 00:39:11,780
är också linjär tid,

501
00:39:11,780 --> 00:39:19,060
då den slutliga lösningen för bestånd är O (n) arbete plus O (n) arbete är fortfarande O (n) arbete.

502
00:39:19,060 --> 00:39:23,900
Så vi har en linjär tid lösningen på våra problem.

503
00:39:23,900 --> 00:39:29,610
Förstår alla denna omvandling?

504
00:39:29,610 --> 00:39:32,140
>> I allmänhet en bra idé att du alltid ska ha

505
00:39:32,140 --> 00:39:34,290
är att försöka minska ett nytt problem som du ser.

506
00:39:34,290 --> 00:39:37,700
Om det ser bekant för ett gammalt problem,

507
00:39:37,700 --> 00:39:39,590
försöka reducera den till ett gammalt problem.

508
00:39:39,590 --> 00:39:41,950
Och om du kan använda alla de verktyg som du har använt på det gamla problemet

509
00:39:41,950 --> 00:39:46,450
att lösa det nya problemet.

510
00:39:46,450 --> 00:39:49,010
Så att slå upp, tekniska intervjuer utmanande.

511
00:39:49,010 --> 00:39:52,280
Dessa problem är förmodligen några av de svårare problemen

512
00:39:52,280 --> 00:39:54,700
som du kan se i en intervju,

513
00:39:54,700 --> 00:39:57,690
så om du inte förstår alla de problem som jag just omfattas, det är okej.

514
00:39:57,690 --> 00:40:01,080
Dessa är några av de mer utmanande problem.

515
00:40:01,080 --> 00:40:03,050
Öva, öva, öva.

516
00:40:03,050 --> 00:40:08,170
Jag gav en hel del problem i allmosor, så definitivt kolla dem ut.

517
00:40:08,170 --> 00:40:11,690
Och lycka på dina intervjuer. Alla mina resurser publiceras på denna länk,

518
00:40:11,690 --> 00:40:15,220
och en av mina äldre vänner har erbjudit sig att göra håna tekniska intervjuer,

519
00:40:15,220 --> 00:40:22,050
så om du är intresserad, e-post kommer Yao på den e-postadressen.

520
00:40:22,050 --> 00:40:26,070
Om du har några frågor, kan du be mig.

521
00:40:26,070 --> 00:40:28,780
Har ni specifika frågor som rör tekniska intervjuer

522
00:40:28,780 --> 00:40:38,440
eller problem som vi har sett så här långt?

523
00:40:38,440 --> 00:40:49,910
Okej. Lycka på dina intervjuer.

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