1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminari: Entrevistes Tècnics]

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

3
00:00:04,630 --> 00:00:08,910
[Aquesta és CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hola a tots, sóc Kenny. Actualment sóc un jove ciència que estudia informàtica.

5
00:00:12,420 --> 00:00:17,310
Sóc un ex TF CS, i m'agradaria tenir això quan era un underclassman,

6
00:00:17,310 --> 00:00:19,380
i és per això que poso a aquest seminari.

7
00:00:19,380 --> 00:00:21,370
Així que espero que us agradi.

8
00:00:21,370 --> 00:00:23,470
Aquest seminari tracta d'entrevistes tècniques,

9
00:00:23,470 --> 00:00:26,650
i tots els meus recursos es poden trobar en aquest enllaç,

10
00:00:26,650 --> 00:00:32,350
aquest enllaç aquí, un parell de recursos.

11
00:00:32,350 --> 00:00:36,550
Així que vaig fer una llista de problemes, en realitat, força problemes.

12
00:00:36,550 --> 00:00:40,800
També una pàgina de recursos en general on podem trobar consells

13
00:00:40,800 --> 00:00:42,870
sobre com preparar-se per una entrevista,

14
00:00:42,870 --> 00:00:46,470
consells sobre el que ha de fer durant una entrevista real,

15
00:00:46,470 --> 00:00:51,910
així com la forma d'abordar els problemes i els recursos per a futures referències.

16
00:00:51,910 --> 00:00:53,980
És tot en línia.

17
00:00:53,980 --> 00:00:58,290
I només per prologar aquest seminari, un descàrrec de responsabilitat,

18
00:00:58,290 --> 00:01:00,690
com això no hauria - la seva preparació de l'entrevista

19
00:01:00,690 --> 00:01:02,800
no s'ha de limitar a aquesta llista.

20
00:01:02,800 --> 00:01:04,750
Això només pretén ser una guia,

21
00:01:04,750 --> 00:01:08,890
ia més s'hauria de prendre tot el que dic amb un gra de sal,

22
00:01:08,890 --> 00:01:14,620
sinó també utilitzar tot el que solia ajudar-lo en la seva preparació de l'entrevista.

23
00:01:14,620 --> 00:01:16,400
>> Vaig a accelerar a través de les següents diapositives

24
00:01:16,400 --> 00:01:18,650
pel que podem arribar als estudis de casos reals.

25
00:01:18,650 --> 00:01:23,630
L'estructura d'una entrevista per a un Postion enginyeria de programari,

26
00:01:23,630 --> 00:01:26,320
típicament és de 30 a 45 minuts,

27
00:01:26,320 --> 00:01:29,810
múltiples rondes, depenent de la companyia.

28
00:01:29,810 --> 00:01:33,090
Sovint se li codificació en un tauler blanc.

29
00:01:33,090 --> 00:01:35,960
Així que una pissarra blanca com aquesta, però sovint en un format més petit.

30
00:01:35,960 --> 00:01:38,540
Si tens una entrevista telefònica, vostè probablement va a utilitzar

31
00:01:38,540 --> 00:01:44,030
ja sigui collabedit o un document de Google Docs perquè vegin vostès viuen codificació

32
00:01:44,030 --> 00:01:46,500
mentre que vostè està sent entrevistat per telèfon.

33
00:01:46,500 --> 00:01:48,490
Una entrevista en si és de 2 o 3 problemes

34
00:01:48,490 --> 00:01:50,620
prova els teus coneixements d'informàtica.

35
00:01:50,620 --> 00:01:54,490
I serà gairebé definitivament involucrar codificació.

36
00:01:54,490 --> 00:01:59,540
Els tipus de preguntes que es veuen són en general les estructures de dades i algoritmes.

37
00:01:59,540 --> 00:02:02,210
I en fer aquest tipus de problemes,

38
00:02:02,210 --> 00:02:07,830
li preguntaran, com, quin és el temps i la complexitat de l'espai, gran O?

39
00:02:07,830 --> 00:02:09,800
Sovint, també demanen més alt nivell preguntes,

40
00:02:09,800 --> 00:02:12,530
així, el disseny d'un sistema,

41
00:02:12,530 --> 00:02:14,770
Com dissenyar el codi?

42
00:02:14,770 --> 00:02:18,370
Què interfícies, el que les classes, els mòduls que el que té en el seu sistema,

43
00:02:18,370 --> 00:02:20,900
i com aquestes interactuen entre si?

44
00:02:20,900 --> 00:02:26,130
Així que les estructures de dades i algoritmes, així com sistemes de disseny.

45
00:02:26,130 --> 00:02:29,180
>> Alguns consells generals Abans d'aprofundir en els estudis de casos.

46
00:02:29,180 --> 00:02:32,300
Crec que la regla més important és sempre estar pensant en veu alta.

47
00:02:32,300 --> 00:02:36,980
L'entrevista se suposa que és la seva oportunitat per mostrar el seu procés de pensament.

48
00:02:36,980 --> 00:02:39,820
L'objectiu de l'entrevista és que l'entrevistador per avaluar

49
00:02:39,820 --> 00:02:42,660
com pensa i com vostè va a través d'un problema.

50
00:02:42,660 --> 00:02:45,210
La pitjor cosa que pots fer és estar en silenci durant tota l'entrevista.

51
00:02:45,210 --> 00:02:50,090
Això és gens bo.

52
00:02:50,090 --> 00:02:53,230
Quan se li dóna a una pregunta, vostè també vol assegurar-se que entén la pregunta.

53
00:02:53,230 --> 00:02:55,350
Així que repeteixo la pregunta de nou en les seves pròpies paraules

54
00:02:55,350 --> 00:02:58,920
i tractar de treballar a fons alguns casos de prova senzills

55
00:02:58,920 --> 00:03:01,530
per assegurar-se que entén la pregunta.

56
00:03:01,530 --> 00:03:05,510
Treballant a través d'un parell de casos de prova també li donarà una intuïció sobre com resoldre aquest problema.

57
00:03:05,510 --> 00:03:11,210
Fins i tot podria descobrir alguns patrons per ajudar a resoldre el problema.

58
00:03:11,210 --> 00:03:14,500
La seva gran consell és no sentir-se frustrat.

59
00:03:14,500 --> 00:03:17,060
No es frustri.

60
00:03:17,060 --> 00:03:19,060
Les entrevistes són un repte, però el pitjor que es pot fer,

61
00:03:19,060 --> 00:03:23,330
a més de ser silenciosa, es visiblement frustrat.

62
00:03:23,330 --> 00:03:27,410
No vol donar aquesta impressió a un entrevistador.

63
00:03:27,410 --> 00:03:33,960
Una cosa que vostè - així, moltes persones, quan van a una entrevista,

64
00:03:33,960 --> 00:03:37,150
en el seu intent de tractar de trobar la millor solució primer,

65
00:03:37,150 --> 00:03:39,950
quan en realitat, en general hi ha una solució òbvia.

66
00:03:39,950 --> 00:03:43,500
Pot ser que sigui lent, pot ser ineficient, sinó que només ha de dir-ho,

67
00:03:43,500 --> 00:03:46,210
només pel que té un punt de partida per treballar millor.

68
00:03:46,210 --> 00:03:48,270
També, assenyalant la solució és lent, en termes de

69
00:03:48,270 --> 00:03:52,160
O gran complexitat de temps o la complexitat de l'espai,

70
00:03:52,160 --> 00:03:54,450
mostrarà l'entrevistador que vostè entén

71
00:03:54,450 --> 00:03:57,510
aquests problemes en escriure codi.

72
00:03:57,510 --> 00:04:01,440
Així que no tingui por d'arribar amb el primer algorisme més simple

73
00:04:01,440 --> 00:04:04,950
i després treballar millor des d'allà.

74
00:04:04,950 --> 00:04:09,810
Qualsevol pregunta fins ara? Bé.

75
00:04:09,810 --> 00:04:11,650
>> Així que anem a bussejar en el nostre primer problema.

76
00:04:11,650 --> 00:04:14,790
"Donada una matriu d'enters n, escriu una funció que estudia la matriu

77
00:04:14,790 --> 00:04:20,209
en lloc de tal manera que totes les permutacions dels n enters són igualment probables. "

78
00:04:20,209 --> 00:04:23,470
I se suposa que té disponible un generador de nombre enter aleatori

79
00:04:23,470 --> 00:04:30,980
que genera un nombre enter en l'interval de 0 a i, rang mitjà.

80
00:04:30,980 --> 00:04:32,970
Tothom entén aquesta pregunta?

81
00:04:32,970 --> 00:04:39,660
Et dono una matriu d'enters n, i vull que barájalo.

82
00:04:39,660 --> 00:04:46,050
En el meu directori, vaig escriure uns quants programes per demostrar el que vull dir.

83
00:04:46,050 --> 00:04:48,910
Vaig a estudiar una matriu de 20 elements,

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

85
00:04:52,490 --> 00:04:57,050
i vull donar sortida a una llista com aquesta.

86
00:04:57,050 --> 00:05:02,890
Així que aquesta és la meva matriu ordenada d'entrada, i vull que barájalo.

87
00:05:02,890 --> 00:05:07,070
Anem a fer-ho de nou.

88
00:05:07,070 --> 00:05:13,780
Tothom entén la pregunta? Bé.

89
00:05:13,780 --> 00:05:16,730
Així que li toca a vostè.

90
00:05:16,730 --> 00:05:21,220
Quines són algunes idees? Pot fer-ho com n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Obert a suggeriments.

92
00:05:34,400 --> 00:05:37,730
Bé. Així que una idea, suggerida per l'Emmy,

93
00:05:37,730 --> 00:05:45,300
és calcular primer un nombre aleatori, sencer aleatori, en un rang de 0 a 20.

94
00:05:45,300 --> 00:05:49,840
Així que assumir la nostra matriu té una longitud de 20.

95
00:05:49,840 --> 00:05:54,800
En el nostre diagrama de 20 elements,

96
00:05:54,800 --> 00:05:58,560
aquesta és la nostra matriu d'entrada.

97
00:05:58,560 --> 00:06:04,590
I ara, el seu suggeriment és crear una nova matriu,

98
00:06:04,590 --> 00:06:08,440
de manera que aquesta serà la matriu de sortida.

99
00:06:08,440 --> 00:06:12,880
I basat en l'i retornat per rand -

100
00:06:12,880 --> 00:06:17,580
així que si jo estava, diguem, 17,

101
00:06:17,580 --> 00:06:25,640
copiar l'element 17 en la primera posició.

102
00:06:25,640 --> 00:06:30,300
Ara hem d'eliminar - hem de canviar tots els elements aquí

103
00:06:30,300 --> 00:06:36,920
de manera que tenim un buit a l'extrem i no hi ha forats en el medi.

104
00:06:36,920 --> 00:06:39,860
I ara repetim el procés.

105
00:06:39,860 --> 00:06:46,360
Ara triem un nombre enter aleatori entre 0 i 19.

106
00:06:46,360 --> 00:06:52,510
Tenim una i nou aquí, i copiem aquest element en aquesta posició.

107
00:06:52,510 --> 00:07:00,960
Llavors canviem articles una i repetim el procés fins que tinguem la nostra nova matriu completa.

108
00:07:00,960 --> 00:07:05,890
Quin és el temps d'execució d'aquest algorisme?

109
00:07:05,890 --> 00:07:08,110
Bé, anem a considerar l'impacte d'això.

110
00:07:08,110 --> 00:07:10,380
Estem canviant cada element.

111
00:07:10,380 --> 00:07:16,800
Quan eliminar aquesta i, que estan canviant tots els elements després que a l'esquerra.

112
00:07:16,800 --> 00:07:21,600
I aquesta és una operació O (n) Cost

113
00:07:21,600 --> 00:07:26,100
perquè el que si s'elimina el primer element?

114
00:07:26,100 --> 00:07:29,670
Així, per cada retir, remenem -

115
00:07:29,670 --> 00:07:32,170
cada retir incorre en una operació O (n),

116
00:07:32,170 --> 00:07:41,520
i ja que tenim n mudances, això condueix a una operació O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Bé. Així bon començament. Bon començament.

118
00:07:49,550 --> 00:07:55,290
>> Un altre suggeriment és utilitzar alguna cosa conegut com el shuffle Knuth,

119
00:07:55,290 --> 00:07:57,540
o la confusió Fisher-Yates.

120
00:07:57,540 --> 00:07:59,630
I en realitat és un shuffle temps lineal.

121
00:07:59,630 --> 00:08:02,200
I la idea és molt similar.

122
00:08:02,200 --> 00:08:05,160
Un cop més, tenim la nostra matriu d'entrada,

123
00:08:05,160 --> 00:08:08,580
però en lloc d'utilitzar dues matrius per a la nostra entrada / sortida,

124
00:08:08,580 --> 00:08:13,590
s'utilitza la primera part de la matriu per seguir la pista de la nostra part estudiat,

125
00:08:13,590 --> 00:08:18,400
i fem un seguiment, i després deixar la resta de la nostra gamma per a la part unshuffled.

126
00:08:18,400 --> 00:08:24,330
Això és el que vull dir. Comencem amb - triem una i,

127
00:08:24,330 --> 00:08:30,910
una matriu a partir de 0 a 20.

128
00:08:30,910 --> 00:08:36,150
El nostre actual del punter apunta al primer índex.

129
00:08:36,150 --> 00:08:39,590
Triem alguns i aquí

130
00:08:39,590 --> 00:08:42,740
i ara canviem.

131
00:08:42,740 --> 00:08:47,690
Així que si això era 5 i això va ser 4,

132
00:08:47,690 --> 00:08:57,150
la matriu resultant tindrà 5 aquí i 4 aquí.

133
00:08:57,150 --> 00:09:00,390
I ara observem un marcador d'aquí.

134
00:09:00,390 --> 00:09:05,770
Tot a l'esquerra s'estudien,

135
00:09:05,770 --> 00:09:15,160
i tot el que està a la dreta unshuffled.

136
00:09:15,160 --> 00:09:17,260
I ara podem repetir el procés.

137
00:09:17,260 --> 00:09:25,210
Triem un índex aleatori entre 1 i 20 ara.

138
00:09:25,210 --> 00:09:30,650
Així que suposem que el nostre nou jo aquí.

139
00:09:30,650 --> 00:09:39,370
Ara canviem això i amb la nostra nova posició actual aquí.

140
00:09:39,370 --> 00:09:44,790
Així que fer un intercanvi d'anada i tornada així.

141
00:09:44,790 --> 00:09:51,630
Permetin-me que aparegui el codi perquè sigui més concret.

142
00:09:51,630 --> 00:09:55,290
Comencem amb la nostra elecció d'i -

143
00:09:55,290 --> 00:09:58,370
comencem amb i igual a 0, triem un lloc a l'atzar j

144
00:09:58,370 --> 00:10:02,420
a la part unshuffled de la matriu, i a n-1.

145
00:10:02,420 --> 00:10:07,280
Així que si sóc aquí, triar un índex aleatori entre aquí i la resta de la matriu,

146
00:10:07,280 --> 00:10:12,410
i intercanviem.

147
00:10:12,410 --> 00:10:17,550
Aquest és tot el codi necessari per barrejar la teva matriu.

148
00:10:17,550 --> 00:10:21,670
Alguna pregunta?

149
00:10:21,670 --> 00:10:25,530
>> Doncs bé, un necessita pregunta és, per què és això correcte?

150
00:10:25,530 --> 00:10:28,360
Per què totes les permutacions igualment probable?

151
00:10:28,360 --> 00:10:30,410
I no vaig a passar per la prova d'això,

152
00:10:30,410 --> 00:10:35,970
però molts problemes en ciències de la computació pot ser provat a través de la inducció.

153
00:10:35,970 --> 00:10:38,520
Quants de vostès estan familiaritzats amb la inducció?

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

155
00:10:40,590 --> 00:10:43,610
Així que vostè pot demostrar l'exactitud d'aquest algorisme per simple inducció,

156
00:10:43,610 --> 00:10:49,540
on la hipòtesi d'inducció seria assumir que

157
00:10:49,540 --> 00:10:53,290
meva baralla torna cada permutació mateixa probabilitat

158
00:10:53,290 --> 00:10:56,120
als elements per primera vegada.

159
00:10:56,120 --> 00:10:58,300
Ara, considerem i + 1.

160
00:10:58,300 --> 00:11:02,550
I per la manera com triem el nostre índex j per intercanviar,

161
00:11:02,550 --> 00:11:05,230
això porta a - i després es treballa en els detalls,

162
00:11:05,230 --> 00:11:07,390
almenys una prova completa de per què aquest algorisme retorna

163
00:11:07,390 --> 00:11:12,800
totes les permutacions amb una probabilitat igualment probables.

164
00:11:12,800 --> 00:11:15,940
>> Tot problema dreta, al costat.

165
00:11:15,940 --> 00:11:19,170
Així que "donat un conjunt de nombres enters, postive, zero, negatiu,

166
00:11:19,170 --> 00:11:21,290
escriure una funció que calcula la suma màxima

167
00:11:21,290 --> 00:11:24,720
de qualsevol submatriu continueous de la matriu d'entrada. "

168
00:11:24,720 --> 00:11:28,370
Un exemple aquí és, en el cas que tots els nombres són positius,

169
00:11:28,370 --> 00:11:31,320
a continuació, en l'actualitat la millor opció és prendre tot el conjunt.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, és igual a 10.

171
00:11:34,690 --> 00:11:36,780
Quan vostè té alguns aspectes negatius d'allà,

172
00:11:36,780 --> 00:11:38,690
en aquest cas només volem els dos primers

173
00:11:38,690 --> 00:11:44,590
perquè triar -1 i / o -3 farà que la nostra suma cap avall.

174
00:11:44,590 --> 00:11:48,120
De vegades pot ser que hàgim de començar al mig de la matriu.

175
00:11:48,120 --> 00:11:53,500
De vegades hem de triar res en absolut, és millor que no tenir res.

176
00:11:53,500 --> 00:11:56,490
I de vegades és millor prendre la caiguda,

177
00:11:56,490 --> 00:12:07,510
perquè després del que és super gran. Llavors, alguna idea?

178
00:12:07,510 --> 00:12:10,970
(Estudiant, inintel · ligible) >> Si.

179
00:12:10,970 --> 00:12:13,560
Suposem que jo no prenc -1.

180
00:12:13,560 --> 00:12:16,170
Llavors, o trio 1.000 i 20.000,

181
00:12:16,170 --> 00:12:18,630
o m'acaba de triar els 3 milions de dòlars.

182
00:12:18,630 --> 00:12:20,760
Bé, la millor opció és prendre tots els números.

183
00:12:20,760 --> 00:12:24,350
Aquesta -1, tot i ser negatiu,

184
00:12:24,350 --> 00:12:31,340
la suma total és millor que jo no fos a prendre -1.

185
00:12:31,340 --> 00:12:36,460
Així que un dels consells que he esmentat abans va anar a dir el obvi clarament

186
00:12:36,460 --> 00:12:40,540
i la solució de força bruta primer.

187
00:12:40,540 --> 00:12:44,340
Quina és la solució de força bruta en aquest problema? Sí?

188
00:12:44,340 --> 00:12:46,890
[Jane] Bé, crec que la solució de força bruta

189
00:12:46,890 --> 00:12:52,600
seria la de sumar totes les combinacions possibles (inintel · ligible).

190
00:12:52,600 --> 00:12:58,250
[Yu] Bé. Així que la idea de Jane és prendre cada possible -

191
00:12:58,250 --> 00:13:01,470
Estic parafrasejant - és prendre cada submatriu continu possible,

192
00:13:01,470 --> 00:13:07,840
calcular la seva suma, i després prendre el màxim de tots els subconjunts possibles contínues.

193
00:13:07,840 --> 00:13:13,310
El que identifica de manera exclusiva una submatriu al meu matriu d'entrada?

194
00:13:13,310 --> 00:13:17,380
Com, què dues coses que necessito? Sí?

195
00:13:17,380 --> 00:13:19,970
(Estudiant, inintel · ligible) Dret >>.

196
00:13:19,970 --> 00:13:22,130
Un límit inferior en l'índex i l'índex del límit superior

197
00:13:22,130 --> 00:13:28,300
determina de manera única una submatriu contínua.

198
00:13:28,300 --> 00:13:31,400
[Estudiant Dona] Estem estimant que és una sèrie de nombres únics?

199
00:13:31,400 --> 00:13:34,280
[Yu] No tant el dubte és, estem assumint la nostra àmplia -

200
00:13:34,280 --> 00:13:39,000
és la nostra matriu tots els nombres únics, i la resposta és no.

201
00:13:39,000 --> 00:13:43,390
>> Si utilitzem la nostra solució de força bruta, llavors els índexs d'inici / fi

202
00:13:43,390 --> 00:13:47,200
únicament determina la nostra subarray contínua.

203
00:13:47,200 --> 00:13:51,680
Així que si iterar per a totes les entrades d'inici possibles,

204
00:13:51,680 --> 00:13:58,320
i per a totes les entrades finals> o = per començar, i n <,

205
00:13:58,320 --> 00:14:05,570
a calcular la suma, i després prenem la suma màxima que hem vist fins ara.

206
00:14:05,570 --> 00:14:07,880
Està clar?

207
00:14:07,880 --> 00:14:12,230
Quina és la gran O d'aquesta solució?

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

209
00:14:16,660 --> 00:14:18,860
No del tot n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Recordeu que iterar des de 0 a n,

211
00:14:25,250 --> 00:14:27,520
així que això és un bucle for.

212
00:14:27,520 --> 00:14:35,120
Ens iterar de nou gairebé des de l'inici fins al final, per un altre bucle.

213
00:14:35,120 --> 00:14:37,640
I ara, dins d'això, hem de resumir cada entrada,

214
00:14:37,640 --> 00:14:43,810
així que això és un altre bucle for. Així que tenim tres bucles for niats, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Bé. Això va com punt de partida.

216
00:14:46,560 --> 00:14:53,180
La nostra solució no és pitjor que n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Tots entenen la solució de força bruta?

218
00:14:55,480 --> 00:14:59,950
>> Bé. Una solució millor és utilitzar una idea anomenada de programació dinàmica.

219
00:14:59,950 --> 00:15:03,040
Si vostè pren CS124, que és Algorismes i Estructures de Dades,

220
00:15:03,040 --> 00:15:05,680
et tornaràs molt familiaritzat amb aquesta tècnica.

221
00:15:05,680 --> 00:15:12,190
I la idea és, intentar construir solucions als problemes més curts primer.

222
00:15:12,190 --> 00:15:17,990
Què vull dir amb això és que en l'actualitat s'ha de preocupar de dues coses: d'inici i fi.

223
00:15:17,990 --> 00:15:29,340
I això és molest. I si poguéssim desfer d'un d'aquests paràmetres?

224
00:15:29,340 --> 00:15:32,650
Una idea és - estem donat al nostre problema original,

225
00:15:32,650 --> 00:15:37,470
trobar la suma màxima de qualsevol submatriu en un interval [O, n-1].

226
00:15:37,470 --> 00:15:47,400
I ara tenim un nou subproblema, on sabem, al nostre actual índex i,

227
00:15:47,400 --> 00:15:52,520
sabem que hem de concloure allà. La nostra subarray ha d'acabar en l'índex actual.

228
00:15:52,520 --> 00:15:57,640
Així que el problema que queda és, On hauríem de començar el nostre subarray?

229
00:15:57,640 --> 00:16:05,160
Té això sentit? Bé.

230
00:16:05,160 --> 00:16:12,030
Així que he codificat això, i anem a veure el que això significa.

231
00:16:12,030 --> 00:16:16,230
Al codirectory, hi ha un programa anomenat subarray,

232
00:16:16,230 --> 00:16:19,470
i es triga nombre d'elements,

233
00:16:19,470 --> 00:16:25,550
i torna la suma subarray màxim en la cistella arrossegant els peus.

234
00:16:25,550 --> 00:16:29,920
Així que en aquest cas, el nostre subarray màxima és de 3.

235
00:16:29,920 --> 00:16:34,850
I això ha pres simplement usant 2 i 1.

236
00:16:34,850 --> 00:16:38,050
Anem a córrer de nou. També és 3.

237
00:16:38,050 --> 00:16:40,950
Però aquesta vegada, tingui en compte com hem arribat fins al 3.

238
00:16:40,950 --> 00:16:46,690
Ens prenem el - que acabem de prendre la 3 es

239
00:16:46,690 --> 00:16:49,980
perquè està envoltat de negatius en ambdós costats,

240
00:16:49,980 --> 00:16:55,080
que aportarà una suma <3.

241
00:16:55,080 --> 00:16:57,820
Anem a córrer en 10 articles.

242
00:16:57,820 --> 00:17:03,200
Aquesta vegada es tracta de 7, prenem el líder 3 i 4.

243
00:17:03,200 --> 00:17:09,450
Aquesta vegada és 8, i obtenim que prenent 1, 4 i 3.

244
00:17:09,450 --> 00:17:16,310
Així que per donar-li una intuïció sobre com podem resoldre aquest problema transformat,

245
00:17:16,310 --> 00:17:18,890
anem a fer una ullada al subgrup.

246
00:17:18,890 --> 00:17:23,460
Ens donen la matriu d'entrada, i sabem que la resposta és 8.

247
00:17:23,460 --> 00:17:26,359
Prenem l'1, 4, i 3.

248
00:17:26,359 --> 00:17:29,090
Però donem una ullada a com en realitat ens van donar aquesta resposta.

249
00:17:29,090 --> 00:17:34,160
Fem una ullada a la submatriu màxim que va desembocar en cada un d'aquests índexs.

250
00:17:34,160 --> 00:17:40,780
Quina és la submatriu màxima que ha d'acabar en la primera posició?

251
00:17:40,780 --> 00:17:46,310
[Estudiant] Zero. >> Zero. Això sí, no es prenen el -5.

252
00:17:46,310 --> 00:17:50,210
Aquí serà 0 també. Sí?

253
00:17:50,210 --> 00:17:56,470
(Estudiant, inintel · ligible)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, ho sento, és un -3.

255
00:17:58,960 --> 00:18:03,220
Així que aquest és un 2, aquest és un -3.

256
00:18:03,220 --> 00:18:08,690
Bé. Així -4, quina és la submatriu màxim per posar fi a aquesta posició

257
00:18:08,690 --> 00:18:12,910
on -4 és en? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Ara, he de acabar en el lloc on es troba a -2.

260
00:18:28,060 --> 00:18:39,330
Així 6, 5, 7, i l'última és 4.

261
00:18:39,330 --> 00:18:43,480
Sabent que aquests són les meves entrades

262
00:18:43,480 --> 00:18:48,130
per al problema transformat en la qual ha d'acabar en cada un d'aquests índexs,

263
00:18:48,130 --> 00:18:51,410
llavors la meva resposta final és simplement, prendre un escombrat a través,

264
00:18:51,410 --> 00:18:53,580
i prendre el nombre màxim.

265
00:18:53,580 --> 00:18:55,620
Així que en aquest cas és 8.

266
00:18:55,620 --> 00:19:00,010
Això implica que la submatriu màxima acaba en aquest índex,

267
00:19:00,010 --> 00:19:04,970
i va començar en algun lloc abans d'ella.

268
00:19:04,970 --> 00:19:09,630
Tothom entén aquesta submatriu transformat?

269
00:19:09,630 --> 00:19:22,160
>> Bé. Bé, anem a esbrinar la recurrència d'això.

270
00:19:22,160 --> 00:19:27,990
Anem a considerar només les primeres entrades.

271
00:19:27,990 --> 00:19:35,930
Així que aquí era 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
I després estava un -2 aquí, i això la va portar a 6.

273
00:19:39,790 --> 00:19:50,800
Així que si dic a l'entrada en la posició i subproblema (i),

274
00:19:50,800 --> 00:19:54,910
Com puc utilitzar la resposta a un subproblema anterior

275
00:19:54,910 --> 00:19:59,360
Per respondre a aquesta subproblema?

276
00:19:59,360 --> 00:20:04,550
Si miro, diguem, però aquesta entrada.

277
00:20:04,550 --> 00:20:09,190
Com puc calcular la resposta 6 per mirar

278
00:20:09,190 --> 00:20:18,780
una combinació d'aquesta matriu i les respostes a subproblemes anteriors d'aquesta matriu? Sí?

279
00:20:18,780 --> 00:20:22,800
[Estudiant Dona] Vostè pren la matriu de sumes

280
00:20:22,800 --> 00:20:25,430
en la posició correcta abans d'ella, de manera que la 8,

281
00:20:25,430 --> 00:20:32,170
a continuació, afegir el subproblema actual.

282
00:20:32,170 --> 00:20:36,460
[Yu] Així que el suggeriment és mirar a aquests dos nombres,

283
00:20:36,460 --> 00:20:40,090
aquest nombre i aquest nombre.

284
00:20:40,090 --> 00:20:50,130
Així que aquest 8 es refereix a la resposta per al subproblema (i - 1).

285
00:20:50,130 --> 00:20:57,300
I anem a trucar al meu matriu d'entrada A.

286
00:20:57,300 --> 00:21:01,470
Per tal de trobar una submatriu màxima que acaba en la posició i,

287
00:21:01,470 --> 00:21:03,980
Tinc dues opcions: o bé pot continuar la submatriu

288
00:21:03,980 --> 00:21:09,790
que va acabar en l'índex anterior, o començar una nova matriu.

289
00:21:09,790 --> 00:21:14,190
Si jo fos a continuar la submatriu que es va iniciar en l'índex anterior,

290
00:21:14,190 --> 00:21:19,260
llavors la suma màxima que pot assolir és la resposta a l'anterior subproblema

291
00:21:19,260 --> 00:21:24,120
a més de l'entrada de la matriu actual.

292
00:21:24,120 --> 00:21:27,550
Però, també té l'opció d'iniciar un nou subconjunt,

293
00:21:27,550 --> 00:21:30,830
en aquest cas la suma és 0.

294
00:21:30,830 --> 00:21:42,860
Així que la resposta és, com a màxim de 0, subproblema i - 1, a més de l'entrada de la matriu actual.

295
00:21:42,860 --> 00:21:46,150
¿Aquesta repetició té sentit?

296
00:21:46,150 --> 00:21:50,840
La nostra recurrència, com acabem de descobrir, és subproblema i

297
00:21:50,840 --> 00:21:54,740
és igual al màxim de la subproblema anterior més la meva entrada de la matriu actual,

298
00:21:54,740 --> 00:22:01,490
el que significa seguir la submatriu anterior,

299
00:22:01,490 --> 00:22:07,250
o 0, començar una nova submatriu al meu índex actual.

300
00:22:07,250 --> 00:22:10,060
I un cop que hem construït aquesta taula de solucions, llavors la nostra resposta final,

301
00:22:10,060 --> 00:22:13,950
acaba de fer un escombrat lineal a través de la matriu subproblema

302
00:22:13,950 --> 00:22:19,890
i prendre el nombre màxim.

303
00:22:19,890 --> 00:22:23,330
Es tracta d'una aplicació exacta del que acabo de dir.

304
00:22:23,330 --> 00:22:27,320
Així que vam crear una matriu subproblema nou subproblemes.

305
00:22:27,320 --> 00:22:32,330
La primera entrada és o bé 0 o la primera entrada, la màxima de les dues.

306
00:22:32,330 --> 00:22:35,670
I per a la resta dels subproblemes

307
00:22:35,670 --> 00:22:39,810
fem servir la repetició exacta que acaba de descobrir.

308
00:22:39,810 --> 00:22:49,960
Ara es calcula el màxim de la nostra àmplia subproblemes, i aquesta és la nostra resposta final.

309
00:22:49,960 --> 00:22:54,130
>> Llavors, quant espai estem fent servir en aquest algorisme?

310
00:22:54,130 --> 00:23:01,470
Si només has pres CS50, llavors no podria haver discutit molt espai.

311
00:23:01,470 --> 00:23:07,750
Bé, una cosa a tenir en compte és que vaig trucar a malloc aquí amb mida n.

312
00:23:07,750 --> 00:23:13,590
Què és el que et suggereix?

313
00:23:13,590 --> 00:23:17,450
Aquest algorisme utilitza l'espai lineal.

314
00:23:17,450 --> 00:23:21,030
Podem fer-ho millor?

315
00:23:21,030 --> 00:23:30,780
Hi ha res que et dones compte que no és necessari per calcular la resposta final?

316
00:23:30,780 --> 00:23:33,290
Crec que una millor pregunta és, ¿quina informació

317
00:23:33,290 --> 00:23:40,680
no hem de portar tot el camí fins al final?

318
00:23:40,680 --> 00:23:44,280
Ara bé, si ens fixem en aquestes dues línies,

319
00:23:44,280 --> 00:23:47,720
que només es preocupen pel subproblema anterior,

320
00:23:47,720 --> 00:23:50,910
i que només es preocupen per el màxim que he vist fins ara.

321
00:23:50,910 --> 00:23:53,610
Per calcular la nostra resposta final, no necessitem tota la matriu.

322
00:23:53,610 --> 00:23:57,450
Només necessitem el darrer número, els dos últims números.

323
00:23:57,450 --> 00:24:02,630
De l'últim número de la matriu subproblema, i l'últim número de la màxima.

324
00:24:02,630 --> 00:24:07,380
Així, de fet, es pot fusionar aquests bucles junts

325
00:24:07,380 --> 00:24:10,460
i van des de l'espai lineal a l'espai constant.

326
00:24:10,460 --> 00:24:15,830
Suma fins al moment actual, aquí, reemplaça el paper del subproblema, la nostra àmplia subproblema.

327
00:24:15,830 --> 00:24:20,020
Així suma actual, fins ara, és la resposta a la subproblema anterior.

328
00:24:20,020 --> 00:24:23,450
I aquesta suma, fins ara, ocupa el lloc del nostre màx.

329
00:24:23,450 --> 00:24:28,100
Calculem el màxim a mesura que avancem.

330
00:24:28,100 --> 00:24:30,890
I així anem des de l'espai lineal constant en l'espai,

331
00:24:30,890 --> 00:24:36,650
i també tenim una solució al nostre problema lineal submatriu.

332
00:24:36,650 --> 00:24:40,740
>> Aquest tipus de preguntes que vostè rebrà durant una entrevista.

333
00:24:40,740 --> 00:24:44,450
Quina és la complexitat de temps, el que és la complexitat de l'espai?

334
00:24:44,450 --> 00:24:50,600
Es pot fer millor? Hi ha coses que no són necessàries per mantenir en tot?

335
00:24:50,600 --> 00:24:55,270
Ho vaig fer per posar en relleu les anàlisis que s'ha de prendre pel seu compte

336
00:24:55,270 --> 00:24:57,400
com el que està treballant a través d'aquests problemes.

337
00:24:57,400 --> 00:25:01,710
Sempre que s'estigui preguntant, "¿Puc fer-ho millor?"

338
00:25:01,710 --> 00:25:07,800
De fet, podem fer alguna cosa millor que això?

339
00:25:07,800 --> 00:25:10,730
Una espècie de pregunta capciosa. No pots, perquè cal

340
00:25:10,730 --> 00:25:13,590
almenys llegir l'entrada al problema.

341
00:25:13,590 --> 00:25:15,570
Així que el fet que vostè necessita com a mínim llegir l'entrada al problema

342
00:25:15,570 --> 00:25:19,580
significa que no es pot fer res millor que el temps lineal,

343
00:25:19,580 --> 00:25:22,870
i no es pot fer res millor que un espai constant.

344
00:25:22,870 --> 00:25:27,060
Així que aquest és, de fet, la millor solució per aquest problema.

345
00:25:27,060 --> 00:25:33,040
Preguntes? Bé.

346
00:25:33,040 --> 00:25:35,190
>> Stock problema del mercat:

347
00:25:35,190 --> 00:25:38,350
"Donada una matriu d'enters n, positiu, zero o negatiu,

348
00:25:38,350 --> 00:25:41,680
que representen el preu d'una acció més de n dies,

349
00:25:41,680 --> 00:25:44,080
escriure una funció per calcular el benefici màxim que es pot fer

350
00:25:44,080 --> 00:25:49,350
tenint en compte que vostè compra i venda de valors en exactament 1 núm aquests dies. "

351
00:25:49,350 --> 00:25:51,690
Essencialment, volem comprar barat, vendre car.

352
00:25:51,690 --> 00:25:58,580
I volem esbrinar el millor benefici que podem fer.

353
00:25:58,580 --> 00:26:11,500
Tornant al meu consell, quin és el clar immediatament, resposta més simple, però és lent?

354
00:26:11,500 --> 00:26:17,690
Sí? (Estudiant, inintel · ligible) >> Sí

355
00:26:17,690 --> 00:26:21,470
>> Pel que s'acaba d'anar bé i mirar els preus de les accions

356
00:26:21,470 --> 00:26:30,550
en cada punt en el temps, (inintel · ligible).

357
00:26:30,550 --> 00:26:33,990
[Yu] Bé, pel que la seva solució - el suggeriment de la computació

358
00:26:33,990 --> 00:26:37,380
el més baix i el més alt computar no funciona necessàriament

359
00:26:37,380 --> 00:26:42,470
perquè la més alta podria passar abans de la més baixa.

360
00:26:42,470 --> 00:26:47,340
Llavors, quina és la solució de força bruta per aquest problema?

361
00:26:47,340 --> 00:26:53,150
Quines són les dues coses que necessito per determinar unívocament el benefici que faig? Dreta.

362
00:26:53,150 --> 00:26:59,410
La solució de força bruta és - oh, per la qual cosa, el suggeriment de George és que només necessiten dos dies

363
00:26:59,410 --> 00:27:02,880
per determinar unívocament el benefici d'aquests dos dies.

364
00:27:02,880 --> 00:27:06,660
Així de calcular cada parell, com compra / venda,

365
00:27:06,660 --> 00:27:12,850
calcular el benefici, que pot ser negatiu o positiu o zero.

366
00:27:12,850 --> 00:27:18,000
Calculeu el guany màxim que fem després de iterar sobre tots els parells de dies.

367
00:27:18,000 --> 00:27:20,330
Aquesta serà la nostra resposta final.

368
00:27:20,330 --> 00:27:25,730
I que la solució serà O (n ^ 2), perquè no hi ha n triar dos parells -

369
00:27:25,730 --> 00:27:30,270
de dies que es pot triar entre els dies finals.

370
00:27:30,270 --> 00:27:32,580
Molt bé, així que no vaig a anar sobre la solució de força bruta aquí.

371
00:27:32,580 --> 00:27:37,420
Jo et diré que hi ha una solució log n n.

372
00:27:37,420 --> 00:27:45,550
Què algorisme veu actualment sabem que és n log n?

373
00:27:45,550 --> 00:27:50,730
No és una pregunta capciosa.

374
00:27:50,730 --> 00:27:54,790
>> Combinar tipus. Merge sort és n log n,

375
00:27:54,790 --> 00:27:57,760
i, de fet, una forma de resoldre aquest problema és utilitzar

376
00:27:57,760 --> 00:28:04,400
una mena de barreja tipus d'idea es diu, en general, dividir i conquerir.

377
00:28:04,400 --> 00:28:07,570
I la idea és la següent.

378
00:28:07,570 --> 00:28:12,400
Vol calcular la millor compra / venda parella a la meitat esquerra.

379
00:28:12,400 --> 00:28:16,480
Troba el millor benefici que vostè pot fer, només amb el núm primera de dos dies.

380
00:28:16,480 --> 00:28:19,780
Llavors vostè vol oompute la millor compra / venda parella a la meitat dreta,

381
00:28:19,780 --> 00:28:23,930
de manera que el n duren més de dos dies.

382
00:28:23,930 --> 00:28:32,400
I ara la pregunta és, com podem combinar aquestes solucions de tornar a estar junts?

383
00:28:32,400 --> 00:28:36,320
Sí? (Estudiant, inintel · ligible)

384
00:28:36,320 --> 00:28:49,890
>> Okay. Així que permetin-me fer un dibuix.

385
00:28:49,890 --> 00:29:03,870
Sí? (George, inintel · ligible)

386
00:29:03,870 --> 00:29:06,450
>> Exactament. Solució de George és exactament correcte.

387
00:29:06,450 --> 00:29:10,040
Així que el seu suggeriment és, en primer lloc calcular millor la compra / venda parell,

388
00:29:10,040 --> 00:29:16,050
i que es produeix en la meitat esquerra, així que anomenarem a aquesta esquerra, esquerra.

389
00:29:16,050 --> 00:29:20,790
La millor compra / venda una que es produeix en la meitat dreta.

390
00:29:20,790 --> 00:29:25,180
Però si només es comparen aquests dos nombres, estem perdent el cas

391
00:29:25,180 --> 00:29:30,460
on comprar i vendre aquí en algun lloc de la meitat dreta.

392
00:29:30,460 --> 00:29:33,810
Comprem a la meitat esquerra, vendre a la meitat dreta.

393
00:29:33,810 --> 00:29:38,490
I la millor manera de calcular millor la compra / venda una que s'estén per les dues meitats

394
00:29:38,490 --> 00:29:43,480
és calcular el mínim aquí i calcular el màxim aquí

395
00:29:43,480 --> 00:29:45,580
i prendre la seva diferència.

396
00:29:45,580 --> 00:29:50,850
Així que els dos casos en què la parella de compra / venda es produeix només aquí,

397
00:29:50,850 --> 00:30:01,910
només aquí, o en ambdues meitats està definida per aquests tres nombres.

398
00:30:01,910 --> 00:30:06,450
Així que el nostre algorisme per combinar les nostres solucions de nou junts,

399
00:30:06,450 --> 00:30:08,350
volem calcular millor la compra / venda parella

400
00:30:08,350 --> 00:30:13,120
on comprem a la meitat esquerra i vendre a la meitat dreta.

401
00:30:13,120 --> 00:30:16,740
I la millor manera de fer-ho és calcular el preu més baix en el primer temps,

402
00:30:16,740 --> 00:30:20,360
el preu més alt en la meitat dreta, i prendre la seva diferència.

403
00:30:20,360 --> 00:30:25,390
Els beneficis resultants tres, aquests tres nombres, es pren el màxim dels tres,

404
00:30:25,390 --> 00:30:32,720
i aquest és el millor benefici que vostè pot fer durant aquests primers dies i al final.

405
00:30:32,720 --> 00:30:36,940
Aquí les línies importants estan en vermell.

406
00:30:36,940 --> 00:30:41,160
Aquesta és una crida recursiva per calcular la resposta en la meitat esquerra.

407
00:30:41,160 --> 00:30:44,760
Aquesta és una crida recursiva per calcular la resposta en la meitat dreta.

408
00:30:44,760 --> 00:30:50,720
Aquests dos bucles per calcular el mínim i el màxim del medi a l'esquerra i la dreta, respectivament.

409
00:30:50,720 --> 00:30:54,970
Ara puc calcular el benefici que s'estén per les dues meitats,

410
00:30:54,970 --> 00:31:00,530
i la resposta final és el màxim d'aquests tres.

411
00:31:00,530 --> 00:31:04,120
Bé.

412
00:31:04,120 --> 00:31:06,420
>> Així que, sí, tenim un algorisme, però la pregunta més gran,

413
00:31:06,420 --> 00:31:08,290
Quina és la complexitat de temps d'això?

414
00:31:08,290 --> 00:31:16,190
I la raó per la qual he esmentat tipus de combinació és que aquesta forma de dividir la resposta

415
00:31:16,190 --> 00:31:19,200
en dos i després la fusió de les nostres solucions de nou junts

416
00:31:19,200 --> 00:31:23,580
és exactament el tipus d'espècie de barreja.

417
00:31:23,580 --> 00:31:33,360
Així que permetin-me anar a través de la durada.

418
00:31:33,360 --> 00:31:41,340
Si es defineix una funció de t (n) ser el nombre de passos

419
00:31:41,340 --> 00:31:50,010
per an dies,

420
00:31:50,010 --> 00:31:54,350
nostres dues trucades recursives

421
00:31:54,350 --> 00:32:00,460
són cadascun costarà t (n / 2),

422
00:32:00,460 --> 00:32:03,540
i hi ha dues d'aquestes trucades.

423
00:32:03,540 --> 00:32:10,020
Ara he de calcular el mínim de la meitat esquerra,

424
00:32:10,020 --> 00:32:17,050
que puc fer en n / 2 hora, més el màxim de la meitat dreta.

425
00:32:17,050 --> 00:32:20,820
Així que això és només n.

426
00:32:20,820 --> 00:32:25,050
I després, a més d'un treball constant.

427
00:32:25,050 --> 00:32:27,770
I aquesta equació de recurrència

428
00:32:27,770 --> 00:32:35,560
és exactament l'equació de recurrència de tipus de mescla.

429
00:32:35,560 --> 00:32:39,170
I tots sabem quin tipus de mescla és log n n temps.

430
00:32:39,170 --> 00:32:46,880
Per tant, el nostre algorisme és també n log n temps.

431
00:32:46,880 --> 00:32:52,220
¿Aquesta iteració té sentit?

432
00:32:52,220 --> 00:32:55,780
Només una breu recapitulació del següent:

433
00:32:55,780 --> 00:32:59,170
T (n) és el nombre de passos per calcular el màxim benefici

434
00:32:59,170 --> 00:33:02,750
en el transcurs de n dies.

435
00:33:02,750 --> 00:33:06,010
La manera com ens separem les nostres crides recursives

436
00:33:06,010 --> 00:33:11,980
està trucant a la nostra solució en els primers dies de n / 2,

437
00:33:11,980 --> 00:33:14,490
així que això és una crida,

438
00:33:14,490 --> 00:33:16,940
i després trucar de nou a la segona meitat.

439
00:33:16,940 --> 00:33:20,440
Així que això és una crida a una altra.

440
00:33:20,440 --> 00:33:25,310
I llavors ens trobem amb un mínim en la meitat esquerra, el que podem fer en el temps lineal,

441
00:33:25,310 --> 00:33:29,010
trobar el màxim de la meitat dreta, el que podem fer en temps lineal.

442
00:33:29,010 --> 00:33:31,570
Així que n / 2 + n / 2 és n.

443
00:33:31,570 --> 00:33:36,020
Llavors tenim un treball constant, que és com fer aritmètica.

444
00:33:36,020 --> 00:33:39,860
Aquesta equació de recurrència és exactament l'equació de recurrència per tipus de mescla.

445
00:33:39,860 --> 00:33:55,490
Per tant, el nostre algoritme de shuffle és també n log n.

446
00:33:55,490 --> 00:33:58,520
Llavors, quant espai estem utilitzant?

447
00:33:58,520 --> 00:34:04,910
Tornem al codi.

448
00:34:04,910 --> 00:34:09,420
>> Una millor pregunta és, quants marcs de pila és el que sempre tenen en un moment donat?

449
00:34:09,420 --> 00:34:11,449
Ja que estem utilitzant recursivitat,

450
00:34:11,449 --> 00:34:23,530
el nombre de marcs de pila determina el nostre ús de l'espai.

451
00:34:23,530 --> 00:34:29,440
Anem a considerar n = 8.

452
00:34:29,440 --> 00:34:36,889
Cridem a estudiar els dies 8,

453
00:34:36,889 --> 00:34:41,580
que cridarà a estudiar a les primeres quatre entrades,

454
00:34:41,580 --> 00:34:46,250
que cridarà a una baralla en les primeres dues entrades.

455
00:34:46,250 --> 00:34:51,550
Així que la nostra pila és - aquesta és la nostra pila.

456
00:34:51,550 --> 00:34:54,980
I llavors cridem a estudiar de nou els dies 1,

457
00:34:54,980 --> 00:34:58,070
i això és el que el nostre escenari base és, per la qual cosa tornar immediatament.

458
00:34:58,070 --> 00:35:04,700
Tenim alguna vegada té més de marcs de pila aquesta gent?

459
00:35:04,700 --> 00:35:08,880
No Com que cada vegada que fem una invocació,

460
00:35:08,880 --> 00:35:10,770
una invocació recursiva per barrejar,

461
00:35:10,770 --> 00:35:13,950
dividim la nostra mida a la meitat.

462
00:35:13,950 --> 00:35:17,020
Així que el nombre màxim de marcs de pila mai tenim en un moment donat

463
00:35:17,020 --> 00:35:28,460
és de l'ordre dels marcs de registre núm pila.

464
00:35:28,460 --> 00:35:42,460
Cada marc de pila disposa d'espai constant,

465
00:35:42,460 --> 00:35:44,410
i per tant la quantitat total d'espai,

466
00:35:44,410 --> 00:35:49,240
la quantitat màxima d'espai que ha consumit alguna vegada és O (log n) espai

467
00:35:49,240 --> 00:36:03,040
on n és el nombre de dies.

468
00:36:03,040 --> 00:36:07,230
>> Ara bé, sempre et preguntes, "Podem fer-ho millor?"

469
00:36:07,230 --> 00:36:12,390
I en particular, ¿es pot reduir a un problema que ja hem resolt?

470
00:36:12,390 --> 00:36:20,040
Un consell: només discuteixen dos problemes abans d'això, i que no serà aleatori.

471
00:36:20,040 --> 00:36:26,200
Podem convertir aquest problema en el mercat de valors problema subarray màxima.

472
00:36:26,200 --> 00:36:40,100
Com podem fer això?

473
00:36:40,100 --> 00:36:42,570
Un de vostès? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, inintel · ligible)

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

476
00:36:53,860 --> 00:36:59,940
Així que el problema subarray màxima,

477
00:36:59,940 --> 00:37:10,610
estem buscant a una suma sobre una submatriu contínua.

478
00:37:10,610 --> 00:37:16,230
I Emmy suggeriment per al problema accions,

479
00:37:16,230 --> 00:37:30,720
considerar els canvis o deltes.

480
00:37:30,720 --> 00:37:37,440
I una foto d'això és - aquest és el preu d'una acció,

481
00:37:37,440 --> 00:37:42,610
però si prenem la diferència entre cada dia consecutiu -

482
00:37:42,610 --> 00:37:45,200
així veiem que el preu màxim, el benefici màxim que podíem fer

483
00:37:45,200 --> 00:37:50,070
és que si anem a comprar aquí i vendre aquí.

484
00:37:50,070 --> 00:37:54,240
Però donem una ullada a la contínua - veurem el problema submatriu.

485
00:37:54,240 --> 00:38:02,510
Així que aquí, podem fer - anar des d'aquí fins aquí,

486
00:38:02,510 --> 00:38:08,410
tenim un canvi positiu, i després anar des d'aquí fins aquí tenim un canvi negatiu.

487
00:38:08,410 --> 00:38:14,220
Però després, en passar d'aquí fins aquí tenim un canvi positiu enorme.

488
00:38:14,220 --> 00:38:20,930
I aquests són els canvis que es volen sumar a aconseguir el nostre benefici final.

489
00:38:20,930 --> 00:38:25,160
Llavors tenim més canvis negatius aquí.

490
00:38:25,160 --> 00:38:29,990
La clau per reduir el nostre problema d'estoc al nostre problema subarray màxim

491
00:38:29,990 --> 00:38:36,630
és considerar els deltes entre els dies.

492
00:38:36,630 --> 00:38:40,630
Així que vam crear una nova matriu anomenada deltes,

493
00:38:40,630 --> 00:38:43,000
inicialitzar la primera entrada sigui 0,

494
00:38:43,000 --> 00:38:46,380
i després per a cada delta (i), deixi que sigui la diferència

495
00:38:46,380 --> 00:38:52,830
de la meva entrada array (i), i la matriu (i - 1).

496
00:38:52,830 --> 00:38:55,530
Llavors diem al nostre procediment de rutina per a un subconjunt maximal

497
00:38:55,530 --> 00:39:01,500
passant per una sèrie de Delta.

498
00:39:01,500 --> 00:39:06,440
I perquè subarray màxim és el temps lineal,

499
00:39:06,440 --> 00:39:09,370
i aquesta reducció, el procés de creació d'aquesta matriu delta,

500
00:39:09,370 --> 00:39:11,780
També és un temps lineal,

501
00:39:11,780 --> 00:39:19,060
llavors la solució final per les accions és O (n) el treball més O (n) el treball, segueix sent O (n) el treball.

502
00:39:19,060 --> 00:39:23,900
Així que tenim una solució en temps lineal al nostre problema.

503
00:39:23,900 --> 00:39:29,610
Tothom entén aquesta transformació?

504
00:39:29,610 --> 00:39:32,140
>> En general, una bona idea que vostè sempre ha de tenir

505
00:39:32,140 --> 00:39:34,290
és tractar de reduir un problema nou que s'està veient.

506
00:39:34,290 --> 00:39:37,700
Si sembla familiar a un vell problema,

507
00:39:37,700 --> 00:39:39,590
intentar reduir-la a un vell problema.

508
00:39:39,590 --> 00:39:41,950
I si es pot utilitzar totes les eines que he fet servir a l'antic problema

509
00:39:41,950 --> 00:39:46,450
per resoldre el nou problema.

510
00:39:46,450 --> 00:39:49,010
Així que per acabar, entrevistes tècniques són desafiants.

511
00:39:49,010 --> 00:39:52,280
Aquests problemes són probablement alguns dels problemes més difícils

512
00:39:52,280 --> 00:39:54,700
que es poden veure en una entrevista,

513
00:39:54,700 --> 00:39:57,690
així que si vostè no entén tots els problemes que acabem de cobrir, està bé.

514
00:39:57,690 --> 00:40:01,080
Aquests són alguns dels problemes més difícils.

515
00:40:01,080 --> 00:40:03,050
Pràctica, pràctica, pràctica.

516
00:40:03,050 --> 00:40:08,170
Em va donar un munt de problemes en el volant, així que definitivament comprovar aquests cap a fora.

517
00:40:08,170 --> 00:40:11,690
I bona sort en les seves entrevistes. Tots els meus recursos es publiquen en aquest enllaç,

518
00:40:11,690 --> 00:40:15,220
i un dels meus amics grans s'ha ofert a fer simulacres d'entrevistes tècniques,

519
00:40:15,220 --> 00:40:22,050
així que si vostè està interessat, un eMail Yao en aquesta direcció de correu electrònic.

520
00:40:22,050 --> 00:40:26,070
Si té algunes preguntes, em pots preguntar.

521
00:40:26,070 --> 00:40:28,780
Vostès tenen preguntes específiques relacionades amb entrevistes tècniques

522
00:40:28,780 --> 00:40:38,440
o d'altres problemes que hem vist fins ara?

523
00:40:38,440 --> 00:40:49,910
Bé. Bé, bona sort en les seves entrevistes.

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