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

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
Hej alle, jeg er Kenny. Jeg er i øjeblikket en junior studere datalogi.

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

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

7
00:00:19,380 --> 00:00:21,370
Så jeg håber du nyder det.

8
00:00:21,370 --> 00:00:23,470
Dette seminar er om tekniske interviews,

9
00:00:23,470 --> 00:00:26,650
og alle mine ressourcer kan findes på dette link,

10
00:00:26,650 --> 00:00:32,350
dette link lige her, et par af ressourcer.

11
00:00:32,350 --> 00:00:36,550
Så jeg lavede en liste over problemer, faktisk en hel del problemer.

12
00:00:36,550 --> 00:00:40,800
Også en generel ressourcer side, hvor vi kan finde tips

13
00:00:40,800 --> 00:00:42,870
om, hvordan man forberede sig til et interview,

14
00:00:42,870 --> 00:00:46,470
tips om, hvad du skal gøre i løbet af en egentlig interview,

15
00:00:46,470 --> 00:00:51,910
samt hvordan man griber problemer og ressourcer til senere brug.

16
00:00:51,910 --> 00:00:53,980
Det er alt sammen online.

17
00:00:53,980 --> 00:00:58,290
Og bare for at indlede denne seminar, en ansvarsfraskrivelse,

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

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

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

21
00:01:04,750 --> 00:01:08,890
og du bør helt sikkert tage alt hvad jeg siger med et gran salt,

22
00:01:08,890 --> 00:01:14,620
men også bruge alt, hvad jeg bruges til at hjælpe dig i din interview forberedelse.

23
00:01:14,620 --> 00:01:16,400
>> Jeg har tænkt mig at fremskynde gennem de næste par dias

24
00:01:16,400 --> 00:01:18,650
så vi kan få de faktiske case studies.

25
00:01:18,650 --> 00:01:23,630
Strukturen i et interview for et software engineering postion,

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

27
00:01:26,320 --> 00:01:29,810
flere runder, afhængig af selskabet.

28
00:01:29,810 --> 00:01:33,090
Ofte vil du blive kodning på en hvid bord.

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

30
00:01:35,960 --> 00:01:38,540
Hvis du har en telefon interview, vil du sandsynligvis bruge

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

32
00:01:44,030 --> 00:01:46,500
mens du bliver interviewet over telefonen.

33
00:01:46,500 --> 00:01:48,490
Et interview selv er typisk 2 eller 3 problemer

34
00:01:48,490 --> 00:01:50,620
teste din computer science viden.

35
00:01:50,620 --> 00:01:54,490
Og det vil næsten helt sikkert indebære kodning.

36
00:01:54,490 --> 00:01:59,540
De typer af spørgsmål, som du vil se er normalt datastrukturer og algoritmer.

37
00:01:59,540 --> 00:02:02,210
Og ved at gøre den slags problemer,

38
00:02:02,210 --> 00:02:07,830
de vil bede dig, vil, hvad er tid og rum kompleksitet, big O?

39
00:02:07,830 --> 00:02:09,800
Ofte beder også højere niveau spørgsmål,

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

41
00:02:12,530 --> 00:02:14,770
hvordan ville du sætte din kode?

42
00:02:14,770 --> 00:02:18,370
Hvilke grænseflader, hvad klasser, hvad moduler, du har i dit system,

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

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

45
00:02:26,130 --> 00:02:29,180
>> Nogle generelle tips, før vi dykker ind i vores case studies.

46
00:02:29,180 --> 00:02:32,300
Jeg tror den vigtigste regel er altid tænker højt.

47
00:02:32,300 --> 00:02:36,980
Interviewet formodes at være din chance for at vise din tankeproces.

48
00:02:36,980 --> 00:02:39,820
Pointen med samtalen er for intervieweren at vurdere

49
00:02:39,820 --> 00:02:42,660
hvordan du tænker og hvordan du går gennem et problem.

50
00:02:42,660 --> 00:02:45,210
Det værste du kan gøre er at være tavs gennem hele interviewet.

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

52
00:02:50,090 --> 00:02:53,230
Når du får et spørgsmål, du også ønsker at sikre, at du forstår spørgsmålet.

53
00:02:53,230 --> 00:02:55,350
Så gentage spørgsmålet tilbage i dine egne ord

54
00:02:55,350 --> 00:02:58,920
og forsøge at arbejde grundige et par enkle testcases

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

56
00:03:01,530 --> 00:03:05,510
Arbejde gennem et par testcases vil også give dig en intuition om, hvordan man løser dette problem.

57
00:03:05,510 --> 00:03:11,210
Du kan endda opdage et par mønstre til at hjælpe dig med at løse problemet.

58
00:03:11,210 --> 00:03:14,500
Deres store tip er ikke at blive frustreret.

59
00:03:14,500 --> 00:03:17,060
Må ikke blive frustreret.

60
00:03:17,060 --> 00:03:19,060
Interviews er udfordrende, men det værste du kan gøre,

61
00:03:19,060 --> 00:03:23,330
ud over at være tavs, skal synligt frustreret.

62
00:03:23,330 --> 00:03:27,410
Du ønsker ikke at give det indtryk at en interviewer.

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

64
00:03:33,960 --> 00:03:37,150
de forsøger at forsøge at finde den bedste løsning først,

65
00:03:37,150 --> 00:03:39,950
når der virkelig, er der normalt en grelt indlysende løsning.

66
00:03:39,950 --> 00:03:43,500
Det kan være langsom, kan det være ineffektiv, men du skal bare oplyse det,

67
00:03:43,500 --> 00:03:46,210
bare så du har et udgangspunkt, hvorfra man kan arbejde bedre.

68
00:03:46,210 --> 00:03:48,270
Også under henvisning til, at opløsningen er langsom med hensyn til

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

70
00:03:52,160 --> 00:03:54,450
vil vise intervieweren, at du forstår

71
00:03:54,450 --> 00:03:57,510
disse spørgsmål, når du skriver kode.

72
00:03:57,510 --> 00:04:01,440
Så vær ikke bange for at komme op med den enkleste algoritme 1:e

73
00:04:01,440 --> 00:04:04,950
og derefter arbejde bedre derfra.

74
00:04:04,950 --> 00:04:09,810
Eventuelle spørgsmål indtil videre? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Så lad os dykke ned i vores første problem.

76
00:04:11,650 --> 00:04:14,790
"Givet et array af n heltal, skrive en funktion, der blander array

77
00:04:14,790 --> 00:04:20,209
på plads, således at alle permutationer af n heltal er lige sandsynlige. "

78
00:04:20,209 --> 00:04:23,470
Og antager at du har til rådighed et tilfældigt heltal generator

79
00:04:23,470 --> 00:04:30,980
der genererer et helt tal i området fra 0 til I, halvt interval.

80
00:04:30,980 --> 00:04:32,970
Skal alle forstår dette spørgsmål?

81
00:04:32,970 --> 00:04:39,660
Jeg giver dig en vifte af n heltal, og jeg vil have dig til at blande det.

82
00:04:39,660 --> 00:04:46,050
I min mappe, skrev jeg et par programmer til at vise, hvad jeg mener.

83
00:04:46,050 --> 00:04:48,910
Jeg har tænkt mig at blande et array af 20 elementer,

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

85
00:04:52,490 --> 00:04:57,050
og jeg vil have dig til at udsende en liste som denne.

86
00:04:57,050 --> 00:05:02,890
Så dette er min sorteres inputarrayet, og jeg vil have dig til at blande det.

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

88
00:05:07,070 --> 00:05:13,780
Skal alle forstå spørgsmålet? Okay.

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

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

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

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

93
00:05:37,730 --> 00:05:45,300
først beregne et tilfældigt tal, tilfældigt heltal, i området 0-20.

94
00:05:45,300 --> 00:05:49,840
Så påtage os vores matrix har en længde på 20.

95
00:05:49,840 --> 00:05:54,800
I vores diagram af 20 elementer,

96
00:05:54,800 --> 00:05:58,560
dette er vores input array.

97
00:05:58,560 --> 00:06:04,590
Og nu, hendes forslag er at skabe et nyt array,

98
00:06:04,590 --> 00:06:08,440
så det bliver output array.

99
00:06:08,440 --> 00:06:12,880
Og baseret på den jeg vendte tilbage ved rand -

100
00:06:12,880 --> 00:06:17,580
så hvis jeg var, lad os sige, 17,

101
00:06:17,580 --> 00:06:25,640
kopiere det 17. element i den første stilling.

102
00:06:25,640 --> 00:06:30,300
Nu skal vi til at slette - vi er nødt til at flytte alle de elementer, der her

103
00:06:30,300 --> 00:06:36,920
over, så vi har en åbning ved enden og ingen huller i midten.

104
00:06:36,920 --> 00:06:39,860
Og nu vi gentage processen.

105
00:06:39,860 --> 00:06:46,360
Nu skal vi vælge et nyt tilfældigt heltal mellem 0 og 19.

106
00:06:46,360 --> 00:06:52,510
Vi har en ny jeg her, og vi kopiere dette element i denne position.

107
00:06:52,510 --> 00:07:00,960
Så vi flytter elementer over og vi gentage processen, indtil vi har vores fulde nyt array.

108
00:07:00,960 --> 00:07:05,890
Hvad er driftstiden for denne algoritme?

109
00:07:05,890 --> 00:07:08,110
Nå, lad os overveje konsekvenserne af dette.

110
00:07:08,110 --> 00:07:10,380
Vi er ved at skifte hvert element.

111
00:07:10,380 --> 00:07:16,800
Når vi fjerner denne i, er vi flytte alle elementer efter det til venstre.

112
00:07:16,800 --> 00:07:21,600
Og det er en O (n) omkostninger

113
00:07:21,600 --> 00:07:26,100
for hvad nu hvis vi fjerner det første element?

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

115
00:07:29,670 --> 00:07:32,170
hver fjernelse lider et O (n) operation,

116
00:07:32,170 --> 00:07:41,520
og da vi har n flytninger fører dette til et 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 andet forslag er at bruge noget kendt som 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 meget ens.

122
00:08:02,200 --> 00:08:05,160
Igen har vi vores input array,

123
00:08:05,160 --> 00:08:08,580
men i stedet for at bruge to arrays for vores input / output,

124
00:08:08,580 --> 00:08:13,590
Vi bruger den første del af sættet til at holde styr på vores blandet portion,

125
00:08:13,590 --> 00:08:18,400
og vi holder styr, og så må vi overlade resten af ​​vores array til den unshuffled del.

126
00:08:18,400 --> 00:08:24,330
Så her er hvad jeg mener. Vi starter med - vi vælger et i,

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

128
00:08:30,910 --> 00:08:36,150
Vores nuværende pointer peger på den første indeks.

129
00:08:36,150 --> 00:08:39,590
Vi vælger nogle jeg her

130
00:08:39,590 --> 00:08:42,740
og nu 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
det resulterende array have 5 her og 4 her.

133
00:08:57,150 --> 00:09:00,390
Og nu vi konstatere en markør her.

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

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

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

137
00:09:17,260 --> 00:09:25,210
Vi vælger et tilfældigt indeks mellem 1 og 20 nu.

138
00:09:25,210 --> 00:09:30,650
Så formoder vores nye i er her.

139
00:09:30,650 --> 00:09:39,370
Nu skal vi bytte denne i med vores nuværende nye position her.

140
00:09:39,370 --> 00:09:44,790
Så vi gør en bytte frem og tilbage på denne måde.

141
00:09:44,790 --> 00:09:51,630
Lad mig hente koden for at gøre det mere konkret.

142
00:09:51,630 --> 00:09:55,290
Vi starter med vores valg af i -

143
00:09:55,290 --> 00:09:58,370
vi starter med i lig med 0, vi vælger en tilfældig placering j

144
00:09:58,370 --> 00:10:02,420
i unshuffled del af sættet, at i n-1.

145
00:10:02,420 --> 00:10:07,280
Så hvis jeg er her, skal du vælge en tilfældig indeks mellem her og resten af ​​array,

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

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

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

149
00:10:21,670 --> 00:10:25,530
>> Tja, en nødvendig Spørgsmålet er, hvorfor er dette korrekt?

150
00:10:25,530 --> 00:10:28,360
Hvorfor er hver permutation lige sandsynlige?

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

152
00:10:30,410 --> 00:10:35,970
men mange problemer i datalogi kan bevises ved induktion.

153
00:10:35,970 --> 00:10:38,520
Hvor mange af jer er bekendt med induktion?

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

155
00:10:40,590 --> 00:10:43,610
Så du kan bevise rigtigheden af ​​denne algoritme ved simpel induktion,

156
00:10:43,610 --> 00:10:49,540
hvor din induktion hypotese ville være, antage, at

157
00:10:49,540 --> 00:10:53,290
min shuffle returnerer hver permutation lige sandsynlige

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

159
00:10:56,120 --> 00:10:58,300
Nu mener jeg, + 1.

160
00:10:58,300 --> 00:11:02,550
Og ved den måde, vi vælger vores indeks j til at bytte,

161
00:11:02,550 --> 00:11:05,230
dette fører til - og så skal du finde ud af detaljerne,

162
00:11:05,230 --> 00:11:07,390
mindst en hel bevis på, hvorfor denne algoritme returnerer

163
00:11:07,390 --> 00:11:12,800
hver permutation med lige sandsynlige sandsynlighed.

164
00:11:12,800 --> 00:11:15,940
>> Okay, næste problem.

165
00:11:15,940 --> 00:11:19,170
Så "givet et array af heltal, postive, nul, negative,

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

167
00:11:21,290 --> 00:11:24,720
enhver continueous subarray af inputarrayet. "

168
00:11:24,720 --> 00:11:28,370
Et eksempel her er, i det tilfælde, hvor alle tal er positive,

169
00:11:28,370 --> 00:11:31,320
så i øjeblikket det bedste valg er at tage hele array.

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

171
00:11:34,690 --> 00:11:36,780
Når du har nogle negativer derinde,

172
00:11:36,780 --> 00:11:38,690
i dette tilfælde vil vi blot de to første

173
00:11:38,690 --> 00:11:44,590
fordi du vælger -1 og / eller -3 vil bringe vores sum ned.

174
00:11:44,590 --> 00:11:48,120
Nogle gange er vi måske nødt til at starte i midten af ​​array.

175
00:11:48,120 --> 00:11:53,500
Nogle gange er vi ønsker at vælge noget som helst, det er bedst ikke at tage noget som helst.

176
00:11:53,500 --> 00:11:56,490
Og nogle gange er det bedre at tage skraldet,

177
00:11:56,490 --> 00:12:07,510
fordi ting efter det er super stor. Så nogen ideer?

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

179
00:12:10,970 --> 00:12:13,560
Antag jeg ikke tage -1.

180
00:12:13,560 --> 00:12:16,170
Så enten jeg vælger 1.000 og 20.000,

181
00:12:16,170 --> 00:12:18,630
eller jeg bare vælge den 3 mia.

182
00:12:18,630 --> 00:12:20,760
Nå, det bedste valg er at tage alle de tal.

183
00:12:20,760 --> 00:12:24,350
Denne -1, til trods for at være negativ,

184
00:12:24,350 --> 00:12:31,340
hele summen er bedre end var jeg ikke til at tage -1.

185
00:12:31,340 --> 00:12:36,460
Så en af ​​de tips jeg nævnte tidligere var at angive tydeligt indlysende

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

187
00:12:40,540 --> 00:12:44,340
Hvad er det brute force løsning på dette problem? Ja?

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

189
00:12:46,890 --> 00:12:52,600
ville være at lægge alle de mulige kombinationer (uforståelig).

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

191
00:12:58,250 --> 00:13:01,470
Jeg parafraserer - er at tage alle mulige kontinuerlig subarray,

192
00:13:01,470 --> 00:13:07,840
beregne sin sum, og derefter tage den største af alle de mulige kontinuerlige subarrays.

193
00:13:07,840 --> 00:13:13,310
Hvad entydigt identificerer en subarray i mit input array?

194
00:13:13,310 --> 00:13:17,380
Ligesom, hvad to ting skal jeg bruge? Ja?

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

196
00:13:19,970 --> 00:13:22,130
En nedre grænse på indeks og en øvre grænse indeks

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

198
00:13:28,300 --> 00:13:31,400
[Kvinde elev] Er vi anslå at det er en vifte af unikke numre?

199
00:13:31,400 --> 00:13:34,280
[Yu] Nej Så hendes spørgsmål er, er vi antager vores array -

200
00:13:34,280 --> 00:13:39,000
er vores array alle unikke numre, og svaret er nej.

201
00:13:39,000 --> 00:13:43,390
>> Hvis vi bruger vores brute force løsning, så start / slut indekser

202
00:13:43,390 --> 00:13:47,200
entydigt bestemmer vores kontinuerlige subarray.

203
00:13:47,200 --> 00:13:51,680
Så hvis vi gentage til alle mulige start poster,

204
00:13:51,680 --> 00:13:58,320
og for alle endelige indtastninger> eller = for at starte, og <n,

205
00:13:58,320 --> 00:14:05,570
du beregne summen, og så må vi tage den maksimale sum, vi har set hidtil.

206
00:14:05,570 --> 00:14:07,880
Er det forstået?

207
00:14:07,880 --> 00:14:12,230
Hvad er den store O i denne løsning?

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

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

210
00:14:18,860 --> 00:14:25,250
Bemærk, at vi gentage 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 gentage igen fra næsten begyndelsen til enden, en anden for løkke.

213
00:14:35,120 --> 00:14:37,640
Og nu, inden det er vi nødt til opsummere hver indrejse,

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

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

216
00:14:46,560 --> 00:14:53,180
Vores løsning er ikke værre end n ^ 3.

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

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

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

220
00:15:03,040 --> 00:15:05,680
vil du blive meget fortrolig med denne teknik.

221
00:15:05,680 --> 00:15:12,190
Og ideen er, så prøv at opbygge løsninger til mindre problemer først.

222
00:15:12,190 --> 00:15:17,990
Hvad jeg mener med dette er, vi har i øjeblikket at bekymre sig om to ting: start og slut.

223
00:15:17,990 --> 00:15:29,340
Og det er irriterende. Hvad hvis vi kunne slippe af med en af ​​disse parametre?

224
00:15:29,340 --> 00:15:32,650
En idé er at - vi er klar givet vores oprindelige problem,

225
00:15:32,650 --> 00:15:37,470
finde den maksimale sum af en subarray i et interval [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Og nu har vi en ny subproblem, hvor vi ved, i vores nuværende indeks i,

227
00:15:47,400 --> 00:15:52,520
Vi ved, at vi må konkludere, at der. Vores subarray skal slutte på det aktuelle indeks.

228
00:15:52,520 --> 00:15:57,640
Så tilbageværende problem er, hvor skal vi starte vores subarray?

229
00:15:57,640 --> 00:16:05,160
Giver det mening? Okay.

230
00:16:05,160 --> 00:16:12,030
Så jeg har kodet det op, og lad os se på, hvad dette betyder.

231
00:16:12,030 --> 00:16:16,230
I codirectory, er der et program kaldet subarray,

232
00:16:16,230 --> 00:16:19,470
og det tager antal varer,

233
00:16:19,470 --> 00:16:25,550
og returnerer den maksimale subarray sum på min blandet liste.

234
00:16:25,550 --> 00:16:29,920
Så i dette tilfælde, er vores maksimale subarray 3.

235
00:16:29,920 --> 00:16:34,850
Og det har taget ved blot at bruge 2 og 1.

236
00:16:34,850 --> 00:16:38,050
Lad os køre den igen. Det er også 3.

237
00:16:38,050 --> 00:16:40,950
Men denne gang, bemærke, hvordan vi fik den 3.

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

239
00:16:46,690 --> 00:16:49,980
fordi det er omgivet af 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
Lad os køre på 10 punkter.

242
00:16:57,820 --> 00:17:03,200
Denne gang er det 7, tager vi den førende 3 og 4.

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

244
00:17:09,450 --> 00:17:16,310
Så for at give dig en intuition om, hvordan vi kan løse dette transformeret problem,

245
00:17:16,310 --> 00:17:18,890
lad os tage et kig på denne subarray.

246
00:17:18,890 --> 00:17:23,460
Vi er givet dette input array, og vi kender svaret er 8.

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

248
00:17:26,359 --> 00:17:29,090
Men lad os se på, hvordan vi rent faktisk fik det svar.

249
00:17:29,090 --> 00:17:34,160
Lad os se på den maksimale subarray, der endte på hvert af disse indeks.

250
00:17:34,160 --> 00:17:40,780
Hvad er den maksimale subarray der skal ende i den første position?

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

252
00:17:46,310 --> 00:17:50,210
Her kommer til at være 0 så godt. Ja?

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

254
00:17:56,470 --> 00:17:58,960
[Yu] Åh, undskyld, 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, hvad er den maksimale subarray at afslutte denne position

257
00:18:08,690 --> 00:18:12,910
hvor -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
Nu må jeg slutte på det sted, hvor -2 er på.

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

261
00:18:39,330 --> 00:18:43,480
Vel vidende, at disse er mine poster

262
00:18:43,480 --> 00:18:48,130
for den transformerede problem, hvor jeg skal ende på hvert af disse indeks,

263
00:18:48,130 --> 00:18:51,410
så mit endelige svar er bare, tage en feje tværs,

264
00:18:51,410 --> 00:18:53,580
og tage det maksimale antal.

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

266
00:18:55,620 --> 00:19:00,010
Dette indebærer, at den maksimale subarray slutter ved dette indeks,

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

268
00:19:04,970 --> 00:19:09,630
Skal alle forstå dette transformeret subarray?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Nå, lad os finde ud af gentagelse for dette.

270
00:19:22,160 --> 00:19:27,990
Lad os overveje bare de første par poster.

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 der en -2 her, og det bragte det ned til 6.

273
00:19:39,790 --> 00:19:50,800
Så hvis jeg kalder indrejse ved position i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
hvordan kan jeg bruge svaret til en tidligere subproblem

275
00:19:54,910 --> 00:19:59,360
at besvare dette subproblem?

276
00:19:59,360 --> 00:20:04,550
Hvis jeg ser på, lad os sige, denne post.

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

278
00:20:09,190 --> 00:20:18,780
en kombination af dette array, og svarene på tidligere delproblemer i denne array? Ja?

279
00:20:18,780 --> 00:20:22,800
[Kvinde elev] Du tager den vifte af beløb

280
00:20:22,800 --> 00:20:25,430
i positionen lige før det, så de 8,

281
00:20:25,430 --> 00:20:32,170
og du derefter tilføje den aktuelle subproblem.

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

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

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

285
00:20:50,130 --> 00:20:57,300
Og lad os kalde min inputarrayet A.

286
00:20:57,300 --> 00:21:01,470
For at finde en maksimal subarray der ender i position i,

287
00:21:01,470 --> 00:21:03,980
Jeg har to valgmuligheder: Jeg kan enten fortsætte subarray

288
00:21:03,980 --> 00:21:09,790
der endte på det foregående indeks, eller starte et nyt array.

289
00:21:09,790 --> 00:21:14,190
Hvis jeg skulle fortsætte den subarray, der startede på det foregående indeks,

290
00:21:14,190 --> 00:21:19,260
så den maksimale sum jeg kan opnå, er svaret på det foregående subproblem

291
00:21:19,260 --> 00:21:24,120
plus den aktuelle array-post.

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

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

294
00:21:30,830 --> 00:21:42,860
Så svaret er max på 0, subproblem i - 1, plus den aktuelle array-post.

295
00:21:42,860 --> 00:21:46,150
Betyder dette tilbagefald mening?

296
00:21:46,150 --> 00:21:50,840
Vores tilbagefald, som vi har lige opdaget, er subproblem i

297
00:21:50,840 --> 00:21:54,740
er lig med den maksimale af den tidligere subproblem plus min nuværende array-post,

298
00:21:54,740 --> 00:22:01,490
hvilket betyder, fortsætter det forrige subarray,

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

300
00:22:07,250 --> 00:22:10,060
Og når vi har opbygget denne tabel af løsninger, så vores endelige svar,

301
00:22:10,060 --> 00:22:13,950
bare lave en lineær fejer hen over subproblem-array

302
00:22:13,950 --> 00:22:19,890
og tage det maksimale antal.

303
00:22:19,890 --> 00:22:23,330
Dette er en nøjagtig gennemførelse af det, jeg lige har sagt.

304
00:22:23,330 --> 00:22:27,320
Så vi opretter en ny subproblem array, delproblemer.

305
00:22:27,320 --> 00:22:32,330
Den første post er enten 0 eller den første post, det maksimale af de to.

306
00:22:32,330 --> 00:22:35,670
Og resten af ​​delproblemer

307
00:22:35,670 --> 00:22:39,810
vi bruger den nøjagtige gentagelse vi lige opdaget.

308
00:22:39,810 --> 00:22:49,960
Nu skal vi beregne det maksimale af vores delproblemer array, og det er vores endelige svar.

309
00:22:49,960 --> 00:22:54,130
>> Så hvor meget plads bruger vi i denne algoritme?

310
00:22:54,130 --> 00:23:01,470
Hvis du kun har taget CS50, så skal du måske ikke har diskuteret plads meget.

311
00:23:01,470 --> 00:23:07,750
Tja, en ting at bemærke er, at jeg ringede malloc her med størrelsen n.

312
00:23:07,750 --> 00:23:13,590
Hvad betyder det foreslå dig?

313
00:23:13,590 --> 00:23:17,450
Denne algoritme anvender lineær plads.

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

315
00:23:21,030 --> 00:23:30,780
Er der noget, du bemærker, at er unødvendigt at beregne det endelige svar?

316
00:23:30,780 --> 00:23:33,290
Jeg gætte et bedre spørgsmål er, hvilke oplysninger

317
00:23:33,290 --> 00:23:40,680
behøver vi ikke at bære hele vejen igennem til slutningen?

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

319
00:23:44,280 --> 00:23:47,720
vi kun interesserer os for den tidligere subproblem,

320
00:23:47,720 --> 00:23:50,910
og vi kun bekymrer sig om det maksimale, vi nogensinde har set hidtil.

321
00:23:50,910 --> 00:23:53,610
For at beregne vores endelige svar, behøver vi ikke hele array.

322
00:23:53,610 --> 00:23:57,450
Vi har kun brug for det sidste nummer, sidste to numre.

323
00:23:57,450 --> 00:24:02,630
Sidste nummer for subproblem array, og sidste tal for den maksimale.

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

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

326
00:24:10,460 --> 00:24:15,830
Løbende sum hidtil her, erstatter den rolle subproblem, vores subproblem array.

327
00:24:15,830 --> 00:24:20,020
Så aktuelle sum, indtil videre, er svaret på det foregående subproblem.

328
00:24:20,020 --> 00:24:23,450
Og dette beløb hidtil træder i stedet for vores max.

329
00:24:23,450 --> 00:24:28,100
Vi beregner det maksimale, som vi hen ad vejen.

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

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

332
00:24:36,650 --> 00:24:40,740
>> Disse former for spørgsmål, du får i løbet af et interview.

333
00:24:40,740 --> 00:24:44,450
Hvad er den tid kompleksitet, hvad er den plads kompleksitet?

334
00:24:44,450 --> 00:24:50,600
Kan du gøre det bedre? Er der ting, der er unødvendige for at holde rundt?

335
00:24:50,600 --> 00:24:55,270
Jeg gjorde det for at fremhæve analyser, som du bør tage på egen hånd

336
00:24:55,270 --> 00:24:57,400
som du arbejder gennem disse problemer.

337
00:24:57,400 --> 00:25:01,710
Altid spørge dig selv, "Kan jeg gøre det bedre?"

338
00:25:01,710 --> 00:25:07,800
Faktisk kan vi gøre det bedre end dette?

339
00:25:07,800 --> 00:25:10,730
Sorter af et trick spørgsmål. Du kan ikke, fordi du har brug for

340
00:25:10,730 --> 00:25:13,590
i det mindste læse indgangen på problemet.

341
00:25:13,590 --> 00:25:15,570
Så det faktum, at du skal i det mindste læse input til problemet

342
00:25:15,570 --> 00:25:19,580
betyder, at du ikke kan gøre det bedre end den lineære tid,

343
00:25:19,580 --> 00:25:22,870
og du kan ikke gøre det bedre end konstant rum.

344
00:25:22,870 --> 00:25:27,060
Så dette er faktisk den bedste løsning på dette problem.

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

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

347
00:25:35,190 --> 00:25:38,350
"Givet et array af n heltal, positive, nul eller negativ,

348
00:25:38,350 --> 00:25:41,680
der repræsenterer prisen for en bestand over n dage,

349
00:25:41,680 --> 00:25:44,080
skrive en funktion til at beregne den maksimale profit, du kan gøre

350
00:25:44,080 --> 00:25:49,350
i betragtning af at du køber og sælger præcis 1 bestand inden for disse n dage. "

351
00:25:49,350 --> 00:25:51,690
Grundlæggende ønsker vi at købe lav, sælge højt.

352
00:25:51,690 --> 00:25:58,580
Og vi ønsker at finde ud af den bedste resultat, vi kan gøre.

353
00:25:58,580 --> 00:26:11,500
Går tilbage til min tip, hvad er det umiddelbart klart, enkleste svar, men det er langsom?

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

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

356
00:26:21,470 --> 00:26:30,550
ved hvert tidspunkt, (uforståelig).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okay, så hendes løsning - hendes forslag om computing

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

359
00:26:37,380 --> 00:26:42,470
idet det højeste kan forekomme før det laveste.

360
00:26:42,470 --> 00:26:47,340
Så hvad er det brute force løsning på dette problem?

361
00:26:47,340 --> 00:26:53,150
Hvad er de to ting, som jeg har brug for at entydigt bestemme den fortjeneste jeg gøre? Right.

362
00:26:53,150 --> 00:26:59,410
Den brute force løsning er - åh, ja, George forslag er, at vi kun nødvendigt med to dages

363
00:26:59,410 --> 00:27:02,880
til entydigt at fastsætte fortjenesten på disse to dage.

364
00:27:02,880 --> 00:27:06,660
Så vi beregne hvert par, gerne købe / sælge,

365
00:27:06,660 --> 00:27:12,850
beregne den fortjeneste, som kunne være negativ eller positiv eller nul.

366
00:27:12,850 --> 00:27:18,000
Beregn den maksimale profit, at vi gør efter iteration over alle par af dage.

367
00:27:18,000 --> 00:27:20,330
Det vil være vores endelige svar.

368
00:27:20,330 --> 00:27:25,730
Og denne løsning vil være O (n ^ 2), fordi der er n vælge to par -

369
00:27:25,730 --> 00:27:30,270
af dage, som du kan vælge mellem sidste dage.

370
00:27:30,270 --> 00:27:32,580
Okay, så jeg har ikke tænkt mig at gå over den brute force løsning her.

371
00:27:32,580 --> 00:27:37,420
Jeg har tænkt mig at fortælle dig, at der er en n log n løsning.

372
00:27:37,420 --> 00:27:45,550
Hvilken algoritme du i øjeblikket ved, det er n log n?

373
00:27:45,550 --> 00:27:50,730
Det er ikke et trick spørgsmål.

374
00:27:50,730 --> 00:27:54,790
>> Flet slags. Flet slags er n log n,

375
00:27:54,790 --> 00:27:57,760
og faktisk er én måde at løse dette problem at bruge

376
00:27:57,760 --> 00:28:04,400
en sammenfletning slags slags idé kaldes, i almindelighed, del og hersk.

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

378
00:28:07,570 --> 00:28:12,400
Du ønsker at beregne det bedste køb / salg parret i den venstre halvdel.

379
00:28:12,400 --> 00:28:16,480
Find det bedste resultat, du kan gøre, bare med den første n over to dage.

380
00:28:16,480 --> 00:28:19,780
Så du ønsker at oompute det bedste køb / salg par på den højre halvdel,

381
00:28:19,780 --> 00:28:23,930
så den sidste n over to dage.

382
00:28:23,930 --> 00:28:32,400
Og nu er spørgsmålet, hvordan kan vi flette disse løsninger sammen igen?

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

384
00:28:36,320 --> 00:28:49,890
>> Okay. Så lad mig tegne et billede.

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

386
00:29:03,870 --> 00:29:06,450
>> Præcis. George løsning er den helt rigtige.

387
00:29:06,450 --> 00:29:10,040
Så hans forslag er først beregne den bedste køber / sælger par,

388
00:29:10,040 --> 00:29:16,050
og der opstår i den venstre halvdel, så lad os kalde det venstre, venstre.

389
00:29:16,050 --> 00:29:20,790
Best køber / sælger par, der opstår i den højre halvdel.

390
00:29:20,790 --> 00:29:25,180
Men hvis vi kun sammenlignet disse to tal, vi mangler sagen

391
00:29:25,180 --> 00:29:30,460
hvor vi køber her og sælge et eller andet sted i højre halvdel.

392
00:29:30,460 --> 00:29:33,810
Vi køber i den venstre halvdel, sælge i højre halvdel.

393
00:29:33,810 --> 00:29:38,490
Og den bedste måde at beregne den bedste køber / sælger par, der strækker sig over begge halvdele

394
00:29:38,490 --> 00:29:43,480
er at beregne den minimale her og beregne den maksimale her

395
00:29:43,480 --> 00:29:45,580
og tage deres forskel.

396
00:29:45,580 --> 00:29:50,850
Så de to tilfælde, hvor køber / sælger par forekommer kun her,

397
00:29:50,850 --> 00:30:01,910
Kun her, eller på begge halvdele defineres af disse tre tal.

398
00:30:01,910 --> 00:30:06,450
Så vores algoritme til at fusionere vores løsninger sammen igen,

399
00:30:06,450 --> 00:30:08,350
vi ønsker at beregne den bedste køber / sælger par

400
00:30:08,350 --> 00:30:13,120
hvor vi køber på venstre halvdel og sælge på den højre halvdel.

401
00:30:13,120 --> 00:30:16,740
Og den bedste måde at gøre det er at beregne den laveste pris i første halvår,

402
00:30:16,740 --> 00:30:20,360
den højeste pris i den højre halvdel, og tage deres forskel.

403
00:30:20,360 --> 00:30:25,390
De resulterende tre overskud, disse tre tal, du tager det maksimale af de tre,

404
00:30:25,390 --> 00:30:32,720
og det er det bedste resultat, du kan gøre i løbet af disse første og slutningen dage.

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

406
00:30:36,940 --> 00:30:41,160
Dette er et rekursivt kald til beregning svaret i den venstre halvdel.

407
00:30:41,160 --> 00:30:44,760
Dette er et rekursivt kald til beregning svaret i den højre halvdel.

408
00:30:44,760 --> 00:30:50,720
Disse to for-løkker beregne min og max til venstre og højre halvdel, henholdsvis.

409
00:30:50,720 --> 00:30:54,970
Nu vil jeg beregne den fortjeneste, der spænder over begge halvdele,

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

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

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

413
00:31:06,420 --> 00:31:08,290
hvad er den tid kompleksiteten af ​​dette?

414
00:31:08,290 --> 00:31:16,190
Og grunden til, at jeg nævnte merge art er, at denne form for opdele svaret

415
00:31:16,190 --> 00:31:19,200
i to og derefter flette vores løsninger sammen igen

416
00:31:19,200 --> 00:31:23,580
er præcis den form for fletningen art.

417
00:31:23,580 --> 00:31:33,360
Så lad mig gå igennem varighed.

418
00:31:33,360 --> 00:31:41,340
Hvis vi defineret en funktion t (n) er antallet af trin

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

420
00:31:50,010 --> 00:31:54,350
vores to rekursive kald

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

422
00:32:00,460 --> 00:32:03,540
og der er to af disse opkald.

423
00:32:03,540 --> 00:32:10,020
Nu har jeg brug for at beregne et minimum af den venstre halvdel,

424
00:32:10,020 --> 00:32:17,050
som jeg kan gøre i n / 2 gang, plus maksimum for den højre halvdel.

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

426
00:32:20,820 --> 00:32:25,050
Og så plus nogle konstant arbejde.

427
00:32:25,050 --> 00:32:27,770
Og denne gentagelse ligning

428
00:32:27,770 --> 00:32:35,560
er netop fornyet ligning for sammenfletning slags.

429
00:32:35,560 --> 00:32:39,170
Og vi ved alle, at fletningen slags er n log n tid.

430
00:32:39,170 --> 00:32:46,880
Derfor er vores algoritme også n log n tid.

431
00:32:46,880 --> 00:32:52,220
Betyder dette iteration mening?

432
00:32:52,220 --> 00:32:55,780
Blot en kort resumé af dette:

433
00:32:55,780 --> 00:32:59,170
T (n) er antallet af trin til at beregne den maksimale profit

434
00:32:59,170 --> 00:33:02,750
i løbet af n dage.

435
00:33:02,750 --> 00:33:06,010
Den måde vi delt op vores rekursive kald

436
00:33:06,010 --> 00:33:11,980
er ved at kalde vores løsning på de første n / 2 dage,

437
00:33:11,980 --> 00:33:14,490
så det er et opkald,

438
00:33:14,490 --> 00:33:16,940
og så kalder vi igen på den anden halvdel.

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

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

441
00:33:25,310 --> 00:33:29,010
finde maksimum for den højre halvdel, som vi kan gøre i lineær tid.

442
00:33:29,010 --> 00:33:31,570
Så n / 2 + n / 2 er blot n.

443
00:33:31,570 --> 00:33:36,020
Så vi har nogle konstant arbejde, der er lyst til at gøre matematik.

444
00:33:36,020 --> 00:33:39,860
Denne tilbagevenden ligning er netop fornyet ligning for sammenfletning slags.

445
00:33:39,860 --> 00:33:55,490
Derfor er vores shuffle algoritme er også n log n.

446
00:33:55,490 --> 00:33:58,520
Så hvor meget plads bruger vi?

447
00:33:58,520 --> 00:34:04,910
Lad os gå tilbage til koden.

448
00:34:04,910 --> 00:34:09,420
>> Et bedre spørgsmål er, hvor mange stakrammer vi nogensinde har på et givet tidspunkt?

449
00:34:09,420 --> 00:34:11,449
Da vi bruger rekursion,

450
00:34:11,449 --> 00:34:23,530
antallet af stakrammer bestemmer vores pladsudnyttelsen.

451
00:34:23,530 --> 00:34:29,440
Lad os overveje n = 8.

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

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

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

455
00:34:46,250 --> 00:34:51,550
Så vores stack er - det er vores stack.

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

457
00:34:54,980 --> 00:34:58,070
og det er hvad vores base case er, så vi vender tilbage med det samme.

458
00:34:58,070 --> 00:35:04,700
Har vi nogensinde har mere end så mange stakrammer?

459
00:35:04,700 --> 00:35:08,880
Nej Fordi hver gang vi gør en besværgelse,

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

461
00:35:10,770 --> 00:35:13,950
vi deler vores størrelse i halve.

462
00:35:13,950 --> 00:35:17,020
Så det maksimale antal stakrammer vi nogensinde har på et givet tidspunkt

463
00:35:17,020 --> 00:35:28,460
er på rækkefølgen af ​​logn stak frames.

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

465
00:35:42,460 --> 00:35:44,410
og derfor den totale mængde plads,

466
00:35:44,410 --> 00:35:49,240
den maksimale mængde plads, vi nogensinde bruge, er O (log n) plads

467
00:35:49,240 --> 00:36:03,040
hvor n er antallet af dage.

468
00:36:03,040 --> 00:36:07,230
>> Nu, altid spørge dig selv, "Kan vi gøre det bedre?"

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

470
00:36:12,390 --> 00:36:20,040
Et vink: vi kun drøftet to andre problemer, før dette, og det kommer ikke til at være shuffle.

471
00:36:20,040 --> 00:36:26,200
Vi kan konvertere dette aktiemarkedet problem i den maksimale subarray problem.

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

473
00:36:40,100 --> 00:36:42,570
En af jer? Emmy?

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

475
00:36:47,680 --> 00:36:53,860
[Yu] Præcis.

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

477
00:36:59,940 --> 00:37:10,610
vi leder efter en sum over en kontinuerlig subarray.

478
00:37:10,610 --> 00:37:16,230
Og Emmy forslag til bestande problem,

479
00:37:16,230 --> 00:37:30,720
overveje de ændringer, eller deltaer.

480
00:37:30,720 --> 00:37:37,440
Og et billede af dette er - det er prisen for en aktie,

481
00:37:37,440 --> 00:37:42,610
men hvis vi tog forskellen mellem hver dag i træk -

482
00:37:42,610 --> 00:37:45,200
så ser vi, at den maksimale pris, maksimal profit vi kunne gøre

483
00:37:45,200 --> 00:37:50,070
er, hvis vi køber her og sælge her.

484
00:37:50,070 --> 00:37:54,240
Men lad os se på den kontinuerlige - lad os se på det subarray problem.

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

486
00:38:02,510 --> 00:38:08,410
vi har en positiv forandring, og derefter gå herfra til her har vi en negativ ændring.

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

488
00:38:14,220 --> 00:38:20,930
Og det er disse ændringer, som vi ønsker at opsummere for at få vores endelige resultat.

489
00:38:20,930 --> 00:38:25,160
Så har vi mere negative ændringer her.

490
00:38:25,160 --> 00:38:29,990
Nøglen til at reducere vores lager problem i vores maksimale subarray problem

491
00:38:29,990 --> 00:38:36,630
er at overveje de deltaer mellem dage.

492
00:38:36,630 --> 00:38:40,630
Så vi skaber et nyt array kaldet deltaer,

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

494
00:38:43,000 --> 00:38:46,380
og derefter for hver delta (i), lad det være forskellen

495
00:38:46,380 --> 00:38:52,830
min inputarrayet (i) og matrix (i - 1).

496
00:38:52,830 --> 00:38:55,530
Så vi kalder vores rutine procedure for en maksimal subarray

497
00:38:55,530 --> 00:39:01,500
passerer i en delta s array.

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 reduktion er denne proces med at skabe 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
så den endelige løsning for bestande er O (n) arbejde plus O (n) arbejde, er stadig O (n) arbejde.

502
00:39:19,060 --> 00:39:23,900
Så vi har en lineær tid løsning på vores problem.

503
00:39:23,900 --> 00:39:29,610
Skal alle forstå denne transformation?

504
00:39:29,610 --> 00:39:32,140
>> I almindelighed, en god idé, at du altid skal have

505
00:39:32,140 --> 00:39:34,290
er at forsøge at reducere et nyt problem, du ser.

506
00:39:34,290 --> 00:39:37,700
Hvis det virker bekendt for et gammelt problem,

507
00:39:37,700 --> 00:39:39,590
Prøv at reducere den til et gammelt problem.

508
00:39:39,590 --> 00:39:41,950
Og hvis du kan bruge alle de værktøjer, du har brugt på den gamle problem

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

510
00:39:46,450 --> 00:39:49,010
Så for at indpakke er tekniske interviews udfordrende.

511
00:39:49,010 --> 00:39:52,280
Disse problemer er sandsynligvis nogle af de mere vanskelige problemer

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

513
00:39:54,700 --> 00:39:57,690
så hvis du ikke forstår alle de problemer, som jeg lige er dækket, det er okay.

514
00:39:57,690 --> 00:40:01,080
Disse er nogle af de mere udfordrende problemer.

515
00:40:01,080 --> 00:40:03,050
Praksis, praksis, praksis.

516
00:40:03,050 --> 00:40:08,170
Jeg gav en masse problemer i handout, så helt sikkert tjekke dem ud.

517
00:40:08,170 --> 00:40:11,690
Og held og lykke på dine interviews. Alle mine ressourcer er udstationeret på dette link,

518
00:40:11,690 --> 00:40:15,220
og en af ​​mine ældre venner har tilbudt at gøre mock tekniske interviews,

519
00:40:15,220 --> 00:40:22,050
så hvis du er interesseret, e-mail vil Yao på denne e-mail-adresse.

520
00:40:22,050 --> 00:40:26,070
Hvis du har nogle spørgsmål, kan du spørge mig.

521
00:40:26,070 --> 00:40:28,780
Tror du fyre har særlige spørgsmål vedrørende tekniske interviews

522
00:40:28,780 --> 00:40:38,440
eller eventuelle problemer, vi har set indtil videre?

523
00:40:38,440 --> 00:40:49,910
Okay. Held og lykke på dine interviews.

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