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

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

3
00:00:04,630 --> 00:00:08,910
[Acest lucru este CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Max toată lumea, Sunt Kenny. Eu sunt în prezent o stiinta junior calculator studiază.

5
00:00:12,420 --> 00:00:17,310
Sunt un fost CS TF, și am vrut să am asta când am fost un underclassman,

6
00:00:17,310 --> 00:00:19,380
și de aceea am da acest seminar.

7
00:00:19,380 --> 00:00:21,370
Așa că sper să vă placă.

8
00:00:21,370 --> 00:00:23,470
Acest seminar este de aproximativ interviuri tehnice,

9
00:00:23,470 --> 00:00:26,650
și toate resursele mele pot fi găsite la acest link,

10
00:00:26,650 --> 00:00:32,350
această legătură într-aici, un cuplu de resurse.

11
00:00:32,350 --> 00:00:36,550
Așa că am făcut o listă de probleme, de fapt, destul de câteva probleme.

12
00:00:36,550 --> 00:00:40,800
De asemenea, un general resurse pagină unde puteți găsi sfaturi

13
00:00:40,800 --> 00:00:42,870
cu privire la modul de a se pregăti pentru un interviu,

14
00:00:42,870 --> 00:00:46,470
sfaturi cu privire la ce trebuie să faceți în timpul unui interviu real,

15
00:00:46,470 --> 00:00:51,910
precum și modul de abordare a problemelor și a resurselor de referință în viitor.

16
00:00:51,910 --> 00:00:53,980
E totul on-line.

17
00:00:53,980 --> 00:00:58,290
Și doar pentru a prefața acestui seminar, o declarație de renunțare,

18
00:00:58,290 --> 00:01:00,690
ca acest lucru nu ar trebui să - preparatul dumneavoastră interviu

19
00:01:00,690 --> 00:01:02,800
nu ar trebui să fie limitată la această listă.

20
00:01:02,800 --> 00:01:04,750
Acest lucru este menit să fie doar un ghid,

21
00:01:04,750 --> 00:01:08,890
și trebuie să luați cu siguranta tot ceea ce spun, cu un bob de sare,

22
00:01:08,890 --> 00:01:14,620
dar folosesc, de asemenea, tot ce am folosit pentru a te ajuta in pregatirea interviului.

23
00:01:14,620 --> 00:01:16,400
>> Am de gând să accelereze prin următoarele câteva slide-uri

24
00:01:16,400 --> 00:01:18,650
astfel încât să putem ajunge la studii de caz reale.

25
00:01:18,650 --> 00:01:23,630
Structura unui interviu pentru o Dvs. puteti interveni pentru inginerie software,

26
00:01:23,630 --> 00:01:26,320
de obicei, aceasta este de 30 la 45 de minute,

27
00:01:26,320 --> 00:01:29,810
runde multiple, în funcție de companie.

28
00:01:29,810 --> 00:01:33,090
De multe ori veți fi de codare pe o tablă albă.

29
00:01:33,090 --> 00:01:35,960
Deci, o tablă albă ca asta, dar de multe ori pe o scară mai mică.

30
00:01:35,960 --> 00:01:38,540
Dacă aveți un interviu telefonic, veți fi, probabil, folosind

31
00:01:38,540 --> 00:01:44,030
fie collabedit sau un document Google astfel încât să poată vedea trăiți de codificare

32
00:01:44,030 --> 00:01:46,500
în timp ce ești intervievat prin telefon.

33
00:01:46,500 --> 00:01:48,490
Un interviu in sine este de obicei 2 sau 3 probleme

34
00:01:48,490 --> 00:01:50,620
testa cunoștințele de informatică.

35
00:01:50,620 --> 00:01:54,490
Și este aproape sigur va implica codificare.

36
00:01:54,490 --> 00:01:59,540
Tipurile de întrebări pe care le veți vedea, de obicei, sunt structuri de date și algoritmi.

37
00:01:59,540 --> 00:02:02,210
Și făcând aceste tipuri de probleme,

38
00:02:02,210 --> 00:02:07,830
vă vor cere, place, ceea ce este timpul și complexitatea spațiului, Big O?

39
00:02:07,830 --> 00:02:09,800
Adesea, ei cer, de asemenea, de nivel superior întrebări,

40
00:02:09,800 --> 00:02:12,530
astfel, proiectarea unui sistem,

41
00:02:12,530 --> 00:02:14,770
cum ai pune în codul?

42
00:02:14,770 --> 00:02:18,370
Ce interfețe, ce clase, ce module aveți în sistemul dumneavoastră,

43
00:02:18,370 --> 00:02:20,900
și cum acestea interacționează împreună?

44
00:02:20,900 --> 00:02:26,130
Deci, structuri de date și algoritmi, precum și sistemele de proiectare.

45
00:02:26,130 --> 00:02:29,180
>> Câteva sfaturi generale înainte de a ne arunca cu capul în studiile noastre de caz sa.

46
00:02:29,180 --> 00:02:32,300
Cred că cea mai importantă regulă este să fie întotdeauna gândire cu voce tare.

47
00:02:32,300 --> 00:02:36,980
Interviul se presupune a fi sansa ta de a scoate în evidență procesul de gândire.

48
00:02:36,980 --> 00:02:39,820
Punctul de interviu este interviul pentru a măsura

49
00:02:39,820 --> 00:02:42,660
cum crezi si cum te duci printr-o problemă.

50
00:02:42,660 --> 00:02:45,210
Cel mai rau lucru il poti face este să tacă de-a lungul întregului interviu.

51
00:02:45,210 --> 00:02:50,090
Asta e doar nu e bine.

52
00:02:50,090 --> 00:02:53,230
Când vi se administrează o întrebare, de asemenea, doriți să vă asigurați că ați înțeles întrebarea.

53
00:02:53,230 --> 00:02:55,350
Deci, întrebarea se repetă din nou în propriile tale cuvinte

54
00:02:55,350 --> 00:02:58,920
și tentativa de a lucra amănunțite câteva cazuri simple de testare

55
00:02:58,920 --> 00:03:01,530
să vă asigurați că ați înțeles întrebarea.

56
00:03:01,530 --> 00:03:05,510
Lucru printr-o câteva cazuri de testare va oferi, de asemenea o intuiție cu privire la modul de a rezolva această problemă.

57
00:03:05,510 --> 00:03:11,210
S-ar putea descoperi chiar câteva modele pentru a vă ajuta să rezolvați problema.

58
00:03:11,210 --> 00:03:14,500
Sfat lor mare este să nu te frustrat.

59
00:03:14,500 --> 00:03:17,060
Nu te frustrat.

60
00:03:17,060 --> 00:03:19,060
Interviurile sunt provocatoare, dar cel mai rău lucru care le puteți face,

61
00:03:19,060 --> 00:03:23,330
în afară de a fi tăcut, trebuie să fie vizibil frustrat.

62
00:03:23,330 --> 00:03:27,410
Tu nu vrei să dau impresia că la un interviu.

63
00:03:27,410 --> 00:03:33,960
Un lucru pe care îl - atât, mulți oameni, atunci când merg într-un interviu,

64
00:03:33,960 --> 00:03:37,150
ei încearcă să încerce să găsească cea mai bună soluție în primul rând,

65
00:03:37,150 --> 00:03:39,950
când, de fapt, există, de obicei, o soluție flagrant evidentă.

66
00:03:39,950 --> 00:03:43,500
Acesta ar putea fi lent, ar putea fi ineficient, dar tu ar trebui să indice pur și simplu,

67
00:03:43,500 --> 00:03:46,210
doar astfel încât să aveți un punct de pornire de la care să funcționeze mai bine.

68
00:03:46,210 --> 00:03:48,270
De asemenea, subliniind soluția este lent, din punct de vedere

69
00:03:48,270 --> 00:03:52,160
O mare complexitate timp sau spațiu de complexitate,

70
00:03:52,160 --> 00:03:54,450
va demonstra că ați înțeles intervievatorului

71
00:03:54,450 --> 00:03:57,510
aceste aspecte atunci când scrierea de cod.

72
00:03:57,510 --> 00:04:01,440
Deci, nu vă fie teamă de a veni cu cea mai simplă algoritm prima

73
00:04:01,440 --> 00:04:04,950
și de a lucra mai bine, apoi de acolo.

74
00:04:04,950 --> 00:04:09,810
Orice întrebări până acum? Bine.

75
00:04:09,810 --> 00:04:11,650
>> Deci, haideți să se scufunde în problema prima noastră.

76
00:04:11,650 --> 00:04:14,790
"Având în vedere o serie de numere intregi n, scrie o funcție care amesteca matrice

77
00:04:14,790 --> 00:04:20,209
în loc, astfel încât toate permutări ale întregi n sunt la fel de probabil. "

78
00:04:20,209 --> 00:04:23,470
Și presupunem că aveți la dispoziție un generator de număr întreg aleator

79
00:04:23,470 --> 00:04:30,980
care generează un număr întreg într-un interval de la 0 la i, gama de jumătate.

80
00:04:30,980 --> 00:04:32,970
Are toată lumea să înțeleagă această întrebare?

81
00:04:32,970 --> 00:04:39,660
Am să vă dau un tablou de întregi n, și vreau să-l amesteca.

82
00:04:39,660 --> 00:04:46,050
În directorul meu, am scris câteva programe pentru a demonstra ceea ce vreau să spun.

83
00:04:46,050 --> 00:04:48,910
Am de gând să shuffle o serie de 20 de elemente,

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

85
00:04:52,490 --> 00:04:57,050
și vreau să vă scoate o listă ca asta.

86
00:04:57,050 --> 00:05:02,890
Deci, aceasta este matrice mea de intrare sortate, și vreau să-l amesteca.

87
00:05:02,890 --> 00:05:07,070
Noi vom face din nou.

88
00:05:07,070 --> 00:05:13,780
Are toată lumea să înțeleagă întrebarea? Bine.

89
00:05:13,780 --> 00:05:16,730
Deci, este de până la tine.

90
00:05:16,730 --> 00:05:21,220
Care sunt unele idei? Poți să-l faci ca n ^ 2, n n log, n?

91
00:05:21,220 --> 00:05:34,400
Deschis la sugestii.

92
00:05:34,400 --> 00:05:37,730
Bine. Deci o idee, sugerata de Emmy,

93
00:05:37,730 --> 00:05:45,300
este primul calcula un număr aleator, întreg aleatoriu, într-un interval de la 0 la 20.

94
00:05:45,300 --> 00:05:49,840
Deci, presupun gama noastră are o lungime de 20.

95
00:05:49,840 --> 00:05:54,800
În diagrama noastră de 20 de elemente,

96
00:05:54,800 --> 00:05:58,560
aceasta este gama noastră de intrare.

97
00:05:58,560 --> 00:06:04,590
Și acum, sugestia ei este de a crea o matrice nouă,

98
00:06:04,590 --> 00:06:08,440
astfel încât acesta va fi matrice de ieșire.

99
00:06:08,440 --> 00:06:12,880
Și pe baza m-am întors de rand -

100
00:06:12,880 --> 00:06:17,580
așa că, dacă am fost, să zicem, 17,

101
00:06:17,580 --> 00:06:25,640
copiați elementul saptesprezecelea în prima poziție.

102
00:06:25,640 --> 00:06:30,300
Acum, avem nevoie pentru a șterge - avem nevoie pentru a schimba toate elementele aici

103
00:06:30,300 --> 00:06:36,920
peste astfel încât să avem un decalaj de la capăt și nu găuri în mijloc.

104
00:06:36,920 --> 00:06:39,860
Și acum vom repeta procesul.

105
00:06:39,860 --> 00:06:46,360
Acum alegem un întreg nou aleator între 0 și 19.

106
00:06:46,360 --> 00:06:52,510
Avem un nou aici i, iar noi să copiați acest element în această poziție.

107
00:06:52,510 --> 00:07:00,960
Apoi ne-am schimba elementele de peste si am repeta procesul până când vom avea noastră gamă completă nouă.

108
00:07:00,960 --> 00:07:05,890
Care este timpul de funcționare al acestui algoritm?

109
00:07:05,890 --> 00:07:08,110
Ei bine, hai să ia în considerare impactul de acest lucru.

110
00:07:08,110 --> 00:07:10,380
Suntem schimbă fiecare element.

111
00:07:10,380 --> 00:07:16,800
Când ne-am eliminarea acestei i, suntem schimbă toate elementele după ce la stânga.

112
00:07:16,800 --> 00:07:21,600
Și acesta este un O (n) costul

113
00:07:21,600 --> 00:07:26,100
pentru că ceea ce dacă am elimina primul element?

114
00:07:26,100 --> 00:07:29,670
Deci, pentru fiecare eliminare, vom elimina -

115
00:07:29,670 --> 00:07:32,170
fiecare îndepărtare își asumă O (n) operarea,

116
00:07:32,170 --> 00:07:41,520
și din moment ce ne-am n mutări, acest lucru duce la un O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Bine. Atât de bun început. Bun început.

118
00:07:49,550 --> 00:07:55,290
>> O altă sugestie este de a folosi ceva cunoscut sub numele de shuffle Knuth,

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

120
00:07:57,540 --> 00:07:59,630
Și e de fapt un shuffle timp liniar.

121
00:07:59,630 --> 00:08:02,200
Și ideea este foarte asemănătoare.

122
00:08:02,200 --> 00:08:05,160
Din nou, avem gama noastră de intrare,

123
00:08:05,160 --> 00:08:08,580
dar în loc de a folosi două matrice de intrare noastră / ieșire,

124
00:08:08,580 --> 00:08:13,590
vom folosi prima parte a matrice pentru a urmări partea noastră amestecate,

125
00:08:13,590 --> 00:08:18,400
și noi urmări, iar apoi vom lăsa restul de matrice noastre pentru porțiunea unshuffled.

126
00:08:18,400 --> 00:08:24,330
Deci, aici e ceea ce vreau să spun. Vom începe cu - vom alege un i,

127
00:08:24,330 --> 00:08:30,910
o matrice 0 la 20.

128
00:08:30,910 --> 00:08:36,150
Indicatorul noastră actuală este orientată spre primul indice.

129
00:08:36,150 --> 00:08:39,590
Am ales pentru unii aici i

130
00:08:39,590 --> 00:08:42,740
iar acum suntem schimb.

131
00:08:42,740 --> 00:08:47,690
Deci, în cazul în care aceasta a fost de 5 și acest lucru a fost de 4,

132
00:08:47,690 --> 00:08:57,150
matrice rezultat va avea 5 aici și 4 aici.

133
00:08:57,150 --> 00:09:00,390
Și acum am observat un marker aici.

134
00:09:00,390 --> 00:09:05,770
Totul la stânga este amestecat,

135
00:09:05,770 --> 00:09:15,160
și totul a dreapta este unshuffled.

136
00:09:15,160 --> 00:09:17,260
Și acum putem repeta procesul.

137
00:09:17,260 --> 00:09:25,210
Am alege un indice aleator între 1 și 20 acum.

138
00:09:25,210 --> 00:09:30,650
Presupun că așa noul nostru i este aici.

139
00:09:30,650 --> 00:09:39,370
Acum ne-am schimba această nouă poziție nostru curentă aici.

140
00:09:39,370 --> 00:09:44,790
Deci, ce facem o pompare înainte și înapoi ca aceasta.

141
00:09:44,790 --> 00:09:51,630
Lasă-mă să aduc codul pentru a face mai concret.

142
00:09:51,630 --> 00:09:55,290
Vom începe cu alegerea noastră de I -

143
00:09:55,290 --> 00:09:58,370
vom începe cu i egal cu 0, alegem o locație aleatorie j

144
00:09:58,370 --> 00:10:02,420
în partea unshuffled de matrice, i la n-1.

145
00:10:02,420 --> 00:10:07,280
Deci, dacă eu sunt aici, pentru a alege un indice aleator între aici și restul de matrice,

146
00:10:07,280 --> 00:10:12,410
și am schimba.

147
00:10:12,410 --> 00:10:17,550
Acest lucru este necesar pentru a amesteca codul matrice dumneavoastră.

148
00:10:17,550 --> 00:10:21,670
Alte întrebări?

149
00:10:21,670 --> 00:10:25,530
>> Ei bine, o nevoie de întrebare este, de ce este asta corect?

150
00:10:25,530 --> 00:10:28,360
De ce este la fel de probabil ca fiecare permutare?

151
00:10:28,360 --> 00:10:30,410
Și nu va trece prin dovada de acest lucru,

152
00:10:30,410 --> 00:10:35,970
dar multe probleme din domeniul științei calculator poate fi dovedit prin inducție.

153
00:10:35,970 --> 00:10:38,520
Câți dintre voi sunt familiarizați cu inducție?

154
00:10:38,520 --> 00:10:40,590
Bine. Mișto.

155
00:10:40,590 --> 00:10:43,610
Astfel încât să puteți dovedi corectitudinea acestui algoritm simplu prin inducție,

156
00:10:43,610 --> 00:10:49,540
în cazul în care ipoteza de inducție ta ar fi, presupune că

157
00:10:49,540 --> 00:10:53,290
Shuffle mea returnează fiecare permutare la fel de probabil

158
00:10:53,290 --> 00:10:56,120
până la primele elemente i.

159
00:10:56,120 --> 00:10:58,300
Acum, ia în considerare i + 1.

160
00:10:58,300 --> 00:11:02,550
Și de modul în care ne alege j noastră index swap,

161
00:11:02,550 --> 00:11:05,230
acest lucru duce la - si apoi lucrezi la detalii,

162
00:11:05,230 --> 00:11:07,390
cel puțin o dovadă completă a acestui algoritm ce revine

163
00:11:07,390 --> 00:11:12,800
fiecare permutare cu probabilitate la fel de probabil.

164
00:11:12,800 --> 00:11:15,940
>> În regulă, următorul problema.

165
00:11:15,940 --> 00:11:19,170
Deci, "având în vedere o serie de numere intregi, pozitiva, zero, negativ,

166
00:11:19,170 --> 00:11:21,290
scrie o funcție care calculează suma maximă

167
00:11:21,290 --> 00:11:24,720
cu privire la orice subarray continueous de matrice de intrare. "

168
00:11:24,720 --> 00:11:28,370
Un exemplu aici este, în cazul în care toate numerele sunt pozitive,

169
00:11:28,370 --> 00:11:31,320
atunci în prezent cea mai bună alegere este de a lua întreaga gamă.

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

171
00:11:34,690 --> 00:11:36,780
Când aveți unele negative acolo,

172
00:11:36,780 --> 00:11:38,690
în acest caz, vrem doar primele două

173
00:11:38,690 --> 00:11:44,590
deoarece alegerea -1 și / sau -3 va aduce suma intre nostru în jos.

174
00:11:44,590 --> 00:11:48,120
Uneori am putea avea să înceapă în mijlocul matrice.

175
00:11:48,120 --> 00:11:53,500
Uneori vrem să aleagă nimic, la toate, cel mai bine este să nu ia nimic.

176
00:11:53,500 --> 00:11:56,490
Și uneori e mai bine să ia toamna,

177
00:11:56,490 --> 00:12:07,510
deoarece lucrul după ce este super mare. Deci, orice idei?

178
00:12:07,510 --> 00:12:10,970
(Student, neinteligibil) >> Da.

179
00:12:10,970 --> 00:12:13,560
Să presupunem că eu nu iau -1.

180
00:12:13,560 --> 00:12:16,170
Apoi, fie aleg 1000 și 20.000,

181
00:12:16,170 --> 00:12:18,630
sau aleg doar de 3 miliarde de euro.

182
00:12:18,630 --> 00:12:20,760
Ei bine, cea mai bună alegere este de a lua toate numerele.

183
00:12:20,760 --> 00:12:24,350
Acest -1, în ciuda fiind negativ,

184
00:12:24,350 --> 00:12:31,340
întreaga sumă este mai bun decât au fost nu de a lua -1.

185
00:12:31,340 --> 00:12:36,460
Deci unul dintre sfaturile le-am menționat mai devreme a fost să indice în mod clar evidente

186
00:12:36,460 --> 00:12:40,540
și soluția brute force primul.

187
00:12:40,540 --> 00:12:44,340
Care este soluția forta bruta în această problemă? Da?

188
00:12:44,340 --> 00:12:46,890
[Jane] Ei bine, eu cred că soluția brute force

189
00:12:46,890 --> 00:12:52,600
ar fi să aduni toate combinațiile posibile (neinteligibil).

190
00:12:52,600 --> 00:12:58,250
[Yu] Ok. Deci, ideea lui Jane este de a lua orice este posibil -

191
00:12:58,250 --> 00:13:01,470
Sunt parafrazarea - este de a lua orice subarray posibil, continuă,

192
00:13:01,470 --> 00:13:07,840
calcula suma intre ei, și apoi să ia maximă a tuturor subarrays posibile continue.

193
00:13:07,840 --> 00:13:13,310
Ce identifică în mod unic o matrice de intrare în subarray meu?

194
00:13:13,310 --> 00:13:17,380
Ca, ce două lucruri am nevoie? Da?

195
00:13:17,380 --> 00:13:19,970
(Student, neinteligibil) >> dreapta.

196
00:13:19,970 --> 00:13:22,130
O limită inferioară pe indicele și un indice de limita superioară

197
00:13:22,130 --> 00:13:28,300
determină în mod unic un subarray continuu.

198
00:13:28,300 --> 00:13:31,400
[Elev Femeie] Ne-am estimare este o serie de numere unice?

199
00:13:31,400 --> 00:13:34,280
[Yu] Nr Deci, întrebarea ei este, suntem presupunând gama noastră -

200
00:13:34,280 --> 00:13:39,000
este gama noastră toate numerele unice, iar răspunsul este nu.

201
00:13:39,000 --> 00:13:43,390
>> Dacă vom folosi soluția noastră forta bruta, apoi indicii de începere / terminare

202
00:13:43,390 --> 00:13:47,200
unic determină subarray nostru continuu.

203
00:13:47,200 --> 00:13:51,680
Deci, dacă am repeta pentru toate intrările de pornire posibile,

204
00:13:51,680 --> 00:13:58,320
și pentru toate intrările end> ​​sau = pentru a începe, și <n,

205
00:13:58,320 --> 00:14:05,570
vă calcula suma intre, iar apoi vom lua suma maximă care le-am văzut până acum.

206
00:14:05,570 --> 00:14:07,880
Este clar acest lucru?

207
00:14:07,880 --> 00:14:12,230
Care este O mare de această soluție?

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

209
00:14:16,660 --> 00:14:18,860
Nu este destul de n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Rețineți că itera de la 0 la n,

211
00:14:25,250 --> 00:14:27,520
asa ca asta e unul pentru buclă.

212
00:14:27,520 --> 00:14:35,120
Am itera din nou de la aproape început până la sfârșit, o altă buclă pentru.

213
00:14:35,120 --> 00:14:37,640
Și acum, în termen de faptul că, trebuie să ne rezuma la fiecare intrare,

214
00:14:37,640 --> 00:14:43,810
asa ca asta e alta pentru buclă. Deci, avem trei imbricate pentru bucle, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Bine. Acest lucru este valabil ca un punct de plecare.

216
00:14:46,560 --> 00:14:53,180
Soluția noastră este mai rău decât n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Are toată lumea înțelege soluția forta bruta?

218
00:14:55,480 --> 00:14:59,950
>> Bine. O soluție mai bună este o idee folosind numit de programare dinamică.

219
00:14:59,950 --> 00:15:03,040
Dacă luați CS124, care este Algoritmi si Structuri de date,

220
00:15:03,040 --> 00:15:05,680
vei deveni foarte familiarizat cu aceasta tehnica.

221
00:15:05,680 --> 00:15:12,190
Iar ideea este, încercați să construiască soluții la problemele mai mici.

222
00:15:12,190 --> 00:15:17,990
Ce vreau să spun prin asta este, avem în prezent trebuie să vă faceți griji despre două lucruri: de început și de sfârșit.

223
00:15:17,990 --> 00:15:29,340
Și asta e enervant. Ce se întâmplă dacă am putea scăpa de una dintre aceste parametri?

224
00:15:29,340 --> 00:15:32,650
O idee este de a - Suntem dat problema noastră inițială,

225
00:15:32,650 --> 00:15:37,470
găsi suma maximă a oricărei subarray într-un interval [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Și acum avem o nouă subproblem, în cazul în care știm, în indexul nostru curent I,

227
00:15:47,400 --> 00:15:52,520
noi știm că trebuie să încheie acolo. Subarray noastră trebuie să se încheie la indexul curent.

228
00:15:52,520 --> 00:15:57,640
Deci, problema rămasă este, în cazul în care ar trebui să începem subarray nostru?

229
00:15:57,640 --> 00:16:05,160
Are acest sens? Bine.

230
00:16:05,160 --> 00:16:12,030
Așa că m-am codat asta, și să ne uităm la ceea ce înseamnă acest lucru.

231
00:16:12,030 --> 00:16:16,230
În codirectory, există un program numit subarray,

232
00:16:16,230 --> 00:16:19,470
și este nevoie de numărul de articole,

233
00:16:19,470 --> 00:16:25,550
și returnează suma intre subarray maximă în lista mea de amestecat.

234
00:16:25,550 --> 00:16:29,920
Deci, în acest caz, subarray nostru maximă este de 3.

235
00:16:29,920 --> 00:16:34,850
Și asta a luat prin utilizarea doar 2 și 1.

236
00:16:34,850 --> 00:16:38,050
Să-l rula din nou. Este, de asemenea 3.

237
00:16:38,050 --> 00:16:40,950
Dar de data asta, notati cum am ajuns 3.

238
00:16:40,950 --> 00:16:46,690
Am luat - am lua doar 3 sine

239
00:16:46,690 --> 00:16:49,980
pentru ca este inconjurata de negative pe ambele fețe,

240
00:16:49,980 --> 00:16:55,080
care va aduce o suma <3.

241
00:16:55,080 --> 00:16:57,820
Să rula pe 10 elemente.

242
00:16:57,820 --> 00:17:03,200
De data aceasta e 7, luăm de conducere 3 și 4.

243
00:17:03,200 --> 00:17:09,450
De data aceasta este 8, și obținem că prin luarea de 1, 4 și 3.

244
00:17:09,450 --> 00:17:16,310
Deci, pentru a vă oferi o intuiție despre cum putem rezolva această problemă transformat,

245
00:17:16,310 --> 00:17:18,890
Să aruncăm o privire la acest subarray.

246
00:17:18,890 --> 00:17:23,460
Suntem dată fiind această matrice de intrare, și știm răspunsul este 8.

247
00:17:23,460 --> 00:17:26,359
Ne ia 1, 4, și 3.

248
00:17:26,359 --> 00:17:29,090
Dar să ne uităm la modul în care am ajuns de fapt, acest răspuns.

249
00:17:29,090 --> 00:17:34,160
Să ne uităm la subarray maximă care sa încheiat la fiecare dintre aceste indicii.

250
00:17:34,160 --> 00:17:40,780
Care e subarray maximă care trebuie să se încheie la prima poziție?

251
00:17:40,780 --> 00:17:46,310
[Student] Zero. Zero >>. Doar nu iau -5.

252
00:17:46,310 --> 00:17:50,210
Aici va fi 0, de asemenea. Da?

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

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, îmi pare rău, acesta este un -3.

255
00:17:58,960 --> 00:18:03,220
Deci, aceasta este o 2, aceasta este o -3.

256
00:18:03,220 --> 00:18:08,690
Bine. Deci -4, ceea ce e subarray maximă pentru a termina această poziție

257
00:18:08,690 --> 00:18:12,910
în cazul în care este la -4? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Acum, trebuie să se încheie la locul unde este la -2.

260
00:18:28,060 --> 00:18:39,330
Deci 6, 5, 7, iar ultima este de 4.

261
00:18:39,330 --> 00:18:43,480
Știind că acestea sunt intrări mele

262
00:18:43,480 --> 00:18:48,130
pentru problema transformat în cazul în care trebuie să se încheie la fiecare dintre aceste indici,

263
00:18:48,130 --> 00:18:51,410
atunci răspunsul meu final este doar, să ia o matura peste,

264
00:18:51,410 --> 00:18:53,580
și să ia numărul maxim.

265
00:18:53,580 --> 00:18:55,620
Deci, în acest caz, e 8.

266
00:18:55,620 --> 00:19:00,010
Acest lucru implică faptul că subarray maximă se termină la acest indice,

267
00:19:00,010 --> 00:19:04,970
și a început undeva în fața sa.

268
00:19:04,970 --> 00:19:09,630
Are toată lumea să înțeleagă asta subarray transformat?

269
00:19:09,630 --> 00:19:22,160
>> Bine. Ei bine, hai să dau seama recurență pentru acest lucru.

270
00:19:22,160 --> 00:19:27,990
Să ia în considerare doar primele câteva intrări.

271
00:19:27,990 --> 00:19:35,930
Deci, aici a fost de 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Și apoi a fost o -2 aici, și că a adus în jos la 6.

273
00:19:39,790 --> 00:19:50,800
Deci, dacă am apela intrarea la pozitia i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
cum pot folosi răspunsul la o subproblem anterioară

275
00:19:54,910 --> 00:19:59,360
pentru a răspunde la această subproblem?

276
00:19:59,360 --> 00:20:04,550
Dacă mă uit la, să spunem, această intrare.

277
00:20:04,550 --> 00:20:09,190
Cum pot calcula răspunsul 6 uitandu-se la

278
00:20:09,190 --> 00:20:18,780
o combinație a acestei matrice și răspunsuri la subprobleme anterioare din acest tablou? Da?

279
00:20:18,780 --> 00:20:22,800
[Elev Femeie] Tu iei matrice sumelor

280
00:20:22,800 --> 00:20:25,430
în poziția corectă în fața sa, astfel încât 8,

281
00:20:25,430 --> 00:20:32,170
și apoi adăugați subproblem curent.

282
00:20:32,170 --> 00:20:36,460
[Yu] Deci sugestia ei este să se uite la aceste două numere,

283
00:20:36,460 --> 00:20:40,090
acest număr și acest număr.

284
00:20:40,090 --> 00:20:50,130
Deci, acest 8 se referă la răspunsul pentru subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
Și să numim A. meu matrice de intrare

286
00:20:57,300 --> 00:21:01,470
În scopul de a găsi un subarray maximă care se termină la poziția i,

287
00:21:01,470 --> 00:21:03,980
Am două opțiuni: pot continua, fie subarray

288
00:21:03,980 --> 00:21:09,790
care a pus capăt la indexul anterior, sau de a începe o nouă matrice.

289
00:21:09,790 --> 00:21:14,190
Dacă ar fi să continue subarray care a început la indicele precedent,

290
00:21:14,190 --> 00:21:19,260
atunci suma maximă pot atinge este răspunsul la subproblem precedentă

291
00:21:19,260 --> 00:21:24,120
plus de intrare matrice curent.

292
00:21:24,120 --> 00:21:27,550
Dar, am, de asemenea, alegerea de a începe o nouă subarray,

293
00:21:27,550 --> 00:21:30,830
caz în care suma este 0.

294
00:21:30,830 --> 00:21:42,860
Deci, răspunsul este maxim la 0, subproblem I - 1, plus intrarea matrice curent.

295
00:21:42,860 --> 00:21:46,150
Are această recurență sens?

296
00:21:46,150 --> 00:21:50,840
Recurență noastră, așa cum tocmai am descoperit, este subproblem i

297
00:21:50,840 --> 00:21:54,740
este egală cu valoarea maximă a subproblem anterior, plus intrarea mea matrice curent,

298
00:21:54,740 --> 00:22:01,490
ceea ce înseamnă continua subarray precedent,

299
00:22:01,490 --> 00:22:07,250
sau 0, începe o nouă subarray la indexul meu curent.

300
00:22:07,250 --> 00:22:10,060
Și odată ce ne-am construit acest tabel de soluții, atunci raspunsul nostru final,

301
00:22:10,060 --> 00:22:13,950
face doar o matura liniar peste matrice subproblem

302
00:22:13,950 --> 00:22:19,890
și să ia numărul maxim.

303
00:22:19,890 --> 00:22:23,330
Aceasta este o punere în aplicare exactă a ceea ce tocmai am spus.

304
00:22:23,330 --> 00:22:27,320
Deci, vom crea o matrice subproblem nou, subprobleme.

305
00:22:27,320 --> 00:22:32,330
Prima intrare este fie 0 sau prima intrare, maxim de cei doi.

306
00:22:32,330 --> 00:22:35,670
Și pentru restul subprobleme

307
00:22:35,670 --> 00:22:39,810
vom folosi repetarea exactă tocmai l-am descoperit.

308
00:22:39,810 --> 00:22:49,960
Acum am calcula maxim de gama noastră subprobleme, și asta e raspunsul nostru final.

309
00:22:49,960 --> 00:22:54,130
>> Deci, cât de mult spațiu suntem folosind în acest algoritm?

310
00:22:54,130 --> 00:23:01,470
Dacă ați luat doar CS50, atunci nu s-ar fi discutat foarte mult spatiu.

311
00:23:01,470 --> 00:23:07,750
Ei bine, un lucru de remarcat este faptul că i-am sunat malloc aici cu n dimensiuni.

312
00:23:07,750 --> 00:23:13,590
Ce înseamnă acest sugeram dumneavoastra?

313
00:23:13,590 --> 00:23:17,450
Acest algoritm folosește spațiu liniar.

314
00:23:17,450 --> 00:23:21,030
Putem face mai bine?

315
00:23:21,030 --> 00:23:30,780
Este ceva care observați că nu este necesară pentru a calcula raspunsul final?

316
00:23:30,780 --> 00:23:33,290
Cred că o întrebare mai bună este, ce informații

317
00:23:33,290 --> 00:23:40,680
nu avem nevoie pentru a transporta tot drumul până la capăt?

318
00:23:40,680 --> 00:23:44,280
Acum, dacă ne uităm la aceste două linii,

319
00:23:44,280 --> 00:23:47,720
ne pasă doar despre subproblem precedent,

320
00:23:47,720 --> 00:23:50,910
și ne pasă doar de maxim care l-am văzut până acum.

321
00:23:50,910 --> 00:23:53,610
Pentru a calcula răspunsul nostru final, nu avem nevoie de matrice întreaga.

322
00:23:53,610 --> 00:23:57,450
Avem nevoie doar de ultimul număr, în ultimele două numere.

323
00:23:57,450 --> 00:24:02,630
Ultimul numar de matrice subproblem, și ultimul număr de maxim.

324
00:24:02,630 --> 00:24:07,380
Deci, de fapt, putem fuziona aceste bucle, împreună

325
00:24:07,380 --> 00:24:10,460
și du-te din spațiu liniar în spațiu constantă.

326
00:24:10,460 --> 00:24:15,830
Suma curent până în prezent, aici, inlocuieste rolul subproblem, gama noastră subproblem.

327
00:24:15,830 --> 00:24:20,020
Deci suma actuală, până în prezent, este răspunsul la subproblem precedent.

328
00:24:20,020 --> 00:24:23,450
Și această sumă, până în prezent, are loc de max noastre.

329
00:24:23,450 --> 00:24:28,100
Noi calcula maximă mergem de-a lungul.

330
00:24:28,100 --> 00:24:30,890
Și așa vom merge din spațiu liniar în spațiu constantă,

331
00:24:30,890 --> 00:24:36,650
și avem, de asemenea, o soluție la problema liniar subarray nostru.

332
00:24:36,650 --> 00:24:40,740
>> Aceste tipuri de întrebări pe care le va primi in timpul unui interviu.

333
00:24:40,740 --> 00:24:44,450
Care este complexitatea timp, ceea ce este complexitatea spațiu?

334
00:24:44,450 --> 00:24:50,600
Poți să o faceți mai bine? Există lucruri care nu sunt necesare pentru a menține în jurul valorii de?

335
00:24:50,600 --> 00:24:55,270
Am făcut acest lucru pentru a evidenția analizele pe care ar trebui să ia pe cont propriu

336
00:24:55,270 --> 00:24:57,400
cum lucrați prin aceste probleme.

337
00:24:57,400 --> 00:25:01,710
Întotdeauna fi te intrebi, "Pot să fac mai bine?"

338
00:25:01,710 --> 00:25:07,800
De fapt, am putea face mai bine decât asta?

339
00:25:07,800 --> 00:25:10,730
Un fel de întrebare capcană. Tu nu poți, pentru că aveți nevoie să

340
00:25:10,730 --> 00:25:13,590
cel puțin citit de intrare la problema.

341
00:25:13,590 --> 00:25:15,570
Deci, faptul că trebuie să citească, cel puțin de intrare la problema

342
00:25:15,570 --> 00:25:19,580
înseamnă că nu puteți face mai bine decât timpul linear,

343
00:25:19,580 --> 00:25:22,870
și nu se poate face mai bine decât spațiul constanta.

344
00:25:22,870 --> 00:25:27,060
Deci, aceasta este, de fapt, cea mai bună soluție pentru această problemă.

345
00:25:27,060 --> 00:25:33,040
Întrebări? Bine.

346
00:25:33,040 --> 00:25:35,190
>> Stocul de piață problema:

347
00:25:35,190 --> 00:25:38,350
"Având în vedere o serie de numere intregi n, pozitiv, zero, sau negativ,

348
00:25:38,350 --> 00:25:41,680
care reprezintă prețul unui stoc de peste zi n,

349
00:25:41,680 --> 00:25:44,080
scrie o funcție pentru a calcula profitul maxim pe care îl poate face

350
00:25:44,080 --> 00:25:49,350
dat fiind faptul că ați cumpăra și vinde exact 1 stoc în aceste zile n ".

351
00:25:49,350 --> 00:25:51,690
În esență, dorim sa cumparam ieftin, vinzi scump.

352
00:25:51,690 --> 00:25:58,580
Și vrem să aflăm mai bun profitul putem face.

353
00:25:58,580 --> 00:26:11,500
Revenind la vârful meu, ceea ce este imediat clar, mai simplu raspuns, dar e lent?

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

355
00:26:17,690 --> 00:26:21,470
Deci, v-ar >> du-te si uita-te la, deși prețurile în stoc

356
00:26:21,470 --> 00:26:30,550
la fiecare punct din timp, (neinteligibil).

357
00:26:30,550 --> 00:26:33,990
[Yu] Ok, deci o soluție - sugestia ei de calcul

358
00:26:33,990 --> 00:26:37,380
Cel mai mic și cel mai mare calcul nu funcționează în mod necesar

359
00:26:37,380 --> 00:26:42,470
deoarece cea mai mare s-ar putea să apară înainte de cea mai mică.

360
00:26:42,470 --> 00:26:47,340
Deci, ce este soluția brute force la această problemă?

361
00:26:47,340 --> 00:26:53,150
Care sunt cele două lucruri pe care am nevoie pentru a determina în mod unic profitul fac? Corect.

362
00:26:53,150 --> 00:26:59,410
Soluția este forta bruta - oh, deci, sugestia lui George este avem nevoie doar de două zile

363
00:26:59,410 --> 00:27:02,880
pentru a determina în mod unic de profit a acestor două zile.

364
00:27:02,880 --> 00:27:06,660
Așa că am calcula fiecare pereche, ca cumpara / vinde,

365
00:27:06,660 --> 00:27:12,850
calcula profitul, care ar putea fi negativ sau pozitiv sau zero.

366
00:27:12,850 --> 00:27:18,000
Calculați profitul maxim pe care o facem după iterarea peste toate perechile de zile.

367
00:27:18,000 --> 00:27:20,330
Care va fi răspunsul nostru final.

368
00:27:20,330 --> 00:27:25,730
Și că această soluție va fi O (n ^ 2), deoarece nu există n alege două perechi -

369
00:27:25,730 --> 00:27:30,270
de zile în care se poate alege între zi finali.

370
00:27:30,270 --> 00:27:32,580
Ok, deci nu am de gând să merg peste soluția brute force aici.

371
00:27:32,580 --> 00:27:37,420
Am de gând să vă spun că există o soluție n log n.

372
00:27:37,420 --> 00:27:45,550
Ce părere aveți algoritm în prezent, știi că este n log n?

373
00:27:45,550 --> 00:27:50,730
Nu este o întrebare capcană.

374
00:27:50,730 --> 00:27:54,790
>> Merge sortare. Merge fel este n log n,

375
00:27:54,790 --> 00:27:57,760
și, de fapt, o modalitate de a rezolva această problemă este de a utiliza

376
00:27:57,760 --> 00:28:04,400
un fel de idee fel îmbinare numit, în general, dezbina si cucereste.

377
00:28:04,400 --> 00:28:07,570
Iar ideea este după cum urmează.

378
00:28:07,570 --> 00:28:12,400
Vrei pentru a calcula cel mai bun cumpărare / vânzare pereche în jumătatea stângă.

379
00:28:12,400 --> 00:28:16,480
Gasesti cel mai bun profitul puteti face, doar cu n primul pe parcursul a două zile.

380
00:28:16,480 --> 00:28:19,780
Apoi doriți să oompute cel mai bun cumpărare / vânzare pereche pe jumătatea din dreapta,

381
00:28:19,780 --> 00:28:23,930
deci n ultimul timp de două zile.

382
00:28:23,930 --> 00:28:32,400
Și acum întrebarea este, cum ne uni aceste soluții din nou împreună?

383
00:28:32,400 --> 00:28:36,320
Da? (Student, neinteligibil)

384
00:28:36,320 --> 00:28:49,890
Bine >>. Așa că lasă-mă să deseneze o imagine.

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

386
00:29:03,870 --> 00:29:06,450
Exact >>. Soluția lui George este exact dreptate.

387
00:29:06,450 --> 00:29:10,040
Deci sugestia lui este, cel mai bun calcula prima cumpărare / vânzare pereche,

388
00:29:10,040 --> 00:29:16,050
și care are loc în jumătatea stângă, așa că hai să numesc asta stânga, stânga.

389
00:29:16,050 --> 00:29:20,790
Cel mai bun cumpara / vinde pereche care are loc în jumătatea din dreapta.

390
00:29:20,790 --> 00:29:25,180
Dar dacă ne-am comparat doar aceste două numere, ne lipsește cazul

391
00:29:25,180 --> 00:29:30,460
în cazul în care vom cumpăra și vinde aici, undeva în jumătatea din dreapta.

392
00:29:30,460 --> 00:29:33,810
Cumparam în jumătatea stângă, vinde în jumătatea din dreapta.

393
00:29:33,810 --> 00:29:38,490
Și cel mai bun mod de a calcula cel mai bun cumpara / vinde pereche care se întinde pe ambele jumatati

394
00:29:38,490 --> 00:29:43,480
este de a calcula minim aici și calcula maxim aici

395
00:29:43,480 --> 00:29:45,580
și să ia diferența lor.

396
00:29:45,580 --> 00:29:50,850
Deci, cele două cazuri în care perechea cumpărare / vânzare are loc numai aici,

397
00:29:50,850 --> 00:30:01,910
numai aici, sau pe ambele jumatati este definit de aceste trei numere.

398
00:30:01,910 --> 00:30:06,450
Deci, algoritmul nostru pentru a intra soluțiile noastre înapoi împreună,

399
00:30:06,450 --> 00:30:08,350
vrem să calculăm cel mai bun cumpărare / vânzare pereche

400
00:30:08,350 --> 00:30:13,120
în cazul în care vom cumpăra pe jumătatea stângă și să vândă pe jumătatea din dreapta.

401
00:30:13,120 --> 00:30:16,740
Și cel mai bun mod de a face acest lucru este de a calcula cel mai mic preț în prima jumătate a anului,

402
00:30:16,740 --> 00:30:20,360
cel mai mare preț în jumătatea dreaptă, și să ia diferența lor.

403
00:30:20,360 --> 00:30:25,390
Rezultată trei profiturilor, aceste trei numere, luați maximă de trei,

404
00:30:25,390 --> 00:30:32,720
si asta e cel mai bun profit poti face peste aceste primele zile și sfârșitul.

405
00:30:32,720 --> 00:30:36,940
Aici liniile importante sunt în roșu.

406
00:30:36,940 --> 00:30:41,160
Acesta este un apel recursiv pentru a calcula răspunsul în jumătatea stângă.

407
00:30:41,160 --> 00:30:44,760
Acesta este un apel recursiv pentru a calcula răspunsul în jumătatea din dreapta.

408
00:30:44,760 --> 00:30:50,720
Aceste două bucle pentru a calcula min și max pe jumătatea stângă și dreapta, respectiv.

409
00:30:50,720 --> 00:30:54,970
Acum am calcula profitul pe care se întinde pe ambele jumatati,

410
00:30:54,970 --> 00:31:00,530
și răspunsul final este maximă a acestor trei.

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

412
00:31:04,120 --> 00:31:06,420
>> Deci, sigur, avem un algoritm, dar întrebarea este mai mare,

413
00:31:06,420 --> 00:31:08,290
ceea ce este complexitatea timp de asta?

414
00:31:08,290 --> 00:31:16,190
Și motivul pentru care am menționat de îmbinare fel este faptul că această formă de diviza răspuns

415
00:31:16,190 --> 00:31:19,200
în două și apoi fuzionarea soluțiile noastre înapoi împreună

416
00:31:19,200 --> 00:31:23,580
este exact forma de sortare îmbinare.

417
00:31:23,580 --> 00:31:33,360
Așa că lasă-mă să trec prin durata.

418
00:31:33,360 --> 00:31:41,340
Dacă am definit o functie T (n) să fie numărul de pași

419
00:31:41,340 --> 00:31:50,010
pentru n zile,

420
00:31:50,010 --> 00:31:54,350
cele două apeluri recursive

421
00:31:54,350 --> 00:32:00,460
sunt fiecare va costa T (n / 2),

422
00:32:00,460 --> 00:32:03,540
și nu există două dintre aceste apeluri.

423
00:32:03,540 --> 00:32:10,020
Acum am nevoie pentru a calcula minima de jumătatea stângă,

424
00:32:10,020 --> 00:32:17,050
pe care eu pot face în n / 2 ora, plus maxim de jumătatea din dreapta.

425
00:32:17,050 --> 00:32:20,820
Deci, aceasta este doar n.

426
00:32:20,820 --> 00:32:25,050
Și apoi, plus ceva de lucru constantă.

427
00:32:25,050 --> 00:32:27,770
Și această ecuație reapariției

428
00:32:27,770 --> 00:32:35,560
este exact ecuația de recurență pentru sortare îmbinare.

429
00:32:35,560 --> 00:32:39,170
Și știm cu toții că este un fel de îmbinare log n n timp.

430
00:32:39,170 --> 00:32:46,880
Prin urmare, algoritmul nostru este, de asemenea, n log n timp.

431
00:32:46,880 --> 00:32:52,220
Are această repetare a face sens?

432
00:32:52,220 --> 00:32:55,780
Doar o recapitulare scurtă de acest lucru:

433
00:32:55,780 --> 00:32:59,170
T (n) este numărul de pași pentru a calcula profitul maxim

434
00:32:59,170 --> 00:33:02,750
pe parcursul a n zile.

435
00:33:02,750 --> 00:33:06,010
Modul în care ne despărțim apeluri recursive noastre

436
00:33:06,010 --> 00:33:11,980
este sunand la soluția noastră în primele zile n / 2,

437
00:33:11,980 --> 00:33:14,490
așa că e un singur apel,

438
00:33:14,490 --> 00:33:16,940
și atunci se numește din nou pe a doua jumătate.

439
00:33:16,940 --> 00:33:20,440
Deci asta e două apeluri.

440
00:33:20,440 --> 00:33:25,310
Și apoi vom găsi o minimă pe jumătatea stângă, pe care le putem face în timp liniar,

441
00:33:25,310 --> 00:33:29,010
găsi maximă jumătatea dreaptă, pe care le putem face in timp liniar.

442
00:33:29,010 --> 00:33:31,570
Deci, n / 2 + n / 2 este doar n..

443
00:33:31,570 --> 00:33:36,020
Atunci avem ceva de lucru constantă, care este ca face aritmetica.

444
00:33:36,020 --> 00:33:39,860
Această ecuație recurență este exact ecuația de recurență pentru sortare îmbinare.

445
00:33:39,860 --> 00:33:55,490
Prin urmare, algoritmul nostru shuffle este, de asemenea n log n.

446
00:33:55,490 --> 00:33:58,520
Deci, cât de mult spațiu suntem folosind?

447
00:33:58,520 --> 00:34:04,910
Să ne întoarcem la codul.

448
00:34:04,910 --> 00:34:09,420
>> O întrebare mai bună este, cât de multe cadre stack-avem vreodată la un moment dat?

449
00:34:09,420 --> 00:34:11,449
Din moment ce suntem cu recursivitate,

450
00:34:11,449 --> 00:34:23,530
numărul de cadre stack determină utilizarea nostru spațiu.

451
00:34:23,530 --> 00:34:29,440
Să considerăm n = 8.

452
00:34:29,440 --> 00:34:36,889
Facem apel la 8 amestecare,

453
00:34:36,889 --> 00:34:41,580
care va apela shuffle pe primele patru intrări,

454
00:34:41,580 --> 00:34:46,250
care va apela un shuffle pe primele două intrări.

455
00:34:46,250 --> 00:34:51,550
Deci stack nostru este - aceasta este stiva noastră.

456
00:34:51,550 --> 00:34:54,980
Și atunci se numește amestecare din nou la 1,

457
00:34:54,980 --> 00:34:58,070
și asta e ceea ce cazul nostru de bază este, deci ne întoarcem imediat.

458
00:34:58,070 --> 00:35:04,700
Avem tot mai mult de această cadre stack de multe?

459
00:35:04,700 --> 00:35:08,880
Nu, pentru că de fiecare dată când facem o invocare,

460
00:35:08,880 --> 00:35:10,770
o invocație recursivă la shuffle,

461
00:35:10,770 --> 00:35:13,950
vom împărți dimensiunea noastră în jumătate.

462
00:35:13,950 --> 00:35:17,020
Deci, numărul maxim de cadre stack avem vreodată la un moment dat

463
00:35:17,020 --> 00:35:28,460
este pe ordinea de cadre log n stivă.

464
00:35:28,460 --> 00:35:42,460
Fiecare cadru stivă are spațiu constanta,

465
00:35:42,460 --> 00:35:44,410
și, prin urmare, valoarea totală a spațiului,

466
00:35:44,410 --> 00:35:49,240
valoarea maximă de spațiu vom folosi vreodată este O (log n) spațiu

467
00:35:49,240 --> 00:36:03,040
unde n este numărul de zile.

468
00:36:03,040 --> 00:36:07,230
>> Acum, întrebați-vă mereu, "putem face mai bine?"

469
00:36:07,230 --> 00:36:12,390
Și, în special, putem reduce această problemă într-o am deja rezolvat?

470
00:36:12,390 --> 00:36:20,040
Un indiciu: am discutat doar două alte probleme înainte de acest lucru, și nu va fi shuffle.

471
00:36:20,040 --> 00:36:26,200
Noi putem transforma această problemă piața bursieră în problema subarray maximă.

472
00:36:26,200 --> 00:36:40,100
Cum putem face acest lucru?

473
00:36:40,100 --> 00:36:42,570
Unul dintre voi? Emmy?

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

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

476
00:36:53,860 --> 00:36:59,940
Deci, problema subarray maximă,

477
00:36:59,940 --> 00:37:10,610
suntem în căutarea pentru o sumă de peste un subarray continuu.

478
00:37:10,610 --> 00:37:16,230
Și sugestia lui Emmy pentru problema stocurilor,

479
00:37:16,230 --> 00:37:30,720
ia în considerare schimbările, sau delte.

480
00:37:30,720 --> 00:37:37,440
Și o imagine a acestui fapt este - aceasta este pretul unei actiuni,

481
00:37:37,440 --> 00:37:42,610
dar dacă am luat diferenta dintre fiecare zi consecutiv -

482
00:37:42,610 --> 00:37:45,200
asa ca am vedea că prețul maxim, profit maxim am putea face

483
00:37:45,200 --> 00:37:50,070
este, dacă vom cumpăra și vinde aici aici.

484
00:37:50,070 --> 00:37:54,240
Dar haideți să ne uităm la continuu - să ne uităm la problema subarray.

485
00:37:54,240 --> 00:38:02,510
Deci, aici, putem face - merge de aici până aici,

486
00:38:02,510 --> 00:38:08,410
avem o schimbare pozitivă, și apoi merge de aici până aici avem o schimbare negativ.

487
00:38:08,410 --> 00:38:14,220
Dar apoi, mergând de aici până aici avem o schimbare uriașă pozitivă.

488
00:38:14,220 --> 00:38:20,930
Și acestea sunt modificările pe care dorim să le rezuma pentru a obține profit nostru final.

489
00:38:20,930 --> 00:38:25,160
Apoi, avem mai multe schimbări negative aici.

490
00:38:25,160 --> 00:38:29,990
Cheia pentru reducerea problema noastră stoc în problema noastră subarray maximă

491
00:38:29,990 --> 00:38:36,630
este să ia în considerare deltele dintre zile.

492
00:38:36,630 --> 00:38:40,630
Deci, vom crea o matrice nou numit delte,

493
00:38:40,630 --> 00:38:43,000
inițializa prima intrare a fi 0,

494
00:38:43,000 --> 00:38:46,380
și apoi pentru fiecare triunghi (i), să fie faptul că diferența

495
00:38:46,380 --> 00:38:52,830
de matrice meu de intrare (i), și matrice (i - 1).

496
00:38:52,830 --> 00:38:55,530
Apoi, noi numim procedura noastră de rutina pentru un maxim subarray

497
00:38:55,530 --> 00:39:01,500
trecerea într-o matrice delta.

498
00:39:01,500 --> 00:39:06,440
Și pentru că subarray maximă este timpul liniar,

499
00:39:06,440 --> 00:39:09,370
și această reducere, acest proces de creare a acestei matrice delta,

500
00:39:09,370 --> 00:39:11,780
Este, de asemenea, timpul linear,

501
00:39:11,780 --> 00:39:19,060
apoi soluția finală pentru stocurile este O (n) de muncă, plus O (n) de muncă, este încă O (n) de muncă.

502
00:39:19,060 --> 00:39:23,900
Deci, avem o soluție de timp liniar la problema noastră.

503
00:39:23,900 --> 00:39:29,610
Are toată lumea să înțeleagă această transformare?

504
00:39:29,610 --> 00:39:32,140
>> În general, o idee buna pe care ar trebui să aveți întotdeauna

505
00:39:32,140 --> 00:39:34,290
este să încercați pentru a reduce o problemă nouă, care te vezi.

506
00:39:34,290 --> 00:39:37,700
În cazul în care se pare cunoscut la o problemă veche,

507
00:39:37,700 --> 00:39:39,590
încercați să reduceți-l la o problema veche.

508
00:39:39,590 --> 00:39:41,950
Și dacă puteți utiliza toate instrumentele pe care le-ați utilizat la vechea problemă

509
00:39:41,950 --> 00:39:46,450
pentru a rezolva problema noua.

510
00:39:46,450 --> 00:39:49,010
Deci, pentru a încheia, interviuri tehnice sunt provocatoare.

511
00:39:49,010 --> 00:39:52,280
Aceste probleme sunt, probabil, unele dintre cele mai dificile probleme

512
00:39:52,280 --> 00:39:54,700
pe care le-ar putea vedea într-un interviu,

513
00:39:54,700 --> 00:39:57,690
așa că, dacă nu înțelegeți toate problemele pe care am reglementate, e în regulă.

514
00:39:57,690 --> 00:40:01,080
Acestea sunt unele dintre cele mai dificile probleme.

515
00:40:01,080 --> 00:40:03,050
Practică, practică, practică.

516
00:40:03,050 --> 00:40:08,170
I-am dat o mulțime de probleme în fișa, deci cu siguranta verificați aceste afară.

517
00:40:08,170 --> 00:40:11,690
Și noroc pe interviuri dvs.. Toate resursele mele sunt postate la acest link,

518
00:40:11,690 --> 00:40:15,220
și unul dintre prietenii mei seniori a oferit să facă interviuri simulate tehnice,

519
00:40:15,220 --> 00:40:22,050
asa ca daca esti interesat, e-mail va Yao la acea adresa de e-mail.

520
00:40:22,050 --> 00:40:26,070
Dacă aveți unele întrebări, puteți să mă întrebi pe mine.

521
00:40:26,070 --> 00:40:28,780
Nu voi aveți întrebări specifice legate de interviuri tehnice

522
00:40:28,780 --> 00:40:38,440
sau orice probleme care le-am vazut pana acum?

523
00:40:38,440 --> 00:40:49,910
Bine. Ei bine, noroc pe interviuri dvs..

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