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

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Universiteti i Harvardit]

3
00:00:04,630 --> 00:00:08,910
[Kjo është CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hi everyone, unë jam Kenny. Unë jam aktualisht një i ri studiuar shkenca kompjuterike.

5
00:00:12,420 --> 00:00:17,310
Unë jam një ish CS TF, dhe I wish I kishte kjo, kur unë isha një underclassman,

6
00:00:17,310 --> 00:00:19,380
dhe kjo është arsyeja pse unë jam duke i dhënë në këtë seminar.

7
00:00:19,380 --> 00:00:21,370
Kështu që unë shpresoj që ju të gëzojë atë.

8
00:00:21,370 --> 00:00:23,470
Ky seminar është rreth intervistave teknike,

9
00:00:23,470 --> 00:00:26,650
dhe të gjitha burimet e mia mund të gjendet në këtë lidhje,

10
00:00:26,650 --> 00:00:32,350
kjo lidhje të drejtë këtu, një çift i burimeve.

11
00:00:32,350 --> 00:00:36,550
Kështu që unë bëra një listë të problemeve, në fakt, mjaft disa probleme.

12
00:00:36,550 --> 00:00:40,800
Gjithashtu një gjeneral burimet faqe ku ne mund të gjeni këshilla

13
00:00:40,800 --> 00:00:42,870
se si të përgatiten për një intervistë,

14
00:00:42,870 --> 00:00:46,470
këshilla mbi atë që ju duhet të bëni gjatë një intervistë aktuale,

15
00:00:46,470 --> 00:00:51,910
si dhe se si t'i qasen problemeve dhe burimet për referencë në të ardhmen.

16
00:00:51,910 --> 00:00:53,980
Kjo është e gjitha në internet.

17
00:00:53,980 --> 00:00:58,290
Dhe vetëm për të parathënie këtë seminar, një mohim,

18
00:00:58,290 --> 00:01:00,690
si kjo nuk duhet - përgatitjen tuaj intervistë

19
00:01:00,690 --> 00:01:02,800
nuk duhet të kufizohet në këtë listë.

20
00:01:02,800 --> 00:01:04,750
Kjo është për qëllim vetëm të jetë një udhëzues,

21
00:01:04,750 --> 00:01:08,890
dhe ju duhet patjetër të marrë çdo gjë që unë them me një kokërr kripë,

22
00:01:08,890 --> 00:01:14,620
por të përdorë gjithashtu edhe gjithçka kam përdorur për t'ju ndihmuar në përgatitjen tuaj intervistës.

23
00:01:14,620 --> 00:01:16,400
>> Unë jam duke shkuar për të shpejtuar nëpër slides ardhshme

24
00:01:16,400 --> 00:01:18,650
kështu që ne mund të merrni për studimet e rasteve aktuale.

25
00:01:18,650 --> 00:01:23,630
Struktura e një intervistë për një pozitë inxhinieri software,

26
00:01:23,630 --> 00:01:26,320
zakonisht është 30-45 minuta,

27
00:01:26,320 --> 00:01:29,810
raunde të shumta, në varësi të kompanisë.

28
00:01:29,810 --> 00:01:33,090
Shpesh ju do të kodimit në një bord të bardhë.

29
00:01:33,090 --> 00:01:35,960
Pra, një bord të bardhë si kjo, por shpesh në një shkallë më të vogël.

30
00:01:35,960 --> 00:01:38,540
Nëse ju jeni të paturit e një intervistë telefonike, ju ndoshta do të jetë duke përdorur

31
00:01:38,540 --> 00:01:44,030
ose collabedit ose një Doc Google në mënyrë që ata mund të shohin jetoni coding

32
00:01:44,030 --> 00:01:46,500
ndërkohë që jeni duke u intervistuar mbi telefon.

33
00:01:46,500 --> 00:01:48,490
Një intervistë në vetvete është zakonisht 2 ose 3 probleme

34
00:01:48,490 --> 00:01:50,620
testimin e njohurive shkenca e kompjuterit tuaj.

35
00:01:50,620 --> 00:01:54,490
Dhe kjo do të përfshijë pothuajse patjetër coding.

36
00:01:54,490 --> 00:01:59,540
Llojet e pyetjeve që ju do të shihni zakonisht janë strukturat e të dhënave dhe algoritmet.

37
00:01:59,540 --> 00:02:02,210
Dhe duke bërë këto lloje të problemeve,

38
00:02:02,210 --> 00:02:07,830
ata do të ju pyes, si, çfarë është koha dhe kompleksiteti hapësirë, i madh o?

39
00:02:07,830 --> 00:02:09,800
Shpesh ata kërkojnë edhe më të larta të nivelit të pyetjeve,

40
00:02:09,800 --> 00:02:12,530
kështu, të hartonin një sistem,

41
00:02:12,530 --> 00:02:14,770
si do ta nxjerr kodin tuaj?

42
00:02:14,770 --> 00:02:18,370
Çfarë Interfaces, çfarë klasa, çfarë module keni në sistemin tuaj,

43
00:02:18,370 --> 00:02:20,900
dhe si këta bashkëveprojnë së bashku?

44
00:02:20,900 --> 00:02:26,130
Prandaj të dhënat strukturat dhe algoritme si dhe sistemet projektim.

45
00:02:26,130 --> 00:02:29,180
>> Disa këshilla të përgjithshme para se të zhyten në të studimeve tona të rasteve.

46
00:02:29,180 --> 00:02:32,300
Unë mendoj se rregulli më i rëndësishëm është gjithmonë duke menduar me zë të lartë.

47
00:02:32,300 --> 00:02:36,980
Intervista është menduar të jetë mundësia juaj për të treguar off procesin e të menduarit tuaj.

48
00:02:36,980 --> 00:02:39,820
Pika e intervistës është për intervistuesit për të vlerësuar

49
00:02:39,820 --> 00:02:42,660
si mendoni dhe si ju shkoni nëpër një problem.

50
00:02:42,660 --> 00:02:45,210
Gjëja më e keqe që ju mund të bëni është të jetë i heshtur gjatë gjithë intervistës në tërësi.

51
00:02:45,210 --> 00:02:50,090
Kjo është vetëm nuk është e mirë.

52
00:02:50,090 --> 00:02:53,230
Kur ju jeni të dhënë një pyetje, edhe ju doni të bëni të sigurtë që ju e kuptoni pyetjen.

53
00:02:53,230 --> 00:02:55,350
Pra, përsëris pyetjen përsëri në fjalët tuaja

54
00:02:55,350 --> 00:02:58,920
dhe përpjekje për të punuar plota disa raste të thjeshta provë

55
00:02:58,920 --> 00:03:01,530
për t'u siguruar që ju të kuptoni pyetjen.

56
00:03:01,530 --> 00:03:05,510
Duke punuar përmes një provë disa raste gjithashtu do t'ju japë një intuitë se si për të zgjidhur këtë problem.

57
00:03:05,510 --> 00:03:11,210
Ju mund të zbuloni edhe disa modele pak të ju ndihmojë të zgjidhur problemin.

58
00:03:11,210 --> 00:03:14,500
Tip i tyre i madh është që të mos merrni frustruar.

59
00:03:14,500 --> 00:03:17,060
A nuk merrni frustruar.

60
00:03:17,060 --> 00:03:19,060
Intervistat janë sfiduese, por gjëja më e keqe që ju mund të bëni,

61
00:03:19,060 --> 00:03:23,330
përveç për të qenë i heshtur, duhet të frustruar në mënyrë të dukshme.

62
00:03:23,330 --> 00:03:27,410
Ju nuk duan të japin përshtypjen se në një intervistuesit.

63
00:03:27,410 --> 00:03:33,960
Një gjë që ju - kështu, shumë njerëz, kur ata të shkojnë në një intervistë,

64
00:03:33,960 --> 00:03:37,150
ata përpiqen të përpiqen për të gjetur zgjidhjen më të mirë e parë,

65
00:03:37,150 --> 00:03:39,950
kur me të vërtetë, ka zakonisht një zgjidhje verbim e qartë.

66
00:03:39,950 --> 00:03:43,500
Ajo mund të jetë i ngadalshëm, mund të jetë i paefektshëm, por ju duhet vetëm të deklarojë atë,

67
00:03:43,500 --> 00:03:46,210
vetëm kështu që ju keni një pikënisje nga e cila për të punuar më mirë.

68
00:03:46,210 --> 00:03:48,270
Gjithashtu, duke vënë në dukje zgjidhje është i ngadalshëm, në drejtim të

69
00:03:48,270 --> 00:03:52,160
Kompleksiteti i madh o kohë apo kompleksiteti hapësirë,

70
00:03:52,160 --> 00:03:54,450
do të demonstrojë të intervistuesit se ju e kuptoni

71
00:03:54,450 --> 00:03:57,510
këto çështje kur shkruani kodin.

72
00:03:57,510 --> 00:04:01,440
Pra, mos kini frikë për të dalë me algorithm thjeshtë parë

73
00:04:01,440 --> 00:04:04,950
dhe pastaj të punojnë më mirë nga atje.

74
00:04:04,950 --> 00:04:09,810
Çdo pyetje deri më tani? Rregull.

75
00:04:09,810 --> 00:04:11,650
>> Pra, le të zhyten në problemin tonë të parë.

76
00:04:11,650 --> 00:04:14,790
"Duke pasur parasysh një grup i integers n, shkruani një funksion që lëvizjet array

77
00:04:14,790 --> 00:04:20,209
në vend të tillë që të gjitha permutations e integers n janë njëlloj të mundshme. "

78
00:04:20,209 --> 00:04:23,470
Dhe të supozojmë që ju keni në dispozicion një gjenerator të rastit numër i plotë

79
00:04:23,470 --> 00:04:30,980
që gjeneron një numër të plotë në një varg prej 0 deri i, varg e gjysmë.

80
00:04:30,980 --> 00:04:32,970
A të gjithë e kuptojnë këtë pyetje?

81
00:04:32,970 --> 00:04:39,660
Unë ju jap një rrjet të integers n, dhe unë dua që ju të riorganizimi atë.

82
00:04:39,660 --> 00:04:46,050
Në directory time, kam shkruar disa programe për të demonstruar se çfarë dua të them.

83
00:04:46,050 --> 00:04:48,910
Unë jam duke shkuar për riorganizimi një rrjet prej 20 elementeve,

84
00:04:48,910 --> 00:04:52,490
nga -10 në 9,

85
00:04:52,490 --> 00:04:57,050
dhe unë dua që ju të shkruani një listë si kjo.

86
00:04:57,050 --> 00:05:02,890
Pra, kjo është array renditura im input, dhe unë dua që ju të riorganizimi atë.

87
00:05:02,890 --> 00:05:07,070
Ne do të bëjmë atë përsëri.

88
00:05:07,070 --> 00:05:13,780
A të gjithë e kuptojnë pyetjen? Rregull.

89
00:05:13,780 --> 00:05:16,730
Kështu që është e deri tek ju.

90
00:05:16,730 --> 00:05:21,220
Cilat janë disa ide? Ju mund të bëni atë si n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Hapur për sugjerime.

92
00:05:34,400 --> 00:05:37,730
Rregull. Pra, një ide, sugjeruar nga Emmy,

93
00:05:37,730 --> 00:05:45,300
është parë llogaritur një numër të rastit, integer rastit, në një varg 0-20.

94
00:05:45,300 --> 00:05:49,840
Pra, supozojmë array jonë ka një gjatësi prej 20.

95
00:05:49,840 --> 00:05:54,800
Në diagramin tonë të 20 elementeve,

96
00:05:54,800 --> 00:05:58,560
kjo është koleksion tona input.

97
00:05:58,560 --> 00:06:04,590
Dhe tani, sugjerimi i saj është që të krijojë një rrjet të ri,

98
00:06:04,590 --> 00:06:08,440
kështu që kjo do të jetë array prodhimit.

99
00:06:08,440 --> 00:06:12,880
Dhe në bazë të i kthyer nga rand -

100
00:06:12,880 --> 00:06:17,580
Pra, nëse unë ishte, le të themi, 17,

101
00:06:17,580 --> 00:06:25,640
kopjoni elementin 17 në vendin e parë.

102
00:06:25,640 --> 00:06:30,300
Tani ne kemi nevojë për të fshirë - ne duhet të zhvendoset të gjitha elementet këtu

103
00:06:30,300 --> 00:06:36,920
mbi kështu që ne kemi një boshllëk në fund dhe nuk ka vrima në mes.

104
00:06:36,920 --> 00:06:39,860
Dhe tani ne përsëris procesin.

105
00:06:39,860 --> 00:06:46,360
Tani ne të zgjedhë një numër të plotë të ri të rastit midis 0 dhe 19.

106
00:06:46,360 --> 00:06:52,510
Ne kemi një i ri këtu, dhe ne kopje këtë element në këtë pozitë.

107
00:06:52,510 --> 00:07:00,960
Pastaj ne zhvendoset artikuj mbi dhe ne përsërisin procesin derisa ne kemi të plotë rrjet tonë të ri.

108
00:07:00,960 --> 00:07:05,890
Cila është koha të drejtuar e këtij algoritmi?

109
00:07:05,890 --> 00:07:08,110
E pra, le të marrin në konsideratë ndikimin e kësaj.

110
00:07:08,110 --> 00:07:10,380
Ne jemi zhvendosur çdo element.

111
00:07:10,380 --> 00:07:16,800
Kur ne hiqni këtë unë, ne jemi zhvendosur të gjitha elementet pas atë të majtë.

112
00:07:16,800 --> 00:07:21,600
Dhe që është një (N) kosto O

113
00:07:21,600 --> 00:07:26,100
sepse ajo që në qoftë se ne të hequr elementin e parë?

114
00:07:26,100 --> 00:07:29,670
Kështu që për çdo largim, kemi hequr -

115
00:07:29,670 --> 00:07:32,170
secili heqjen krijon një operacion (n) O,

116
00:07:32,170 --> 00:07:41,520
dhe që ne kemi n removals, kjo çon në një riorganizimi (n ^ 2) O.

117
00:07:41,520 --> 00:07:49,550
Rregull. Pra, fillim i mirë. Fillim i mirë.

118
00:07:49,550 --> 00:07:55,290
>> Një tjetër sugjerim është që të përdorin diçka të njohur si riorganizimi Knuth,

119
00:07:55,290 --> 00:07:57,540
ose Fisher-Jets riorganizimi.

120
00:07:57,540 --> 00:07:59,630
Dhe kjo është në fakt një riorganizimi lineare kohë.

121
00:07:59,630 --> 00:08:02,200
Dhe ideja është shumë e ngjashme.

122
00:08:02,200 --> 00:08:05,160
Përsëri, ne kemi koleksion tonë input,

123
00:08:05,160 --> 00:08:08,580
por në vend të përdorimit të dy vargjeve për input / output tonë,

124
00:08:08,580 --> 00:08:13,590
ne përdorim pjesën e parë të vektorit të mbajnë gjurmët e pjesës sonë riorganizoi,

125
00:08:13,590 --> 00:08:18,400
dhe do të vazhdojmë rrugën, dhe pastaj kemi lënë pjesën tjetër të array tonë për pjesën unshuffled.

126
00:08:18,400 --> 00:08:24,330
Kështu që këtu është ajo që dua të them. Ne nisem me - kemi zgjedhur një i,

127
00:08:24,330 --> 00:08:30,910
një grup 0-20.

128
00:08:30,910 --> 00:08:36,150
Akrep jonë e tanishme është vënë në indeksin e parë.

129
00:08:36,150 --> 00:08:39,590
Ne të zgjedhin disa here i

130
00:08:39,590 --> 00:08:42,740
dhe tani ne bie në ujdi.

131
00:08:42,740 --> 00:08:47,690
Pra, nëse kjo ishte 5 dhe kjo ishte 4,

132
00:08:47,690 --> 00:08:57,150
array rezulton do të ketë 5 këtu dhe 4 here.

133
00:08:57,150 --> 00:09:00,390
Dhe tani ne vërejmë një shënues këtu.

134
00:09:00,390 --> 00:09:05,770
Çdo gjë në të majtë është riorganizoi,

135
00:09:05,770 --> 00:09:15,160
dhe çdo gjë në të djathtë është unshuffled.

136
00:09:15,160 --> 00:09:17,260
Dhe tani ne mund të përsëris procesin.

137
00:09:17,260 --> 00:09:25,210
Ne zgjidhni një indeks të rastit ndërmjet 1 dhe 20 tani.

138
00:09:25,210 --> 00:09:30,650
Pra mendoj tonë të ri i është këtu.

139
00:09:30,650 --> 00:09:39,370
Tani ne këtë shkëmbim i pozitës aktuale me tonë të re këtu.

140
00:09:39,370 --> 00:09:44,790
Pra, ne do të shkëmbejnë një mbrapa dhe me radhë si kjo.

141
00:09:44,790 --> 00:09:51,630
Më lejoni të sjell deri kodin për ta bërë atë më konkret.

142
00:09:51,630 --> 00:09:55,290
Ne fillim me zgjedhjen tonë të I -

143
00:09:55,290 --> 00:09:58,370
ne fillim me i barabartë me 0, ne të zgjedhë një j rastit vendndodhjen

144
00:09:58,370 --> 00:10:02,420
në pjesën unshuffled e vektorit, I te n-1.

145
00:10:02,420 --> 00:10:07,280
Pra, nëse unë jam këtu, zgjidhni një indeks të rastit midis këtu dhe pjesën tjetër të grup,

146
00:10:07,280 --> 00:10:12,410
dhe ne swap.

147
00:10:12,410 --> 00:10:17,550
Kjo është e gjitha kodin e nevojshme për të riorganizimi Array tuaj.

148
00:10:17,550 --> 00:10:21,670
Çdo pyetje?

149
00:10:21,670 --> 00:10:25,530
>> E pra, një pyetje e nevojshme është, pse është kjo e saktë?

150
00:10:25,530 --> 00:10:28,360
Pse është çdo ndryshim në mënyrë të barabartë të ngjarë?

151
00:10:28,360 --> 00:10:30,410
Dhe unë nuk do të shkojnë nëpër provë e kësaj,

152
00:10:30,410 --> 00:10:35,970
por shumë probleme në shkenca kompjuterike mund të provohet me anë të induksionit.

153
00:10:35,970 --> 00:10:38,520
Sa prej jush janë të njohur me induksion?

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

155
00:10:40,590 --> 00:10:43,610
Kështu që ju mund të provojë saktësinë e këtij algoritmi me induksion të thjeshtë,

156
00:10:43,610 --> 00:10:49,540
ku hipoteza juaj induksion do të jetë, të supozojmë se

157
00:10:49,540 --> 00:10:53,290
riorganizimi im kthehet çdo ndryshim në mënyrë të barabartë të ngjarë

158
00:10:53,290 --> 00:10:56,120
deri tek elementet parë kam.

159
00:10:56,120 --> 00:10:58,300
Tani, unë e konsiderojnë + 1.

160
00:10:58,300 --> 00:11:02,550
Dhe nga rruga, ne zgjidhni j tonë indeksi të bie në ujdi,

161
00:11:02,550 --> 00:11:05,230
kjo çon në - dhe pastaj ju punojnë jashtë detajet,

162
00:11:05,230 --> 00:11:07,390
të paktën një provë plotë i pse kjo algoritmi kthen

163
00:11:07,390 --> 00:11:12,800
çdo ndërrim me probabilitet të barabartë të mundshme.

164
00:11:12,800 --> 00:11:15,940
>> Të gjithë të drejtë, problemi tjetër.

165
00:11:15,940 --> 00:11:19,170
Pra "jepet një rrjet të integers, postive, zero, negativ,

166
00:11:19,170 --> 00:11:21,290
shkruajnë një funksion që llogarit shumën maksimale

167
00:11:21,290 --> 00:11:24,720
e çdo subarray continueous e array input. "

168
00:11:24,720 --> 00:11:28,370
Një shembull këtu është, në rastin kur të gjithë numrat janë pozitive,

169
00:11:28,370 --> 00:11:31,320
pastaj aktualisht zgjidhja më e mirë është që të marrë array tërë.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, e barabartë me 10.

171
00:11:34,690 --> 00:11:36,780
Kur ju keni disa negative në atje,

172
00:11:36,780 --> 00:11:38,690
në këtë rast ne duam vetëm dy të parat

173
00:11:38,690 --> 00:11:44,590
sepse zgjedhur -1 dhe / ose do të sjellë shumën -3 tonë poshtë.

174
00:11:44,590 --> 00:11:48,120
Ndonjëherë ne mund të kemi për të filluar në mes të grup.

175
00:11:48,120 --> 00:11:53,500
Ndonjëherë ne duam të zgjidhni asgjë në të gjitha, ajo është e mirë për të mos marrë asgjë.

176
00:11:53,500 --> 00:11:56,490
Dhe nganjëherë kjo është më mirë për të marrë në vjeshtë,

177
00:11:56,490 --> 00:12:07,510
sepse gjëja pasi ajo është super i madh. Pra, ndonjë ide?

178
00:12:07,510 --> 00:12:10,970
(Student, i pakuptueshëm) >> Po.

179
00:12:10,970 --> 00:12:13,560
Mendoj unë nuk do të marrë -1.

180
00:12:13,560 --> 00:12:16,170
Pastaj ose kam zgjedhur 1.000 dhe 20.000,

181
00:12:16,170 --> 00:12:18,630
ose unë vetëm të zgjedhin 3 miliardë.

182
00:12:18,630 --> 00:12:20,760
E pra, zgjidhja më e mirë është që të marrë të gjitha numrat.

183
00:12:20,760 --> 00:12:24,350
Kjo -1, pavarësisht se janë negative,

184
00:12:24,350 --> 00:12:31,340
shuma e tërë është më mirë se unë nuk kanë qenë për të marrë -1.

185
00:12:31,340 --> 00:12:36,460
Pra, një nga këshilla e kam përmendur më herët ishte të shtetit të qartë të dukshme

186
00:12:36,460 --> 00:12:40,540
dhe zgjidhja e brute force parë.

187
00:12:40,540 --> 00:12:44,340
Cila është zgjidhja brute force në këtë problem? Po?

188
00:12:44,340 --> 00:12:46,890
[Jane] E pra, unë mendoj se zgjidhja brutale fuqi

189
00:12:46,890 --> 00:12:52,600
do të jetë për të shtoni deri gjitha kombinimet e mundshme (pakuptueshëm).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Pra, ideja Jane është që të marrë çdo mundur -

191
00:12:58,250 --> 00:13:01,470
Unë jam Konvertime - është që të marrë çdo subarray mundshme të vazhdueshme,

192
00:13:01,470 --> 00:13:07,840
llogaritin shumën e saj, dhe pastaj të marrë maksimumin e të gjitha subarrays mundshme të vazhdueshme.

193
00:13:07,840 --> 00:13:13,310
Çfarë identifikon në mënyrë unike një subarray në grup tim input?

194
00:13:13,310 --> 00:13:17,380
Si, çka dy gjëra nuk kam nevojë? Po?

195
00:13:17,380 --> 00:13:19,970
(Student, i pakuptueshëm) E drejta. >>

196
00:13:19,970 --> 00:13:22,130
Një ulët i detyruar në indeksin dhe një indeksi sipërme të lidhur

197
00:13:22,130 --> 00:13:28,300
unike përcakton një subarray vazhdueshme.

198
00:13:28,300 --> 00:13:31,400
[Student Femër] A kemi vlerësuar se është një grup i numrave unik?

199
00:13:31,400 --> 00:13:34,280
[Yu] Nr Pra, pyetjes së saj është, jemi duke supozuar koleksion tonë -

200
00:13:34,280 --> 00:13:39,000
është array tonë të gjithë numrat unik, dhe përgjigja është jo.

201
00:13:39,000 --> 00:13:43,390
>> Nëse ne përdorim zgjidhje tonë shtazë fuqi, atëherë në fillim / fund indekset

202
00:13:43,390 --> 00:13:47,200
unike përcakton subarray tonë të vazhdueshme.

203
00:13:47,200 --> 00:13:51,680
Pra, nëse ne iterate për të gjitha shënimet e fillimit të mundshme,

204
00:13:51,680 --> 00:13:58,320
dhe për të gjitha shënimet në fund të> ose = për të filluar, dhe <n,

205
00:13:58,320 --> 00:14:05,570
ju llogaritin shumën, dhe pastaj ne kemi marrë shumën maksimale që kemi parë deri më tani.

206
00:14:05,570 --> 00:14:07,880
A është kjo e qartë?

207
00:14:07,880 --> 00:14:12,230
Çfarë është O e madhe e kësaj zgjidhjeje?

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

209
00:14:16,660 --> 00:14:18,860
Jo mjaft n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Vini re se ne iterate nga 0 deri n,

211
00:14:25,250 --> 00:14:27,520
kështu që është një për lak.

212
00:14:27,520 --> 00:14:35,120
Ne iterate përsëri nga pothuajse për fillimin deri në fund, një tjetër për lak.

213
00:14:35,120 --> 00:14:37,640
Dhe tani, në kuadër të kësaj, ne kemi për të përmbledhur çdo hyrje,

214
00:14:37,640 --> 00:14:43,810
kështu që është një tjetër për lak. Pra, ne kemi tre mbivendosur për sythe, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Rregull. Kjo shkon si një pikë fillimi.

216
00:14:46,560 --> 00:14:53,180
Zgjidhja jonë nuk është më e keqe se n ^ 3.

217
00:14:53,180 --> 00:14:55,480
A të gjithë e kuptojnë zgjidhje shtazë fuqi?

218
00:14:55,480 --> 00:14:59,950
>> Rregull. Një zgjidhje më të mirë është duke përdorur një ide të quajtur programimi dinamik.

219
00:14:59,950 --> 00:15:03,040
Nëse ju merrni CS124, e cila është Algoritmet dhe strukturat të dhënave,

220
00:15:03,040 --> 00:15:05,680
ju do të bëhet shumë i njohur me këtë teknikë.

221
00:15:05,680 --> 00:15:12,190
Dhe ideja është, do të përpiqen për të ndërtuar zgjidhje për problemet më të vogla të parë.

222
00:15:12,190 --> 00:15:17,990
Çfarë dua të them me këtë është, ne aktualisht duhet të shqetësohen për dy gjëra: e fillimit dhe në fund.

223
00:15:17,990 --> 00:15:29,340
Dhe kjo është i bezdisshëm. Çfarë ndodh nëse ne mund të shpëtoj nga një prej këtyre parametrave?

224
00:15:29,340 --> 00:15:32,650
Një ide është që të - we're dhënë problemi ynë origjinal,

225
00:15:32,650 --> 00:15:37,470
gjeni shumën maksimale të çdo subarray në një gamë [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Dhe tani ne kemi një subproblem ri, ku ne e dimë, në indeksin tonë të tanishëm i,

227
00:15:47,400 --> 00:15:52,520
ne e dimë ne duhet të konkludojmë atje. Subarray jonë duhet të përfundojë në indeksin aktual.

228
00:15:52,520 --> 00:15:57,640
Pra, problemi mbetur është, ku ne duhet të fillojë subarray tonë?

229
00:15:57,640 --> 00:16:05,160
A ka kjo kuptim? Rregull.

230
00:16:05,160 --> 00:16:12,030
Kështu që unë kam koduar këtë ide, dhe le të shohim se çfarë kjo do të thotë.

231
00:16:12,030 --> 00:16:16,230
Në codirectory, ka një program të quajtur subarray,

232
00:16:16,230 --> 00:16:19,470
dhe kjo merr numrin e artikujve,

233
00:16:19,470 --> 00:16:25,550
dhe ai kthen shumën maksimale subarray në listën time riorganizoi.

234
00:16:25,550 --> 00:16:29,920
Pra, në këtë rast, subarray tonë maksimal është 3.

235
00:16:29,920 --> 00:16:34,850
Dhe kjo është marrë nga vetëm duke përdorur 2 dhe 1.

236
00:16:34,850 --> 00:16:38,050
Le të drejtuar atë përsëri. Është gjithashtu 3.

237
00:16:38,050 --> 00:16:40,950
Por këtë herë, vini re se si kemi marrë 3.

238
00:16:40,950 --> 00:16:46,690
Ne mori - ne vetëm të marrë 3 vetë

239
00:16:46,690 --> 00:16:49,980
sepse ajo është e rrethuar nga negative në të dyja anët,

240
00:16:49,980 --> 00:16:55,080
e cila do të sjellë një shumë të <3.

241
00:16:55,080 --> 00:16:57,820
Le të kandidojë në 10 objekte.

242
00:16:57,820 --> 00:17:03,200
Këtë herë ajo është 7, ne kemi marrë 3 dhe 4 udhëheqës.

243
00:17:03,200 --> 00:17:09,450
Këtë herë ajo është 8, dhe ne kemi marrë se duke marrë 1, 4 dhe 3.

244
00:17:09,450 --> 00:17:16,310
Pra, për të ju jap një intuitë se si ne mund të zgjidhur këtë problem transformuar,

245
00:17:16,310 --> 00:17:18,890
le të marrin një vështrim në këtë subarray.

246
00:17:18,890 --> 00:17:23,460
Ne jemi duke i dhënë këtë koleksion input, dhe ne e dimë se përgjigja është 8.

247
00:17:23,460 --> 00:17:26,359
Ne kemi marrë 1, 4, dhe 3.

248
00:17:26,359 --> 00:17:29,090
Por le të shohim se si ne fakt mori atë përgjigje.

249
00:17:29,090 --> 00:17:34,160
Le të shikojmë në subarray maksimal që përfundoi në secilin prej këtyre treguesve.

250
00:17:34,160 --> 00:17:40,780
Çfarë është subarray maksimal që duhet të përfundojë në pozitën e parë?

251
00:17:40,780 --> 00:17:46,310
[Student] zero. Zero >>. Vetëm mos të marrë -5.

252
00:17:46,310 --> 00:17:50,210
Këtu ajo do të jetë 0 si. Po?

253
00:17:50,210 --> 00:17:56,470
(, Student i pakuptueshëm)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, më vjen keq, kjo është një -3.

255
00:17:58,960 --> 00:18:03,220
Kështu kjo është një 2, kjo është një -3.

256
00:18:03,220 --> 00:18:08,690
Rregull. Pra -4, çfarë është subarray maksimal për t'i dhënë fund atë pozitë

257
00:18:08,690 --> 00:18:12,910
ku -4 është në? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Tani, unë duhet të përfundojë në vendin ku është në -2.

260
00:18:28,060 --> 00:18:39,330
Kështu 6, 5, 7, dhe e fundit është 4.

261
00:18:39,330 --> 00:18:43,480
Duke ditur se këto janë shënimet e mia

262
00:18:43,480 --> 00:18:48,130
për problemin e transformuar, ku unë duhet të përfundojë në secilin prej këtyre indekseve,

263
00:18:48,130 --> 00:18:51,410
atëherë përgjigjja ime përfundimtare është vetëm, të marrë një spastrim të gjithë,

264
00:18:51,410 --> 00:18:53,580
dhe për të marrë numrin maksimal.

265
00:18:53,580 --> 00:18:55,620
Kështu që në këtë rast është 8.

266
00:18:55,620 --> 00:19:00,010
Kjo nënkupton që subarray maksimal përfundon në këtë indeks,

267
00:19:00,010 --> 00:19:04,970
dhe ka filluar diku para tij.

268
00:19:04,970 --> 00:19:09,630
A të gjithë e kuptojnë këtë subarray transformuar?

269
00:19:09,630 --> 00:19:22,160
>> Rregull. E pra, le të kuptoj se për këtë përsëritje.

270
00:19:22,160 --> 00:19:27,990
Le të konsiderojmë vetëm shënimet e para.

271
00:19:27,990 --> 00:19:35,930
Kështu këtu ajo ishte 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Dhe pastaj ka pasur një -2 këtu, dhe që e solli atë deri në 6.

273
00:19:39,790 --> 00:19:50,800
Pra, nëse unë e quaj hyrja në pozicionin i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
si mund ta përdorin përgjigje për një subproblem mëparshme

275
00:19:54,910 --> 00:19:59,360
për t'iu përgjigjur kësaj subproblem?

276
00:19:59,360 --> 00:20:04,550
Nëse unë të shikoni në, le të themi, kjo hyrje.

277
00:20:04,550 --> 00:20:09,190
Si mund të llogaritin përgjigje 6 duke shikuar në

278
00:20:09,190 --> 00:20:18,780
një kombinim i këtij grup dhe përgjigjet ndaj subproblems mëparshme në këtë grup? Po?

279
00:20:18,780 --> 00:20:22,800
[Student Femër] Ju merrni rrjet të shumave

280
00:20:22,800 --> 00:20:25,430
në pozitë të drejtë para tij, kështu që 8,

281
00:20:25,430 --> 00:20:32,170
dhe pastaj ju shtoni subproblem aktuale.

282
00:20:32,170 --> 00:20:36,460
[Yu] Pra sugjerimi i saj është që të shikojmë në këto dy numra,

283
00:20:36,460 --> 00:20:40,090
ky numër dhe ky numër.

284
00:20:40,090 --> 00:20:50,130
Kështu kjo 8 referohet përgjigjes për subproblem (I - 1).

285
00:20:50,130 --> 00:20:57,300
Dhe le të thërrasë A. array time input

286
00:20:57,300 --> 00:21:01,470
Në mënyrë që të gjeni një subarray maksimal që përfundon në pozitën unë,

287
00:21:01,470 --> 00:21:03,980
Unë kam dy zgjedhje: ose unë mund të vazhdojë subarray

288
00:21:03,980 --> 00:21:09,790
që përfundoi në indeksin e mëparshme, apo të fillojë një koleksion të ri.

289
00:21:09,790 --> 00:21:14,190
Nëse unë do të vazhdojë subarray që filloi në indeksin e mëparshme,

290
00:21:14,190 --> 00:21:19,260
atëherë shuma maksimale që unë mund të arrijë është përgjigje për subproblem mëparshme

291
00:21:19,260 --> 00:21:24,120
plus hyrja aktuale array.

292
00:21:24,120 --> 00:21:27,550
Por, unë gjithashtu kanë zgjedhjen e fillimit të një subarray ri,

293
00:21:27,550 --> 00:21:30,830
në të cilin rast shuma është 0.

294
00:21:30,830 --> 00:21:42,860
Pra përgjigja është max e 0, subproblem i - 1, plus hyrja aktuale array.

295
00:21:42,860 --> 00:21:46,150
Përsëritja e bën këtë kuptim?

296
00:21:46,150 --> 00:21:50,840
Përsëritja jonë, si ne vetëm zbuluar, është i subproblem

297
00:21:50,840 --> 00:21:54,740
është e barabartë me maksimumin e mëparshme subproblem plus hyrje aktual array tim,

298
00:21:54,740 --> 00:22:01,490
që do të thotë të vazhdojë subarray mëparshme,

299
00:22:01,490 --> 00:22:07,250
ose 0, të fillojë një subarray ri në indeksin tim aktual.

300
00:22:07,250 --> 00:22:10,060
Dhe një herë ne kemi ndërtuar këtë tryezë të zgjidhjeve, atëherë përgjigjja jonë përfundimtare,

301
00:22:10,060 --> 00:22:13,950
vetëm të bëjë një spastrim lineare përgjatë array subproblem

302
00:22:13,950 --> 00:22:19,890
dhe për të marrë numrin maksimal.

303
00:22:19,890 --> 00:22:23,330
Kjo është një zbatim i saktë i asaj që unë sapo thashë.

304
00:22:23,330 --> 00:22:27,320
Pra, ne kemi krijuar një koleksion të ri subproblem, subproblems.

305
00:22:27,320 --> 00:22:32,330
Hyrja e parë është ose 0 ose hyrja e parë, maksimale e atyre dyjave.

306
00:22:32,330 --> 00:22:35,670
Dhe për pjesën tjetër të subproblems

307
00:22:35,670 --> 00:22:39,810
ne përdorim përsëritjen e saktë kemi vetëm zbuluar.

308
00:22:39,810 --> 00:22:49,960
Tani kemi llogaritur maksimumin e subproblems array tonë, dhe kjo është përgjigjja jonë përfundimtare.

309
00:22:49,960 --> 00:22:54,130
>> Pra, sa hapësirë ​​jemi duke përdorur në këtë algorithm?

310
00:22:54,130 --> 00:23:01,470
Nëse ju keni marrë vetëm CS50, atëherë ju nuk mund të ketë hapësirë ​​diskutuar shumë.

311
00:23:01,470 --> 00:23:07,750
E pra, një gjë të theksohet është se unë quhet malloc këtu me madhësi n.

312
00:23:07,750 --> 00:23:13,590
Çfarë do të sugjerojnë për ju?

313
00:23:13,590 --> 00:23:17,450
Kjo algorithm përdor hapësirë ​​lineare.

314
00:23:17,450 --> 00:23:21,030
Mund të bëjmë më mirë?

315
00:23:21,030 --> 00:23:30,780
A ka ndonjë gjë që ju vini re se është e panevojshme për të llogaritur përgjigjen përfundimtare?

316
00:23:30,780 --> 00:23:33,290
I guess një pyetje më e mirë është, çfarë informacioni

317
00:23:33,290 --> 00:23:40,680
nuk kemi nevojë për të kryer gjatë gjithë rrugës deri në fund?

318
00:23:40,680 --> 00:23:44,280
Tani, nëse ne shikojmë në këto dy linja,

319
00:23:44,280 --> 00:23:47,720
ne vetëm kujdesen për subproblem mëparshëm,

320
00:23:47,720 --> 00:23:50,910
dhe ne vetëm kujdesen për maksimumin që kemi parë ndonjëherë deri më tani.

321
00:23:50,910 --> 00:23:53,610
Për të llogaritur përgjigjen tonë final, ne nuk kemi nevojë array tërë.

322
00:23:53,610 --> 00:23:57,450
Ne duhet vetëm numrin e fundit, zgjasin dy numra.

323
00:23:57,450 --> 00:24:02,630
Numri i fundit për grup subproblem, dhe numri i fundit për maksimum.

324
00:24:02,630 --> 00:24:07,380
Pra, në fakt, ne mund të bashkohen këto sythe së bashku

325
00:24:07,380 --> 00:24:10,460
dhe shkoni nga hapësira lineare në hapësirë ​​të vazhdueshme.

326
00:24:10,460 --> 00:24:15,830
Shuma aktuale deri më tani, këtu, zëvendëson rolin e subproblem, array tonë subproblem.

327
00:24:15,830 --> 00:24:20,020
Pra shuma aktuale, deri më tani, është përgjigje për subproblem mëparshëm.

328
00:24:20,020 --> 00:24:23,450
Dhe se shuma, deri më tani, merr vendin e max tonë.

329
00:24:23,450 --> 00:24:28,100
Ne llogaritur maksimumin si ne të shkojnë së bashku.

330
00:24:28,100 --> 00:24:30,890
Dhe kështu ne do të shkojmë nga hapësira lineare në hapësirë ​​të vazhdueshme,

331
00:24:30,890 --> 00:24:36,650
dhe ne gjithashtu kemi një zgjidhje për problemin tonë lineare subarray.

332
00:24:36,650 --> 00:24:40,740
>> Këto lloje të pyetjeve që ju do të merrni gjatë një interviste.

333
00:24:40,740 --> 00:24:44,450
Çfarë është kompleksiteti koha, çfarë është kompleksiteti hapësirë?

334
00:24:44,450 --> 00:24:50,600
Ju mund të bëni më mirë? A ka gjëra që janë të panevojshme për të mbajtur rreth?

335
00:24:50,600 --> 00:24:55,270
Unë e bëri këtë për analizat që ju duhet të marrë në tuaj

336
00:24:55,270 --> 00:24:57,400
si ju jeni duke punuar me këto probleme.

337
00:24:57,400 --> 00:25:01,710
Gjithmonë të jetë pyetur veten, "A mund të bëj më mirë?"

338
00:25:01,710 --> 00:25:07,800
Në fakt, mund të bëjmë më mirë se kjo?

339
00:25:07,800 --> 00:25:10,730
Lloj i një pyetje mashtrim. Ju nuk mund të, sepse keni nevojë për të

340
00:25:10,730 --> 00:25:13,590
te pakten lexoni dhëna për problemin.

341
00:25:13,590 --> 00:25:15,570
Pra, fakti që ju duhet të paktën të lexojnë të dhëna të problemit

342
00:25:15,570 --> 00:25:19,580
do të thotë se ju nuk mund të bëni më mirë se koha lineare,

343
00:25:19,580 --> 00:25:22,870
dhe ju nuk mund të bëni më mirë se hapësirë ​​të vazhdueshme.

344
00:25:22,870 --> 00:25:27,060
Pra, kjo është, në fakt, zgjidhja më e mirë për këtë problem.

345
00:25:27,060 --> 00:25:33,040
Pyetje? Rregull.

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

347
00:25:35,190 --> 00:25:38,350
"Duke pasur parasysh një grup i integers N, pozitive, zero, ose negativ,

348
00:25:38,350 --> 00:25:41,680
që përfaqësojnë çmimin e aksioneve gjatë ditëve n,

349
00:25:41,680 --> 00:25:44,080
shkruajnë një funksion për të llogaritur fitimin maksimal që ju mund të bëni

350
00:25:44,080 --> 00:25:49,350
duke qenë se ju blerë dhe shitur saktësisht 1 aksioneve brenda këtyre ditëve n. "

351
00:25:49,350 --> 00:25:51,690
Në thelb, ne duam të blerë të ulët, të shesë të lartë.

352
00:25:51,690 --> 00:25:58,580
Dhe ne duam që të kuptoj se e fitimit më të mirë ne mund të bëjë.

353
00:25:58,580 --> 00:26:11,500
Going back to majë tim, ajo është menjëherë e qartë, përgjigja më e thjeshtë, por është e ngadaltë?

354
00:26:11,500 --> 00:26:17,690
Po? (Student, i pakuptueshëm) >> Po.

355
00:26:17,690 --> 00:26:21,470
Pra, ju do >> të shkoni vetëm dhe pse të shikojmë në çmimet e aksioneve

356
00:26:21,470 --> 00:26:30,550
në çdo pikë në kohë, (pakuptueshëm).

357
00:26:30,550 --> 00:26:33,990
[Yu] Mirë, kështu që zgjidhja e saj - sugjerimin e saj e informatikes

358
00:26:33,990 --> 00:26:37,380
të ulët dhe informatikë të lartë nuk do të punojë

359
00:26:37,380 --> 00:26:42,470
sepse mund të ndodhë para se të më të ulët.

360
00:26:42,470 --> 00:26:47,340
Pra, çfarë është zgjidhja brute force për këtë problem?

361
00:26:47,340 --> 00:26:53,150
Cilat janë dy gjëra që unë duhet të unike të përcaktuar fitimin kam bërë? Drejtë.

362
00:26:53,150 --> 00:26:59,410
Zgjidhja brute force është - oh, kështu që, sugjerimi Gjergjit është që ne duhet vetëm dy ditë

363
00:26:59,410 --> 00:27:02,880
për të përcaktuar unike fitimin e këtyre dy ditëve.

364
00:27:02,880 --> 00:27:06,660
Pra, ne llogaritin çdo palë, si të blerë / shitur,

365
00:27:06,660 --> 00:27:12,850
llogaritur fitimin, i cili mund të jetë pozitiv ose negativ ose zero.

366
00:27:12,850 --> 00:27:18,000
Llogaritur fitimin maksimal që kemi bërë pas iterating mbi të gjitha palë ditë.

367
00:27:18,000 --> 00:27:20,330
Kjo do të jetë përgjigjja jonë përfundimtare.

368
00:27:20,330 --> 00:27:25,730
Dhe se zgjidhja do të jetë në O (n ^ 2), për shkak se ka n zgjedh dy çifte -

369
00:27:25,730 --> 00:27:30,270
e ditëve që ju mund të zgjidhni në mes të ditëve të fundit.

370
00:27:30,270 --> 00:27:32,580
Mirë, kështu që unë nuk jam duke shkuar për të shkuar mbi zgjidhjen e forcës brutale këtu.

371
00:27:32,580 --> 00:27:37,420
Unë jam duke shkuar për të ju them se ka një n log n zgjidhje.

372
00:27:37,420 --> 00:27:45,550
Çfarë algoritmi ju momentalisht e dini se është n log n?

373
00:27:45,550 --> 00:27:50,730
Kjo nuk është një pyetje mashtrim.

374
00:27:50,730 --> 00:27:54,790
>> Merge lloj. Merge lloj është n log n,

375
00:27:54,790 --> 00:27:57,760
dhe në fakt, një mënyrë për të zgjidhur këtë problem është që të përdorin

376
00:27:57,760 --> 00:28:04,400
një lloj lloj bashkojë të idesë quajtur, në përgjithësi, përça dhe sundo.

377
00:28:04,400 --> 00:28:07,570
Dhe ideja është si vijon.

378
00:28:07,570 --> 00:28:12,400
Ju dëshironi për të llogaritur mirë të blej / shitur palë në gjysmën e majtë.

379
00:28:12,400 --> 00:28:16,480
Gjej fitim të mirë që ju mund të bëni, vetëm me n e parë mbi dy ditësh.

380
00:28:16,480 --> 00:28:19,780
Pastaj ju doni të oompute mirë të blej / shitur palë në gjysmën e djathtë,

381
00:28:19,780 --> 00:28:23,930
kështu që n fundit gjatë dy ditëve.

382
00:28:23,930 --> 00:28:32,400
Dhe tani pyetja është, si nuk kemi bashkojë këto zgjidhje përsëri së bashku?

383
00:28:32,400 --> 00:28:36,320
Po? (, Student i pakuptueshëm)

384
00:28:36,320 --> 00:28:49,890
Mirë >>. Pra më lejoni të nxjerrë një foto.

385
00:28:49,890 --> 00:29:03,870
Po? (George, i pakuptueshëm)

386
00:29:03,870 --> 00:29:06,450
Pikërisht >>. Zgjidhja Gjergjit është saktësisht e drejtë.

387
00:29:06,450 --> 00:29:10,040
Pra sugjerimi i tij është, së pari të llogaritur mirë palë Blej / Shes,

388
00:29:10,040 --> 00:29:16,050
dhe që ndodh në gjysmën e majtë, kështu që le ta quajmë se majtë, u largua.

389
00:29:16,050 --> 00:29:20,790
Më të mirë të blerë / shitur palë që ndodh në gjysmën e duhur.

390
00:29:20,790 --> 00:29:25,180
Por në qoftë se ne krahasim me vetëm këto dy numra, ne jemi të humbur rastin

391
00:29:25,180 --> 00:29:30,460
ku kemi blerë dhe shitur këtu diku në gjysmën e duhur.

392
00:29:30,460 --> 00:29:33,810
Ne blerë në gjysmën e majtë, të shitur në gjysmën e duhur.

393
00:29:33,810 --> 00:29:38,490
Dhe mënyra më e mirë për të llogaritur mirë palë Blej / Shes që përfshin të dy gjysmave

394
00:29:38,490 --> 00:29:43,480
është për të llogaritur minimumin këtu dhe llogaritur maksimumin këtu

395
00:29:43,480 --> 00:29:45,580
dhe për të marrë diferencën e tyre.

396
00:29:45,580 --> 00:29:50,850
Kështu të dy rastet ku Blej / Shes palë ndodh vetëm këtu,

397
00:29:50,850 --> 00:30:01,910
vetëm këtu, apo në të dy gjysmave është përcaktuar nga këto tre numra.

398
00:30:01,910 --> 00:30:06,450
Pra algorithm tonë të bashkojë zgjidhjet tona përsëri së bashku,

399
00:30:06,450 --> 00:30:08,350
ne duam të llogaritur mirë palë Blej / Shes

400
00:30:08,350 --> 00:30:13,120
ku kemi blerë në gjysmën e majtë dhe të shitur në gjysmën e djathtë.

401
00:30:13,120 --> 00:30:16,740
Dhe mënyra më e mirë për të bërë këtë është për të llogaritur çmimin më të ulët në gjysmën e parë,

402
00:30:16,740 --> 00:30:20,360
çmimi më i lartë në gjysmën e duhur, dhe për të marrë diferencën e tyre.

403
00:30:20,360 --> 00:30:25,390
Rezultojnë me tre fitimet, këto tre numra, ju merrni maksimumin e tre,

404
00:30:25,390 --> 00:30:32,720
dhe kjo është fitimi më i mirë që ju mund të bëni mbi këto ditët e para dhe në fund.

405
00:30:32,720 --> 00:30:36,940
Këtu linja të rëndësishme janë në të kuqe.

406
00:30:36,940 --> 00:30:41,160
Kjo është një thirrje rekursive për të llogaritur përgjigjen në gjysmën e majtë.

407
00:30:41,160 --> 00:30:44,760
Kjo është një thirrje rekursive për të llogaritur përgjigjen në gjysmën e duhur.

408
00:30:44,760 --> 00:30:50,720
Këto dy sythe për të llogaritur min dhe max në gjysmën e majtë dhe të djathtë, respektivisht.

409
00:30:50,720 --> 00:30:54,970
Tani unë llogaris fitimin që përfshin të dy gjysmave,

410
00:30:54,970 --> 00:31:00,530
dhe përgjigja përfundimtare është maksimumi i këtyre tre.

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

412
00:31:04,120 --> 00:31:06,420
>> Pra, i sigurt, ne kemi një algoritëm, por pyetja e madhe është,

413
00:31:06,420 --> 00:31:08,290
çfarë është kompleksiteti koha e kjo?

414
00:31:08,290 --> 00:31:16,190
Dhe arsyeja pse kam përmendur lloj bashkojë është se kjo formë e ndajnë përgjigje

415
00:31:16,190 --> 00:31:19,200
në dy dhe pastaj bashkimi zgjidhjet tona përsëri së bashku

416
00:31:19,200 --> 00:31:23,580
është pikërisht forma e lloj bashkohen.

417
00:31:23,580 --> 00:31:33,360
Pra më lejoni të shkoj nëpër kohëzgjatje.

418
00:31:33,360 --> 00:31:41,340
Nëse ne definuar një funksion t (n) të jetë numri i hapave

419
00:31:41,340 --> 00:31:50,010
për ditë n,

420
00:31:50,010 --> 00:31:54,350
thirrje dy tona gjithkund rekursive

421
00:31:54,350 --> 00:32:00,460
janë secili do të kushtojë t (n / 2),

422
00:32:00,460 --> 00:32:03,540
dhe ka dy këtyre thirrjeve.

423
00:32:03,540 --> 00:32:10,020
Tani kam nevojë për të llogaritur minimumin e gjysmës së majtë,

424
00:32:10,020 --> 00:32:17,050
që unë mund të bëjë në të n / 2 kohë, plus maksimum prej gjysmës së djathtë.

425
00:32:17,050 --> 00:32:20,820
Pra, kjo është vetëm n.

426
00:32:20,820 --> 00:32:25,050
Dhe pastaj plus disa punë të vazhdueshme.

427
00:32:25,050 --> 00:32:27,770
Dhe ky ekuacion përsëritje

428
00:32:27,770 --> 00:32:35,560
është pikërisht përsëritje ekuacioni për lloj bashkohen.

429
00:32:35,560 --> 00:32:39,170
Dhe ne të gjithë e dimë se lloj bashkojë është log n n kohë.

430
00:32:39,170 --> 00:32:46,880
Prandaj, algorithm tonë është gjithashtu n log n kohë.

431
00:32:46,880 --> 00:32:52,220
A ka kjo përsëritje kuptim?

432
00:32:52,220 --> 00:32:55,780
Vetëm një radhitje të shkurtër të kësaj:

433
00:32:55,780 --> 00:32:59,170
T (n) është numri i hapave për të llogaritur fitimin maksimal

434
00:32:59,170 --> 00:33:02,750
gjatë ditëve n.

435
00:33:02,750 --> 00:33:06,010
Mënyra se si ndahet thirrjet tona gjithkund rekursive

436
00:33:06,010 --> 00:33:11,980
është duke bërë thirrje zgjidhje tonë në ditët e para n / 2,

437
00:33:11,980 --> 00:33:14,490
kështu që është një thirrje,

438
00:33:14,490 --> 00:33:16,940
dhe pastaj ne e quajmë përsëri në gjysmën e dytë.

439
00:33:16,940 --> 00:33:20,440
Pra, kjo është dy telefonata.

440
00:33:20,440 --> 00:33:25,310
Dhe atëherë ne gjejmë një minimum në gjysmën e majtë, të cilat ne mund të bëjmë në kohë lineare,

441
00:33:25,310 --> 00:33:29,010
gjeni maksimumin e gjysmës së djathtë, të cilat ne mund të bëjmë në kohë lineare.

442
00:33:29,010 --> 00:33:31,570
Pra, n / 2 + n / 2 është vetëm n.

443
00:33:31,570 --> 00:33:36,020
Pastaj ne kemi disa punë të vazhdueshme, e cila është bërë si aritmetikë.

444
00:33:36,020 --> 00:33:39,860
Ky ekuacion është pikërisht përsëritje ekuacioni për përsëritje lloj bashkohen.

445
00:33:39,860 --> 00:33:55,490
Prandaj, algorithm tonë riorganizimi është gjithashtu n log n.

446
00:33:55,490 --> 00:33:58,520
Pra, sa hapësirë ​​jemi duke përdorur?

447
00:33:58,520 --> 00:34:04,910
Le të kthehemi në kodin.

448
00:34:04,910 --> 00:34:09,420
>> Një pyetje më e mirë është, sa korniza rafte nuk kemi ndonjëherë kanë në çdo moment të caktuar?

449
00:34:09,420 --> 00:34:11,449
Që ne jemi duke përdorur recursion,

450
00:34:11,449 --> 00:34:23,530
numri i kornizave rafte përcakton përdorimin tonë hapësirë.

451
00:34:23,530 --> 00:34:29,440
Le të konsiderojmë n = 8.

452
00:34:29,440 --> 00:34:36,889
Ne e quajmë riorganizim më 8,

453
00:34:36,889 --> 00:34:41,580
e cila do të thërrasë riorganizimi në katër shënimet e parë,

454
00:34:41,580 --> 00:34:46,250
e cila do të thërrasë një riorganizim në të dy shënimet e para.

455
00:34:46,250 --> 00:34:51,550
Pra, rafte ynë është - kjo është rafte tonë.

456
00:34:51,550 --> 00:34:54,980
Dhe pastaj ne e quajmë riorganizim përsëri në 1,

457
00:34:54,980 --> 00:34:58,070
dhe kjo është ajo që rasti ynë bazë është, kështu që ne të kthehet menjëherë.

458
00:34:58,070 --> 00:35:04,700
A kemi ndonjëherë kanë më shumë se kjo rafte korniza shumë?

459
00:35:04,700 --> 00:35:08,880
Nr Sepse çdo herë që ne bëjmë një risi,

460
00:35:08,880 --> 00:35:10,770
një thirrje e muzës recursive për të riorganizimi,

461
00:35:10,770 --> 00:35:13,950
ne ndarje madhësinë tonë në gjysmën e saj.

462
00:35:13,950 --> 00:35:17,020
Pra, numri maksimal i kornizave rafte ne ndonjëherë kemi në çdo moment të caktuar

463
00:35:17,020 --> 00:35:28,460
është në mënyrë të log n rafte korniza.

464
00:35:28,460 --> 00:35:42,460
Çdo kornizë pirg ka hapësirë ​​të vazhdueshëm,

465
00:35:42,460 --> 00:35:44,410
dhe prandaj shuma e përgjithshme e hapësirës,

466
00:35:44,410 --> 00:35:49,240
shuma maksimale e hapësirës ne ndonjëherë përdorin është O (log n) hapësirë

467
00:35:49,240 --> 00:36:03,040
ku n është numri i ditëve.

468
00:36:03,040 --> 00:36:07,230
>> Tani, gjithmonë të pyesni veten, "A mund të bëjmë më mirë?"

469
00:36:07,230 --> 00:36:12,390
Dhe në veçanti, mund të zvogëlojë këtë për një problem që ne kemi zgjidhur tashmë?

470
00:36:12,390 --> 00:36:20,040
Një aluzion: ne vetëm dy diskutuan probleme të tjera para kësaj, dhe kjo nuk do të jetë riorganizimi.

471
00:36:20,040 --> 00:36:26,200
Ne mund të konvertohet në këtë problem të tregut të aksioneve në problemin subarray maksimal.

472
00:36:26,200 --> 00:36:40,100
Si mund ta bëjë këtë?

473
00:36:40,100 --> 00:36:42,570
Njëri prej jush? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, i pakuptueshëm)

475
00:36:47,680 --> 00:36:53,860
[Yu] Pikërisht.

476
00:36:53,860 --> 00:36:59,940
Pra, problemi maksimal subarray,

477
00:36:59,940 --> 00:37:10,610
ne jemi duke kërkuar për një shumë mbi një subarray vazhdueshme.

478
00:37:10,610 --> 00:37:16,230
Emmy dhe sugjerim për problemin rezervave,

479
00:37:16,230 --> 00:37:30,720
konsideratë ndryshimet, ose deltat.

480
00:37:30,720 --> 00:37:37,440
Dhe një foto e kjo është - kjo është çmimi i një gjendje,

481
00:37:37,440 --> 00:37:42,610
por në qoftë se ne e mori dallimin në mes të çdo dite radhazi -

482
00:37:42,610 --> 00:37:45,200
kështu ne shohim se çmimi maksimal, fitimi maksimal ne mund të bëjë

483
00:37:45,200 --> 00:37:50,070
është nëse kemi blerë këtu dhe shesin këtu.

484
00:37:50,070 --> 00:37:54,240
Por le të shohim në të vazhdueshëm - le të shohim problemin subarray.

485
00:37:54,240 --> 00:38:02,510
Kështu që këtu, ne mund të bëjë - duke shkuar nga këtu për këtu,

486
00:38:02,510 --> 00:38:08,410
ne kemi një ndryshim pozitiv, dhe pastaj duke shkuar nga këtu për këtu kemi një ndryshim negativ.

487
00:38:08,410 --> 00:38:14,220
Por atëherë, duke shkuar nga këtu që këtu kemi një ndryshim të madh pozitiv.

488
00:38:14,220 --> 00:38:20,930
Dhe këto janë ndryshimet që ne duam të përmbledhur për të marrë fitim tonë përfundimtar.

489
00:38:20,930 --> 00:38:25,160
Pastaj kemi ndryshime më negativ këtu.

490
00:38:25,160 --> 00:38:29,990
Çelësi për të zvogëluar problemin e aksioneve në problemin tonë maksimal subarray

491
00:38:29,990 --> 00:38:36,630
është që të marrë në konsideratë deltat mes ditë.

492
00:38:36,630 --> 00:38:40,630
Pra, ne kemi krijuar një koleksion të ri të quajtur Deltat,

493
00:38:40,630 --> 00:38:43,000
nisja hyrjen e parë të jetë 0,

494
00:38:43,000 --> 00:38:46,380
dhe pastaj për secilin delta (I), le që të jetë ndryshimi

495
00:38:46,380 --> 00:38:52,830
i grup im dhëna (I), dhe grup (I - 1).

496
00:38:52,830 --> 00:38:55,530
Pastaj ne e quajmë procedurë rutinë tonë për një subarray maksimal

497
00:38:55,530 --> 00:39:01,500
kalimin në grup një delta-së.

498
00:39:01,500 --> 00:39:06,440
Dhe për shkak se subarray maksimal është koha lineare,

499
00:39:06,440 --> 00:39:09,370
dhe ky reduktim, ky proces i krijimit të kësaj grup delta,

500
00:39:09,370 --> 00:39:11,780
Është gjithashtu koha lineare,

501
00:39:11,780 --> 00:39:19,060
atëherë zgjidhja përfundimtare për rezervat është O (n) plus o puna (n) të punës, është ende O (n) të punës.

502
00:39:19,060 --> 00:39:23,900
Pra, ne kemi një zgjidhje lineare kohë për problemin tonë.

503
00:39:23,900 --> 00:39:29,610
A e kuptojnë të gjithë këtë transformim?

504
00:39:29,610 --> 00:39:32,140
>> Në përgjithësi, një ide e mirë që ju duhet të keni gjithmonë

505
00:39:32,140 --> 00:39:34,290
po përpiqen për të reduktuar një problem të ri që ju jeni duke parë.

506
00:39:34,290 --> 00:39:37,700
Në qoftë se kjo duket e njohur për një problem të vjetër,

507
00:39:37,700 --> 00:39:39,590
përpiqen reduktuar atë në një problem të vjetër.

508
00:39:39,590 --> 00:39:41,950
Dhe në qoftë se ju mund të përdorni të gjitha mjetet që ju keni përdorur në problemin e vjetër

509
00:39:41,950 --> 00:39:46,450
për të zgjidhur problemin e ri.

510
00:39:46,450 --> 00:39:49,010
Pra, për të përfunduar, intervista teknike janë sfiduese.

511
00:39:49,010 --> 00:39:52,280
Këto probleme janë ndoshta disa nga problemet më të vështira

512
00:39:52,280 --> 00:39:54,700
që ju mund të shihni në një intervistë,

513
00:39:54,700 --> 00:39:57,690
kështu që nëse ju nuk e kuptoni të gjitha problemet që kam mbuluar vetëm, kjo është në rregull.

514
00:39:57,690 --> 00:40:01,080
Këto janë disa nga problemet më sfiduese.

515
00:40:01,080 --> 00:40:03,050
Praktikë, praktikë, praktikë.

516
00:40:03,050 --> 00:40:08,170
I dha një shumë problemeve në prospekt, kështu që patjetër të kontrolloni ato jashtë.

517
00:40:08,170 --> 00:40:11,690
Dhe fat të mirë në intervistat tuaja. Të gjitha burimet e mia janë postuar në këtë link,

518
00:40:11,690 --> 00:40:15,220
dhe një nga miqtë e mi të lartë ka ofruar për të bërë intervista tallen teknike,

519
00:40:15,220 --> 00:40:22,050
kështu që nëse ju jeni të interesuar, email Will Yao në atë adresë e-mail.

520
00:40:22,050 --> 00:40:26,070
Nëse keni ndonjë pyetje, ju mund të pyesni mua.

521
00:40:26,070 --> 00:40:28,780
A ju djema keni pyetje specifike në lidhje me intervistat teknike

522
00:40:28,780 --> 00:40:38,440
apo ndonjë problem që ne kemi parë deri më tani?

523
00:40:38,440 --> 00:40:49,910
Rregull. E pra, fat të mirë në intervistat tuaja.

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