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

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

3
00:00:04,630 --> 00:00:08,910
[Dette er CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hei alle sammen, jeg er Kenny. Jeg er for tiden en junior studerer informatikk.

5
00:00:12,420 --> 00:00:17,310
Jeg er en tidligere CS TF, og jeg skulle ønske jeg hadde dette da jeg var en underclassman,

6
00:00:17,310 --> 00:00:19,380
og det er derfor jeg gir dette seminaret.

7
00:00:19,380 --> 00:00:21,370
Så jeg håper du liker den.

8
00:00:21,370 --> 00:00:23,470
Dette seminaret er om tekniske intervjuer,

9
00:00:23,470 --> 00:00:26,650
og alle mine ressurser kan bli funnet på denne linken,

10
00:00:26,650 --> 00:00:32,350
denne linken her, et par av ressurser.

11
00:00:32,350 --> 00:00:36,550
Så jeg laget en liste over problemer, faktisk, ganske mange problemer.

12
00:00:36,550 --> 00:00:40,800
Også en generell ressurser siden hvor vi kan finne tips

13
00:00:40,800 --> 00:00:42,870
om hvordan å forberede for et intervju,

14
00:00:42,870 --> 00:00:46,470
tips om hva du bør gjøre under en faktisk intervju,

15
00:00:46,470 --> 00:00:51,910
samt hvordan å nærme problemer og ressurser for fremtidig referanse.

16
00:00:51,910 --> 00:00:53,980
Det er alle på Internett.

17
00:00:53,980 --> 00:00:58,290
Og bare for å forord dette seminaret, en ansvarsfraskrivelse,

18
00:00:58,290 --> 00:01:00,690
som dette bør ikke - intervjuet forberedelse

19
00:01:00,690 --> 00:01:02,800
bør ikke være begrenset til denne listen.

20
00:01:02,800 --> 00:01:04,750
Dette er kun ment som en veiledning,

21
00:01:04,750 --> 00:01:08,890
og du bør definitivt ta alt jeg sier med en klype salt,

22
00:01:08,890 --> 00:01:14,620
men også bruke alt jeg pleide å hjelpe deg i din intervju forberedelse.

23
00:01:14,620 --> 00:01:16,400
>> Jeg kommer til å få fart gjennom de neste par lysbilder

24
00:01:16,400 --> 00:01:18,650
slik at vi kan få til faktiske case studier.

25
00:01:18,650 --> 00:01:23,630
Strukturen i et intervju for en software engineering posisjon,

26
00:01:23,630 --> 00:01:26,320
vanligvis er det 30 til 45 minutter,

27
00:01:26,320 --> 00:01:29,810
flere runder, avhengig av selskapet.

28
00:01:29,810 --> 00:01:33,090
Ofte vil du bli koding på en hvit bord.

29
00:01:33,090 --> 00:01:35,960
Så en hvit bord som dette, men ofte på en mindre skala.

30
00:01:35,960 --> 00:01:38,540
Hvis du har en telefon intervju, vil du sannsynligvis bruke

31
00:01:38,540 --> 00:01:44,030
enten collabedit eller en Google Doc, slik at de kan se du bor koding

32
00:01:44,030 --> 00:01:46,500
mens du blir intervjuet over telefon.

33
00:01:46,500 --> 00:01:48,490
Et intervju i seg selv er vanligvis 2 eller 3 problemer

34
00:01:48,490 --> 00:01:50,620
teste informatikk kunnskap.

35
00:01:50,620 --> 00:01:54,490
Og det vil nesten helt sikkert innebære koding.

36
00:01:54,490 --> 00:01:59,540
De typer spørsmål som du ser er vanligvis datastrukturer og algoritmer.

37
00:01:59,540 --> 00:02:02,210
Og ved å gjøre slike problemer,

38
00:02:02,210 --> 00:02:07,830
de vil spørre deg, liker, er det tid og rom kompleksitet, stor O?

39
00:02:07,830 --> 00:02:09,800
Ofte de ber også høyere nivå spørsmål,

40
00:02:09,800 --> 00:02:12,530
så, designe et system,

41
00:02:12,530 --> 00:02:14,770
hvordan ville du legge ut koden?

42
00:02:14,770 --> 00:02:18,370
Hva grensesnitt, hvilke klasser, hva moduler du har i systemet ditt,

43
00:02:18,370 --> 00:02:20,900
og hvordan disse kommuniserer sammen?

44
00:02:20,900 --> 00:02:26,130
Så datastrukturer og algoritmer, samt utforme systemer.

45
00:02:26,130 --> 00:02:29,180
>> Noen generelle tips før vi dykke inn i våre case-studier.

46
00:02:29,180 --> 00:02:32,300
Jeg tror den viktigste regelen er alltid å tenke høyt.

47
00:02:32,300 --> 00:02:36,980
Intervjuet er ment å være din sjanse til å vise frem din tankeprosess.

48
00:02:36,980 --> 00:02:39,820
Poenget med intervjuet er for intervjueren å måle

49
00:02:39,820 --> 00:02:42,660
hvordan du tenker og hvordan du går gjennom et problem.

50
00:02:42,660 --> 00:02:45,210
Det verste du kan gjøre er å være stille i hele intervjuet.

51
00:02:45,210 --> 00:02:50,090
Det er bare ikke bra.

52
00:02:50,090 --> 00:02:53,230
Når du får et spørsmål, du også ønsker å være sikker på at du forstår spørsmålet.

53
00:02:53,230 --> 00:02:55,350
Så gjentar spørsmålet tilbake med dine egne ord

54
00:02:55,350 --> 00:02:58,920
og forsøke å arbeide grundig noen enkle testtilfeller

55
00:02:58,920 --> 00:03:01,530
å sikre at du forstår spørsmålet.

56
00:03:01,530 --> 00:03:05,510
Arbeider gjennom noen test tilfeller vil også gi deg en intuisjon om hvordan å løse dette problemet.

57
00:03:05,510 --> 00:03:11,210
Du kan selv finne noen mønstre for å hjelpe deg å løse problemet.

58
00:03:11,210 --> 00:03:14,500
Deres stor tips er å ikke bli frustrert.

59
00:03:14,500 --> 00:03:17,060
Ikke bli frustrert.

60
00:03:17,060 --> 00:03:19,060
Intervjuer er utfordrende, men det verste du kan gjøre,

61
00:03:19,060 --> 00:03:23,330
i tillegg til å være stille, er å være synlig frustrert.

62
00:03:23,330 --> 00:03:27,410
Du ønsker ikke å gi det inntrykket til en intervjuer.

63
00:03:27,410 --> 00:03:33,960
En ting som du - så mange mennesker, når de går inn i et intervju,

64
00:03:33,960 --> 00:03:37,150
de forsøker å prøve å finne den beste løsningen først,

65
00:03:37,150 --> 00:03:39,950
når du egentlig er det vanligvis en iøynefallende løsning.

66
00:03:39,950 --> 00:03:43,500
Det kan være treg, kan det være ineffektiv, men du bør bare si det,

67
00:03:43,500 --> 00:03:46,210
bare så du har et utgangspunkt for å arbeide bedre.

68
00:03:46,210 --> 00:03:48,270
Også peker ut løsningen er treg, i form av

69
00:03:48,270 --> 00:03:52,160
big O tidskompleksitet eller plass kompleksitet,

70
00:03:52,160 --> 00:03:54,450
vil demonstrere til intervjueren at du forstår

71
00:03:54,450 --> 00:03:57,510
disse problemene når du skriver koden.

72
00:03:57,510 --> 00:04:01,440
Så ikke vær redd for å komme opp med den enkleste algoritme første

73
00:04:01,440 --> 00:04:04,950
og deretter arbeide bedre derfra.

74
00:04:04,950 --> 00:04:09,810
Eventuelle spørsmål så langt? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Så la oss dykke inn i vår første problem.

76
00:04:11,650 --> 00:04:14,790
"Gitt en rekke n heltall, skrive en funksjon som stokker matrisen

77
00:04:14,790 --> 00:04:20,209
på plass, slik at alle permutasjoner av de n heltallene er like sannsynlig. "

78
00:04:20,209 --> 00:04:23,470
Og anta at du har tilgjengelig en tilfeldig heltall generator

79
00:04:23,470 --> 00:04:30,980
som genererer et heltall i området fra 0 til jeg, halv-serien.

80
00:04:30,980 --> 00:04:32,970
Forstår alle dette spørsmålet?

81
00:04:32,970 --> 00:04:39,660
Jeg gir deg en rekke n heltall, og jeg vil at du skal shuffle det.

82
00:04:39,660 --> 00:04:46,050
I katalogen min, skrev jeg noen programmer for å demonstrere hva jeg mener.

83
00:04:46,050 --> 00:04:48,910
Jeg kommer til å shuffle en rekke 20 elementer,

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

85
00:04:52,490 --> 00:04:57,050
og jeg vil at du skal sende en liste som dette.

86
00:04:57,050 --> 00:05:02,890
Så dette er min sortert innspill array, og jeg vil at du skal shuffle det.

87
00:05:02,890 --> 00:05:07,070
Vi vil gjøre det igjen.

88
00:05:07,070 --> 00:05:13,780
Forstår alle spørsmålet? Okay.

89
00:05:13,780 --> 00:05:16,730
Så det er opp til deg.

90
00:05:16,730 --> 00:05:21,220
Hva er noen ideer? Kan du gjøre det som n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Åpne for forslag.

92
00:05:34,400 --> 00:05:37,730
Okay. Så en idé, foreslått av Emmy,

93
00:05:37,730 --> 00:05:45,300
er først beregne et tilfeldig tall, tilfeldig heltall, i et område fra 0 til 20.

94
00:05:45,300 --> 00:05:49,840
Så anta vårt utvalg har en lengde på 20.

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

96
00:05:54,800 --> 00:05:58,560
Dette er våre innspill array.

97
00:05:58,560 --> 00:06:04,590
Og nå, er hennes forslag om å opprette en ny array,

98
00:06:04,590 --> 00:06:08,440
så dette blir resultatet array.

99
00:06:08,440 --> 00:06:12,880
Og basert på jeg returnerte etter rand -

100
00:06:12,880 --> 00:06:17,580
så hvis jeg var, la oss si, 17,

101
00:06:17,580 --> 00:06:25,640
kopiere syttende elementet inn i den første stilling.

102
00:06:25,640 --> 00:06:30,300
Nå må vi slette - vi trenger å skifte alle elementene her

103
00:06:30,300 --> 00:06:36,920
over slik at vi har et gap på slutten og ingen hull i midten.

104
00:06:36,920 --> 00:06:39,860
Og nå er vi gjenta prosessen.

105
00:06:39,860 --> 00:06:46,360
Nå er vi plukke en ny tilfeldig heltall mellom 0 og 19.

106
00:06:46,360 --> 00:06:52,510
Vi har en ny jeg her, og kopierer vi dette elementet i denne posisjonen.

107
00:06:52,510 --> 00:07:00,960
Da vi skiftet elementer over og vi gjentar prosessen til vi har vår fulle ny rekke.

108
00:07:00,960 --> 00:07:05,890
Hva er kjøretiden for denne algoritmen?

109
00:07:05,890 --> 00:07:08,110
Vel, la oss vurdere virkningen av dette.

110
00:07:08,110 --> 00:07:10,380
Vi er skiftende hvert element.

111
00:07:10,380 --> 00:07:16,800
Når vi fjerner dette i, er vi skiftende alle elementene etter den til venstre.

112
00:07:16,800 --> 00:07:21,600
Og det er en O (n) for et måltid

113
00:07:21,600 --> 00:07:26,100
fordi hva hvis vi fjerner det første elementet?

114
00:07:26,100 --> 00:07:29,670
Så for hver fjerning, fjerner vi -

115
00:07:29,670 --> 00:07:32,170
hver fjerning medfører en O (n) drift,

116
00:07:32,170 --> 00:07:41,520
og siden vi har n flytting, fører dette til en O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Okay. Så god start. God start.

118
00:07:49,550 --> 00:07:55,290
>> Et annet forslag er å bruke noe som kalles Knuth shuffle,

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

120
00:07:57,540 --> 00:07:59,630
Og det er faktisk en lineær tid shuffle.

121
00:07:59,630 --> 00:08:02,200
Og ideen er veldig lik.

122
00:08:02,200 --> 00:08:05,160
Igjen har vi våre innspill array,

123
00:08:05,160 --> 00:08:08,580
men i stedet for å bruke to arrays for vår input / output,

124
00:08:08,580 --> 00:08:13,590
vi bruker den første del av rekken til å holde styr på vår stokket del,

125
00:08:13,590 --> 00:08:18,400
og vi holde styr, og da vi la resten av matrisen vår for unshuffled delen.

126
00:08:18,400 --> 00:08:24,330
Så her er hva jeg mener. Vi starter med - vi velger en i,

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

128
00:08:30,910 --> 00:08:36,150
Vår nåværende pekeren peker til den første indeksen.

129
00:08:36,150 --> 00:08:39,590
Vi velger noen jeg her

130
00:08:39,590 --> 00:08:42,740
og nå har vi bytte.

131
00:08:42,740 --> 00:08:47,690
Så hvis dette var 5, og dette var 4,

132
00:08:47,690 --> 00:08:57,150
den resulterende matrisen vil ha 5 her og 4 her.

133
00:08:57,150 --> 00:09:00,390
Og nå har vi oppmerksom på en markør her.

134
00:09:00,390 --> 00:09:05,770
Alt til venstre er stokket

135
00:09:05,770 --> 00:09:15,160
og alt til høyre er unshuffled.

136
00:09:15,160 --> 00:09:17,260
Og nå kan vi gjenta prosessen.

137
00:09:17,260 --> 00:09:25,210
Vi velger en tilfeldig indeks mellom 1 og 20 nå.

138
00:09:25,210 --> 00:09:30,650
Så antar vår nye jeg er her.

139
00:09:30,650 --> 00:09:39,370
Nå er vi bytte denne i med vår nåværende ny stilling her.

140
00:09:39,370 --> 00:09:44,790
Så vi en byttering frem og tilbake som dette.

141
00:09:44,790 --> 00:09:51,630
La meg få opp koden for å gjøre det mer konkret.

142
00:09:51,630 --> 00:09:55,290
Vi starter med vårt valg av i -

143
00:09:55,290 --> 00:09:58,370
vi starter med i lik 0, henter vi et tilfeldig sted j

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

145
00:10:02,420 --> 00:10:07,280
Så hvis jeg er her, velge en tilfeldig indeks mellom her og resten av tabellen,

146
00:10:07,280 --> 00:10:12,410
og vi bytte.

147
00:10:12,410 --> 00:10:17,550
Dette er all koden er nødvendig for å shuffle din array.

148
00:10:17,550 --> 00:10:21,670
Eventuelle spørsmål?

149
00:10:21,670 --> 00:10:25,530
>> Vel, trengte ett spørsmål er, hvorfor er dette riktig?

150
00:10:25,530 --> 00:10:28,360
Hvorfor er alle permutasjon like sannsynlig?

151
00:10:28,360 --> 00:10:30,410
Og jeg vil ikke gå gjennom bevis på dette,

152
00:10:30,410 --> 00:10:35,970
men mange problemer i informatikk kan påvises gjennom induksjon.

153
00:10:35,970 --> 00:10:38,520
Hvor mange av dere er kjent med induksjon?

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

155
00:10:40,590 --> 00:10:43,610
Så du kan bevise riktigheten av denne algoritmen ved enkel induksjon,

156
00:10:43,610 --> 00:10:49,540
hvor induksjon hypotese ville være, anta at

157
00:10:49,540 --> 00:10:53,290
min shuffle returnerer hver permutasjon like sannsynlig

158
00:10:53,290 --> 00:10:56,120
opp til de første jeg elementer.

159
00:10:56,120 --> 00:10:58,300
Nå vurderer jeg + 1.

160
00:10:58,300 --> 00:11:02,550
Og ved måten vi velger våre indeksen j for å bytte,

161
00:11:02,550 --> 00:11:05,230
Dette fører til - og så jobbe ut detaljene,

162
00:11:05,230 --> 00:11:07,390
minst en fullstendig bevis på hvorfor dette algoritmen returnerer

163
00:11:07,390 --> 00:11:12,800
hver permutasjon med like sannsynlig sannsynlighet.

164
00:11:12,800 --> 00:11:15,940
>> Greit, neste problem.

165
00:11:15,940 --> 00:11:19,170
Så "gitt en rekke heltall, postive, null, negativ,

166
00:11:19,170 --> 00:11:21,290
skrive en funksjon som beregner den maksimale sum

167
00:11:21,290 --> 00:11:24,720
i alle continueous subarray av input array. "

168
00:11:24,720 --> 00:11:28,370
Et eksempel her er, i det tilfellet hvor alle tall er positive,

169
00:11:28,370 --> 00:11:31,320
så i dag er det beste valget er å ta hele array.

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

171
00:11:34,690 --> 00:11:36,780
Når du har noen negative i det,

172
00:11:36,780 --> 00:11:38,690
i dette tilfellet bare vi ønsker de to første

173
00:11:38,690 --> 00:11:44,590
fordi velge -1 og / eller -3 vil bringe vår sum ned.

174
00:11:44,590 --> 00:11:48,120
Noen ganger kan vi kanskje begynne i midten av tabellen.

175
00:11:48,120 --> 00:11:53,500
Noen ganger ønsker vi å velge noe i det hele tatt, det er best å ikke ta noe.

176
00:11:53,500 --> 00:11:56,490
Og noen ganger er det bedre å ta fallet,

177
00:11:56,490 --> 00:12:07,510
fordi ting etter det er super store. Så noen ideer?

178
00:12:07,510 --> 00:12:10,970
(Student, uforståelig) >> Ja.

179
00:12:10,970 --> 00:12:13,560
Antar at jeg ikke tar -1.

180
00:12:13,560 --> 00:12:16,170
Så enten jeg velger 1000 og 20.000,

181
00:12:16,170 --> 00:12:18,630
eller jeg bare velge 3 milliarder kroner.

182
00:12:18,630 --> 00:12:20,760
Vel, er det beste valget for å ta alle tallene.

183
00:12:20,760 --> 00:12:24,350
Dette -1, til tross for å være negativ,

184
00:12:24,350 --> 00:12:31,340
hele summen er bedre enn det som var jeg ikke å ta -1.

185
00:12:31,340 --> 00:12:36,460
Så en av de tipsene jeg nevnte tidligere var å oppgi tydelig opplagt

186
00:12:36,460 --> 00:12:40,540
og brute force løsning først.

187
00:12:40,540 --> 00:12:44,340
Hva er brute force løsningen i dette problemet? Ja?

188
00:12:44,340 --> 00:12:46,890
[Jane] Vel, jeg tror det brute force løsning

189
00:12:46,890 --> 00:12:52,600
ville være å legge opp alle mulige kombinasjoner (uforståelig).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Så Jane idé er å ta alle mulige -

191
00:12:58,250 --> 00:13:01,470
Jeg er parafrasering - er å ta alle mulige kontinuerlig subarray,

192
00:13:01,470 --> 00:13:07,840
beregne summen, og deretter ta maksimalt av alle mulige kontinuerlige subarrays.

193
00:13:07,840 --> 00:13:13,310
Hva identifiserer en subarray i min inngang array?

194
00:13:13,310 --> 00:13:17,380
Liker, hva to ting trenger jeg? Ja?

195
00:13:17,380 --> 00:13:19,970
(Student, uforståelig) >> Høyre.

196
00:13:19,970 --> 00:13:22,130
En nedre grense på indeksen og en øvre bundet indeks

197
00:13:22,130 --> 00:13:28,300
unikt bestemmer en kontinuerlig subarray.

198
00:13:28,300 --> 00:13:31,400
[Kvinne student] Er vi estimere det er en rekke unike numre?

199
00:13:31,400 --> 00:13:34,280
[Yu] Nei Så spørsmålet hennes er, er vi antar vårt utvalg -

200
00:13:34,280 --> 00:13:39,000
er vår rekke alle unike numre, og svaret er nei.

201
00:13:39,000 --> 00:13:43,390
>> Hvis vi bruker vår brute force-løsning, så start / slutt indekser

202
00:13:43,390 --> 00:13:47,200
unikt bestemmer vår kontinuerlige subarray.

203
00:13:47,200 --> 00:13:51,680
Så hvis vi iterate for alle mulige start oppføringer,

204
00:13:51,680 --> 00:13:58,320
og for alle end oppføringer> eller = for å starte, og <n,

205
00:13:58,320 --> 00:14:05,570
du beregne summen, og så tar vi den maksimale summen vi har sett så langt.

206
00:14:05,570 --> 00:14:07,880
Er dette klart?

207
00:14:07,880 --> 00:14:12,230
Hva er den store O av denne løsningen?

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

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

210
00:14:18,860 --> 00:14:25,250
Merk at vi iterate fra 0 til n,

211
00:14:25,250 --> 00:14:27,520
så det er en for-løkke.

212
00:14:27,520 --> 00:14:35,120
Vi iterate igjen fra nesten begynnelsen til slutten, en annen for loop.

213
00:14:35,120 --> 00:14:37,640
Og nå, i løpet av denne, må vi oppsummere hver oppføring,

214
00:14:37,640 --> 00:14:43,810
så det er en annen for loop. Så vi har tre nestet for løkker, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Dette går som et utgangspunkt.

216
00:14:46,560 --> 00:14:53,180
Vår løsning er ikke verre enn n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Forstår alle brute force løsning?

218
00:14:55,480 --> 00:14:59,950
>> Okay. En bedre løsning er å bruke en idé kalles dynamisk programmering.

219
00:14:59,950 --> 00:15:03,040
Hvis du tar CS124, som er Algoritmer og datastrukturer,

220
00:15:03,040 --> 00:15:05,680
vil du bli godt kjent med denne teknikken.

221
00:15:05,680 --> 00:15:12,190
Og ideen er å forsøke å bygge opp løsninger til mindre problemer først.

222
00:15:12,190 --> 00:15:17,990
Hva jeg mener med dette er, men for øyeblikket har å bekymre deg to ting: Start og slutt.

223
00:15:17,990 --> 00:15:29,340
Og det er irriterende. Hva om vi kunne bli kvitt en av disse parametrene?

224
00:15:29,340 --> 00:15:32,650
En idé er å - vi gitt vår opprinnelige problem,

225
00:15:32,650 --> 00:15:37,470
finner den maksimale sum enhver subarray i et område [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Og nå har vi en ny deloppgave, hvor vi vet, i vår nåværende indeksen i,

227
00:15:47,400 --> 00:15:52,520
vi vet at vi må konkludere der. Vår subarray må slutte på dagens indeks.

228
00:15:52,520 --> 00:15:57,640
Så de resterende problemet er, hvor skal vi begynne vår subarray?

229
00:15:57,640 --> 00:16:05,160
Betyr dette fornuftig? Okay.

230
00:16:05,160 --> 00:16:12,030
Så jeg har kodet dette opp, og la oss se på hva dette betyr.

231
00:16:12,030 --> 00:16:16,230
I codirectory, det er et program som heter subarray,

232
00:16:16,230 --> 00:16:19,470
og det tar flere elementer,

233
00:16:19,470 --> 00:16:25,550
og den returnerer maksimal subarray summen i min stokket listen.

234
00:16:25,550 --> 00:16:29,920
Så i dette tilfellet, er vår maksimal subarray 3.

235
00:16:29,920 --> 00:16:34,850
Og det er tatt ved bare å bruke 2 og 1.

236
00:16:34,850 --> 00:16:38,050
La oss kjøre det igjen. Det er også tre.

237
00:16:38,050 --> 00:16:40,950
Men denne gangen, merk hvordan vi fikk 3.

238
00:16:40,950 --> 00:16:46,690
Vi tok - vi bare ta 3 selv

239
00:16:46,690 --> 00:16:49,980
fordi det er omgitt av negativer på begge sider,

240
00:16:49,980 --> 00:16:55,080
som vil bringe en sum <3.

241
00:16:55,080 --> 00:16:57,820
La oss kjøre på 10 elementer.

242
00:16:57,820 --> 00:17:03,200
Denne gangen er det 7, tar vi den ledende 3 og 4.

243
00:17:03,200 --> 00:17:09,450
Denne gangen er det 8, og vi får det ved å ta 1, 4 og 3.

244
00:17:09,450 --> 00:17:16,310
Så for å gi deg en intuisjon om hvordan vi kan løse dette forvandlet problem,

245
00:17:16,310 --> 00:17:18,890
la oss ta en titt på denne subarray.

246
00:17:18,890 --> 00:17:23,460
Vi får denne inngangen array, og vi vet svaret er 8.

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

248
00:17:26,359 --> 00:17:29,090
Men la oss se på hvordan vi faktisk fikk det svaret.

249
00:17:29,090 --> 00:17:34,160
La oss se på den maksimale subarray som endte på hver av disse indeksene.

250
00:17:34,160 --> 00:17:40,780
Hva er den maksimale subarray som har til slutt på den første posisjonen?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. >> Zero. Bare ikke ta den -5.

252
00:17:46,310 --> 00:17:50,210
Her det kommer til å være 0 i tillegg. Ja?

253
00:17:50,210 --> 00:17:56,470
(Student, uforståelig)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, beklager, det er en -3.

255
00:17:58,960 --> 00:18:03,220
Så dette er en 2, er dette en -3.

256
00:18:03,220 --> 00:18:08,690
Okay. Så -4, hva er den maksimale subarray å avslutte den posisjonen

257
00:18:08,690 --> 00:18:12,910
der -4 er på? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Nå må jeg avslutte på stedet der -2 er på.

260
00:18:28,060 --> 00:18:39,330
Så 6, 5, 7, og den siste er 4.

261
00:18:39,330 --> 00:18:43,480
Vel vitende om at disse er mine oppføringer

262
00:18:43,480 --> 00:18:48,130
for den transformerte problem der jeg må slutte på hver av disse indeksene,

263
00:18:48,130 --> 00:18:51,410
så mitt endelige svar er bare, ta en sveip over,

264
00:18:51,410 --> 00:18:53,580
og ta det maksimale antallet.

265
00:18:53,580 --> 00:18:55,620
Så i dette tilfellet er det 8.

266
00:18:55,620 --> 00:19:00,010
Dette innebærer at maksimal subarray ender på denne indeksen,

267
00:19:00,010 --> 00:19:04,970
og startet et sted før det.

268
00:19:04,970 --> 00:19:09,630
Forstår alle dette transformert subarray?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Vel, la oss finne ut tilbakefall for dette.

270
00:19:22,160 --> 00:19:27,990
La oss vurdere bare de første oppføringene.

271
00:19:27,990 --> 00:19:35,930
Så her var det 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Og så var det en -2 her, og som brakte den ned til 6.

273
00:19:39,790 --> 00:19:50,800
Så hvis jeg kaller oppføringen i posisjon i deloppgave (i),

274
00:19:50,800 --> 00:19:54,910
hvordan kan jeg bruke svar til en tidligere deloppgave

275
00:19:54,910 --> 00:19:59,360
å svare på dette deloppgave?

276
00:19:59,360 --> 00:20:04,550
Hvis jeg ser på, la oss si, dette innlegget.

277
00:20:04,550 --> 00:20:09,190
Hvordan kan jeg beregne svaret 6 ved å se på

278
00:20:09,190 --> 00:20:18,780
en kombinasjon av denne tabellen og svar på tidligere deloppgaver i denne matrisen? Ja?

279
00:20:18,780 --> 00:20:22,800
[Kvinne student] Du tar rekke summer

280
00:20:22,800 --> 00:20:25,430
i posisjon rett før den, så 8 den,

281
00:20:25,430 --> 00:20:32,170
og deretter legge til gjeldende deloppgave.

282
00:20:32,170 --> 00:20:36,460
[Yu] Så hennes forslag er å se på disse to tallene,

283
00:20:36,460 --> 00:20:40,090
dette nummeret og dette nummeret.

284
00:20:40,090 --> 00:20:50,130
Så dette 8 refererer til svaret for deloppgave (i - 1).

285
00:20:50,130 --> 00:20:57,300
Og la oss kalle min inngang rekke A.

286
00:20:57,300 --> 00:21:01,470
For å finne en maksimal subarray som ender i posisjon i,

287
00:21:01,470 --> 00:21:03,980
Jeg har to valg: Jeg kan enten fortsette subarray

288
00:21:03,980 --> 00:21:09,790
som endte på forrige indeks, eller starte en ny rekke.

289
00:21:09,790 --> 00:21:14,190
Hvis jeg skulle fortsette subarray som startet på den forrige indeks,

290
00:21:14,190 --> 00:21:19,260
så den maksimale summen jeg kan oppnå er svaret på det forrige deloppgave

291
00:21:19,260 --> 00:21:24,120
pluss den gjeldende matrisen oppføring.

292
00:21:24,120 --> 00:21:27,550
Men, jeg har også valg å starte en ny subarray,

293
00:21:27,550 --> 00:21:30,830
i hvilket tilfelle summen er 0..

294
00:21:30,830 --> 00:21:42,860
Så svaret er maks av 0, deloppgave i - 1, pluss dagens utvalg oppføring.

295
00:21:42,860 --> 00:21:46,150
Betyr dette tilbakefall forstand?

296
00:21:46,150 --> 00:21:50,840
Vår tilbakefall, som vi nettopp oppdaget, er deloppgave i

297
00:21:50,840 --> 00:21:54,740
er lik den maksimale av forrige deloppgave pluss min nåværende utvalg oppføring,

298
00:21:54,740 --> 00:22:01,490
som betyr fortsette den forrige subarray,

299
00:22:01,490 --> 00:22:07,250
eller 0, starte en ny subarray på min nåværende indeksen.

300
00:22:07,250 --> 00:22:10,060
Og når vi har bygget opp denne tabellen av løsninger, og vår endelige svaret,

301
00:22:10,060 --> 00:22:13,950
bare gjøre en lineær sveip over deloppgave rekke

302
00:22:13,950 --> 00:22:19,890
og ta det maksimale antallet.

303
00:22:19,890 --> 00:22:23,330
Dette er en nøyaktig gjennomføring av det jeg nettopp sa.

304
00:22:23,330 --> 00:22:27,320
Så lager vi en ny deloppgave array, deloppgaver.

305
00:22:27,320 --> 00:22:32,330
Den første oppføringen er enten 0 eller den første oppføringen, maksimum av de to.

306
00:22:32,330 --> 00:22:35,670
Og for resten av deloppgaver

307
00:22:35,670 --> 00:22:39,810
vi bruker nøyaktig gjentakelse vi bare oppdaget.

308
00:22:39,810 --> 00:22:49,960
Nå er vi beregne maksimalt vår deloppgaver array, og det er vårt endelige svar.

309
00:22:49,960 --> 00:22:54,130
>> Så hvor mye plass vi bruker i denne algoritmen?

310
00:22:54,130 --> 00:23:01,470
Hvis du bare har tatt CS50, så du kanskje ikke har diskutert plass veldig mye.

311
00:23:01,470 --> 00:23:07,750
Vel, en ting å merke seg at jeg ringte malloc her med størrelse n.

312
00:23:07,750 --> 00:23:13,590
Hva foreslår det for deg?

313
00:23:13,590 --> 00:23:17,450
Denne algoritmen benytter lineære plass.

314
00:23:17,450 --> 00:23:21,030
Kan vi gjøre det bedre?

315
00:23:21,030 --> 00:23:30,780
Er det noe som du merker at er unødvendig å beregne det endelige svaret?

316
00:23:30,780 --> 00:23:33,290
Jeg antar et bedre spørsmål er, hva slags informasjon

317
00:23:33,290 --> 00:23:40,680
vi trenger ikke å bære hele veien gjennom til slutt?

318
00:23:40,680 --> 00:23:44,280
Nå, hvis vi ser på disse to linjene,

319
00:23:44,280 --> 00:23:47,720
vi bare bryr seg om den forrige deloppgave,

320
00:23:47,720 --> 00:23:50,910
og vi bare bryr seg om maksimalt vi noensinne har sett så langt.

321
00:23:50,910 --> 00:23:53,610
Å beregne vårt endelige svar, trenger vi ikke hele tabellen.

322
00:23:53,610 --> 00:23:57,450
Vi trenger bare det siste tallet, to siste tallene.

323
00:23:57,450 --> 00:24:02,630
Siste tall for deloppgave array, og siste nummer for det maksimale.

324
00:24:02,630 --> 00:24:07,380
Så, faktisk, kan vi smelte disse loopene sammen

325
00:24:07,380 --> 00:24:10,460
og gå fra lineær plass til konstant plass.

326
00:24:10,460 --> 00:24:15,830
Nåværende sum så langt, her, erstatter rolle deloppgave, vår deloppgave array.

327
00:24:15,830 --> 00:24:20,020
Så dagens sum, så langt, er svaret på det forrige deloppgave.

328
00:24:20,020 --> 00:24:23,450
Og at summen, så langt, tar plassen til maks vår.

329
00:24:23,450 --> 00:24:28,100
Vi beregne maksimalt mens vi går langs.

330
00:24:28,100 --> 00:24:30,890
Og så skal vi gå fra lineær plass til konstant plass,

331
00:24:30,890 --> 00:24:36,650
og vi har også en lineær løsning til våre subarray problem.

332
00:24:36,650 --> 00:24:40,740
>> Slike spørsmål vil du få under et intervju.

333
00:24:40,740 --> 00:24:44,450
Hva er tiden kompleksitet, hva er plass kompleksitet?

334
00:24:44,450 --> 00:24:50,600
Kan du gjøre det bedre? Er det ting som er unødvendig å holde rundt?

335
00:24:50,600 --> 00:24:55,270
Jeg gjorde dette for å markere analyser som du bør ta på egen hånd

336
00:24:55,270 --> 00:24:57,400
som du arbeider gjennom disse problemene.

337
00:24:57,400 --> 00:25:01,710
Alltid spørre deg selv: "Kan jeg gjøre det bedre?"

338
00:25:01,710 --> 00:25:07,800
Faktisk kan vi gjøre bedre enn dette?

339
00:25:07,800 --> 00:25:10,730
Sortering av et lurespørsmål. Du kan ikke, fordi du må

340
00:25:10,730 --> 00:25:13,590
minst lese inngangen til problemet.

341
00:25:13,590 --> 00:25:15,570
Så det faktum at du må minst lese innspill til problemet

342
00:25:15,570 --> 00:25:19,580
betyr at du ikke kan gjøre det bedre enn lineær tid,

343
00:25:19,580 --> 00:25:22,870
og du kan ikke gjøre det bedre enn konstant plass.

344
00:25:22,870 --> 00:25:27,060
Så dette er faktisk den beste løsningen på dette problemet.

345
00:25:27,060 --> 00:25:33,040
Spørsmål? Okay.

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

347
00:25:35,190 --> 00:25:38,350
"Gitt en rekke n heltall, positive, null eller negativ,

348
00:25:38,350 --> 00:25:41,680
som representerer prisen på en aksje over n dager,

349
00:25:41,680 --> 00:25:44,080
skrive en funksjon for å beregne maksimalt utbytte du kan gjøre

350
00:25:44,080 --> 00:25:49,350
gitt at du kjøper og selger nøyaktig 1 på lager innen disse n dager. "

351
00:25:49,350 --> 00:25:51,690
I hovedsak ønsker vi å kjøpe lavt, selger høy.

352
00:25:51,690 --> 00:25:58,580
Og vi ønsker å finne ut det beste resultat vi kan gjøre.

353
00:25:58,580 --> 00:26:11,500
Går tilbake til mitt tips, hva er umiddelbart klart, enkleste svaret, men det er treg?

354
00:26:11,500 --> 00:26:17,690
Ja? (Student, uforståelig) >> Ja.

355
00:26:17,690 --> 00:26:21,470
>> Så du ville bare gå selv og se på aksjekurser

356
00:26:21,470 --> 00:26:30,550
på hvert punkt i tid, (uforståelige).

357
00:26:30,550 --> 00:26:33,990
[Yu] Ok, så hennes løsning - hennes forslag for databehandling

358
00:26:33,990 --> 00:26:37,380
den laveste og beregne den høyeste ikke nødvendigvis fungere

359
00:26:37,380 --> 00:26:42,470
fordi den høyeste kan oppstå før den laveste.

360
00:26:42,470 --> 00:26:47,340
Så hva er den brute force løsning på dette problemet?

361
00:26:47,340 --> 00:26:53,150
Hva er de to tingene som jeg trenger å unikt bestemme overskuddet jeg gjøre? Høyre.

362
00:26:53,150 --> 00:26:59,410
Den brute force løsningen er - oh, så er George forslag vi trenger bare to dager

363
00:26:59,410 --> 00:27:02,880
å unikt bestemme resultatet av disse to dagene.

364
00:27:02,880 --> 00:27:06,660
Så vi beregne hvert par, liker kjøpe / selge,

365
00:27:06,660 --> 00:27:12,850
beregne fortjeneste, noe som kan være negativt eller positivt eller null.

366
00:27:12,850 --> 00:27:18,000
Beregn maksimal profitt som vi gjør etter iterating over alle par av dagene.

367
00:27:18,000 --> 00:27:20,330
Som vil være vår endelige svaret.

368
00:27:20,330 --> 00:27:25,730
Og at løsningen vil være O (n ^ 2), fordi det er n velge to par -

369
00:27:25,730 --> 00:27:30,270
dager som du kan velge blant siste dagene.

370
00:27:30,270 --> 00:27:32,580
Ok, så jeg har ikke tenkt å gå over brute force løsningen her.

371
00:27:32,580 --> 00:27:37,420
Jeg kommer til å fortelle deg at det er en n log n løsning.

372
00:27:37,420 --> 00:27:45,550
Hva algoritme har du nå vet det er n log n?

373
00:27:45,550 --> 00:27:50,730
Det er ikke et lurespørsmål.

374
00:27:50,730 --> 00:27:54,790
>> Flette slag. Flette sort er n log n,

375
00:27:54,790 --> 00:27:57,760
og faktisk er en måte å løse dette problemet for å bruke

376
00:27:57,760 --> 00:28:04,400
en sammenslåing slags slags idé kalt, generelt, splitt og hersk.

377
00:28:04,400 --> 00:28:07,570
Og tanken er som følger.

378
00:28:07,570 --> 00:28:12,400
Du ønsker å beregne den beste kjøp / salg par i venstre halvdel.

379
00:28:12,400 --> 00:28:16,480
Finn det beste resultat du kan gjøre, bare med de første n over to dager.

380
00:28:16,480 --> 00:28:19,780
Så du ønsker å oompute den beste kjøp / salg par på høyre halvdel,

381
00:28:19,780 --> 00:28:23,930
slik at den siste n over to dager.

382
00:28:23,930 --> 00:28:32,400
Og nå er spørsmålet, hvordan flette vi disse løsningene sammen igjen?

383
00:28:32,400 --> 00:28:36,320
Ja? (Student, uforståelig)

384
00:28:36,320 --> 00:28:49,890
>> Ok. Så la meg tegne et bilde.

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

386
00:29:03,870 --> 00:29:06,450
>> Nettopp. George løsning er helt riktig.

387
00:29:06,450 --> 00:29:10,040
Så hans forslag er først beregne den beste kjøp / salg par,

388
00:29:10,040 --> 00:29:16,050
og som oppstår i venstre halvdel, så la oss kalle det venstre, venstre.

389
00:29:16,050 --> 00:29:20,790
Best kjøp / salg par som oppstår i høyre halvdel.

390
00:29:20,790 --> 00:29:25,180
Men hvis vi bare sammenlignet disse to tallene, vi mangler saken

391
00:29:25,180 --> 00:29:30,460
hvor vi kjøper her og selge et sted i høyre halvdel.

392
00:29:30,460 --> 00:29:33,810
Vi kjøper i venstre halvdel, selge i høyre halvdel.

393
00:29:33,810 --> 00:29:38,490
Og den beste måten å beregne den beste kjøp / salg par som spenner begge omganger

394
00:29:38,490 --> 00:29:43,480
er å beregne minimum her og beregne maksimum her

395
00:29:43,480 --> 00:29:45,580
og ta sin forskjell.

396
00:29:45,580 --> 00:29:50,850
Slik at de to tilfellene hvor kjøpe / selge paret oppstår bare her,

397
00:29:50,850 --> 00:30:01,910
bare her, eller på begge halvdeler er definert av disse tre tallene.

398
00:30:01,910 --> 00:30:06,450
Så vår algoritme for å fusjonere våre løsninger sammen,

399
00:30:06,450 --> 00:30:08,350
vi ønsker å beregne den beste kjøp / salg par

400
00:30:08,350 --> 00:30:13,120
hvor vi kjøper på venstre halvdel og selge på høyre halvdel.

401
00:30:13,120 --> 00:30:16,740
Og den beste måten å gjøre det på er å beregne den laveste prisen i første halvår,

402
00:30:16,740 --> 00:30:20,360
den høyeste prisen i høyre halvdel, og ta sin forskjell.

403
00:30:20,360 --> 00:30:25,390
De resulterende tre profitt, disse tre tallene, tar du maksimalt tre,

404
00:30:25,390 --> 00:30:32,720
og det er det beste resultat kan du gjøre over disse første og slutten dagene.

405
00:30:32,720 --> 00:30:36,940
Her viktige linjer er i rødt.

406
00:30:36,940 --> 00:30:41,160
Dette er en rekursiv samtale for å beregne svaret i venstre halvdel.

407
00:30:41,160 --> 00:30:44,760
Dette er en rekursiv kall til beregne svaret i høyre halvdel.

408
00:30:44,760 --> 00:30:50,720
Disse to for løkker beregne min og maks på venstre og høyre halvdel, henholdsvis.

409
00:30:50,720 --> 00:30:54,970
Nå har jeg beregne fortjeneste som spenner begge omganger,

410
00:30:54,970 --> 00:31:00,530
og det endelige svaret er maksimum av disse tre.

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

412
00:31:04,120 --> 00:31:06,420
>> Så sikker, har vi en algoritme, men større spørsmål er,

413
00:31:06,420 --> 00:31:08,290
Hva er tiden kompleksiteten av denne?

414
00:31:08,290 --> 00:31:16,190
Og grunnen til at jeg nevnte flette typen er at denne formen for deler svaret

415
00:31:16,190 --> 00:31:19,200
i to og deretter flette våre løsninger sammen

416
00:31:19,200 --> 00:31:23,580
er akkurat den formen for flettingen slag.

417
00:31:23,580 --> 00:31:33,360
Så la meg gå gjennom varigheten.

418
00:31:33,360 --> 00:31:41,340
Hvis vi definerer en funksjon T (n) til å være antall trinn

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

420
00:31:50,010 --> 00:31:54,350
våre to rekursive samtaler

421
00:31:54,350 --> 00:32:00,460
er hver kommer til å koste t (n / 2),

422
00:32:00,460 --> 00:32:03,540
og det er to av disse samtalene.

423
00:32:03,540 --> 00:32:10,020
Nå trenger jeg å beregne minimum av venstre halvdel,

424
00:32:10,020 --> 00:32:17,050
som jeg kan gjøre i n / 2 gang, pluss maksimalt høyre halvdel.

425
00:32:17,050 --> 00:32:20,820
Så dette er bare n.

426
00:32:20,820 --> 00:32:25,050
Og så pluss noen konstant arbeid.

427
00:32:25,050 --> 00:32:27,770
Og dette tilbakefall ligningen

428
00:32:27,770 --> 00:32:35,560
er nøyaktig gjentakelse ligningen for flettingen slag.

429
00:32:35,560 --> 00:32:39,170
Og vi vet alle at flettingen sort er n log n tid.

430
00:32:39,170 --> 00:32:46,880
Derfor er vårt algoritmen også n log n tid.

431
00:32:46,880 --> 00:32:52,220
Betyr dette iterasjon forstand?

432
00:32:52,220 --> 00:32:55,780
Bare en kort oppsummering av dette:

433
00:32:55,780 --> 00:32:59,170
T (n) er antallet av trinn for å beregne maksimal profitt

434
00:32:59,170 --> 00:33:02,750
løpet av n dager.

435
00:33:02,750 --> 00:33:06,010
Måten vi delt opp våre rekursive samtaler

436
00:33:06,010 --> 00:33:11,980
er ved å ringe vår løsning på de første n / 2 dager,

437
00:33:11,980 --> 00:33:14,490
så det er en samtale,

438
00:33:14,490 --> 00:33:16,940
og da vi ringe igjen på den andre halvdelen.

439
00:33:16,940 --> 00:33:20,440
Så det er to samtaler.

440
00:33:20,440 --> 00:33:25,310
Og så finner vi et minimum på venstre halvdel, som vi kan gjøre i lineær tid,

441
00:33:25,310 --> 00:33:29,010
Finn den maksimale høyre halvdel, som vi kan gjøre i lineær tid.

442
00:33:29,010 --> 00:33:31,570
So n / 2 + n / 2 er like n.

443
00:33:31,570 --> 00:33:36,020
Så har vi noen konstant arbeid, som er som gjør regning.

444
00:33:36,020 --> 00:33:39,860
Dette tilbakefall ligningen er akkurat tilbakefall ligningen for flettingen slag.

445
00:33:39,860 --> 00:33:55,490
Derfor er vår shuffle algoritmen også n log n.

446
00:33:55,490 --> 00:33:58,520
Så hvor mye plass vi bruker?

447
00:33:58,520 --> 00:34:04,910
La oss gå tilbake til koden.

448
00:34:04,910 --> 00:34:09,420
>> Et bedre spørsmål er, hvor mange stack rammer vi noensinne har til enhver tid?

449
00:34:09,420 --> 00:34:11,449
Siden vi bruker rekursjon,

450
00:34:11,449 --> 00:34:23,530
antall stack rammer bestemmer vår plassbruken.

451
00:34:23,530 --> 00:34:29,440
La oss vurdere n = 8.

452
00:34:29,440 --> 00:34:36,889
Vi kaller shuffle på 8,

453
00:34:36,889 --> 00:34:41,580
som vil kalle shuffle på de fire første oppføringene,

454
00:34:41,580 --> 00:34:46,250
som vil kalle en shuffle på de to første oppføringene.

455
00:34:46,250 --> 00:34:51,550
Så vår stabelen er - dette er vår stabelen.

456
00:34:51,550 --> 00:34:54,980
Og så kaller vi shuffle igjen på 1,

457
00:34:54,980 --> 00:34:58,070
og det er det vår base case er, så vi kommer tilbake med en gang.

458
00:34:58,070 --> 00:35:04,700
Har vi noen gang har mer enn så mange stabel rammer?

459
00:35:04,700 --> 00:35:08,880
Nei Fordi hver gang vi gjør en påkallelse,

460
00:35:08,880 --> 00:35:10,770
en rekursiv påkalling til shuffle,

461
00:35:10,770 --> 00:35:13,950
vi deler vår størrelse i to.

462
00:35:13,950 --> 00:35:17,020
Så det maksimale antallet stack rammer vi noensinne har til enhver tid

463
00:35:17,020 --> 00:35:28,460
er i størrelsesorden av log n stabel rammer.

464
00:35:28,460 --> 00:35:42,460
Hver stabel ramme har konstant plass,

465
00:35:42,460 --> 00:35:44,410
og derfor den totale mengde plass,

466
00:35:44,410 --> 00:35:49,240
den maksimale mengden plass som vi noen gang bruke er O (log n) plass

467
00:35:49,240 --> 00:36:03,040
der n er antall dager.

468
00:36:03,040 --> 00:36:07,230
>> Nå spør deg selv: «Kan vi gjøre det bedre?"

469
00:36:07,230 --> 00:36:12,390
Og i særdeleshet, kan vi redusere dette til et problem vi har allerede løst?

470
00:36:12,390 --> 00:36:20,040
Et hint: vi bare diskutert to andre problemer før dette, og det er ikke til å være shuffle.

471
00:36:20,040 --> 00:36:26,200
Vi kan konvertere dette aksjemarkedet problem i maksimal subarray problemet.

472
00:36:26,200 --> 00:36:40,100
Hvordan kan vi gjøre dette?

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

474
00:36:42,570 --> 00:36:47,680
(Emmy, uforståelig)

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

476
00:36:53,860 --> 00:36:59,940
Så maksimal subarray problem,

477
00:36:59,940 --> 00:37:10,610
Vi leter etter en sum over en sammenhengende subarray.

478
00:37:10,610 --> 00:37:16,230
Og Emmy forslag for aksjer problem,

479
00:37:16,230 --> 00:37:30,720
vurdere endringer, eller deltaer.

480
00:37:30,720 --> 00:37:37,440
Og et bilde av dette er - dette er prisen på en aksje,

481
00:37:37,440 --> 00:37:42,610
men hvis vi tok forskjellen mellom hver dag på rad -

482
00:37:42,610 --> 00:37:45,200
så ser vi at den høyeste prisen, maksimal profitt vi kunne gjøre

483
00:37:45,200 --> 00:37:50,070
er hvis vi kjøper her og selge her.

484
00:37:50,070 --> 00:37:54,240
Men la oss se på den kontinuerlige - la oss se på subarray problemet.

485
00:37:54,240 --> 00:38:02,510
Så her kan vi gjøre - går herfra til her,

486
00:38:02,510 --> 00:38:08,410
vi har en positiv endring, og deretter gå herfra til her har vi en negativ endring.

487
00:38:08,410 --> 00:38:14,220
Men så, går herfra til her har vi en stor positiv endring.

488
00:38:14,220 --> 00:38:20,930
Og disse er de endringene som vi ønsker å oppsummere å få vår sluttresultat.

489
00:38:20,930 --> 00:38:25,160
Da har vi mer negative endringer her.

490
00:38:25,160 --> 00:38:29,990
Nøkkelen til å redusere vårt lager problem i vår maksimal subarray problem

491
00:38:29,990 --> 00:38:36,630
er å vurdere deltaer mellom dagene.

492
00:38:36,630 --> 00:38:40,630
Så lager vi en ny array kalt deltaer,

493
00:38:40,630 --> 00:38:43,000
initialisere den første oppføringen til å være 0,

494
00:38:43,000 --> 00:38:46,380
og deretter for hver delta (i), la det være forskjellen

495
00:38:46,380 --> 00:38:52,830
av min inngang matrise (i), og matrise (i - 1).

496
00:38:52,830 --> 00:38:55,530
Så vi kaller vår rutine for en maksimal subarray

497
00:38:55,530 --> 00:39:01,500
passerer i et delta fylking.

498
00:39:01,500 --> 00:39:06,440
Og fordi maksimal subarray er lineær tid,

499
00:39:06,440 --> 00:39:09,370
og denne reduksjonen, denne prosessen med å opprette denne delta array,

500
00:39:09,370 --> 00:39:11,780
er også lineær tid,

501
00:39:11,780 --> 00:39:19,060
deretter den endelige løsningen for aksjer er O (n) arbeid pluss O (n) arbeid, er fortsatt O (n) arbeid.

502
00:39:19,060 --> 00:39:23,900
Så vi har en lineær tid løsningen på problemet vårt.

503
00:39:23,900 --> 00:39:29,610
Forstår alle denne transformasjonen?

504
00:39:29,610 --> 00:39:32,140
>> Generelt, en god idé at du bør alltid ha

505
00:39:32,140 --> 00:39:34,290
er å prøve å redusere et nytt problem som du ser.

506
00:39:34,290 --> 00:39:37,700
Hvis det ser kjent ut et gammelt problem,

507
00:39:37,700 --> 00:39:39,590
forsøke å redusere det til et gammelt problem.

508
00:39:39,590 --> 00:39:41,950
Og hvis du kan bruke alle verktøyene som du har brukt på det gamle problemet

509
00:39:41,950 --> 00:39:46,450
å løse det nye problem.

510
00:39:46,450 --> 00:39:49,010
Så for å bryte opp, er tekniske intervjuer utfordrende.

511
00:39:49,010 --> 00:39:52,280
Disse problemene er sannsynligvis noen av de mer vanskelige problemer

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

513
00:39:54,700 --> 00:39:57,690
så hvis du ikke forstår alle de problemene som jeg bare dekket, er det greit.

514
00:39:57,690 --> 00:40:01,080
Dette er noen av de mer utfordrende problemer.

515
00:40:01,080 --> 00:40:03,050
Øve, øve, øve.

516
00:40:03,050 --> 00:40:08,170
Jeg ga en masse problemer i handout, så definitivt sjekke dem ut.

517
00:40:08,170 --> 00:40:11,690
Og lykke til på dine intervjuer. Alle mine ressurser er lagt ut på denne linken,

518
00:40:11,690 --> 00:40:15,220
og en av mine senior venner har tilbudt seg å gjøre spotte tekniske intervjuer,

519
00:40:15,220 --> 00:40:22,050
så hvis du er interessert, e-post vil Yao på den e-postadressen.

520
00:40:22,050 --> 00:40:26,070
Hvis du har noen spørsmål, kan du spørre meg.

521
00:40:26,070 --> 00:40:28,780
Gjør dere har konkrete spørsmål knyttet til tekniske intervjuer

522
00:40:28,780 --> 00:40:38,440
eller eventuelle problemer vi har sett så langt?

523
00:40:38,440 --> 00:40:49,910
Okay. Vel, lykke til på dine intervjuer.

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