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

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

3
00:00:04,630 --> 00:00:08,910
[See on CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Tere kõigile, ma olen Kenny. Olen praegu noorem õpib arvutiteadus.

5
00:00:12,420 --> 00:00:17,310
Ma olen endine CS TF, ja ma soovin, et oli see, kui ma olin underclassman,

6
00:00:17,310 --> 00:00:19,380
ja sellepärast ma annan selle seminari.

7
00:00:19,380 --> 00:00:21,370
Nii et ma loodan, et te naudite seda.

8
00:00:21,370 --> 00:00:23,470
See seminar on umbes tehniline intervjuud,

9
00:00:23,470 --> 00:00:26,650
ja kõik minu ressursid võib leida seda linki,

10
00:00:26,650 --> 00:00:32,350
seda linki just siin, paar ressursse.

11
00:00:32,350 --> 00:00:36,550
Tegin nimekirja probleemidest, tegelikult üsna palju probleeme.

12
00:00:36,550 --> 00:00:40,800
Ka üldine ressursside lehel kus me võime leida vihjeid

13
00:00:40,800 --> 00:00:42,870
kuidas valmistuda intervjuu,

14
00:00:42,870 --> 00:00:46,470
vihjeid selle kohta, mida sa peaksid tegema ajal tegelik intervjuu,

15
00:00:46,470 --> 00:00:51,910
samuti kuidas läheneda probleeme ja ressursse edaspidiseks.

16
00:00:51,910 --> 00:00:53,980
See kõik on võrgus.

17
00:00:53,980 --> 00:00:58,290
Ja just eessõna seminari, disclaimer,

18
00:00:58,290 --> 00:01:00,690
nagu see ei tohiks - sinu intervjuu ettevalmistus

19
00:01:00,690 --> 00:01:02,800
ei tohiks piirduda sellesse nimekirja.

20
00:01:02,800 --> 00:01:04,750
See on mõeldud ainult juhistena,

21
00:01:04,750 --> 00:01:08,890
ja siis tuleb kindlasti võtta kõik, mida ma öelda tera soola,

22
00:01:08,890 --> 00:01:14,620
aga kasutada ka kõik, mida ma kasutada, et aidata teil oma intervjuu ettevalmistus.

23
00:01:14,620 --> 00:01:16,400
>> Ma lähen Speed ​​läbi järgmise paari slaidid

24
00:01:16,400 --> 00:01:18,650
nii saame tegeliku juhtumiuuringud.

25
00:01:18,650 --> 00:01:23,630
Struktuuri intervjuus tarkvaratehnika asendis,

26
00:01:23,630 --> 00:01:26,320
tavaliselt on 30 kuni 45 minutit,

27
00:01:26,320 --> 00:01:29,810
Mitme vooru, olenevalt äriühingust.

28
00:01:29,810 --> 00:01:33,090
Sageli saate kodeering valge tahvel.

29
00:01:33,090 --> 00:01:35,960
Nii valge tahvel meeldib see, kuid sageli ka väiksemas mastaabis.

30
00:01:35,960 --> 00:01:38,540
Kui sul on telefon intervjuu, peate ilmselt kasutama

31
00:01:38,540 --> 00:01:44,030
kas collabedit või Google Doc et nad saaksid näha sa elad kodeerimine

32
00:01:44,030 --> 00:01:46,500
kui oled intervjuul telefoni teel.

33
00:01:46,500 --> 00:01:48,490
Intervjuu ise on tavaliselt 2 või 3 probleeme

34
00:01:48,490 --> 00:01:50,620
testida oma arvuti teadust teadmised.

35
00:01:50,620 --> 00:01:54,490
Ja see on peaaegu kindlasti kaasata kodeerimine.

36
00:01:54,490 --> 00:01:59,540
Tüüpi küsimusi, mida te näete on tavaliselt andmestruktuurid ja algoritmid.

37
00:01:59,540 --> 00:02:02,210
Ja seda tehes selliseid probleeme,

38
00:02:02,210 --> 00:02:07,830
nad teilt küsida, nagu, mis on ajas ja ruumis keerukus, suur O?

39
00:02:07,830 --> 00:02:09,800
Tihti nad ka küsida kõrgema taseme küsimusi,

40
00:02:09,800 --> 00:02:12,530
nii, projekteerimine süsteem,

41
00:02:12,530 --> 00:02:14,770
kuidas sa panema oma koodi?

42
00:02:14,770 --> 00:02:18,370
Mis liidesed, mida klassid, mida moodulid on teil oma süsteemi,

43
00:02:18,370 --> 00:02:20,900
ja kuidas need mõjutavad üksteist?

44
00:02:20,900 --> 00:02:26,130
Nii andmestruktuurid ja algoritmid, samuti disainida süsteeme.

45
00:02:26,130 --> 00:02:29,180
>> Mõned üldised nõuanded enne kui me sukelduda meie juhtumiuuringud.

46
00:02:29,180 --> 00:02:32,300
Arvan, et kõige tähtsam reegel on alati mõtlesin valjusti.

47
00:02:32,300 --> 00:02:36,980
Intervjuu peaks olema sinu võimalus uhkeldama oma mõtlemisprotsessi.

48
00:02:36,980 --> 00:02:39,820
Punkt intervjuu on intervjueerija hinnata

49
00:02:39,820 --> 00:02:42,660
kuidas te arvate ja kuidas te lähete kaudu probleem.

50
00:02:42,660 --> 00:02:45,210
Halvim, mida saate teha, on olla vait kogu intervjuu.

51
00:02:45,210 --> 00:02:50,090
See on lihtsalt ei ole hea.

52
00:02:50,090 --> 00:02:53,230
Kui teile antakse küsimus, sa ka tahad teha kindel, et sa küsimusest aru.

53
00:02:53,230 --> 00:02:55,350
Nii et kordan küsimust tagasi oma sõnadega

54
00:02:55,350 --> 00:02:58,920
ja üritab teha põhjalik mõne lihtsa katse juhtudel

55
00:02:58,920 --> 00:03:01,530
veenduge küsimusest aru.

56
00:03:01,530 --> 00:03:05,510
Töö kaudu paar katsejuhtumite teile ka intuitsiooni, kuidas seda probleemi lahendada.

57
00:03:05,510 --> 00:03:11,210
Sa võid isegi leida mõned mudelid, mis aitavad teil probleemi lahendada.

58
00:03:11,210 --> 00:03:14,500
Nende suur ots on mitte saada pettunud.

59
00:03:14,500 --> 00:03:17,060
Ärge saage pettunud.

60
00:03:17,060 --> 00:03:19,060
Intervjuud on raske, kuid kõige hullem asi, mida teha,

61
00:03:19,060 --> 00:03:23,330
lisaks on vaikne, tuleb nähtavalt pettunud.

62
00:03:23,330 --> 00:03:27,410
Sa ei taha anda seda muljet, et küsitleja.

63
00:03:27,410 --> 00:03:33,960
Üks asi, mida - nii paljud inimesed, kui nad lähevad vestlusele

64
00:03:33,960 --> 00:03:37,150
nad üritavad püüda leida parim lahendus esiteks,

65
00:03:37,150 --> 00:03:39,950
kui tõesti, seal on tavaliselt pimestavalt ilmne lahendus.

66
00:03:39,950 --> 00:03:43,500
See võib olla aeglane, siis võib olla ebaefektiivne, kuid siis tuleb lihtsalt märkida see,

67
00:03:43,500 --> 00:03:46,210
lihtsalt nii et teil on lähtepunkt, millest paremini tööle.

68
00:03:46,210 --> 00:03:48,270
Samuti, juhtides tähelepanu lahendus on aeglane, nii

69
00:03:48,270 --> 00:03:52,160
Big O ajakeerukust või ruumi keerukus,

70
00:03:52,160 --> 00:03:54,450
näitab, et intervjueerija et saate aru

71
00:03:54,450 --> 00:03:57,510
neid teemasid kirjalikult koodi.

72
00:03:57,510 --> 00:04:01,440
Nii et ärge kartke tulla kõige lihtsam algoritm 1.

73
00:04:01,440 --> 00:04:04,950
ja siis koo parem sealt.

74
00:04:04,950 --> 00:04:09,810
Kõik küsimused siiani? Okei.

75
00:04:09,810 --> 00:04:11,650
>> Nii et olgem sukelduda meie esimene probleem.

76
00:04:11,650 --> 00:04:14,790
"Arvestades array n täisarvu kirjutada funktsioon, mis segab massiivi

77
00:04:14,790 --> 00:04:20,209
paika nii, et kõik permutatsiooni n täisarvu on võrdselt tõenäoline. "

78
00:04:20,209 --> 00:04:23,470
Ja eeldada, teil on olemas juhuslik täisarv generaator

79
00:04:23,470 --> 00:04:30,980
mis tekitab täisarv vahemikus 0 kuni i, pool vahemikus.

80
00:04:30,980 --> 00:04:32,970
Kas kõik mõistavad seda küsimust?

81
00:04:32,970 --> 00:04:39,660
Ma annan teile massiivi n täisarvu ja ma tahan, et sa shuffle ta.

82
00:04:39,660 --> 00:04:46,050
Minu kataloogis, ma kirjutasin mõned programmid näidata, mida ma mõtlen.

83
00:04:46,050 --> 00:04:48,910
Ma lähen shuffle array 20 elementi,

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

85
00:04:52,490 --> 00:04:57,050
ja ma tahan, et sa väljastada nimekirja niimoodi.

86
00:04:57,050 --> 00:05:02,890
Nii et see on minu järjestatud massiivist, ja ma tahan, et sa shuffle ta.

87
00:05:02,890 --> 00:05:07,070
Me teeme seda jälle.

88
00:05:07,070 --> 00:05:13,780
Kas kõik küsimusest aru? Okei.

89
00:05:13,780 --> 00:05:16,730
Nii et see on kuni teil.

90
00:05:16,730 --> 00:05:21,220
Mis on mõned ideed? Kas sa seda kui n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Avatud ettepanekutele.

92
00:05:34,400 --> 00:05:37,730
Okei. Nii et üks idee, soovitas Emmy,

93
00:05:37,730 --> 00:05:45,300
kõigepealt arvutada juhusliku numbri, juhuslik täisarv, vahemikus 0-20.

94
00:05:45,300 --> 00:05:49,840
Nii et meil on meie massiivi pikkus on 20.

95
00:05:49,840 --> 00:05:54,800
Meie diagramm 20 elementi,

96
00:05:54,800 --> 00:05:58,560
see on meie massiivist.

97
00:05:58,560 --> 00:06:04,590
Ja nüüd, tema ettepanek on luua uus massiiv,

98
00:06:04,590 --> 00:06:08,440
nii et see on väljund massiivi.

99
00:06:08,440 --> 00:06:12,880
Ja mis põhineb i poolt tagastatud rand -

100
00:06:12,880 --> 00:06:17,580
nii et kui ma olin, ütleme, 17,

101
00:06:17,580 --> 00:06:25,640
kopeerida 17. element esimesel kohal.

102
00:06:25,640 --> 00:06:30,300
Nüüd tuleb kustutada - me peame minema kõik elemendid siin

103
00:06:30,300 --> 00:06:36,920
üle, et meil on lõpupoole ja auke keskel.

104
00:06:36,920 --> 00:06:39,860
Ja nüüd me protsessi korrata.

105
00:06:39,860 --> 00:06:46,360
Nüüd korja uus juhuslik täisarv vahemikus 0 ja 19.

106
00:06:46,360 --> 00:06:52,510
Meil on uus i siin, ja me kopeerida see element selles asendis.

107
00:06:52,510 --> 00:07:00,960
Siis me vahetustega teemad üle ja me protsessi korrata, kuni meil on meie terve uue massiivi.

108
00:07:00,960 --> 00:07:05,890
Mis on läbijooksuaeg Selle algoritmi?

109
00:07:05,890 --> 00:07:08,110
Noh, olgem kaaluma, millist mõju see.

110
00:07:08,110 --> 00:07:10,380
Meil on hakanud iga element.

111
00:07:10,380 --> 00:07:16,800
Kui me eemaldada selle mina, me nihkuvad kõik elemendid peale seda vasakule.

112
00:07:16,800 --> 00:07:21,600
Ja see on O (n) maksumus

113
00:07:21,600 --> 00:07:26,100
sest mis siis, kui me eemaldage esimene element?

114
00:07:26,100 --> 00:07:29,670
Nii et iga eemaldamine, me eemaldada -

115
00:07:29,670 --> 00:07:32,170
iga eemaldamine kannab O (n) käitamine,

116
00:07:32,170 --> 00:07:41,520
ja kuna me oleme n kolimine, see viib O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Okei. Nii et hea algus. Hea algus.

118
00:07:49,550 --> 00:07:55,290
>> Teine võimalus on kasutada midagi, mida nimetatakse Knuth shuffle,

119
00:07:55,290 --> 00:07:57,540
või Fisher-Yates shuffle.

120
00:07:57,540 --> 00:07:59,630
Ja see on tegelikult lineaarne aeg shuffle.

121
00:07:59,630 --> 00:08:02,200
Ja see idee on väga sarnased.

122
00:08:02,200 --> 00:08:05,160
Jällegi on meil massiivist,

123
00:08:05,160 --> 00:08:08,580
kuid selle asemel kahe massiivi meie sisend / väljund,

124
00:08:08,580 --> 00:08:13,590
me kasutame esimest osa massiivi jälgida meie segatud osa,

125
00:08:13,590 --> 00:08:18,400
ja me jälgida, ja siis me lahkume meie ülejäänud massiivi unshuffled osa.

126
00:08:18,400 --> 00:08:24,330
Nii et siin on, mida ma mõtlen. Me alustad - me valime i,

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

128
00:08:30,910 --> 00:08:36,150
Meie praegune osuti osutab esimesele indeks.

129
00:08:36,150 --> 00:08:39,590
Valisime mõned i siin

130
00:08:39,590 --> 00:08:42,740
ja nüüd me vahetada.

131
00:08:42,740 --> 00:08:47,690
Nii et kui see oli 5 ja see oli 4,

132
00:08:47,690 --> 00:08:57,150
tulemuseks massiivi on 5 siin ja 4. siin.

133
00:08:57,150 --> 00:09:00,390
Ja nüüd pange tähele marker siin.

134
00:09:00,390 --> 00:09:05,770
Kõik vasakul on segatud,

135
00:09:05,770 --> 00:09:15,160
ja kõike seda õigust unshuffled.

136
00:09:15,160 --> 00:09:17,260
Ja nüüd saame protsessi korrata.

137
00:09:17,260 --> 00:09:25,210
Valisime juhuslik indeks 1 ja 20 vahel nüüd.

138
00:09:25,210 --> 00:09:30,650
Olgu, oletame meie uus i on siin.

139
00:09:30,650 --> 00:09:39,370
Nüüd vaheta seda ma meie praegune uus positsioon siin.

140
00:09:39,370 --> 00:09:44,790
Nii et me vahetada edasi-tagasi niimoodi.

141
00:09:44,790 --> 00:09:51,630
Lubage mul tuua kood, et oleks konkreetsem.

142
00:09:51,630 --> 00:09:55,290
Alustame meie valikut i -

143
00:09:55,290 --> 00:09:58,370
alustame i võrdne 0, me valime suvalise koha j

144
00:09:58,370 --> 00:10:02,420
aastal unshuffled osa massiiv, i kuni n-1.

145
00:10:02,420 --> 00:10:07,280
Nii et kui ma olen siin, valida juhuslik indeks vahel siin ja ülejäänud massiiv,

146
00:10:07,280 --> 00:10:12,410
ja me vahetada.

147
00:10:12,410 --> 00:10:17,550
See on kõik koodi vaja shuffle oma massiivi.

148
00:10:17,550 --> 00:10:21,670
Kas on küsimusi?

149
00:10:21,670 --> 00:10:25,530
>> Noh, üks vaja küsimusele, miks on see õige?

150
00:10:25,530 --> 00:10:28,360
Miks on iga permutatsioon sama tõenäoline?

151
00:10:28,360 --> 00:10:30,410
Ja ma ei lähe läbi selle tõestuseks,

152
00:10:30,410 --> 00:10:35,970
kuid palju probleeme arvuti teadust saab tõestada läbi induktsiooni.

153
00:10:35,970 --> 00:10:38,520
Kui palju te olete tuttav induktsioon?

154
00:10:38,520 --> 00:10:40,590
Okei. Lahe.

155
00:10:40,590 --> 00:10:43,610
Nii saab õigsuse tõendamisel seda algoritmi lihtsate induktsioon,

156
00:10:43,610 --> 00:10:49,540
kus teie induktsiooni hüpotees oleks eeldada, et

157
00:10:49,540 --> 00:10:53,290
minu shuffle naaseb iga permutatsioon sama tõenäoline

158
00:10:53,290 --> 00:10:56,120
kuni esimese i elemente.

159
00:10:56,120 --> 00:10:58,300
Nüüd leiavad i + 1.

160
00:10:58,300 --> 00:11:02,550
Ja muide me valime meie indeks j vahetada,

161
00:11:02,550 --> 00:11:05,230
see viib - ja siis töötada välja andmed,

162
00:11:05,230 --> 00:11:07,390
vähemalt täis tõend selle kohta, miks see algoritm tagastab

163
00:11:07,390 --> 00:11:12,800
iga permutatsioon koos sama tõenäoline tõenäosus.

164
00:11:12,800 --> 00:11:15,940
>> Olgu, järgmine probleem.

165
00:11:15,940 --> 00:11:19,170
Nii et "antud massiivi täisarvud, positiivse väärtuse, null, negatiivne,

166
00:11:19,170 --> 00:11:21,290
kirjutada funktsioon, mis arvutab maksimaalne summa

167
00:11:21,290 --> 00:11:24,720
mis tahes continueous subarray on massiivist. "

168
00:11:24,720 --> 00:11:28,370
Üheks näiteks on siin, juhul kui kõik numbrid on positiivne,

169
00:11:28,370 --> 00:11:31,320
siis praegu parim valik on võtta terve rida.

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

171
00:11:34,690 --> 00:11:36,780
Kui teil on mõned negatiivid seal,

172
00:11:36,780 --> 00:11:38,690
Sel juhul me lihtsalt tahame kahe esimese

173
00:11:38,690 --> 00:11:44,590
sest valides -1 ja / või -3 toovad meie summa maha.

174
00:11:44,590 --> 00:11:48,120
Vahel me võib-olla hakata keset massiivi.

175
00:11:48,120 --> 00:11:53,500
Vahel tahame valida midagi üldse on parem mitte võtta midagi.

176
00:11:53,500 --> 00:11:56,490
Ja mõnikord on parem võtta sügisel,

177
00:11:56,490 --> 00:12:07,510
sest asja pärast on super suur. Nii et mingeid ideid?

178
00:12:07,510 --> 00:12:10,970
(Õpilane, arusaamatult) >> Jah.

179
00:12:10,970 --> 00:12:13,560
Oletame, et ma ei võta -1.

180
00:12:13,560 --> 00:12:16,170
Siis kas ma valida 1000 ja 20000,

181
00:12:16,170 --> 00:12:18,630
või ma lihtsalt valida 3 miljardit eurot.

182
00:12:18,630 --> 00:12:20,760
Noh, parim valik on võtta kõik numbrid.

183
00:12:20,760 --> 00:12:24,350
See -1, hoolimata sellest, et negatiivne,

184
00:12:24,350 --> 00:12:31,340
kogu summa on parem kui oleksin mitte võtta -1.

185
00:12:31,340 --> 00:12:36,460
Nii et ühe vihjeid mainisin oli märgitud selgelt ilmne

186
00:12:36,460 --> 00:12:40,540
ja jõuvõtete lahendus esimesena.

187
00:12:40,540 --> 00:12:44,340
Mis on jõuvõtete lahendus sellele probleemile? Jah?

188
00:12:44,340 --> 00:12:46,890
[Jane] Ma arvan, et jõuvõtete lahendus

189
00:12:46,890 --> 00:12:52,600
oleks lisada kuni kõik võimalikud kombinatsioonid (arusaamatu).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okei. Nii et Jane'i idee on teha kõik võimalik -

191
00:12:58,250 --> 00:13:01,470
Ma olen parafraseerides - on võtta kõikvõimalikke pidev subarray,

192
00:13:01,470 --> 00:13:07,840
arvutada selle summa ja seejärel võtta maksimaalselt kõik võimalikud pidev subarrays.

193
00:13:07,840 --> 00:13:13,310
Mis identifitseerib subarray minu massiivist?

194
00:13:13,310 --> 00:13:17,380
Nagu, mida kaks asja on vaja? Jah?

195
00:13:17,380 --> 00:13:19,970
(Õpilane, arusaamatult) >> Õigus.

196
00:13:19,970 --> 00:13:22,130
Alampiiri indeks ja ülemise indeksiga

197
00:13:22,130 --> 00:13:28,300
üheselt kindlaks pidev subarray.

198
00:13:28,300 --> 00:13:31,400
[Naine üliõpilane] Kas me selle hindamine on array ainulaadne numbrid?

199
00:13:31,400 --> 00:13:34,280
[Yu] No Nii et tema küsimus on, kas me eeldades meie massiivi -

200
00:13:34,280 --> 00:13:39,000
on meie massiivi kõik kordumatud numbrid, ja vastus on ei.

201
00:13:39,000 --> 00:13:43,390
>> Kui me kasutame oma jõuvõtete lahendus, siis start / lõpp indeksid

202
00:13:43,390 --> 00:13:47,200
üheselt määrab meie pidev subarray.

203
00:13:47,200 --> 00:13:51,680
Nii et kui me itereerima kõigi võimalike algus kirjed

204
00:13:51,680 --> 00:13:58,320
ja kõik lõpuks kanded> või = alustada, ja <n,

205
00:13:58,320 --> 00:14:05,570
sa arvutama summa, ja siis võtame maksimaalse summa oleme näinud siiani.

206
00:14:05,570 --> 00:14:07,880
Kas see selge?

207
00:14:07,880 --> 00:14:12,230
Mis on suur O see lahendus?

208
00:14:12,230 --> 00:14:16,660
Ajalises mõttes.

209
00:14:16,660 --> 00:14:18,860
Mitte päris n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Pange tähele, et me itereerima 0 kuni n,

211
00:14:25,250 --> 00:14:27,520
nii et on üks silmus.

212
00:14:27,520 --> 00:14:35,120
Me itereerima taas peaaegu algusest lõpuni, teine ​​silmus.

213
00:14:35,120 --> 00:14:37,640
Ja nüüd, selles on meil Kokkuvõttes iga kirje,

214
00:14:37,640 --> 00:14:43,810
nii see on teine ​​silmus. Nii et meil on kolm nested jaoks silmuseid, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okei. See läheb lähtepunktiks.

216
00:14:46,560 --> 00:14:53,180
Meie lahendus ei ole halvem kui n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Kas kõik mõistavad jõuvõtete lahendus?

218
00:14:55,480 --> 00:14:59,950
>> Okei. Parem lahendus on kasutada mõte nimetatakse dünaamilise programmeerimise.

219
00:14:59,950 --> 00:15:03,040
Kui te võtate CS124, mis on Algoritmid ja andmestruktuurid,

220
00:15:03,040 --> 00:15:05,680
sinust saab väga hästi seda tehnikat.

221
00:15:05,680 --> 00:15:12,190
Ja see idee on, proovige luua lahendusi väiksemad probleemid esimesena.

222
00:15:12,190 --> 00:15:17,990
Mida ma mõtlen on see, meil on praegu muretsema kahte asja: algus ja lõpp.

223
00:15:17,990 --> 00:15:29,340
Ja see on tüütu. Mis siis, kui me võiksime saada lahti üks neist parameetrid?

224
00:15:29,340 --> 00:15:32,650
Üks mõte on - Me oleme andnud meie algne probleem,

225
00:15:32,650 --> 00:15:37,470
leida maksimaalne summa igal subarray vahemikus [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Ja nüüd on meil uus subproblem, kus me teame, et meie praegustes indeks i,

227
00:15:47,400 --> 00:15:52,520
me teame, et me peame järeldama seal. Meie subarray peab lõppema indeks.

228
00:15:52,520 --> 00:15:57,640
Nii et ülejäänud probleem on, kus me peaksime alustama meie subarray?

229
00:15:57,640 --> 00:16:05,160
Kas see on mõttekas? Okei.

230
00:16:05,160 --> 00:16:12,030
Nii et ma olen kodeeritud see üles ja vaatame, mida see tähendab.

231
00:16:12,030 --> 00:16:16,230
Aastal codirectory, seal on programm nimega subarray,

232
00:16:16,230 --> 00:16:19,470
ja see võtab mitmeid punkte,

233
00:16:19,470 --> 00:16:25,550
ja see tagastab maksimaalse subarray summa minu segatud nimekirja.

234
00:16:25,550 --> 00:16:29,920
Nii et antud juhul meie maksimaalse subarray on 3.

235
00:16:29,920 --> 00:16:34,850
Ja see on võtnud lihtsalt kasutades 2 ja 1.

236
00:16:34,850 --> 00:16:38,050
Olgem käivitage see uuesti. See on ka 3.

237
00:16:38,050 --> 00:16:40,950
Aga seekord, pange tähele, kuidas me saime 3.

238
00:16:40,950 --> 00:16:46,690
Tegime - me lihtsalt võtame 3 ise

239
00:16:46,690 --> 00:16:49,980
sest see on ümbritsetud negatiivid mõlemalt poolt,

240
00:16:49,980 --> 00:16:55,080
mis toob summa <3.

241
00:16:55,080 --> 00:16:57,820
Lähme sõitma 10 vastet.

242
00:16:57,820 --> 00:17:03,200
Seekord on see 7, võtame juhtiv 3 ja 4.

243
00:17:03,200 --> 00:17:09,450
Seekord on see 8, ning saame, et võttes 1, 4 ja 3.

244
00:17:09,450 --> 00:17:16,310
Nii et teile intuitsiooni sellest, kuidas me saame lahendada selle ümber probleemi,

245
00:17:16,310 --> 00:17:18,890
võtame pilk see subarray.

246
00:17:18,890 --> 00:17:23,460
Me arvestades seda massiivist, ja me teame, et vastus on 8.

247
00:17:23,460 --> 00:17:26,359
Võtame 1, 4 ja 3.

248
00:17:26,359 --> 00:17:29,090
Aga vaatame, kuidas me tegelikult sain selle vastuse.

249
00:17:29,090 --> 00:17:34,160
Vaatame maksimaalne subarray mis lõppes kell Kõigi nende indeksite.

250
00:17:34,160 --> 00:17:40,780
Mis on maksimaalne subarray et peab lõppema Esimesel kohal?

251
00:17:40,780 --> 00:17:46,310
[Student] Null. >> Zero. Lihtsalt ei võta -5.

252
00:17:46,310 --> 00:17:50,210
Siin see läheb 0. samuti. Jah?

253
00:17:50,210 --> 00:17:56,470
(Õpilane, arusaamatult)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, vabandust, see on -3.

255
00:17:58,960 --> 00:18:03,220
Nii et see on 2, see on -3.

256
00:18:03,220 --> 00:18:08,690
Okei. Nii -4, mis on maksimaalne subarray lõppu selles asendis

257
00:18:08,690 --> 00:18:12,910
kus -4 on? Null.

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

259
00:18:22,570 --> 00:18:28,060
Nüüd pean end kohas, kus -2 on kell.

260
00:18:28,060 --> 00:18:39,330
Nii et 6, 5, 7, ja viimane on 4.

261
00:18:39,330 --> 00:18:43,480
Teades, et need on minu sissekanded

262
00:18:43,480 --> 00:18:48,130
jaoks ümber probleem, kus ma peab lõppema igal neist indeksid,

263
00:18:48,130 --> 00:18:51,410
siis minu lõplik vastus on lihtsalt, kui heita pühkima üle,

264
00:18:51,410 --> 00:18:53,580
ja võtta maksimaalse arvu.

265
00:18:53,580 --> 00:18:55,620
Nii et antud juhul on see 8.

266
00:18:55,620 --> 00:19:00,010
See tähendab, et maksimaalne subarray lõpeb see indeks

267
00:19:00,010 --> 00:19:04,970
ja hakkas kuskil enne seda.

268
00:19:04,970 --> 00:19:09,630
Kas kõik mõistavad seda muutnud subarray?

269
00:19:09,630 --> 00:19:22,160
>> Okei. Noh, olgem nuputada kordumise selle eest.

270
00:19:22,160 --> 00:19:27,990
Vaatleme ainult paar esimest kirjet.

271
00:19:27,990 --> 00:19:35,930
Nii et siin oli 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Ja siis oli -2 siin, ja et tõi ta alla 6.

273
00:19:39,790 --> 00:19:50,800
Nii et kui ma kutsun kanne positsioonis i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
kuidas ma saan kasutada vastus varem subproblem

275
00:19:54,910 --> 00:19:59,360
vastata sellele subproblem?

276
00:19:59,360 --> 00:20:04,550
Kui ma vaatan, ütleme, et see sissekanne.

277
00:20:04,550 --> 00:20:09,190
Kuidas arvutada vastus 6 vaadates

278
00:20:09,190 --> 00:20:18,780
kombinatsioon selle massiivi ja vastused eelmine subproblems selles massiivi? Jah?

279
00:20:18,780 --> 00:20:22,800
[Naine üliõpilane] Sa võta massiivi summade

280
00:20:22,800 --> 00:20:25,430
asendis just enne seda, seega 8,

281
00:20:25,430 --> 00:20:32,170
ja siis lisada praeguse subproblem.

282
00:20:32,170 --> 00:20:36,460
[Yu] Nii et tema soovitus on vaadata need kaks numbrit,

283
00:20:36,460 --> 00:20:40,090
see number ja see number.

284
00:20:40,090 --> 00:20:50,130
Nii et see 8 viidatakse vastus subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
Ja olgem helistan oma massiivist A.

286
00:20:57,300 --> 00:21:01,470
Selleks, et leida maksimaalne subarray et lõpeb asendis i,

287
00:21:01,470 --> 00:21:03,980
Mul on kaks valikut: võin kas jätkata subarray

288
00:21:03,980 --> 00:21:09,790
mis lõppes eelmisel indeks, või alustada uue massiivi.

289
00:21:09,790 --> 00:21:14,190
Kui ma peaksin jätkama subarray et algas eelmisel indeks,

290
00:21:14,190 --> 00:21:19,260
siis maksimaalne summa võin saavutada, on vastus eelmisele subproblem

291
00:21:19,260 --> 00:21:24,120
pluss praegune massiivi kirje.

292
00:21:24,120 --> 00:21:27,550
Aga mul on ka valik algab uus subarray,

293
00:21:27,550 --> 00:21:30,830
sel juhul summa on 0..

294
00:21:30,830 --> 00:21:42,860
Nii et vastus on max 0, subproblem i - 1, millele lisandub jooksev massiivi kirje.

295
00:21:42,860 --> 00:21:46,150
Kas see kordub mõtet?

296
00:21:46,150 --> 00:21:50,840
Meie kordumine, nagu me just avastasin, on subproblem i

297
00:21:50,840 --> 00:21:54,740
on võrdne maksimaalse eelmise subproblem pluss minu praegune massiivi kirje

298
00:21:54,740 --> 00:22:01,490
mis tähendab jätkata eelmise subarray,

299
00:22:01,490 --> 00:22:07,250
või 0, alustada uut subarray minu praegune indeks.

300
00:22:07,250 --> 00:22:10,060
Ja kui oleme rajanud tabelis lahendusi, siis meie lõplik vastus,

301
00:22:10,060 --> 00:22:13,950
lihtsalt ei lineaarse pühkima kogu subproblem massiivi

302
00:22:13,950 --> 00:22:19,890
ja võtta maksimaalse arvu.

303
00:22:19,890 --> 00:22:23,330
See on täpne rakendamine, mida ma just ütlesin.

304
00:22:23,330 --> 00:22:27,320
Nii loome uue subproblem massiiv, subproblems.

305
00:22:27,320 --> 00:22:32,330
Esimene sissekanne on kas 0 või esimese sisenemise, kuni need kaks.

306
00:22:32,330 --> 00:22:35,670
Ja kogu ülejäänud subproblems

307
00:22:35,670 --> 00:22:39,810
me kasutame täpne kordumine me just avastanud.

308
00:22:39,810 --> 00:22:49,960
Nüüd arvutage maksimaalne meie subproblems massiiv, ja see on meie lõplik vastus.

309
00:22:49,960 --> 00:22:54,130
>> Nii et kui palju ruumi on meil kasutades seda algoritmi?

310
00:22:54,130 --> 00:23:01,470
Kui oled ainult võtta CS50, siis sa ei pruugi arutanud ruumi väga palju.

311
00:23:01,470 --> 00:23:07,750
Noh, üks asi on tähele panna, et ma helistasin malloc siin arvu n.

312
00:23:07,750 --> 00:23:13,590
Mida see sulle ütleb?

313
00:23:13,590 --> 00:23:17,450
See algoritm kasutab lineaarse ruumi.

314
00:23:17,450 --> 00:23:21,030
Kas me teha paremini?

315
00:23:21,030 --> 00:23:30,780
Kas on midagi, mida te teate, et ei ole vaja arvutada lõplik vastus?

316
00:23:30,780 --> 00:23:33,290
Ma arvan, et parem küsimus on, millist teavet

317
00:23:33,290 --> 00:23:40,680
me ei pea tegema kogu tee kuni lõpuni?

318
00:23:40,680 --> 00:23:44,280
Nüüd, kui me vaatame neid kahte ritta,

319
00:23:44,280 --> 00:23:47,720
me ainult hoolid eelmise subproblem,

320
00:23:47,720 --> 00:23:50,910
ja me ainult hoolid maksimaalne oleme kunagi näinud siiani.

321
00:23:50,910 --> 00:23:53,610
Arvutada meie lõplik vastus, et me ei pea kogu massiivi.

322
00:23:53,610 --> 00:23:57,450
Meil on vaja ainult viimase numbri kaks viimast numbrit.

323
00:23:57,450 --> 00:24:02,630
Viimase numbri jaoks subproblem massiiv, ja viimane number on maksimaalne.

324
00:24:02,630 --> 00:24:07,380
Nii, et tegelikult me ​​ei sulavad need silmad koos

325
00:24:07,380 --> 00:24:10,460
ja minna lineaarse ruumi pidevalt ruumi.

326
00:24:10,460 --> 00:24:15,830
Praegune summa seni siin, asendab rolli subproblem, meie subproblem massiivi.

327
00:24:15,830 --> 00:24:20,020
Nii et praegune summa, seni on vastus eelmisele subproblem.

328
00:24:20,020 --> 00:24:23,450
Ja see summa, seni on koht meie maks.

329
00:24:23,450 --> 00:24:28,100
Me arvutame maksimaalne kui me läheme mööda.

330
00:24:28,100 --> 00:24:30,890
Ja nii me minna lineaarse ruumi pidevalt ruumi,

331
00:24:30,890 --> 00:24:36,650
ja meil on ka lineaarne lahendus meie subarray probleem.

332
00:24:36,650 --> 00:24:40,740
>> Sellised küsimused saad vestluse käigus.

333
00:24:40,740 --> 00:24:44,450
Mis on aeg keerukus; mida on ruumi keerukus?

334
00:24:44,450 --> 00:24:50,600
Kas sa suudad paremini? Kas on asju, mis on vajalik, et hoida umbes?

335
00:24:50,600 --> 00:24:55,270
Ma tegin seda rõhutada analüüsid, mida peaks arvesse võtma oma

336
00:24:55,270 --> 00:24:57,400
kui te töötate läbi nende probleeme.

337
00:24:57,400 --> 00:25:01,710
Alati tuleb küsida endalt: "Kas ma saan teha paremini?"

338
00:25:01,710 --> 00:25:07,800
Tegelikult me ​​saame teha paremini kui see?

339
00:25:07,800 --> 00:25:10,730
Omamoodi konksuga küsimus. Sa ei saa, sest sa pead

340
00:25:10,730 --> 00:25:13,590
vähemalt lugeda sisendi probleem.

341
00:25:13,590 --> 00:25:15,570
Nii et teil on vaja vähemalt lugeda sisendi probleem

342
00:25:15,570 --> 00:25:19,580
tähendab, et te ei saa teha paremini kui lineaarne aeg,

343
00:25:19,580 --> 00:25:22,870
ja sa ei saa seda teha paremini kui pidev ruumi.

344
00:25:22,870 --> 00:25:27,060
Nii et see on tegelikult parim lahendus sellele probleemile.

345
00:25:27,060 --> 00:25:33,040
Küsimused? Okei.

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

347
00:25:35,190 --> 00:25:38,350
"Arvestades array n täisarvu, positiivne, null, või negatiivne,

348
00:25:38,350 --> 00:25:41,680
mis esindavad hind börsil üle n päeva,

349
00:25:41,680 --> 00:25:44,080
Kirjuta funktsioon arvutada maksimaalset kasumit saab teha

350
00:25:44,080 --> 00:25:49,350
sest sa osta ja müüa täpselt 1 laos nendes n päeva. "

351
00:25:49,350 --> 00:25:51,690
Sisuliselt tahame osta madal, müüa kõrge.

352
00:25:51,690 --> 00:25:58,580
Ja me tahame välja nuputada parim kasum saame teha.

353
00:25:58,580 --> 00:26:11,500
Tulles tagasi minu otsa, mis on kohe selge, lihtsaim lahendus, kuid see on aeglane?

354
00:26:11,500 --> 00:26:17,690
Jah? (Õpilane, arusaamatult) >> Jah.

355
00:26:17,690 --> 00:26:21,470
>> Et siis lihtsalt minna küll ja vaadata aktsia hinda

356
00:26:21,470 --> 00:26:30,550
igal ajahetkel (arusaamatu).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okei, nii et tema lahendus - tema soovitus arvutustehnika

358
00:26:33,990 --> 00:26:37,380
madalaim ning arvutamise kõrgeima ei pruugi toimida

359
00:26:37,380 --> 00:26:42,470
sest kõrgeim võivad ilmneda enne madalaim.

360
00:26:42,470 --> 00:26:47,340
Mis on jõuvõtete lahendus sellele probleemile?

361
00:26:47,340 --> 00:26:53,150
Millised on kaks asja, mida ma pean üheselt määrata kasumi teen? Õigus.

362
00:26:53,150 --> 00:26:59,410
Jõuvõtete lahendus on - oh, jah, Jüri ettepanek on meil vaja ainult kaks päeva

363
00:26:59,410 --> 00:27:02,880
üheselt kindlaks kasum nende kahe päeva jooksul.

364
00:27:02,880 --> 00:27:06,660
Nii et me arvutame iga paari meeldib osta / müüa,

365
00:27:06,660 --> 00:27:12,850
arvutada kasumit, mis võiks olla negatiivne või positiivne või null.

366
00:27:12,850 --> 00:27:18,000
Arvuta maksimaalne kasum, et me teeme pärast itereerimise üle kõik paari päeva jooksul.

367
00:27:18,000 --> 00:27:20,330
See on meie lõplik vastus.

368
00:27:20,330 --> 00:27:25,730
Ja see lahendus on O (n ^ 2), sest seal on n valida kaks paari -

369
00:27:25,730 --> 00:27:30,270
päevade saab valida seas lõpus päeva.

370
00:27:30,270 --> 00:27:32,580
Okei, nii et ma ei lähe üle jõuvõtete lahendus siin.

371
00:27:32,580 --> 00:27:37,420
Ma ütlen teile, et seal on n log n lahendus.

372
00:27:37,420 --> 00:27:45,550
Mis algoritm sa praegu tean, et on n log n?

373
00:27:45,550 --> 00:27:50,730
See ei ole trikiga küsimus.

374
00:27:50,730 --> 00:27:54,790
>> Merge omamoodi. Merge sorteerida on n log n,

375
00:27:54,790 --> 00:27:57,760
ja tegelikult üks viis selle probleemi lahendamiseks on kasutada

376
00:27:57,760 --> 00:28:04,400
ühendamise omamoodi selline idee nimega üldiselt jaga ja valitse.

377
00:28:04,400 --> 00:28:07,570
Ja mõte on järgmine.

378
00:28:07,570 --> 00:28:12,400
Sa tahad arvutada parim osta / müüa paari vasakul pool.

379
00:28:12,400 --> 00:28:16,480
Leia parimaid kasumit saad teha, lihtsalt esimese n üle kahe päeva.

380
00:28:16,480 --> 00:28:19,780
Siis sa tahad oompute parim osta / müüa paar paremal pool,

381
00:28:19,780 --> 00:28:23,930
nii viimane n üle kahe päeva.

382
00:28:23,930 --> 00:28:32,400
Ja nüüd on küsimus selles, kuidas me ühendada need lahendused jälle koos?

383
00:28:32,400 --> 00:28:36,320
Jah? (Õpilane, arusaamatult)

384
00:28:36,320 --> 00:28:49,890
>> Okei. Las ma joonistan pildi.

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

386
00:29:03,870 --> 00:29:06,450
>> Täpselt. George lahendus on täpselt õige.

387
00:29:06,450 --> 00:29:10,040
Nii et tema ettepanek on esimene arvutada parim osta / müüa paar,

388
00:29:10,040 --> 00:29:16,050
ja mis toimub vasakul pool, nii et olgem nimetame seda vasakule, vasakule.

389
00:29:16,050 --> 00:29:20,790
Parim osta / müüa paar, mis toimub paremal pool.

390
00:29:20,790 --> 00:29:25,180
Aga kui me ainult võrreldes nende kahe arvu, et meil puuduvad juhul

391
00:29:25,180 --> 00:29:30,460
kus me ostame siin ja müüa kusagil paremal pool.

392
00:29:30,460 --> 00:29:33,810
Ostame vasakul pool, müüa paremal pool.

393
00:29:33,810 --> 00:29:38,490
Ja parim viis arvutada parim osta / müüa paar, mis ulatub mõlemal poolajal

394
00:29:38,490 --> 00:29:43,480
on arvutada miinimum siin ja arvutage maksimaalne siia

395
00:29:43,480 --> 00:29:45,580
ja võtta nende erinevus.

396
00:29:45,580 --> 00:29:50,850
Nii et kaks juhtumit, kus osta / müüa paar esineb ainult siin,

397
00:29:50,850 --> 00:30:01,910
ainult siin, või mõlemas otsas on määratletud need kolm numbrit.

398
00:30:01,910 --> 00:30:06,450
Nii et meie algoritm ühendada meie lahenduste tagasi kokku,

399
00:30:06,450 --> 00:30:08,350
me tahame arvutada parim osta / müüa paar

400
00:30:08,350 --> 00:30:13,120
kus me ostame vasakul pool ja müüa paremal pool.

401
00:30:13,120 --> 00:30:16,740
Ja parim viis seda teha on arvutada madalaima hinnaga aasta esimesel poolel,

402
00:30:16,740 --> 00:30:20,360
kõrgeima hinnaga paremal pool, ja võtta nende erinevus.

403
00:30:20,360 --> 00:30:25,390
Saadud 3 kasumist, need kolm numbrit, siis võtab maksimaalselt kolm,

404
00:30:25,390 --> 00:30:32,720
ja see on parim kasum saad teha üle need esimesed ja lõpuks päeva.

405
00:30:32,720 --> 00:30:36,940
Siin tähtsamad read on punased.

406
00:30:36,940 --> 00:30:41,160
See on rekursiivne kõne arvutada vastus vasakul pool.

407
00:30:41,160 --> 00:30:44,760
See on rekursiivne kõne arvutada vastus paremal pool.

408
00:30:44,760 --> 00:30:50,720
Need kaks silmuseid arvutama min ja max vasakul ja paremal pool võrra.

409
00:30:50,720 --> 00:30:54,970
Nüüd ma arvutama kasumit, mis ulatub mõlemas otsas,

410
00:30:54,970 --> 00:31:00,530
ja lõplik vastus on suurim neist kolmest.

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

412
00:31:04,120 --> 00:31:06,420
>> Niisiis, muidugi, meil on algoritm, kuid suurem küsimus on,

413
00:31:06,420 --> 00:31:08,290
Kui pikk on aeg keerukus seda?

414
00:31:08,290 --> 00:31:16,190
Ja põhjus, miks ma mainisin ühendamise omamoodi on see, et selles vormis jagada vastus

415
00:31:16,190 --> 00:31:19,200
kaheks ja siis ühinevad meie lahendusi taas kokku

416
00:31:19,200 --> 00:31:23,580
Just kujul ühendamise omamoodi.

417
00:31:23,580 --> 00:31:33,360
Nii et lubage mul minna läbi kestus.

418
00:31:33,360 --> 00:31:41,340
Kui me defineerinud funktsiooni t (n) olla mitmeid samme

419
00:31:41,340 --> 00:31:50,010
kui n päeva,

420
00:31:50,010 --> 00:31:54,350
meie kahe rekursiivne kõne

421
00:31:54,350 --> 00:32:00,460
on iga läheb maksma t (n / 2),

422
00:32:00,460 --> 00:32:03,540
ja seal on kaks neist kõned.

423
00:32:03,540 --> 00:32:10,020
Nüüd on mul vaja arvutada vähemalt vasakul pool,

424
00:32:10,020 --> 00:32:17,050
mis ma teha saan n / 2 aega, pluss maksimaalselt paremal pool.

425
00:32:17,050 --> 00:32:20,820
Nii et see on lihtsalt n.

426
00:32:20,820 --> 00:32:25,050
Ja siis pluss mõned pidevat tööd.

427
00:32:25,050 --> 00:32:27,770
Ja see kordub võrrand

428
00:32:27,770 --> 00:32:35,560
Just kordumise võrrand ühendamise omamoodi.

429
00:32:35,560 --> 00:32:39,170
Ja me kõik teame, et ühendamise sorteerida on n log n korda.

430
00:32:39,170 --> 00:32:46,880
Seega, meie algoritmi ka n log n korda.

431
00:32:46,880 --> 00:32:52,220
Kas see iteratsiooni on mõtet?

432
00:32:52,220 --> 00:32:55,780
Lihtsalt lühikokkuvõtet sellest:

433
00:32:55,780 --> 00:32:59,170
T (n) on mitmeid samme, et arvutada maksimaalne kasum

434
00:32:59,170 --> 00:33:02,750
jooksul n päeva.

435
00:33:02,750 --> 00:33:06,010
Kuidas me lahku meie rekursiivne kõne

436
00:33:06,010 --> 00:33:11,980
on helistades meie lahendus esimese n / 2 päeva,

437
00:33:11,980 --> 00:33:14,490
nii et on üks kõne

438
00:33:14,490 --> 00:33:16,940
ja siis me kutsume taas aasta teisel poolel.

439
00:33:16,940 --> 00:33:20,440
Nii et kaks kõnet.

440
00:33:20,440 --> 00:33:25,310
Ja siis me leiame vähemalt vasakul pool, mis me teha saame, on lineaarne aeg,

441
00:33:25,310 --> 00:33:29,010
leida maksimaalselt paremal pool, mida me saame teha lineaarne aeg.

442
00:33:29,010 --> 00:33:31,570
Nii n / 2 + n / 2 on lihtsalt n.

443
00:33:31,570 --> 00:33:36,020
Siis meil on mõned pidev töö, mis on nagu tehes aritmeetika.

444
00:33:36,020 --> 00:33:39,860
See kordumise võrrand on täpselt kordumise võrrand ühendamise omamoodi.

445
00:33:39,860 --> 00:33:55,490
Seega, meie shuffle algoritm on ka n log n.

446
00:33:55,490 --> 00:33:58,520
Nii et kui palju ruumi on meil kasutada?

447
00:33:58,520 --> 00:34:04,910
Lähme tagasi kood.

448
00:34:04,910 --> 00:34:09,420
>> Parem küsimus on, kui palju korstna raamid me kunagi igal ajahetkel?

449
00:34:09,420 --> 00:34:11,449
Kuna me kasutame rekursioon,

450
00:34:11,449 --> 00:34:23,530
arvu korstnat raamid määrab meie ruumikasutuse.

451
00:34:23,530 --> 00:34:29,440
Vaatleme n = 8.

452
00:34:29,440 --> 00:34:36,889
Kutsume shuffle 8.,

453
00:34:36,889 --> 00:34:41,580
mis kutsuvad shuffle esimese nelja kirjed

454
00:34:41,580 --> 00:34:46,250
mis kutsuvad shuffle kahe esimese kanded.

455
00:34:46,250 --> 00:34:51,550
Nii et meie stack on - see on meie pinu.

456
00:34:51,550 --> 00:34:54,980
Ja siis me kutsume shuffle jälle 1

457
00:34:54,980 --> 00:34:58,070
ja see, mida meie tugipunkt on, et me kohe tagasi.

458
00:34:58,070 --> 00:35:04,700
Kas me kunagi olla rohkem kui nii palju korstna raame?

459
00:35:04,700 --> 00:35:08,880
No Sest iga kord, kui me teeme appihüüd,

460
00:35:08,880 --> 00:35:10,770
rekursiivne pöördumine shuffle,

461
00:35:10,770 --> 00:35:13,950
me jagame meie suuruste poole.

462
00:35:13,950 --> 00:35:17,020
Nii maksimaalne arv virnas raamid me kunagi igal ajahetkel

463
00:35:17,020 --> 00:35:28,460
on järjekorras log n korstnat raame.

464
00:35:28,460 --> 00:35:42,460
Iga freimi on pidev ruumi,

465
00:35:42,460 --> 00:35:44,410
ja seega kogusumma ruumi,

466
00:35:44,410 --> 00:35:49,240
maksimaalne summa ruumi me kunagi kasutada on O (log n) ruum

467
00:35:49,240 --> 00:36:03,040
kus n on päevade arv.

468
00:36:03,040 --> 00:36:07,230
>> Nüüd, alati endalt küsima, "Kas me teha paremini?"

469
00:36:07,230 --> 00:36:12,390
Ja eriti, kas me saame vähendada seda probleemi me oleme juba lahendatud?

470
00:36:12,390 --> 00:36:20,040
Vihje: me ainult arutasid kahe teise probleeme enne seda, ja see ei kavatse olla shuffle.

471
00:36:20,040 --> 00:36:26,200
Me ei saa muuta seda aktsiaturu probleem arvesse maksimaalne subarray probleem.

472
00:36:26,200 --> 00:36:40,100
Kuidas me saame seda teha?

473
00:36:40,100 --> 00:36:42,570
Üks teist? Emmy?

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

475
00:36:47,680 --> 00:36:53,860
[Yu] Täpselt.

476
00:36:53,860 --> 00:36:59,940
Nii maksimaalne subarray probleem,

477
00:36:59,940 --> 00:37:10,610
me otsime summa üle pideva subarray.

478
00:37:10,610 --> 00:37:16,230
Ja Emmy ettepanekut varude probleem,

479
00:37:16,230 --> 00:37:30,720
kaaluda muudatusi või deltad.

480
00:37:30,720 --> 00:37:37,440
Ja pilt on see - see on hind börsil,

481
00:37:37,440 --> 00:37:42,610
kuid kui me võtame vahe iga järgneva päeva -

482
00:37:42,610 --> 00:37:45,200
nii me näeme, et maksimaalne hind, maksimaalne kasum saaksime

483
00:37:45,200 --> 00:37:50,070
on see, kui me ostame siin ja müüvad siin.

484
00:37:50,070 --> 00:37:54,240
Aga vaatame pidevalt - vaatame subarray probleem.

485
00:37:54,240 --> 00:38:02,510
Nii et siin, saame teha - lähed siit siiani,

486
00:38:02,510 --> 00:38:08,410
meil on positiivne muutus, ja siis läheb siit siiani meil on negatiivne muutus.

487
00:38:08,410 --> 00:38:14,220
Aga siis läheb siit siiani meil on suur positiivne muutus.

488
00:38:14,220 --> 00:38:20,930
Ja need muutused, mida me tahame kokku saada meie lõplik kasum.

489
00:38:20,930 --> 00:38:25,160
Siis on meil rohkem negatiivseid muutusi siin.

490
00:38:25,160 --> 00:38:29,990
Vähendamisel ülioluline meie varu probleem meie maksimaalse subarray probleem

491
00:38:29,990 --> 00:38:36,630
on kaaluda deltad päeva vahel.

492
00:38:36,630 --> 00:38:40,630
Nii loome uue massiivi nimega deltadega

493
00:38:40,630 --> 00:38:43,000
initsialiseerida esimese sisenemise olema 0,

494
00:38:43,000 --> 00:38:46,380
ja siis iga delta (i), olgu see erinevus

495
00:38:46,380 --> 00:38:52,830
minu massiivist (i), ja massiiv (i - 1).

496
00:38:52,830 --> 00:38:55,530
Siis me nimetame meie rutiinne protseduur maksimaalne subarray

497
00:38:55,530 --> 00:39:01,500
läbivad Delta massiivi.

498
00:39:01,500 --> 00:39:06,440
Ja kuna maksimaalne subarray on lineaarne aeg,

499
00:39:06,440 --> 00:39:09,370
ja see vähenemine, see loomas see delta massiiv,

500
00:39:09,370 --> 00:39:11,780
Samuti on lineaarne aeg,

501
00:39:11,780 --> 00:39:19,060
siis lõplik lahendus varud on O (n) töö pluss O (n) töö on ikka O (n) tööd.

502
00:39:19,060 --> 00:39:23,900
Nii et meil on lineaarne aeg lahendus meie probleemile.

503
00:39:23,900 --> 00:39:29,610
Kas kõik mõistavad selle muutuse?

504
00:39:29,610 --> 00:39:32,140
>> Üldiselt on hea mõte, et sa peaksid alati olema

505
00:39:32,140 --> 00:39:34,290
on püüda vähendada uus probleem, et te näete.

506
00:39:34,290 --> 00:39:37,700
Kui tundub tuttav vana probleem,

507
00:39:37,700 --> 00:39:39,590
proovige vähendada seda vana probleem.

508
00:39:39,590 --> 00:39:41,950
Ja kui sa ei kasuta kõiki vahendeid, mida olen kasutanud vana probleem

509
00:39:41,950 --> 00:39:46,450
lahendada uusi probleeme.

510
00:39:46,450 --> 00:39:49,010
Nii et soojalt riidesse panema, tehniline intervjuud on keeruline.

511
00:39:49,010 --> 00:39:52,280
Need probleemid on ilmselt ühed kõige raskemad probleemid

512
00:39:52,280 --> 00:39:54,700
et võite näha intervjuus,

513
00:39:54,700 --> 00:39:57,690
nii et kui sa ei mõista kõiki probleeme, et ma lihtsalt kaetud, see on okei.

514
00:39:57,690 --> 00:40:01,080
Need on mõned rohkem probleemid.

515
00:40:01,080 --> 00:40:03,050
Praktika, praktika, praktika.

516
00:40:03,050 --> 00:40:08,170
Ma andsin palju probleeme jaotusmaterjali, nii kindlasti vaadata need läbi.

517
00:40:08,170 --> 00:40:11,690
Ja hea õnne oma intervjuud. Kõik minu ressursid on postitanud seda linki,

518
00:40:11,690 --> 00:40:15,220
ja üks mu vanem sõbrad on pakkunud teha mõnitama tehnilise intervjuud,

519
00:40:15,220 --> 00:40:22,050
nii et kui olete huvitatud, email Yao tol e-posti aadress.

520
00:40:22,050 --> 00:40:26,070
Kui teil on küsimusi, võite küsida mind.

521
00:40:26,070 --> 00:40:28,780
Kas teiega on konkreetseid küsimusi, mis on seotud tehnilise intervjuud

522
00:40:28,780 --> 00:40:38,440
või mingeid probleeme oleme näinud nii kaugele?

523
00:40:38,440 --> 00:40:49,910
Okei. Noh, õnne oma intervjuud.

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