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

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

3
00:00:04,630 --> 00:00:08,910
[Dit is CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hallo iedereen, ik ben Kenny. Ik ben momenteel een junior studie informatica.

5
00:00:12,420 --> 00:00:17,310
Ik ben een ex-CS TF, en ik wou dat ik had dit toen ik een Underclassman,

6
00:00:17,310 --> 00:00:19,380
en dat is waarom ik ben van dit seminar.

7
00:00:19,380 --> 00:00:21,370
Dus ik hoop dat je ervan geniet.

8
00:00:21,370 --> 00:00:23,470
Dit seminar gaat over technische interviews,

9
00:00:23,470 --> 00:00:26,650
en al mijn bronnen is te vinden op deze link,

10
00:00:26,650 --> 00:00:32,350
deze link hier, een paar van de middelen.

11
00:00:32,350 --> 00:00:36,550
Dus maakte ik een lijst van problemen, eigenlijk, nogal wat problemen.

12
00:00:36,550 --> 00:00:40,800
Ook een algemene middelen pagina waar we kunnen vinden tips

13
00:00:40,800 --> 00:00:42,870
over het opstellen voor een interview,

14
00:00:42,870 --> 00:00:46,470
tips over wat u moet doen tijdens een echte interview,

15
00:00:46,470 --> 00:00:51,910
alsook hoe je problemen en de middelen voor toekomstige referentie te benaderen.

16
00:00:51,910 --> 00:00:53,980
Het is allemaal online.

17
00:00:53,980 --> 00:00:58,290
En alleen maar om dit seminar, een disclaimer voorwoord,

18
00:00:58,290 --> 00:01:00,690
als dit mag niet - je interview voorbereiding

19
00:01:00,690 --> 00:01:02,800
mag niet worden beperkt tot deze lijst.

20
00:01:02,800 --> 00:01:04,750
Dit is alleen bedoeld om een ​​gids te zijn,

21
00:01:04,750 --> 00:01:08,890
en je moet zeker alles wat ik zeg met een korreltje zout,

22
00:01:08,890 --> 00:01:14,620
maar ook gebruik maken van alles wat ik gebruikt om u te helpen in uw interview voorbereiding.

23
00:01:14,620 --> 00:01:16,400
>> Ik ga om sneller door de volgende paar dia's

24
00:01:16,400 --> 00:01:18,650
zodat we kunnen krijgen om de werkelijke case studies.

25
00:01:18,650 --> 00:01:23,630
De structuur van een interview voor een software engineering positie,

26
00:01:23,630 --> 00:01:26,320
typisch is 30 tot 45 minuten,

27
00:01:26,320 --> 00:01:29,810
meerdere ronden, afhankelijk van het bedrijf.

28
00:01:29,810 --> 00:01:33,090
Vaak zult u codering op een wit bord.

29
00:01:33,090 --> 00:01:35,960
Dus een wit bord als dit, maar vaak op een kleinere schaal.

30
00:01:35,960 --> 00:01:38,540
Als je met een telefonisch interview, zult u waarschijnlijk worden met behulp van

31
00:01:38,540 --> 00:01:44,030
hetzij collabedit of een Google Doc, zodat ze kunnen zien live coding

32
00:01:44,030 --> 00:01:46,500
terwijl je wordt geïnterviewd over de telefoon.

33
00:01:46,500 --> 00:01:48,490
Een interview zelf is meestal 2 of 3 problemen

34
00:01:48,490 --> 00:01:50,620
het testen van uw informatica kennis.

35
00:01:50,620 --> 00:01:54,490
En het zal bijna zeker te coderen.

36
00:01:54,490 --> 00:01:59,540
De aard van de vragen die u zult zien zijn meestal data structuren en algoritmen.

37
00:01:59,540 --> 00:02:02,210
En in het doen van dit soort problemen,

38
00:02:02,210 --> 00:02:07,830
ze zullen je vragen wilt,, wat is de tijd en ruimte complexiteit, grote O?

39
00:02:07,830 --> 00:02:09,800
Vaak zijn ze ook vragen een hoger niveau vragen,

40
00:02:09,800 --> 00:02:12,530
dus om een ​​systeem,

41
00:02:12,530 --> 00:02:14,770
hoe zou u de lay-out uw code?

42
00:02:14,770 --> 00:02:18,370
Wat interfaces, welke klassen, welke modules heb je in je systeem,

43
00:02:18,370 --> 00:02:20,900
en hoe deze op elkaar inwerken bij elkaar?

44
00:02:20,900 --> 00:02:26,130
Dus datastructuren en algoritmen, alsmede het ontwerpen van systemen.

45
00:02:26,130 --> 00:02:29,180
>> Enkele algemene tips voordat we duiken in onze case studies.

46
00:02:29,180 --> 00:02:32,300
Ik denk dat de belangrijkste regel is altijd denken hardop.

47
00:02:32,300 --> 00:02:36,980
Het interview wordt verondersteld om uw kans om te pronken met uw denkproces zijn.

48
00:02:36,980 --> 00:02:39,820
Het punt van het interview is voor de interviewer te peilen naar

49
00:02:39,820 --> 00:02:42,660
hoe je denkt en hoe je door een probleem.

50
00:02:42,660 --> 00:02:45,210
Het ergste wat je kunt doen is stil zijn gedurende het hele interview.

51
00:02:45,210 --> 00:02:50,090
Dat is gewoon niet goed.

52
00:02:50,090 --> 00:02:53,230
Wanneer u een vraag gegeven, kunt u ook willen ervoor zorgen dat u inzicht in de vraag.

53
00:02:53,230 --> 00:02:55,350
Dus terug de vraag herhalen in uw eigen woorden

54
00:02:55,350 --> 00:02:58,920
en proberen om grondig een paar eenvoudige test cases te werken

55
00:02:58,920 --> 00:03:01,530
om ervoor te zorgen u inzicht in de vraag.

56
00:03:01,530 --> 00:03:05,510
Werken door middel van een enkele test cases zal u ook een intuïtie over hoe dit probleem op te lossen.

57
00:03:05,510 --> 00:03:11,210
Je zou zelfs kunnen ontdekken een paar patronen om u te helpen oplossen van het probleem.

58
00:03:11,210 --> 00:03:14,500
Hun grote tip is om niet gefrustreerd.

59
00:03:14,500 --> 00:03:17,060
Raak niet gefrustreerd.

60
00:03:17,060 --> 00:03:19,060
Interviews zijn uitdagend, maar het ergste wat je kunt doen,

61
00:03:19,060 --> 00:03:23,330
Naast zwijgen, is zichtbaar gefrustreerd.

62
00:03:23,330 --> 00:03:27,410
Je wilt niet die indruk te geven aan een interviewer.

63
00:03:27,410 --> 00:03:33,960
Een ding dat je - zo, veel mensen, wanneer ze gaan in een interview,

64
00:03:33,960 --> 00:03:37,150
ze proberen om te proberen de beste oplossing eerst vinden,

65
00:03:37,150 --> 00:03:39,950
terwijl het in feite, is er meestal een overduidelijk oplossing.

66
00:03:39,950 --> 00:03:43,500
Het is misschien traag, is het misschien inefficiënt, maar je moet gewoon zeggen dat,

67
00:03:43,500 --> 00:03:46,210
gewoon zo heb je een startpunt van waaruit beter te werken.

68
00:03:46,210 --> 00:03:48,270
Ook wijzen de oplossing langzaam qua

69
00:03:48,270 --> 00:03:52,160
big O tijd complexiteit of ruimte complexiteit,

70
00:03:52,160 --> 00:03:54,450
zal tonen aan de interviewer dat u begrijpt

71
00:03:54,450 --> 00:03:57,510
deze problemen bij het schrijven van code.

72
00:03:57,510 --> 00:04:01,440
Dus niet eerst bang om te komen met de meest eenvoudige algoritme

73
00:04:01,440 --> 00:04:04,950
en dan beter werken vanaf daar.

74
00:04:04,950 --> 00:04:09,810
Eventuele vragen tot nu toe? Oke.

75
00:04:09,810 --> 00:04:11,650
>> Dus laten we een duik nemen in ons eerste probleem.

76
00:04:11,650 --> 00:04:14,790
"Bij een array van n gehele getallen, schrijf een functie die de array schudt

77
00:04:14,790 --> 00:04:20,209
in plaats zodat alle permutaties van de n gehele getallen gelijkelijk waarschijnlijk. "

78
00:04:20,209 --> 00:04:23,470
En neem aan dat je beschikken over een willekeurig geheel getal generator

79
00:04:23,470 --> 00:04:30,980
dat genereert een geheel getal in een bereik van 0 tot i, half bereik.

80
00:04:30,980 --> 00:04:32,970
Heeft iedereen begrijpt deze vraag?

81
00:04:32,970 --> 00:04:39,660
Ik geef je een array van n gehele getallen, en ik wil dat je shuffle het.

82
00:04:39,660 --> 00:04:46,050
In mijn map, schreef ik een paar programma's om te laten zien wat ik bedoel.

83
00:04:46,050 --> 00:04:48,910
Ik ga shuffle een array van 20 elementen,

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

85
00:04:52,490 --> 00:04:57,050
en ik wil dat je een lijst als deze uit te voeren.

86
00:04:57,050 --> 00:05:02,890
Dus dit is mijn gesorteerd input array, en ik wil dat je shuffle het.

87
00:05:02,890 --> 00:05:07,070
We zullen nog een keer doen.

88
00:05:07,070 --> 00:05:13,780
Heeft iedereen begrijpen van de vraag? Oke.

89
00:05:13,780 --> 00:05:16,730
Dus het is aan jou.

90
00:05:16,730 --> 00:05:21,220
Wat zijn sommige ideeën? Kun je het als n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Open voor suggesties.

92
00:05:34,400 --> 00:05:37,730
Oke. Dus een idee, voorgesteld door Emmy,

93
00:05:37,730 --> 00:05:45,300
is eerst een willekeurig getal willekeurig getal in een bereik berekenen 0 tot 20.

94
00:05:45,300 --> 00:05:49,840
Zo nemen onze matrix heeft een lengte van 20.

95
00:05:49,840 --> 00:05:54,800
In onze diagram van 20 elementen,

96
00:05:54,800 --> 00:05:58,560
dit is onze input array.

97
00:05:58,560 --> 00:06:04,590
En nu, haar suggestie is het creëren van een nieuwe array,

98
00:06:04,590 --> 00:06:08,440
dus de uitgang array.

99
00:06:08,440 --> 00:06:12,880
En gebaseerd op de i geretourneerd rand -

100
00:06:12,880 --> 00:06:17,580
dus als ik was, laten we zeggen, 17,

101
00:06:17,580 --> 00:06:25,640
kopieer 17e element in de eerste positie.

102
00:06:25,640 --> 00:06:30,300
Nu moeten we verwijderen - we moeten hier verschuiven alle elementen

103
00:06:30,300 --> 00:06:36,920
om, zodat we een gat aan het einde en geen gaten in het midden hebben.

104
00:06:36,920 --> 00:06:39,860
En nu we het proces herhalen.

105
00:06:39,860 --> 00:06:46,360
Nu kiezen we een nieuw willekeurig geheel getal tussen 0 en 19.

106
00:06:46,360 --> 00:06:52,510
We hebben een nieuwe i hier, en we kopiëren dit element in deze positie.

107
00:06:52,510 --> 00:07:00,960
Dan hebben we verschuiven artikelen over en herhalen we het proces tot we onze volledige nieuwe array.

108
00:07:00,960 --> 00:07:05,890
Wat is de looptijd van dit algoritme?

109
00:07:05,890 --> 00:07:08,110
Nou, laten we eens kijken naar de impact van deze.

110
00:07:08,110 --> 00:07:10,380
We verschuiven elk element.

111
00:07:10,380 --> 00:07:16,800
Als we dit verwijderen i, zijn we verschuiven alle elementen na naar links.

112
00:07:16,800 --> 00:07:21,600
En dat is een O (n) kosten

113
00:07:21,600 --> 00:07:26,100
want wat als we het eerste element te verwijderen?

114
00:07:26,100 --> 00:07:29,670
Dus voor elke verwijdering, verwijderen we -

115
00:07:29,670 --> 00:07:32,170
elke verwijdering loopt een O (n) operatie,

116
00:07:32,170 --> 00:07:41,520
en aangezien we hebben n verhuizingen, leidt dit tot een O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Oke. Zo goed begin. Goede start.

118
00:07:49,550 --> 00:07:55,290
>> Een andere suggestie is het gebruik van iets dat bekend staat als de Knuth shuffle,

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

120
00:07:57,540 --> 00:07:59,630
En het is eigenlijk een lineaire tijd shuffle.

121
00:07:59,630 --> 00:08:02,200
Het idee is zeer vergelijkbaar.

122
00:08:02,200 --> 00:08:05,160
Nogmaals, we hebben onze input array,

123
00:08:05,160 --> 00:08:08,580
maar in plaats van met behulp van twee arrays voor onze input / output,

124
00:08:08,580 --> 00:08:13,590
we het eerste gedeelte van de matrix te houden van onze geschud gedeelte,

125
00:08:13,590 --> 00:08:18,400
en we houden, en dan gaan we de rest van ons aanbod te laten voor de unshuffled gedeelte.

126
00:08:18,400 --> 00:08:24,330
Dus hier is wat ik bedoel. We beginnen met - we kiezen een i,

127
00:08:24,330 --> 00:08:30,910
een array van 0 tot 20.

128
00:08:30,910 --> 00:08:36,150
Onze huidige pointer wijst naar de eerste index.

129
00:08:36,150 --> 00:08:39,590
We kiezen een aantal i hier

130
00:08:39,590 --> 00:08:42,740
en nu zijn we ruilen.

131
00:08:42,740 --> 00:08:47,690
Als dit 5 en dit was 4,

132
00:08:47,690 --> 00:08:57,150
de resulterende array zal hier hebben 5 hier en 4.

133
00:08:57,150 --> 00:09:00,390
En nu zien we een marker hier.

134
00:09:00,390 --> 00:09:05,770
Alles wat naar links wordt geschud,

135
00:09:05,770 --> 00:09:15,160
en alles aan de rechterkant wordt unshuffled.

136
00:09:15,160 --> 00:09:17,260
En nu kunnen we het proces herhalen.

137
00:09:17,260 --> 00:09:25,210
We kiezen een willekeurige index tussen 1 en 20 nu.

138
00:09:25,210 --> 00:09:30,650
Dus stel onze nieuwe i is hier.

139
00:09:30,650 --> 00:09:39,370
Nu we dit ik hier wisselen met onze huidige nieuwe positie.

140
00:09:39,370 --> 00:09:44,790
Dus we een ruilen heen en weer als deze.

141
00:09:44,790 --> 00:09:51,630
Laat me brengen de code om het meer concreet.

142
00:09:51,630 --> 00:09:55,290
We beginnen met onze keuze van i -

143
00:09:55,290 --> 00:09:58,370
we beginnen met i gelijk is aan 0, kiezen we een willekeurige locatie j

144
00:09:58,370 --> 00:10:02,420
in de unshuffled gedeelte van de matrix, om i n-1.

145
00:10:02,420 --> 00:10:07,280
Dus als ik hier ben, kies dan een willekeurige index tussen hier en de rest van de array,

146
00:10:07,280 --> 00:10:12,410
en we wisselen.

147
00:10:12,410 --> 00:10:17,550
Dit is allemaal de code die nodig is om shuffle uw array.

148
00:10:17,550 --> 00:10:21,670
Nog vragen?

149
00:10:21,670 --> 00:10:25,530
>> Nou ja, een nodig vraag is, waarom is dit juist?

150
00:10:25,530 --> 00:10:28,360
Waarom is elke permutatie even waarschijnlijk?

151
00:10:28,360 --> 00:10:30,410
En ik zal niet gaan door het bewijs van deze,

152
00:10:30,410 --> 00:10:35,970
maar veel problemen in de informatica kan worden aangetoond door middel van inductie.

153
00:10:35,970 --> 00:10:38,520
Hoeveel van u bekend bent met inductie?

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

155
00:10:40,590 --> 00:10:43,610
Dus je kunt bewijzen dat de correctheid van dit algoritme door eenvoudige inductie,

156
00:10:43,610 --> 00:10:49,540
waar uw inductiehypothese zou zijn, gaan ervan uit dat

157
00:10:49,540 --> 00:10:53,290
mijn shuffle weer elke permutatie even waarschijnlijk

158
00:10:53,290 --> 00:10:56,120
tot de eerste elementen i.

159
00:10:56,120 --> 00:10:58,300
Nu, overweeg dan i + 1.

160
00:10:58,300 --> 00:11:02,550
En door de manier waarop we kiezen onze index j om te ruilen,

161
00:11:02,550 --> 00:11:05,230
dit leidt tot - en dan werk je de details,

162
00:11:05,230 --> 00:11:07,390
ten minste een volledig bewijs van waarom dit algoritme terug

163
00:11:07,390 --> 00:11:12,800
elke permutatie met even waarschijnlijk waarschijnlijkheid.

164
00:11:12,800 --> 00:11:15,940
>> Oke, volgende probleem.

165
00:11:15,940 --> 00:11:19,170
Dus "gegeven een array van integers, postive, nul, negatief,

166
00:11:19,170 --> 00:11:21,290
schrijf een functie die het maximale bedrag berekent

167
00:11:21,290 --> 00:11:24,720
van elke continueous subarray van de input array. "

168
00:11:24,720 --> 00:11:28,370
Een voorbeeld is, in het geval waarin alle getallen positief,

169
00:11:28,370 --> 00:11:31,320
dan is op dit moment de beste keuze is om de hele reeks.

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

171
00:11:34,690 --> 00:11:36,780
Wanneer u een aantal negatieven hebben daar,

172
00:11:36,780 --> 00:11:38,690
in dit geval willen we gewoon de eerste twee

173
00:11:38,690 --> 00:11:44,590
omdat het kiezen van -1 en / of -3 brengt ons som naar beneden.

174
00:11:44,590 --> 00:11:48,120
Soms we zouden moeten beginnen in het midden van de array.

175
00:11:48,120 --> 00:11:53,500
Soms willen we helemaal niets te kiezen, het is het beste om niets nemen.

176
00:11:53,500 --> 00:11:56,490
En soms is het beter om de val,

177
00:11:56,490 --> 00:12:07,510
omdat de zaak nadat het is super groot. Dus even welke ideeën?

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

179
00:12:10,970 --> 00:12:13,560
Stel dat ik niet -1 nemen.

180
00:12:13,560 --> 00:12:16,170
Dan ofwel kies ik 1.000 en 20.000,

181
00:12:16,170 --> 00:12:18,630
of ik gewoon kiezen voor de 3 miljard.

182
00:12:18,630 --> 00:12:20,760
Nou, de beste keuze is om alle nummers.

183
00:12:20,760 --> 00:12:24,350
Dit -1, ondanks het feit dat negatieve,

184
00:12:24,350 --> 00:12:31,340
de gehele som is beter dan I waren niet op -1 nemen.

185
00:12:31,340 --> 00:12:36,460
Dus een van de tips die ik eerder noemde was de duidelijk moge duidelijk zijn

186
00:12:36,460 --> 00:12:40,540
en de brute kracht oplossing eerst.

187
00:12:40,540 --> 00:12:44,340
Wat is de brute kracht oplossing in dit probleem? Ja?

188
00:12:44,340 --> 00:12:46,890
[Jane] Nou, ik denk dat de brute kracht oplossing

189
00:12:46,890 --> 00:12:52,600
zou zijn om toe te voegen op alle mogelijke combinaties (onverstaanbaar).

190
00:12:52,600 --> 00:12:58,250
[Yu] Oke. Dus Jane's idee is om alle mogelijke -

191
00:12:58,250 --> 00:13:01,470
Ik ben parafraseren - is het nemen van alle mogelijke continue subarray,

192
00:13:01,470 --> 00:13:07,840
berekenen de som, en neem dan het maximum van alle mogelijke continue subarrays.

193
00:13:07,840 --> 00:13:13,310
Wat een unieke identificatie van een subarray in mijn input array?

194
00:13:13,310 --> 00:13:17,380
Zoals, wat twee dingen heb ik nodig? Ja?

195
00:13:17,380 --> 00:13:19,970
(Student, onverstaanbaar) >> Juist.

196
00:13:19,970 --> 00:13:22,130
Een ondergrens op de index en een bovengrens index

197
00:13:22,130 --> 00:13:28,300
unieke bepaalt een continue subarray.

198
00:13:28,300 --> 00:13:31,400
[Vrouwelijke student] Zijn we schatten dat het een serie van unieke nummers?

199
00:13:31,400 --> 00:13:34,280
[Yu] Nee Dus haar vraag is, gaan we uit van ons aanbod -

200
00:13:34,280 --> 00:13:39,000
is ons aanbod alle unieke nummers, en het antwoord is nee.

201
00:13:39,000 --> 00:13:43,390
>> Als we gebruik maken van onze brute kracht oplossing, dan is de start / eind indices

202
00:13:43,390 --> 00:13:47,200
unieke bepaalt onze continue subarray.

203
00:13:47,200 --> 00:13:51,680
Dus als we bovenstaande bewerking voor alle mogelijke start inzendingen,

204
00:13:51,680 --> 00:13:58,320
en voor alle eind inzendingen> of = om te beginnen, en <n,

205
00:13:58,320 --> 00:14:05,570
berekent u de som, en dan nemen we de maximale som die we tot nu toe hebben gezien.

206
00:14:05,570 --> 00:14:07,880
Is dit duidelijk?

207
00:14:07,880 --> 00:14:12,230
Wat is de big O van deze oplossing?

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

209
00:14:16,660 --> 00:14:18,860
Niet helemaal n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Merk op dat we herhalen van 0 tot n,

211
00:14:25,250 --> 00:14:27,520
dus dat is een for-lus.

212
00:14:27,520 --> 00:14:35,120
We herhalen nogmaals van bijna het begin tot het einde, een ander for-lus.

213
00:14:35,120 --> 00:14:37,640
En nu, binnen die moeten we vatten elk item,

214
00:14:37,640 --> 00:14:43,810
dus dat is een ander for-lus. Dus we hebben drie geneste for-lussen, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Oke. Dit gaat als uitgangspunt.

216
00:14:46,560 --> 00:14:53,180
Onze oplossing is niet slechter dan n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Heeft iedereen begrijpen van de brute kracht oplossing?

218
00:14:55,480 --> 00:14:59,950
>> Oke. Een betere oplossing is het gebruik van een idee genaamd dynamisch programmeren.

219
00:14:59,950 --> 00:15:03,040
Als u CS124, dat is Algoritmen en datastructuren,

220
00:15:03,040 --> 00:15:05,680
word je zeer vertrouwd met deze techniek.

221
00:15:05,680 --> 00:15:12,190
En het idee is, proberen op te bouwen oplossingen voor kleinere problemen eerst.

222
00:15:12,190 --> 00:15:17,990
Wat ik bedoel is, dat we op dit moment zorgen te maken over twee dingen: begin en einde.

223
00:15:17,990 --> 00:15:29,340
En dat is vervelend. Wat als we konden ontdoen van een van deze parameters?

224
00:15:29,340 --> 00:15:32,650
Een idee is om - we gezien onze oorspronkelijke probleem,

225
00:15:32,650 --> 00:15:37,470
vindt de maximale som van elke subarray tussen [O, n-1].

226
00:15:37,470 --> 00:15:47,400
En nu hebben we een nieuw deelprobleem, waar we weten, in onze huidige index i,

227
00:15:47,400 --> 00:15:52,520
we weten dat we moeten daar af te sluiten. Onze subarray moet eindigen aan de huidige index.

228
00:15:52,520 --> 00:15:57,640
Dus het resterende probleem is, moeten waar we beginnen onze subarray?

229
00:15:57,640 --> 00:16:05,160
Is dit logisch? Oke.

230
00:16:05,160 --> 00:16:12,030
Dus ik heb gecodeerd dit op, en laten we eens kijken naar wat dit betekent.

231
00:16:12,030 --> 00:16:16,230
In de codirectory, is er een programma genaamd subarray,

232
00:16:16,230 --> 00:16:19,470
en het duurt aantal items,

233
00:16:19,470 --> 00:16:25,550
en geeft hij de maximale subarray bedrag in mijn geschud lijst.

234
00:16:25,550 --> 00:16:29,920
Dus in dit geval maximaal onze subarray 3.

235
00:16:29,920 --> 00:16:34,850
En dat is genomen door gewoon met behulp van 2 en 1.

236
00:16:34,850 --> 00:16:38,050
Laten we het opnieuw draaien. Het is ook 3.

237
00:16:38,050 --> 00:16:40,950
Maar deze keer, let op hoe we de 3 kregen.

238
00:16:40,950 --> 00:16:46,690
We namen de - we gewoon de 3 zelf

239
00:16:46,690 --> 00:16:49,980
omdat het is omgeven door de negatieven aan beide zijden,

240
00:16:49,980 --> 00:16:55,080
die een bedrag brengen <3.

241
00:16:55,080 --> 00:16:57,820
Laten we draaien op 10 items.

242
00:16:57,820 --> 00:17:03,200
Deze keer is het 7, nemen we de leidende 3 en 4.

243
00:17:03,200 --> 00:17:09,450
Deze keer is 8 en we dat verkrijgen door 1, 4 en 3.

244
00:17:09,450 --> 00:17:16,310
Dus om u een idee te geven over hoe we dit oplossen getransformeerd probleem,

245
00:17:16,310 --> 00:17:18,890
laten we eens een kijkje op deze subarray.

246
00:17:18,890 --> 00:17:23,460
We krijgen deze input array, en we weten dat het antwoord is 8.

247
00:17:23,460 --> 00:17:26,359
We nemen de 1, 4, en 3.

248
00:17:26,359 --> 00:17:29,090
Maar laten we eens kijken hoe we kregen eigenlijk dat antwoord.

249
00:17:29,090 --> 00:17:34,160
Laten we eens kijken naar de maximale subarray die eindigde op elk van deze indices.

250
00:17:34,160 --> 00:17:40,780
Wat is de maximale subarray die moet eindigen bij de eerste positie?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. >> Zero. Gewoon niet nemen de -5.

252
00:17:46,310 --> 00:17:50,210
Hier gaat worden 0 ook. Ja?

253
00:17:50,210 --> 00:17:56,470
(Student, onverstaanbaar)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, sorry, het is een -3.

255
00:17:58,960 --> 00:18:03,220
Dit is dus een 2, dit is een -3.

256
00:18:03,220 --> 00:18:08,690
Oke. Dus -4, wat is de maximale subarray om die positie te beëindigen

257
00:18:08,690 --> 00:18:12,910
waar -4 is op? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Nu moet ik eindigen op de plaats waar -2 is op.

260
00:18:28,060 --> 00:18:39,330
Dus 6, 5, 7 en de laatste 4.

261
00:18:39,330 --> 00:18:43,480
Wetende dat dit zijn mijn gegevens

262
00:18:43,480 --> 00:18:48,130
voor de getransformeerde probleem waar ik moet eindigen bij elk van deze indices,

263
00:18:48,130 --> 00:18:51,410
dan is mijn definitieve antwoord is gewoon, neem een ​​sweep over,

264
00:18:51,410 --> 00:18:53,580
en neem het maximale aantal.

265
00:18:53,580 --> 00:18:55,620
Dus in dit geval is het 8.

266
00:18:55,620 --> 00:19:00,010
Dit betekent dat de maximale subarray eindigt deze index,

267
00:19:00,010 --> 00:19:04,970
en begon ergens voordat het.

268
00:19:04,970 --> 00:19:09,630
Heeft iedereen dit begrijpen getransformeerd subarray?

269
00:19:09,630 --> 00:19:22,160
>> Oke. Nou, laten we erachter te komen de herhaling voor.

270
00:19:22,160 --> 00:19:27,990
Laten we eens kijken naar de eerste paar inzendingen.

271
00:19:27,990 --> 00:19:35,930
Hier was 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
En dan was er een -2 hier, en dat bracht het naar beneden tot 6.

273
00:19:39,790 --> 00:19:50,800
Dus als ik de ingang op positie i deelprobleem (i),

274
00:19:50,800 --> 00:19:54,910
hoe kan ik het antwoord gebruiken om een ​​vorige deelprobleem

275
00:19:54,910 --> 00:19:59,360
dit deelprobleem beantwoorden?

276
00:19:59,360 --> 00:20:04,550
Als ik kijk naar, laten we zeggen, dit bericht.

277
00:20:04,550 --> 00:20:09,190
Hoe kan ik het antwoord 6 berekenen door te kijken naar

278
00:20:09,190 --> 00:20:18,780
een combinatie van deze array en de antwoorden op eerdere deelproblemen in deze array? Ja?

279
00:20:18,780 --> 00:20:22,800
[Vrouwelijke student] Je neemt de array van bedragen

280
00:20:22,800 --> 00:20:25,430
in de positie vlak voor, dus de 8,

281
00:20:25,430 --> 00:20:32,170
en dan voegt u de huidige deelprobleem.

282
00:20:32,170 --> 00:20:36,460
[Yu] Dus haar suggestie is om te kijken naar deze twee getallen,

283
00:20:36,460 --> 00:20:40,090
dit aantal en dit aantal.

284
00:20:40,090 --> 00:20:50,130
Dus 8 de antwoord voor de deelprobleem (i - 1).

285
00:20:50,130 --> 00:20:57,300
En laten we mijn input array A.

286
00:20:57,300 --> 00:21:01,470
Om een ​​maximale subarray die eindigt op positie i vinden,

287
00:21:01,470 --> 00:21:03,980
Ik heb twee keuzes: ik kan doorgaan met de subarray

288
00:21:03,980 --> 00:21:09,790
dat eindigde bij de vorige index, of start een nieuwe array.

289
00:21:09,790 --> 00:21:14,190
Als ik de subarray die begon bij de vorige index blijven,

290
00:21:14,190 --> 00:21:19,260
dan het maximale bedrag kan ik bereiken is het antwoord op de vorige deelprobleem

291
00:21:19,260 --> 00:21:24,120
plus de huidige array invoer.

292
00:21:24,120 --> 00:21:27,550
Maar, ik heb ook de keuze van het starten van een nieuwe subarray,

293
00:21:27,550 --> 00:21:30,830
in welk geval de som is 0.

294
00:21:30,830 --> 00:21:42,860
Dus het antwoord is max van 0, deelprobleem i - 1, plus de huidige array invoer.

295
00:21:42,860 --> 00:21:46,150
Betekent dit herhaling zinvol?

296
00:21:46,150 --> 00:21:50,840
Onze herhaling, zoals we net ontdekt, is deelprobleem i

297
00:21:50,840 --> 00:21:54,740
is gelijk aan het maximum van de voorgaande deelprobleem plus mijn huidige array vermelding

298
00:21:54,740 --> 00:22:01,490
waardoor verder de vorige subarray,

299
00:22:01,490 --> 00:22:07,250
of 0, start een nieuwe subarray bij mijn huidige index.

300
00:22:07,250 --> 00:22:10,060
En als we eenmaal hebben opgebouwd deze tafel van oplossingen, dan is onze definitieve antwoord,

301
00:22:10,060 --> 00:22:13,950
gewoon een lineaire sweep over het deelprobleem reeks

302
00:22:13,950 --> 00:22:19,890
en neem het maximale aantal.

303
00:22:19,890 --> 00:22:23,330
Dit is een exacte uitvoering van wat ik net zei.

304
00:22:23,330 --> 00:22:27,320
Dus maken we een nieuwe deelprobleem array deelproblemen.

305
00:22:27,320 --> 00:22:32,330
De eerste regel is 0 of de eerste invoer, het maximum van deze twee.

306
00:22:32,330 --> 00:22:35,670
En voor de rest van de deelproblemen

307
00:22:35,670 --> 00:22:39,810
gebruiken we de exacte herhaling we net ontdekt.

308
00:22:39,810 --> 00:22:49,960
Nu berekenen we het maximum van onze deelproblemen array, en dat is onze uiteindelijke antwoord.

309
00:22:49,960 --> 00:22:54,130
>> Dus hoeveel ruimte gebruiken we in dit algoritme?

310
00:22:54,130 --> 00:23:01,470
Als je alleen genomen CS50, dan heb je misschien nog niet besproken ruimte heel veel.

311
00:23:01,470 --> 00:23:07,750
Nou, een ding om op te merken is dat ik de naam hier malloc met grootte n.

312
00:23:07,750 --> 00:23:13,590
Wat betekent die suggereren voor u?

313
00:23:13,590 --> 00:23:17,450
Dit algoritme lineaire ruimte.

314
00:23:17,450 --> 00:23:21,030
Kan er beter?

315
00:23:21,030 --> 00:23:30,780
Is er iets dat je merkt dat niet nodig is om het definitieve antwoord te berekenen?

316
00:23:30,780 --> 00:23:33,290
Ik denk dat een betere vraag is, welke informatie

317
00:23:33,290 --> 00:23:40,680
hoeven we niet de hele weg te dragen tot het einde?

318
00:23:40,680 --> 00:23:44,280
Nu, als we kijken naar deze twee lijnen,

319
00:23:44,280 --> 00:23:47,720
we alleen de zorg over de vorige deelprobleem,

320
00:23:47,720 --> 00:23:50,910
en we alleen de zorg over het maximale wat we ooit hebben gezien tot nu toe.

321
00:23:50,910 --> 00:23:53,610
Om onze uiteindelijke antwoord te berekenen, hoeven we niet de hele array.

322
00:23:53,610 --> 00:23:57,450
We hebben alleen het laatste nummer, laatste twee getallen.

323
00:23:57,450 --> 00:24:02,630
Laatste nummer voor de deelprobleem array en laatste nummer voor het maximum.

324
00:24:02,630 --> 00:24:07,380
Dus, in feite, kunnen we samensmelten deze lussen

325
00:24:07,380 --> 00:24:10,460
en gaan van lineaire ruimte constant ruimte.

326
00:24:10,460 --> 00:24:15,830
Huidige bedrag tot nu toe, hier, vervangt de rol van deelprobleem, onze deelprobleem array.

327
00:24:15,830 --> 00:24:20,020
Dus de huidige som, tot nu toe, is het antwoord op de vorige deelprobleem.

328
00:24:20,020 --> 00:24:23,450
En dat bedrag, tot nu toe, neemt de plaats in van onze max.

329
00:24:23,450 --> 00:24:28,100
We berekenen de maximale terwijl we verder gaan.

330
00:24:28,100 --> 00:24:30,890
En zo gaan we van lineaire ruimte om een ​​constante ruimte,

331
00:24:30,890 --> 00:24:36,650
en we hebben ook een lineaire oplossing voor ons subarray probleem.

332
00:24:36,650 --> 00:24:40,740
>> Dit soort vragen krijg je tijdens een interview.

333
00:24:40,740 --> 00:24:44,450
Wat is de tijd complexiteit, wat is de ruimte complexiteit?

334
00:24:44,450 --> 00:24:50,600
Kan jij dat ook? Zijn er dingen die niet nodig zijn om in de buurt?

335
00:24:50,600 --> 00:24:55,270
Ik deed dit om analyses die je moet nemen op uw eigen markeren

336
00:24:55,270 --> 00:24:57,400
als je werkt door middel van deze problemen.

337
00:24:57,400 --> 00:25:01,710
Altijd jezelf de vraag: "Kan ik het beter doen?"

338
00:25:01,710 --> 00:25:07,800
In feite, kan het beter dan dit?

339
00:25:07,800 --> 00:25:10,730
Soort van een strikvraag. Je kunt niet, want je moet

340
00:25:10,730 --> 00:25:13,590
ten minste over de ingang voor het probleem.

341
00:25:13,590 --> 00:25:15,570
Dus het feit dat je nodig hebt om in ieder geval te lezen de ingang van het probleem

342
00:25:15,570 --> 00:25:19,580
betekent dat je niet beter kan doen dan de lineaire tijd,

343
00:25:19,580 --> 00:25:22,870
en je kan niet beter doen dan constant de ruimte.

344
00:25:22,870 --> 00:25:27,060
Dit is dus in feite de beste oplossing voor dit probleem.

345
00:25:27,060 --> 00:25:33,040
Vragen? Oke.

346
00:25:33,040 --> 00:25:35,190
>> Beurs probleem:

347
00:25:35,190 --> 00:25:38,350
"Bij een array van n gehele getallen, positief, nul of negatief,

348
00:25:38,350 --> 00:25:41,680
dat vertegenwoordigen de prijs van een aandeel meer dan n dagen,

349
00:25:41,680 --> 00:25:44,080
schrijf een functie om de maximale winst die u kunt maken berekenen

350
00:25:44,080 --> 00:25:49,350
gezien het feit dat u koopt en precies 1 voorraad te verkopen binnen deze n dagen. "

351
00:25:49,350 --> 00:25:51,690
In wezen willen we laag kopen, hoog verkopen.

352
00:25:51,690 --> 00:25:58,580
En we willen achterhalen van de beste winst die we kunnen maken.

353
00:25:58,580 --> 00:26:11,500
Terug te gaan naar mijn tip, wat is de direct duidelijk en eenvoudigste antwoord, maar het is traag?

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

355
00:26:17,690 --> 00:26:21,470
>> Dus je zou gewoon al gaan kijken naar de aandelenkoersen

356
00:26:21,470 --> 00:26:30,550
op elk punt in de tijd, (onverstaanbaar).

357
00:26:30,550 --> 00:26:33,990
[Yu] Oke, dus haar oplossing - haar suggestie van de computer

358
00:26:33,990 --> 00:26:37,380
de laagste en het berekenen van de hoogste niet noodzakelijkerwijs werkt

359
00:26:37,380 --> 00:26:42,470
omdat de hoogste kan plaatsvinden voordat de laagste.

360
00:26:42,470 --> 00:26:47,340
Dus wat is de brute kracht oplossing voor dit probleem?

361
00:26:47,340 --> 00:26:53,150
Wat zijn de twee dingen die ik nodig heb om uniek te bepalen van de winst die ik maak? Juist.

362
00:26:53,150 --> 00:26:59,410
De brute kracht oplossing is - oh, ja, George's suggestie is dat we alleen maar moet minimaal twee dagen

363
00:26:59,410 --> 00:27:02,880
als unieke bepalen van de winst van die twee dagen.

364
00:27:02,880 --> 00:27:06,660
Dus we berekenen elk paar, wil kopen / verkopen,

365
00:27:06,660 --> 00:27:12,850
berekenen van de winst, die zouden kunnen worden negatief of positief of nul.

366
00:27:12,850 --> 00:27:18,000
Bereken de maximale winst die we maken na itereren over alle paren van dagen.

367
00:27:18,000 --> 00:27:20,330
Dat zal onze uiteindelijke antwoord.

368
00:27:20,330 --> 00:27:25,730
En die oplossing wordt O (n ^ 2), omdat er n kiezen twee paar -

369
00:27:25,730 --> 00:27:30,270
dagen dat u kunt kiezen uit eind dagen.

370
00:27:30,270 --> 00:27:32,580
Oke, dus ik ben niet van plan hier te gaan over de brute kracht oplossing.

371
00:27:32,580 --> 00:27:37,420
Ik ga je vertellen dat er een n log n oplossing.

372
00:27:37,420 --> 00:27:45,550
Wat algoritme heb je momenteel dat is n log n?

373
00:27:45,550 --> 00:27:50,730
Het is geen strikvraag.

374
00:27:50,730 --> 00:27:54,790
>> Samenvoegen soort. Samenvoegen soort is n log n,

375
00:27:54,790 --> 00:27:57,760
en in feite een manier om dit probleem te gebruiken

376
00:27:57,760 --> 00:28:04,400
een merge sort soort idee genaamd, in het algemeen, verdeel en heers.

377
00:28:04,400 --> 00:28:07,570
Het idee is als volgt.

378
00:28:07,570 --> 00:28:12,400
U wilt de beste koop te berekenen / paar verkopen in de linker helft.

379
00:28:12,400 --> 00:28:16,480
Vind de beste winst die je kunt maken met alleen de eerste n over twee dagen.

380
00:28:16,480 --> 00:28:19,780
Dan wil je de beste koop oompute / paar verkopen op de rechter helft,

381
00:28:19,780 --> 00:28:23,930
dus de laatste n over twee dagen.

382
00:28:23,930 --> 00:28:32,400
En nu de vraag is, hoe gaan we nu samenvoegen deze oplossingen weer bij elkaar?

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

384
00:28:36,320 --> 00:28:49,890
>> Oke. Dus laat me een tekening.

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

386
00:29:03,870 --> 00:29:06,450
>> Precies. George's oplossing is precies goed.

387
00:29:06,450 --> 00:29:10,040
Dus zijn suggestie is in de eerste berekenen de beste koop / verkoop paar,

388
00:29:10,040 --> 00:29:16,050
en dat gebeurt in de linker helft, dus laten we noemen dat links, links.

389
00:29:16,050 --> 00:29:20,790
Beste kopen / verkopen paar dat zich voordoet in de rechter helft.

390
00:29:20,790 --> 00:29:25,180
Maar als we alleen vergeleken deze twee getallen, we missen het geval

391
00:29:25,180 --> 00:29:30,460
waar we hier kopen en verkopen ergens in de rechter helft.

392
00:29:30,460 --> 00:29:33,810
Wij kopen in de linker helft, verkopen in de rechter helft.

393
00:29:33,810 --> 00:29:38,490
En de beste manier om de beste koop / verkoop paar dat beide helften overspant berekenen

394
00:29:38,490 --> 00:29:43,480
is de minimale hier berekenen en hier berekenen de maximum

395
00:29:43,480 --> 00:29:45,580
en nemen hun verschil.

396
00:29:45,580 --> 00:29:50,850
Dus de twee gevallen waarin de buy / sell paar treedt alleen hier,

397
00:29:50,850 --> 00:30:01,910
alleen hier, of beide helften bestaat uit deze drie cijfers.

398
00:30:01,910 --> 00:30:06,450
Dus ons algoritme om onze oplossingen samen te voegen weer bij elkaar,

399
00:30:06,450 --> 00:30:08,350
We willen de beste koop / verkoop pair berekenen

400
00:30:08,350 --> 00:30:13,120
waar kopen we op de linker helft en verkopen op de rechter helft.

401
00:30:13,120 --> 00:30:16,740
En de beste manier om dat te doen is om de laagste prijs te berekenen in de eerste helft,

402
00:30:16,740 --> 00:30:20,360
de hoogste prijs in de rechter helft, en nemen hun verschil.

403
00:30:20,360 --> 00:30:25,390
De resulterende drie winst, deze drie nummers, neem je het maximum van de drie,

404
00:30:25,390 --> 00:30:32,720
en dat is de beste winst die u kunt maken over deze eerste en einde dag.

405
00:30:32,720 --> 00:30:36,940
Hier zijn de belangrijkste lijnen zijn in het rood.

406
00:30:36,940 --> 00:30:41,160
Dit is een recursieve aanroep van het antwoord in de linkerhelft berekenen.

407
00:30:41,160 --> 00:30:44,760
Dit is een recursieve aanroep van het antwoord berekenen in de rechterhelft.

408
00:30:44,760 --> 00:30:50,720
Deze twee lussen voor het berekenen min en max op de linker en rechter respectievelijk.

409
00:30:50,720 --> 00:30:54,970
Nu bereken ik de winst die beide helften overspant,

410
00:30:54,970 --> 00:31:00,530
en het uiteindelijke antwoord is het maximum van deze drie.

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

412
00:31:04,120 --> 00:31:06,420
>> Dus, zeker, we hebben een algoritme, maar de grotere vraag is,

413
00:31:06,420 --> 00:31:08,290
wat is de tijd complexiteit van dit?

414
00:31:08,290 --> 00:31:16,190
En de reden waarom ik noemde merge sort is dat deze vorm van het antwoord te verdelen

415
00:31:16,190 --> 00:31:19,200
in twee en dan samenvoegen onze oplossingen weer bij elkaar

416
00:31:19,200 --> 00:31:23,580
is precies de vorm van merge sort.

417
00:31:23,580 --> 00:31:33,360
Dus laat me gaan door de duur.

418
00:31:33,360 --> 00:31:41,340
Als we gedefinieerd een functie t (n) het aantal stappen worden

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

420
00:31:50,010 --> 00:31:54,350
onze twee recursieve aanroepen

421
00:31:54,350 --> 00:32:00,460
elk naar t (n / 2) kosten,

422
00:32:00,460 --> 00:32:03,540
en er is twee van deze gesprekken.

423
00:32:03,540 --> 00:32:10,020
Nu moet ik het minimum van de linker helft berekenen,

424
00:32:10,020 --> 00:32:17,050
die ik kan doen in n / 2 keer, plus het maximum van de rechter helft.

425
00:32:17,050 --> 00:32:20,820
Dus dit is gewoon n.

426
00:32:20,820 --> 00:32:25,050
En dan plus een aantal constante werk.

427
00:32:25,050 --> 00:32:27,770
En deze herhaling vergelijking

428
00:32:27,770 --> 00:32:35,560
is precies de herhaling vergelijking voor merge sort.

429
00:32:35,560 --> 00:32:39,170
En we weten allemaal dat merge sort is n log n tijd.

430
00:32:39,170 --> 00:32:46,880
Daarom wordt ons algoritme ook n log n tijd.

431
00:32:46,880 --> 00:32:52,220
Betekent dit iteratie zinvol?

432
00:32:52,220 --> 00:32:55,780
Even een korte samenvatting van deze:

433
00:32:55,780 --> 00:32:59,170
T (n) is het aantal stappen om maximale winst te berekenen

434
00:32:59,170 --> 00:33:02,750
de loop van n dagen.

435
00:33:02,750 --> 00:33:06,010
De manier waarop we opgesplitst onze recursieve oproepen

436
00:33:06,010 --> 00:33:11,980
is door te bellen onze oplossing op de eerste n / 2 dagen,

437
00:33:11,980 --> 00:33:14,490
dus dat is een oproep,

438
00:33:14,490 --> 00:33:16,940
en dan noemen we weer op de tweede helft.

439
00:33:16,940 --> 00:33:20,440
Dus dat is twee gesprekken.

440
00:33:20,440 --> 00:33:25,310
En dan vinden we een minimum op de linker helft, die we kunnen doen in de lineaire tijd,

441
00:33:25,310 --> 00:33:29,010
vinden het maximum van de rechter helft, die we kunnen doen in de lineaire tijd.

442
00:33:29,010 --> 00:33:31,570
Dus n / 2 + n / 2 is gewoon n.

443
00:33:31,570 --> 00:33:36,020
Dan hebben we een aantal constante werk, dat is als het doen van rekenkunde.

444
00:33:36,020 --> 00:33:39,860
Deze herhaling vergelijking is precies de herhaling vergelijking voor merge sort.

445
00:33:39,860 --> 00:33:55,490
Vandaar dat onze shuffle algoritme is ook n log n.

446
00:33:55,490 --> 00:33:58,520
Dus hoeveel ruimte gebruiken we?

447
00:33:58,520 --> 00:34:04,910
Laten we terug gaan naar de code.

448
00:34:04,910 --> 00:34:09,420
>> Een betere vraag is, hoeveel stack frames die we ooit hebben op een bepaald moment?

449
00:34:09,420 --> 00:34:11,449
Aangezien we met behulp van recursie,

450
00:34:11,449 --> 00:34:23,530
het aantal stack frames bepaalt onze ruimte gebruik.

451
00:34:23,530 --> 00:34:29,440
Laten we eens kijken n = 8.

452
00:34:29,440 --> 00:34:36,889
Wij roepen shuffle op 8,

453
00:34:36,889 --> 00:34:41,580
die zal shuffle een beroep doen op de eerste vier items,

454
00:34:41,580 --> 00:34:46,250
deze zal een shuffle op de eerste twee items.

455
00:34:46,250 --> 00:34:51,550
Dus onze stack is - dit is onze stack.

456
00:34:51,550 --> 00:34:54,980
En dan noemen we shuffle weer op 1,

457
00:34:54,980 --> 00:34:58,070
en dat is wat ons basisscenario is, dus we onmiddellijk terug.

458
00:34:58,070 --> 00:35:04,700
Hebben we ooit meer dan dit aantal stack frames hebben?

459
00:35:04,700 --> 00:35:08,880
Nee, omdat elke keer dat we doen een aanroeping,

460
00:35:08,880 --> 00:35:10,770
een recursieve aanroep op shuffle,

461
00:35:10,770 --> 00:35:13,950
verdelen we onze omvang in de helft.

462
00:35:13,950 --> 00:35:17,020
Dus het maximum aantal stack frames die we ooit hebben op een gegeven moment

463
00:35:17,020 --> 00:35:28,460
is in de orde van log n stapel frames.

464
00:35:28,460 --> 00:35:42,460
Elke stapel frame heeft een constante ruimte,

465
00:35:42,460 --> 00:35:44,410
, zodat de totale hoeveelheid ruimte,

466
00:35:44,410 --> 00:35:49,240
de maximale hoeveelheid ruimte die we ooit gebruiken is O (log n) ruimte

467
00:35:49,240 --> 00:36:03,040
waarbij n het aantal dagen.

468
00:36:03,040 --> 00:36:07,230
>> Nu, altijd afvragen: "Kan het beter?"

469
00:36:07,230 --> 00:36:12,390
En in het bijzonder, kunnen we de prijs dat dit een probleem die we al hebben opgelost?

470
00:36:12,390 --> 00:36:20,040
Een hint: we slechts twee andere problemen besproken voordat dit, en het is niet van plan om shuffle.

471
00:36:20,040 --> 00:36:26,200
We kunnen omzetten beurs probleem in de maximale subarray probleem.

472
00:36:26,200 --> 00:36:40,100
Hoe kunnen we dit doen?

473
00:36:40,100 --> 00:36:42,570
Een van jullie? Emmy?

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

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

476
00:36:53,860 --> 00:36:59,940
Zodat de maximale subarray probleem

477
00:36:59,940 --> 00:37:10,610
We zijn op zoek naar een som over een continu subarray.

478
00:37:10,610 --> 00:37:16,230
En Emmy's suggestie voor de voorraden probleem,

479
00:37:16,230 --> 00:37:30,720
rekening houden met de veranderingen, of de delta's.

480
00:37:30,720 --> 00:37:37,440
En een foto van deze is - dat is de prijs van een aandeel,

481
00:37:37,440 --> 00:37:42,610
maar als we namen het verschil tussen elke opeenvolgende dag -

482
00:37:42,610 --> 00:37:45,200
zo zien we dat de maximale prijs, maximale winst konden we

483
00:37:45,200 --> 00:37:50,070
is als we hier kopen en verkopen hier.

484
00:37:50,070 --> 00:37:54,240
Maar laten we eens kijken naar de voortdurende - laten we eens kijken naar de subarray probleem.

485
00:37:54,240 --> 00:38:02,510
Dus hier kunnen we - gaan van hier naar hier,

486
00:38:02,510 --> 00:38:08,410
hebben we een positieve verandering, en dan gaan van hier naar hier hebben we een negatieve verandering.

487
00:38:08,410 --> 00:38:14,220
Maar dan, gaat van hier naar hier hebben we een enorme positieve verandering.

488
00:38:14,220 --> 00:38:20,930
En dit zijn de veranderingen die we willen vatten om onze uiteindelijke winst te halen.

489
00:38:20,930 --> 00:38:25,160
Dan hebben we meer negatieve veranderingen hier.

490
00:38:25,160 --> 00:38:29,990
De sleutel tot het verminderen van onze voorraad probleem in onze maximale subarray probleem

491
00:38:29,990 --> 00:38:36,630
is om te overwegen de delta's tussen dagen.

492
00:38:36,630 --> 00:38:40,630
Dus maken we een nieuwe array met de naam delta's,

493
00:38:40,630 --> 00:38:43,000
initialiseren van de eerste binnenkomst op 0,

494
00:38:43,000 --> 00:38:46,380
en dan voor elke delta (i), laat dat zo het verschil

495
00:38:46,380 --> 00:38:52,830
mijn input array (i) en array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Dan noemen we onze routine procedure voor een maximale subarray

497
00:38:55,530 --> 00:39:01,500
passeren in array een delta's.

498
00:39:01,500 --> 00:39:06,440
En omdat maximale subarray is lineaire tijd,

499
00:39:06,440 --> 00:39:09,370
en deze daling, dit proces van het creëren van deze delta array,

500
00:39:09,370 --> 00:39:11,780
Ook lineaire tijd,

501
00:39:11,780 --> 00:39:19,060
dan is de definitieve oplossing voor de bestanden is O (n) werk plus O (n) werk, is nog steeds O (n) werk.

502
00:39:19,060 --> 00:39:23,900
Dus hebben we een lineaire tijd oplossing voor ons probleem.

503
00:39:23,900 --> 00:39:29,610
Heeft iedereen begrijpt deze transformatie?

504
00:39:29,610 --> 00:39:32,140
>> In het algemeen is het een goed idee dat je altijd zou moeten hebben

505
00:39:32,140 --> 00:39:34,290
is proberen om een ​​nieuw probleem dat je ziet verminderen.

506
00:39:34,290 --> 00:39:37,700
Als het ziet er bekend uit voor een oud probleem,

507
00:39:37,700 --> 00:39:39,590
proberen terug te brengen tot een oud probleem.

508
00:39:39,590 --> 00:39:41,950
En als je kunt gebruik maken van alle tools die je hebt gebruikt op het oude probleem

509
00:39:41,950 --> 00:39:46,450
de nieuwe probleem.

510
00:39:46,450 --> 00:39:49,010
Dus om af te ronden, worden technische interviews uitdagend.

511
00:39:49,010 --> 00:39:52,280
Deze problemen zijn waarschijnlijk een van de meest moeilijke problemen

512
00:39:52,280 --> 00:39:54,700
dat je zou kunnen zien in een interview,

513
00:39:54,700 --> 00:39:57,690
dus als je het niet begrijpt alle problemen die ik net bedekt, het is oke.

514
00:39:57,690 --> 00:40:01,080
Dit zijn enkele van de meer uitdagende problemen.

515
00:40:01,080 --> 00:40:03,050
Oefenen, oefenen, oefenen.

516
00:40:03,050 --> 00:40:08,170
Ik gaf veel problemen in de hand-out, dus zeker check deze uit.

517
00:40:08,170 --> 00:40:11,690
En veel geluk op uw interviews. Al mijn bronnen zijn gepost op deze link,

518
00:40:11,690 --> 00:40:15,220
en een van mijn senior vrienden heeft aangeboden om mock technische interviews te doen,

519
00:40:15,220 --> 00:40:22,050
dus als je geïnteresseerd bent, e-mail zal Yao op dat e-mailadres.

520
00:40:22,050 --> 00:40:26,070
Als u nog vragen, dan kunt u het mij vraagt.

521
00:40:26,070 --> 00:40:28,780
Hebben jullie specifieke vragen met betrekking tot technische interviews

522
00:40:28,780 --> 00:40:38,440
of problemen die we tot nu toe gezien?

523
00:40:38,440 --> 00:40:49,910
Oke. Nou, veel geluk op uw interviews.

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