1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminario: Entrevistas Técnicas]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, da Universidade de Harvard]

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

4
00:00:08,910 --> 00:00:12,420
Ola a todos, eu son o Kenny. Actualmente son informática Júnior estudar.

5
00:00:12,420 --> 00:00:17,310
Eu son un ex-CS TF, e eu desexo que eu tiven iso cando eu era un underclassman,

6
00:00:17,310 --> 00:00:19,380
e é por iso que eu estou dando este seminario.

7
00:00:19,380 --> 00:00:21,370
Entón eu espero que che guste.

8
00:00:21,370 --> 00:00:23,470
Este seminario é de preto de entrevistas técnicas,

9
00:00:23,470 --> 00:00:26,650
e todos os meus recursos poden ser atopados nesta ligazón,

10
00:00:26,650 --> 00:00:32,350
este enlace aquí, unha parella de recursos.

11
00:00:32,350 --> 00:00:36,550
Entón eu fixen unha lista de problemas, de feito, algúns problemas.

12
00:00:36,550 --> 00:00:40,800
Tamén unha páxina de recursos en xeral, onde podemos atopar consellos

13
00:00:40,800 --> 00:00:42,870
sobre como se preparar para unha entrevista,

14
00:00:42,870 --> 00:00:46,470
suxestións sobre o que ten que facer durante unha entrevista real,

15
00:00:46,470 --> 00:00:51,910
así como a forma de abordar os problemas e recursos para referencia futura.

16
00:00:51,910 --> 00:00:53,980
É todo online.

17
00:00:53,980 --> 00:00:58,290
E só para prefaciar este seminario, un aviso,

18
00:00:58,290 --> 00:01:00,690
como este non debería - a súa preparación para entrevistas

19
00:01:00,690 --> 00:01:02,800
non se debe limitar a esta lista.

20
00:01:02,800 --> 00:01:04,750
Isto só serve para ser un guía,

21
00:01:04,750 --> 00:01:08,890
e ten que definitivamente dar todo o que eu digo con un gran de sal,

22
00:01:08,890 --> 00:01:14,620
pero tamén usar todo o que eu adoitaba axudar na súa preparación para entrevistas.

23
00:01:14,620 --> 00:01:16,400
>> Eu estou indo para acelerar a través dos seguintes diapositivas

24
00:01:16,400 --> 00:01:18,650
para que poidamos chegar aos estudos de casos reais.

25
00:01:18,650 --> 00:01:23,630
A estrutura dunha entrevista a un postion enxeñaría de software,

26
00:01:23,630 --> 00:01:26,320
é tipicamente 30 a 45 minutos,

27
00:01:26,320 --> 00:01:29,810
múltiples ciclos, dependendo da empresa.

28
00:01:29,810 --> 00:01:33,090
Moitas veces vai ser a codificación nun cadro branco.

29
00:01:33,090 --> 00:01:35,960
Así, un cadro branco como este, pero moitas veces nunha escala menor.

30
00:01:35,960 --> 00:01:38,540
Se vostede está tendo unha entrevista por teléfono, probablemente vai estar usando

31
00:01:38,540 --> 00:01:44,030
ou collabedit ou un Google Doc para que poidan velo en directo de codificación

32
00:01:44,030 --> 00:01:46,500
mentres está sendo entrevistado por teléfono.

33
00:01:46,500 --> 00:01:48,490
Nunha entrevista en si é tipicamente 2 ou 3 problemas

34
00:01:48,490 --> 00:01:50,620
probar o seu coñecemento de informática.

35
00:01:50,620 --> 00:01:54,490
E vai case certamente implica codificación.

36
00:01:54,490 --> 00:01:59,540
Os tipos de preguntas que ver son xeralmente estruturas de datos e algoritmos.

37
00:01:59,540 --> 00:02:02,210
E, ao facer este tipo de problemas,

38
00:02:02,210 --> 00:02:07,830
eles van pedir-lle, así, o que é o tempo ea complexidade do espazo, grande?

39
00:02:07,830 --> 00:02:09,800
Moitas veces, eles tamén pedir maior nivel de preguntas,

40
00:02:09,800 --> 00:02:12,530
Así, proxectar un sistema,

41
00:02:12,530 --> 00:02:14,770
como é que pór para fóra o seu código?

42
00:02:14,770 --> 00:02:18,370
Cales interfaces, que as clases, que módulos ten no seu sistema,

43
00:02:18,370 --> 00:02:20,900
e como estes interactúan entre si?

44
00:02:20,900 --> 00:02:26,130
Así estruturas de datos e algoritmos, así como sistemas de proxecto.

45
00:02:26,130 --> 00:02:29,180
>> Algunhas suxestións xerais, antes de mergullar nos nosos estudios de caso.

46
00:02:29,180 --> 00:02:32,300
Creo que a regra máis importante é estar sempre a pensar en voz alta.

47
00:02:32,300 --> 00:02:36,980
A entrevista é suposta ser a súa oportunidade de amosar o seu proceso de pensamento.

48
00:02:36,980 --> 00:02:39,820
O punto da entrevista é para o entrevistador para avaliar

49
00:02:39,820 --> 00:02:42,660
como pensa e como pasar por un problema.

50
00:02:42,660 --> 00:02:45,210
A peor cousa que pode facer é estar en silencio durante toda a entrevista.

51
00:02:45,210 --> 00:02:50,090
Isto é só non é bo.

52
00:02:50,090 --> 00:02:53,230
Cando ten unha pregunta, tamén quere ter a certeza de que entendeu a pregunta.

53
00:02:53,230 --> 00:02:55,350
Entón, repito a pregunta de volta nas súas propias palabras

54
00:02:55,350 --> 00:02:58,920
e intento de traballar completas nalgúns casos de proba simple

55
00:02:58,920 --> 00:03:01,530
para estar seguro de que entendeu a pregunta.

56
00:03:01,530 --> 00:03:05,510
Traballando a través de algúns casos de proba tamén lle dará unha intuición sobre como solucionar este problema.

57
00:03:05,510 --> 00:03:11,210
Pode até descubrir algúns patróns para axudar a resolver o problema.

58
00:03:11,210 --> 00:03:14,500
A súa gran Consello é non ficar frustrado.

59
00:03:14,500 --> 00:03:17,060
Non sexa errado.

60
00:03:17,060 --> 00:03:19,060
Entrevistas son un reto, pero a peor cousa que pode facer,

61
00:03:19,060 --> 00:03:23,330
ademais de ser silencioso, é para ser visiblemente frustrado.

62
00:03:23,330 --> 00:03:27,410
Non quere dar a impresión de que a un entrevistador.

63
00:03:27,410 --> 00:03:33,960
Unha cousa que - así, moitas persoas, cando eles entran nunha entrevista,

64
00:03:33,960 --> 00:03:37,150
eles tentan tratar de atopar a mellor solución en primeiro lugar,

65
00:03:37,150 --> 00:03:39,950
cando, en realidade, hai normalmente unha solución moi evidente.

66
00:03:39,950 --> 00:03:43,500
Pode ser lento, pode ser ineficiente, pero ten que só afirmar que,

67
00:03:43,500 --> 00:03:46,210
Só para que vostede un punto de partida para traballar mellor.

68
00:03:46,210 --> 00:03:48,270
Ademais, a apuntar para fóra a solución é lenta, en termos de

69
00:03:48,270 --> 00:03:52,160
O gran complexidade de tempo ou a complexidade do espazo,

70
00:03:52,160 --> 00:03:54,450
ha demostrar a entrevistador que entenda

71
00:03:54,450 --> 00:03:57,510
estas cuestións ao escribir código.

72
00:03:57,510 --> 00:04:01,440
Polo tanto, non teña medo de vir cara arriba con o máis simple algoritmo de primeira

73
00:04:01,440 --> 00:04:04,950
e, entón, traballar mellor a partir de aí.

74
00:04:04,950 --> 00:04:09,810
Todas as preguntas ata agora? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Entón imos mergullar no noso primeiro problema.

76
00:04:11,650 --> 00:04:14,790
"Dado un conxunto de n enteiros, escriba unha función que embaralha a matriz

77
00:04:14,790 --> 00:04:20,209
en tal lugar que todas as permutacións dos n enteiros son igualmente probables. "

78
00:04:20,209 --> 00:04:23,470
E asumir que ten dispoñible un xerador de número aleatorio

79
00:04:23,470 --> 00:04:30,980
que xera un número enteiro na gama de 0 a i, gama da metade.

80
00:04:30,980 --> 00:04:32,970
Será que todo o mundo entender esta cuestión?

81
00:04:32,970 --> 00:04:39,660
Eu darlle un array de enteiros n, e quero que embaralhar-lo.

82
00:04:39,660 --> 00:04:46,050
No meu directorio, escribín algúns programas para demostrar o que quero dicir.

83
00:04:46,050 --> 00:04:48,910
Eu estou indo a barallar unha matriz de 20 elementos,

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

85
00:04:52,490 --> 00:04:57,050
e quero que a saída dunha lista como esta.

86
00:04:57,050 --> 00:05:02,890
Entón, esta é a miña matriz entrada clasificada, e quero que embaralhar-lo.

87
00:05:02,890 --> 00:05:07,070
Nós imos facelo de novo.

88
00:05:07,070 --> 00:05:13,780
Será que todo o mundo entendeu a pregunta? Okay.

89
00:05:13,780 --> 00:05:16,730
Entón cabe a vostede.

90
00:05:16,730 --> 00:05:21,220
Cales son algunhas ideas? Podes facelo como n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Aberto a suxestións.

92
00:05:34,400 --> 00:05:37,730
Okay. Entón, unha idea, suxerida polo Emmy,

93
00:05:37,730 --> 00:05:45,300
é primeiro calcular un número aleatorio, enteiro aleatorio, nun intervalo de 0 a 20.

94
00:05:45,300 --> 00:05:49,840
Así, asumir a nosa matriz ten unha lonxitude de 20.

95
00:05:49,840 --> 00:05:54,800
No noso diagrama de 20 elementos,

96
00:05:54,800 --> 00:05:58,560
Esta é a nosa matriz de entrada.

97
00:05:58,560 --> 00:06:04,590
E agora, a suxestión é crear unha nova matriz,

98
00:06:04,590 --> 00:06:08,440
por iso esta será a matriz de saída.

99
00:06:08,440 --> 00:06:12,880
Está baseado no I retornado por Rand -

100
00:06:12,880 --> 00:06:17,580
Entón, se eu era, imos dicir, 17,

101
00:06:17,580 --> 00:06:25,640
copiar o elemento 17 para a primeira posición.

102
00:06:25,640 --> 00:06:30,300
Agora necesitamos borrar - necesitamos cambiar todos os elementos aquí

103
00:06:30,300 --> 00:06:36,920
de forma que temos unha lagoa ao final e non hai buratos no medio.

104
00:06:36,920 --> 00:06:39,860
E agora nós repita o proceso.

105
00:06:39,860 --> 00:06:46,360
Agora imos escoller un novo enteiro aleatorio entre 0 e 19.

106
00:06:46,360 --> 00:06:52,510
Temos un i novo aquí, e copiamos este elemento para esa posición.

107
00:06:52,510 --> 00:07:00,960
Entón cambiamos os elementos sobre os e repita o proceso ata que temos a nosa gama completa de novo.

108
00:07:00,960 --> 00:07:05,890
Cal é o tempo de execución deste algoritmo?

109
00:07:05,890 --> 00:07:08,110
Ben, imos considerar o impacto desta.

110
00:07:08,110 --> 00:07:10,380
Estamos cambiando a cada elemento.

111
00:07:10,380 --> 00:07:16,800
Cando eliminar esta i, estamos cambiando todos os elementos despois á esquerda.

112
00:07:16,800 --> 00:07:21,600
E iso é un O custo (n)

113
00:07:21,600 --> 00:07:26,100
porque o que se elimina o primeiro elemento?

114
00:07:26,100 --> 00:07:29,670
Así, para cada retirada, eliminar -

115
00:07:29,670 --> 00:07:32,170
Cada retirada incorre nunha operación de O (n),

116
00:07:32,170 --> 00:07:41,520
e unha vez que temos n remocións, iso leva a un barallar O (n ^ 2).

117
00:07:41,520 --> 00:07:49,550
Okay. Entón bo comezo. Bo comezo.

118
00:07:49,550 --> 00:07:55,290
>> Outra suxestión é usar algo coñecido como o shuffle Knuth,

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

120
00:07:57,540 --> 00:07:59,630
E é realmente un shuffle tempo lineal.

121
00:07:59,630 --> 00:08:02,200
E a idea é moi semellante.

122
00:08:02,200 --> 00:08:05,160
Unha vez máis, temos a nosa matriz de entrada,

123
00:08:05,160 --> 00:08:08,580
pero en vez de utilizar dúas matrices para a entrada / saída,

124
00:08:08,580 --> 00:08:13,590
usamos a primeira porción da matriz para controlar a porción embaralhadas,

125
00:08:13,590 --> 00:08:18,400
e estamos a seguir, e despois deixamos o resto da nosa matriz para a parte unshuffled.

126
00:08:18,400 --> 00:08:24,330
Entón, aquí está o que quero dicir. Comezamos con - podemos escoller un i,

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

128
00:08:30,910 --> 00:08:36,150
O noso actual do punteiro está apuntando para o primeiro índice.

129
00:08:36,150 --> 00:08:39,590
Nós escoller algúns aquí i

130
00:08:39,590 --> 00:08:42,740
e agora imos cambiar.

131
00:08:42,740 --> 00:08:47,690
Así, se este era 5 e esta foi 4,

132
00:08:47,690 --> 00:08:57,150
a matriz resultante terá 5 aquí e 4 aquí.

133
00:08:57,150 --> 00:09:00,390
E agora, notamos un marcador aquí.

134
00:09:00,390 --> 00:09:05,770
Todo para a esquerda é embaralhado,

135
00:09:05,770 --> 00:09:15,160
e todo a dereita está unshuffled.

136
00:09:15,160 --> 00:09:17,260
E agora podemos repetir o proceso.

137
00:09:17,260 --> 00:09:25,210
Nós escoller un índice chou entre 1 e 20 agora.

138
00:09:25,210 --> 00:09:30,650
Entón supoño que o noso novo i é aquí.

139
00:09:30,650 --> 00:09:39,370
Agora imos cambiar este i coa nosa posición actual de novo aquí.

140
00:09:39,370 --> 00:09:44,790
Entón nós facemos un troco de e cara atrás como este.

141
00:09:44,790 --> 00:09:51,630
Deixe-me traer o código para facelo máis concreto.

142
00:09:51,630 --> 00:09:55,290
Nós comezamos coa nosa selección de i -

143
00:09:55,290 --> 00:09:58,370
comezamos con i igual a 0, nós escoller un lugar ao chou j

144
00:09:58,370 --> 00:10:02,420
na porción unshuffled da matriz, i an-1.

145
00:10:02,420 --> 00:10:07,280
Entón, se eu estou aquí, escoller un índice chou entre aquí e no resto da matriz,

146
00:10:07,280 --> 00:10:12,410
e trocamos.

147
00:10:12,410 --> 00:10:17,550
Este é todo o código necesario para barallar a súa matriz.

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

149
00:10:21,670 --> 00:10:25,530
>> Ben, unha pregunta é necesaria, por que iso é correcto?

150
00:10:25,530 --> 00:10:28,360
Por que todas as permutacións igualmente probables?

151
00:10:28,360 --> 00:10:30,410
E eu non vou pasar pola proba diso,

152
00:10:30,410 --> 00:10:35,970
pero moitos problemas en ciencia da computación pode ser comprobada a través de indución.

153
00:10:35,970 --> 00:10:38,520
Como moitos de vostedes está familiarizado coa indución?

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

155
00:10:40,590 --> 00:10:43,610
Así, pode probar a corrección do algoritmo por indución simple,

156
00:10:43,610 --> 00:10:49,540
onde a súa hipótese de indución sería, supoña que

157
00:10:49,540 --> 00:10:53,290
meu shuffle retorna todas as permutacións igualmente probable

158
00:10:53,290 --> 00:10:56,120
ata elementos que primeiro.

159
00:10:56,120 --> 00:10:58,300
Agora, considere i + 1.

160
00:10:58,300 --> 00:11:02,550
E polo xeito que escollemos o noso índice j para intercambiar,

161
00:11:02,550 --> 00:11:05,230
iso leva a - e entón traballar os detalles,

162
00:11:05,230 --> 00:11:07,390
polo menos, unha proba chea de porque este algoritmo retorna

163
00:11:07,390 --> 00:11:12,800
Cada intercambio con probabilidade igualmente probables.

164
00:11:12,800 --> 00:11:15,940
>> Todo o problema, mesmo ao lado.

165
00:11:15,940 --> 00:11:19,170
Así, "dado un array de enteiros, postive, cero, negativo,

166
00:11:19,170 --> 00:11:21,290
escribir unha función que calcula a suma máxima

167
00:11:21,290 --> 00:11:24,720
de calquera subarray continueous da matriz de entrada. "

168
00:11:24,720 --> 00:11:28,370
Un exemplo aquí é, no caso de que todos os números son positivos,

169
00:11:28,370 --> 00:11:31,320
a continuación, actualmente a mellor opción é levar todo o conxunto.

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

171
00:11:34,690 --> 00:11:36,780
Cando ten algúns aspectos negativos alí,

172
00:11:36,780 --> 00:11:38,690
neste caso, nós só queremos os dous primeiros

173
00:11:38,690 --> 00:11:44,590
porque escoller -1 e / ou -3 traerá nosa suma abaixo.

174
00:11:44,590 --> 00:11:48,120
Ás veces, pode ter que comezar no medio da matriz.

175
00:11:48,120 --> 00:11:53,500
Ás veces queremos elixir nada, pero o mellor é non tomar nada.

176
00:11:53,500 --> 00:11:56,490
E ás veces é mellor tomar a caída,

177
00:11:56,490 --> 00:12:07,510
porque a cousa despois que é super grande. Entón, algunha idea?

178
00:12:07,510 --> 00:12:10,970
(Estudante, inintelixible) >> Yeah.

179
00:12:10,970 --> 00:12:13,560
E se eu non tomar -1.

180
00:12:13,560 --> 00:12:16,170
A continuación, eu escollo 1.000 e 20.000,

181
00:12:16,170 --> 00:12:18,630
ou eu só escoller o 3 millóns.

182
00:12:18,630 --> 00:12:20,760
Ben, a mellor opción é levar todos os números.

183
00:12:20,760 --> 00:12:24,350
Este -1, a pesar de ser negativo,

184
00:12:24,350 --> 00:12:31,340
toda a suma é maior que os que non a tomar -1.

185
00:12:31,340 --> 00:12:36,460
Polo tanto, unha das suxestións que eu mencionen anteriormente era para dicir o evidente claramente

186
00:12:36,460 --> 00:12:40,540
É a solución de forza bruta en primeiro lugar.

187
00:12:40,540 --> 00:12:44,340
Cal é a solución de forza bruta neste problema? Si?

188
00:12:44,340 --> 00:12:46,890
[Jane] Ben, eu creo que a solución de forza bruta

189
00:12:46,890 --> 00:12:52,600
sería sumar todas as combinacións posíbeis (inintelixible).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Entón Jane idea é levar todos os posibles -

191
00:12:58,250 --> 00:13:01,470
Estou parafraseando - é levar cada subarray posible, continua,

192
00:13:01,470 --> 00:13:07,840
calcular a súa suma, a continuación, tomar o máximo de todas as posibles subarrays continuas.

193
00:13:07,840 --> 00:13:13,310
O que identifica un subarray na miña matriz de entrada?

194
00:13:13,310 --> 00:13:17,380
Como dúas cousas que eu teño? Si?

195
00:13:17,380 --> 00:13:19,970
(Estudante, inintelixible) dereito. >>

196
00:13:19,970 --> 00:13:22,130
Un límite inferior no índice e un índice límite superior

197
00:13:22,130 --> 00:13:28,300
determina únicamente unha submatriz continua.

198
00:13:28,300 --> 00:13:31,400
[Estudante Feminino] Estamos estimando que é unha matriz de números únicos?

199
00:13:31,400 --> 00:13:34,280
[Yu] Non Entón, a pregunta é, será que estamos asumindo a nosa matriz -

200
00:13:34,280 --> 00:13:39,000
é a nosa matriz de todos os números orixinais, ea resposta é non.

201
00:13:39,000 --> 00:13:43,390
>> Se usarmos a nosa solución de forza bruta, entón os índices de inicio / fin

202
00:13:43,390 --> 00:13:47,200
exclusivamente determina nosa subarray continua.

203
00:13:47,200 --> 00:13:51,680
Entón, se nós iterar para todas as entradas posíbeis de inicio,

204
00:13:51,680 --> 00:13:58,320
e para todas as entradas finais> ou = para comezar, e <n,

205
00:13:58,320 --> 00:14:05,570
vostede calcular a suma, e entón tomamos o importe máximo que vimos ata agora.

206
00:14:05,570 --> 00:14:07,880
Isto está claro?

207
00:14:07,880 --> 00:14:12,230
Que é o gran esta solución?

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

209
00:14:16,660 --> 00:14:18,860
Non é así N ^ 2.

210
00:14:18,860 --> 00:14:25,250
Nótese que nós iterar de 0 a n,

211
00:14:25,250 --> 00:14:27,520
de xeito que é un loop for.

212
00:14:27,520 --> 00:14:35,120
Repetimos novamente case o comezo ata o final, outro para loop.

213
00:14:35,120 --> 00:14:37,640
E agora, dentro diso, temos que resumir cada entrada,

214
00:14:37,640 --> 00:14:43,810
de xeito que é outro para loop. Polo tanto, temos tres aniñados loops, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Iso vale como un punto de partida.

216
00:14:46,560 --> 00:14:53,180
A nosa solución non é peor que n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Será que todo o mundo entender a solución de forza bruta?

218
00:14:55,480 --> 00:14:59,950
>> Okay. A mellor solución é usar unha idea chamada de programación dinámica.

219
00:14:59,950 --> 00:15:03,040
Se tomar CS124, que é Algoritmos e estruturas de datos,

220
00:15:03,040 --> 00:15:05,680
vai converterse moi familiarizado con esta técnica.

221
00:15:05,680 --> 00:15:12,190
E a idea é, tentar construír solucións para pequenos problemas, en primeiro lugar.

222
00:15:12,190 --> 00:15:17,990
O que quero dicir con isto é, actualmente temos que se preocupar con dúas cousas: inicio e finalización.

223
00:15:17,990 --> 00:15:29,340
E iso é irritante. O que se podería librarse dun deses parámetros?

224
00:15:29,340 --> 00:15:32,650
Unha idea é - nós dado o noso problema orixinal,

225
00:15:32,650 --> 00:15:37,470
atopar a suma máxima de calquera subarray no intervalo [O, N-1].

226
00:15:37,470 --> 00:15:47,400
E agora temos un novo subproblema, onde sabemos que, na nosa actual índice i,

227
00:15:47,400 --> 00:15:52,520
sabemos que temos que concluír alí. O noso subarray debe terminar o índice actual.

228
00:15:52,520 --> 00:15:57,640
Así, o problema restante é, por onde debemos comezar a nosa subarray?

229
00:15:57,640 --> 00:16:05,160
Será que isto ten sentido? Okay.

230
00:16:05,160 --> 00:16:12,030
Entón eu codificado isto, e imos ver o que isto significa.

231
00:16:12,030 --> 00:16:16,230
No codirectory, hai un programa chamado subarray,

232
00:16:16,230 --> 00:16:19,470
e leva o número de elementos,

233
00:16:19,470 --> 00:16:25,550
e retorna a suma subarray máxima na miña lista de embaralhadas.

234
00:16:25,550 --> 00:16:29,920
Polo tanto, neste caso, a nosa subarray máxima é de 3.

235
00:16:29,920 --> 00:16:34,850
E que se toma só usando 2 e 1.

236
00:16:34,850 --> 00:16:38,050
Imos executa-lo de novo. É tamén 3.

237
00:16:38,050 --> 00:16:40,950
Pero esta vez, observe como chegamos a 3.

238
00:16:40,950 --> 00:16:46,690
Pegamos o - nós tomamos a 3 en si

239
00:16:46,690 --> 00:16:49,980
porque está rodeado por negativos en ambos os lados,

240
00:16:49,980 --> 00:16:55,080
que vai traer unha suma <3.

241
00:16:55,080 --> 00:16:57,820
Imos correr en 10 elementos.

242
00:16:57,820 --> 00:17:03,200
Esta vez é 7, tomamos a 3 e 4 de liderado.

243
00:17:03,200 --> 00:17:09,450
Esta vez é 8, e obtemos que tomando 1, 4 e 3.

244
00:17:09,450 --> 00:17:16,310
Entón, para darlle unha intuición sobre como podemos solucionar este problema transformado,

245
00:17:16,310 --> 00:17:18,890
imos dar un ollo neste subarray.

246
00:17:18,890 --> 00:17:23,460
Estamos dando esta matriz de entrada, e sabemos que a resposta é 8.

247
00:17:23,460 --> 00:17:26,359
Tomamos o 1, 4 e 3.

248
00:17:26,359 --> 00:17:29,090
Pero imos ver como é que realmente teño esa resposta.

249
00:17:29,090 --> 00:17:34,160
Imos ollar para o subarray máxima que terminou en cada un destes índices.

250
00:17:34,160 --> 00:17:40,780
Cal é a subarray máxima que ten que rematar na primeira posición?

251
00:17:40,780 --> 00:17:46,310
[Estudante] Cero. >> Cero. Só non tomar a -5.

252
00:17:46,310 --> 00:17:50,210
Aquí vai ser 0 tamén. Si?

253
00:17:50,210 --> 00:17:56,470
(Inintelixible, estudante)

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

255
00:17:58,960 --> 00:18:03,220
Polo tanto, este é un grupo 2, é dicir un -3.

256
00:18:03,220 --> 00:18:08,690
Okay. Entón -4, o que é o subarray máxima para acabar con esa posición

257
00:18:08,690 --> 00:18:12,910
onde -4 é en? Cero.

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

259
00:18:22,570 --> 00:18:28,060
Agora teño que rematar no local onde está -2.

260
00:18:28,060 --> 00:18:39,330
Entón, 6, 5, 7, eo último é de 4.

261
00:18:39,330 --> 00:18:43,480
Sabendo que estas son as miñas entradas

262
00:18:43,480 --> 00:18:48,130
para o problema transformou onde debe rematar en cada un destes índices,

263
00:18:48,130 --> 00:18:51,410
entón a miña resposta final é xusto, facer unha pescudas en todo,

264
00:18:51,410 --> 00:18:53,580
e ter o número máximo.

265
00:18:53,580 --> 00:18:55,620
Polo tanto, neste caso, é 8.

266
00:18:55,620 --> 00:19:00,010
Isto implica que o subarray máxima remata neste índice,

267
00:19:00,010 --> 00:19:04,970
e comezou en algún lugar antes.

268
00:19:04,970 --> 00:19:09,630
Será que todo o mundo entender iso subarray converter?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Ben, imos descubrir a recorrencia para iso.

270
00:19:22,160 --> 00:19:27,990
Imos considerar só as entradas primeiros.

271
00:19:27,990 --> 00:19:35,930
Entón, aquí foi de 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
E entón houbo un -2 aquí, e que trouxo para abaixo a 6.

273
00:19:39,790 --> 00:19:50,800
Entón, se eu chamar a entrada na posición i subproblema (i),

274
00:19:50,800 --> 00:19:54,910
como podo utilizar a resposta a un subproblema anterior

275
00:19:54,910 --> 00:19:59,360
Para responder a esta subproblema?

276
00:19:59,360 --> 00:20:04,550
Se eu ollar para, imos dicir, esa entrada.

277
00:20:04,550 --> 00:20:09,190
Como podo calcular a resposta 6 mirando

278
00:20:09,190 --> 00:20:18,780
unha combinación desa matriz e as respostas a subproblemas anteriores desta serie? Si?

279
00:20:18,780 --> 00:20:22,800
[Estudante Feminino] Vostede toma a matriz de sumas

280
00:20:22,800 --> 00:20:25,430
na posición correcta antes de que, para que o 8,

281
00:20:25,430 --> 00:20:32,170
e entón engade o subproblema actual.

282
00:20:32,170 --> 00:20:36,460
[Yu] Entón a suxestión é mirar para estes dous números,

283
00:20:36,460 --> 00:20:40,090
Este número é este número.

284
00:20:40,090 --> 00:20:50,130
Polo tanto, este 8 refírese á resposta a subproblema (i - 1).

285
00:20:50,130 --> 00:20:57,300
E imos chamar miña entrada matriz A.

286
00:20:57,300 --> 00:21:01,470
Co fin de atopar unha submatriz máxima que remata na posición i,

287
00:21:01,470 --> 00:21:03,980
Eu teño dúas opcións: eu pode continuar subarray

288
00:21:03,980 --> 00:21:09,790
que rematou no índice anterior, ou iniciar unha nova matriz.

289
00:21:09,790 --> 00:21:14,190
Se eu fose para continuar a subarray que comezou no índice anterior,

290
00:21:14,190 --> 00:21:19,260
a continuación, o importe máximo que se pode conseguir é a resposta para o subproblema anterior

291
00:21:19,260 --> 00:21:24,120
máis a entrada da matriz actual.

292
00:21:24,120 --> 00:21:27,550
Pero eu tamén ten a opción de iniciar un novo subarray,

293
00:21:27,550 --> 00:21:30,830
caso en que a suma é igual a 0.

294
00:21:30,830 --> 00:21:42,860
Polo tanto, a resposta é o máximo de 0, subproblema i - 1, máis a entrada da matriz actual.

295
00:21:42,860 --> 00:21:46,150
Será que esa recorrencia ten sentido?

296
00:21:46,150 --> 00:21:50,840
O noso recorrencia, coma acabamos de descubrir, é subproblema i

297
00:21:50,840 --> 00:21:54,740
é igual ao máximo do subproblema anterior máis a miña entrada matriz actual,

298
00:21:54,740 --> 00:22:01,490
o que significa que segue a subarray anterior,

299
00:22:01,490 --> 00:22:07,250
ou 0, iniciar un subarray novo no meu índice actual.

300
00:22:07,250 --> 00:22:10,060
E unha vez que nós construímos esta táboa de solucións, entón a nosa resposta final,

301
00:22:10,060 --> 00:22:13,950
basta facer unha pescudas lineal en toda a matriz subproblema

302
00:22:13,950 --> 00:22:19,890
e ter o número máximo.

303
00:22:19,890 --> 00:22:23,330
Esta é unha implementación exacta do que eu dixen.

304
00:22:23,330 --> 00:22:27,320
Entón, creamos unha matriz subproblema novo, subproblemas.

305
00:22:27,320 --> 00:22:32,330
A primeira entrada é 0 ou a primeira entrada, o máximo destes dous.

306
00:22:32,330 --> 00:22:35,670
E para o resto dos subproblemas

307
00:22:35,670 --> 00:22:39,810
usan a repetición exacta que acaba de descubrir.

308
00:22:39,810 --> 00:22:49,960
Agora imos calcular o valor máximo da nosa matriz subproblemas, e esa é a nosa resposta final.

309
00:22:49,960 --> 00:22:54,130
>> Entón, canto espazo estamos usando este algoritmo?

310
00:22:54,130 --> 00:23:01,470
Se só toma CS50, entón pode non ter discutido moito espazo.

311
00:23:01,470 --> 00:23:07,750
Ben, unha cousa a notar é que eu chamei malloc aquí con tamaño n.

312
00:23:07,750 --> 00:23:13,590
O que isto lle suxire?

313
00:23:13,590 --> 00:23:17,450
Este algoritmo utiliza o espazo linear.

314
00:23:17,450 --> 00:23:21,030
Podemos facer mellor?

315
00:23:21,030 --> 00:23:30,780
¿Hai algunha cousa que entender o que é necesario para calcular a resposta final?

316
00:23:30,780 --> 00:23:33,290
Eu creo que a mellor pregunta é, que información

317
00:23:33,290 --> 00:23:40,680
non necesitamos levar todo o camiño ata o final?

318
00:23:40,680 --> 00:23:44,280
Agora, se miramos para estas dúas liñas,

319
00:23:44,280 --> 00:23:47,720
que só se preocupan o subproblema anterior,

320
00:23:47,720 --> 00:23:50,910
e nós só se preocupan o máximo que vimos ata agora.

321
00:23:50,910 --> 00:23:53,610
Para calcular a resposta final, nós non necesitamos de toda a matriz.

322
00:23:53,610 --> 00:23:57,450
Nós só necesitamos do último número, dous últimos números.

323
00:23:57,450 --> 00:24:02,630
Último número para a matriz subproblema, e último número ao máximo.

324
00:24:02,630 --> 00:24:07,380
Entón, en realidade, pode-se fundir eses lazos xuntos

325
00:24:07,380 --> 00:24:10,460
e ir de espazo a espazo lineal constante.

326
00:24:10,460 --> 00:24:15,830
Suma actual, ata agora, aquí, substitúe a función do subproblema, a nosa matriz subproblema.

327
00:24:15,830 --> 00:24:20,020
Suma tan actual, ata agora, é a resposta para o subproblema anterior.

328
00:24:20,020 --> 00:24:23,450
E que suma ata agora toma o lugar do noso máximo.

329
00:24:23,450 --> 00:24:28,100
Nós calcular o valor máximo a medida que avanzamos.

330
00:24:28,100 --> 00:24:30,890
E así imos de espazo lineal para o espazo constante,

331
00:24:30,890 --> 00:24:36,650
e tamén temos unha solución para o noso problema lineal subarray.

332
00:24:36,650 --> 00:24:40,740
>> Estes tipos de preguntas que vai ter durante unha entrevista.

333
00:24:40,740 --> 00:24:44,450
Cal é a complexidade de tempo, o que é a complexidade do espazo?

334
00:24:44,450 --> 00:24:50,600
Podes facer mellor? Existen cousas que son innecesarios para manter en torno?

335
00:24:50,600 --> 00:24:55,270
Eu fixen isto para destacar análises que ten que tomar no seu propio

336
00:24:55,270 --> 00:24:57,400
como se está a traballar con estes problemas.

337
00:24:57,400 --> 00:25:01,710
Sempre estar se pregunta: "Podo facer mellor?"

338
00:25:01,710 --> 00:25:07,800
En realidade, podemos facer mellor que iso?

339
00:25:07,800 --> 00:25:10,730
Unha especie de pegadinha. Vostede non pode, porque precisa

340
00:25:10,730 --> 00:25:13,590
Polo menos ler a entrada para o problema.

341
00:25:13,590 --> 00:25:15,570
Así, o feito de que precisa ler polo menos a entrada para o problema

342
00:25:15,570 --> 00:25:19,580
significa que non pode facer mellor do que o tempo lineal,

343
00:25:19,580 --> 00:25:22,870
e non pode facer mellor do que o espazo constante.

344
00:25:22,870 --> 00:25:27,060
Polo tanto, este é, de feito, a mellor solución para este problema.

345
00:25:27,060 --> 00:25:33,040
Preguntas? Okay.

346
00:25:33,040 --> 00:25:35,190
>> Problema do mercado de accións:

347
00:25:35,190 --> 00:25:38,350
"Dado un conxunto de n enteiros, positivos, cero ou negativo,

348
00:25:38,350 --> 00:25:41,680
que representan o prezo dunha acción máis n días

349
00:25:41,680 --> 00:25:44,080
escribir unha función para calcular o beneficio máximo que pode facer

350
00:25:44,080 --> 00:25:49,350
unha vez que compra e vende exactamente un stock dentro deses n días. "

351
00:25:49,350 --> 00:25:51,690
Esencialmente, queremos mercar na baixa e vender na alta.

352
00:25:51,690 --> 00:25:58,580
E queremos descubrir o mellor beneficio que podemos facer.

353
00:25:58,580 --> 00:26:11,500
Volvendo ao meu punta, o que é a resposta máis simple inmediatamente claro, pero é lento?

354
00:26:11,500 --> 00:26:17,690
Si? (Estudante, inintelixible) >> Si

355
00:26:17,690 --> 00:26:21,470
>> Entón tería só que ir e ollar para os prezos das accións

356
00:26:21,470 --> 00:26:30,550
en cada punto no tempo, (inintelixible).

357
00:26:30,550 --> 00:26:33,990
[Yu] Ok, entón a súa solución - súa suxestión de computación

358
00:26:33,990 --> 00:26:37,380
menor e computar o maior non significa necesariamente traballar

359
00:26:37,380 --> 00:26:42,470
porque o máis elevado poden ocorrer antes de máis baixa.

360
00:26:42,470 --> 00:26:47,340
Entón, cal é a solución de forza bruta para este problema?

361
00:26:47,340 --> 00:26:53,150
Cales son as dúas cousas que eu teño determinar de xeito único o beneficio que fago? Dereito.

362
00:26:53,150 --> 00:26:59,410
A solución de forza bruta é - oh, entón, a suxestión de Jorge é que só teño dous días

363
00:26:59,410 --> 00:27:02,880
exclusivamente para determinar o beneficio destes dous días.

364
00:27:02,880 --> 00:27:06,660
Entón imos calcular cada par, como comprar / vender,

365
00:27:06,660 --> 00:27:12,850
calcular o beneficio, o que pode ser negativo ou positivo ou cero.

366
00:27:12,850 --> 00:27:18,000
Calcule o beneficio máximo que facemos despois da iteração sobre todos os pares de días.

367
00:27:18,000 --> 00:27:20,330
Esa será a nosa resposta final.

368
00:27:20,330 --> 00:27:25,730
E que a solución vai ser o (n ^ 2), porque non hai n escoller dous pares -

369
00:27:25,730 --> 00:27:30,270
de días que pode escoller entre os días finais.

370
00:27:30,270 --> 00:27:32,580
Ok, entón eu non vou pasar por riba da solución de forza bruta aquí.

371
00:27:32,580 --> 00:27:37,420
Eu vou dicir-lle que hai unha solución n log n.

372
00:27:37,420 --> 00:27:45,550
O algoritmo que sabe actualmente que é n log n?

373
00:27:45,550 --> 00:27:50,730
Non é unha pregunta capciosa.

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

375
00:27:54,790 --> 00:27:57,760
e, en realidade, unha forma de resolver este problema é usar

376
00:27:57,760 --> 00:28:04,400
un tipo merge sort de idea chamada, en xeral, dividir e conquistar.

377
00:28:04,400 --> 00:28:07,570
E a idea é a seguinte.

378
00:28:07,570 --> 00:28:12,400
Quere calcular a mellor compra / venda par na media esquerda.

379
00:28:12,400 --> 00:28:16,480
Atopar o mellor beneficio que pode facer, só co n primeiro en dous días.

380
00:28:16,480 --> 00:28:19,780
Entón quere oompute mellor compra / venda par na metade dereita,

381
00:28:19,780 --> 00:28:23,930
para n último dous días.

382
00:28:23,930 --> 00:28:32,400
E agora a pregunta é, como se funden estas solucións xuntos de novo?

383
00:28:32,400 --> 00:28:36,320
Si? (Inintelixible, estudante)

384
00:28:36,320 --> 00:28:49,890
Ok >>. Entón deixe-me tirar unha foto.

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

386
00:29:03,870 --> 00:29:06,450
>> Exactamente. Resolución George é exactamente correcto.

387
00:29:06,450 --> 00:29:10,040
Así, a súa suxestión é, primeiro calcular o mellor par de compra / venda,

388
00:29:10,040 --> 00:29:16,050
e que ocorre na metade esquerda, entón imos chamar iso de esquerda, á esquerda.

389
00:29:16,050 --> 00:29:20,790
Mellor mercar / vender par que ocorre na media dereita.

390
00:29:20,790 --> 00:29:25,180
Pero se se compara só estes dous números, estamos perdendo o caso

391
00:29:25,180 --> 00:29:30,460
onde mercar aquí e vender en algún lugar do media dereita.

392
00:29:30,460 --> 00:29:33,810
Nós compramos na metade esquerda, vender na metade dereita.

393
00:29:33,810 --> 00:29:38,490
E a mellor forma de calcular o mellor par de compra / venda que abrangue ambas as metades

394
00:29:38,490 --> 00:29:43,480
é calcular o mínimo aquí e calcular o valor máximo aquí

395
00:29:43,480 --> 00:29:45,580
e tomar a súa diferenza.

396
00:29:45,580 --> 00:29:50,850
Así, os dous casos en que o par de compra / venda ocorre só aquí,

397
00:29:50,850 --> 00:30:01,910
Só aquí, ou en ambas as metades é definida por estas tres números.

398
00:30:01,910 --> 00:30:06,450
Así, o noso algoritmo para fundir nosas solucións de volta,

399
00:30:06,450 --> 00:30:08,350
queremos calcular o mellor par de compra / venda

400
00:30:08,350 --> 00:30:13,120
onde mercar na metade esquerda e vender na media dereita.

401
00:30:13,120 --> 00:30:16,740
E a mellor forma de facelo é calcular o menor prezo no primeiro semestre,

402
00:30:16,740 --> 00:30:20,360
o prezo máis alto na media dereita, e tomar a súa diferenza.

403
00:30:20,360 --> 00:30:25,390
Os beneficios resultantes tres, eses tres números, aproveitar o máximo de tres,

404
00:30:25,390 --> 00:30:32,720
e que é o mellor beneficio que pode facer sobre estes primeiros días e fin.

405
00:30:32,720 --> 00:30:36,940
Aquí as liñas importantes están en vermello.

406
00:30:36,940 --> 00:30:41,160
Esta é unha chamada recursiva para calcular a resposta na media esquerda.

407
00:30:41,160 --> 00:30:44,760
Esta é unha chamada recursiva para calcular a resposta na media dereita.

408
00:30:44,760 --> 00:30:50,720
Estes dous circuítos para calcular o mínimo eo máximo na metade esquerda e dereita, respectivamente.

409
00:30:50,720 --> 00:30:54,970
Agora eu calcular o beneficio que abrangue as dúas metades,

410
00:30:54,970 --> 00:31:00,530
ea resposta final é o máximo de tres.

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

412
00:31:04,120 --> 00:31:06,420
>> Entón, por suposto, temos un algoritmo, pero a gran cuestión é,

413
00:31:06,420 --> 00:31:08,290
o que é a complexidade de tempo deste?

414
00:31:08,290 --> 00:31:16,190
E a razón pola que eu mencionen merge sort é que esa forma de dividir a resposta

415
00:31:16,190 --> 00:31:19,200
en dous e, a continuación, fundindo as nosas solucións xuntos de novo

416
00:31:19,200 --> 00:31:23,580
é exactamente a forma de clasificación por intercalação.

417
00:31:23,580 --> 00:31:33,360
Entón deixe-me pasar o tempo.

418
00:31:33,360 --> 00:31:41,340
Se definimos unha función t (n) para ser o número de etapas

419
00:31:41,340 --> 00:31:50,010
de n días

420
00:31:50,010 --> 00:31:54,350
nosas dúas chamadas recursivas

421
00:31:54,350 --> 00:32:00,460
son cada custará t (n / 2),

422
00:32:00,460 --> 00:32:03,540
e hai dúas desas conexións.

423
00:32:03,540 --> 00:32:10,020
Agora eu teño calcular o valor mínimo da metade esquerda,

424
00:32:10,020 --> 00:32:17,050
que i pode facer en n / 2 hora, máis o máximo da metade dereita.

425
00:32:17,050 --> 00:32:20,820
Entón, este é só o n.

426
00:32:20,820 --> 00:32:25,050
E despois algún traballo constante.

427
00:32:25,050 --> 00:32:27,770
E esta ecuación recorrencia

428
00:32:27,770 --> 00:32:35,560
é exactamente a ecuación de recorrencia para merge sort.

429
00:32:35,560 --> 00:32:39,170
E todos sabemos que tipo de mesclagem é n log n tempo.

430
00:32:39,170 --> 00:32:46,880
Polo tanto, o noso algoritmo é tamén n log n tempo.

431
00:32:46,880 --> 00:32:52,220
Será que esta iteração ten sentido?

432
00:32:52,220 --> 00:32:55,780
Só unha breve recapitulación do presente:

433
00:32:55,780 --> 00:32:59,170
T (n) é o número de pasos para calcular o máximo de lucro

434
00:32:59,170 --> 00:33:02,750
ao longo do día n.

435
00:33:02,750 --> 00:33:06,010
O xeito como nos separamos nosas chamadas recursivas

436
00:33:06,010 --> 00:33:11,980
e chamando a nosa solución nos primeiros días n / 2,

437
00:33:11,980 --> 00:33:14,490
de xeito que é unha chamada,

438
00:33:14,490 --> 00:33:16,940
e, a continuación, chamamos de novo no segundo semestre.

439
00:33:16,940 --> 00:33:20,440
Entón, iso é dúas chamadas.

440
00:33:20,440 --> 00:33:25,310
E, entón, atopar un mínimo na metade esquerda, o que podemos facer en tempo lineal,

441
00:33:25,310 --> 00:33:29,010
atopar o máximo da metade dereita, o que podemos facer en tempo lineal.

442
00:33:29,010 --> 00:33:31,570
Entón N / 2 + n / 2 é só n.

443
00:33:31,570 --> 00:33:36,020
Entón temos un traballo constante, que é como facer aritmética.

444
00:33:36,020 --> 00:33:39,860
Esta ecuación de recorrencia é exactamente a ecuación de recorrencia para merge sort.

445
00:33:39,860 --> 00:33:55,490
Por iso, o noso algoritmo shuffle é tamén n log n.

446
00:33:55,490 --> 00:33:58,520
Entón, canto espazo estamos a usar?

447
00:33:58,520 --> 00:34:04,910
Imos volver para o código.

448
00:34:04,910 --> 00:34:09,420
>> A mellor pregunta é, cantos cadros de pila que xa temos en determinado momento?

449
00:34:09,420 --> 00:34:11,449
Como estamos utilizando a recursividade,

450
00:34:11,449 --> 00:34:23,530
o número de cadros de pila determina a nosa utilización do espazo.

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

452
00:34:29,440 --> 00:34:36,889
Chamamos embaralhe 8,

453
00:34:36,889 --> 00:34:41,580
que ha chamar embaralhe as catro primeiras entradas,

454
00:34:41,580 --> 00:34:46,250
que pode chamar un shuffle nas dúas primeiras entradas.

455
00:34:46,250 --> 00:34:51,550
Polo tanto, a nosa pila é - esta é a nosa pila.

456
00:34:51,550 --> 00:34:54,980
E entón chamamos barallar de novo en 1,

457
00:34:54,980 --> 00:34:58,070
e iso é o que o noso caso base é, por iso, volver inmediatamente.

458
00:34:58,070 --> 00:35:04,700
Será que xa ten máis que esta pila de cadros moitos?

459
00:35:04,700 --> 00:35:08,880
Non porque cada vez que facemos unha invocación,

460
00:35:08,880 --> 00:35:10,770
unha invocación recursiva para shuffle,

461
00:35:10,770 --> 00:35:13,950
dividimos o noso tamaño á metade.

462
00:35:13,950 --> 00:35:17,020
Así, o número máximo de cadros de pila que xa teñen en calquera momento

463
00:35:17,020 --> 00:35:28,460
é da orde de cadros de rexistro n pila.

464
00:35:28,460 --> 00:35:42,460
Cada cadro de pila ten espazo constante,

465
00:35:42,460 --> 00:35:44,410
e, polo tanto, a cantidade de espazo total,

466
00:35:44,410 --> 00:35:49,240
a cantidade máxima de espazo que sempre uso é o espazo (log n)

467
00:35:49,240 --> 00:36:03,040
onde n é o número de días.

468
00:36:03,040 --> 00:36:07,230
>> Agora, sempre pregunta a si mesmo: "Podemos facer mellor?"

469
00:36:07,230 --> 00:36:12,390
E, en particular, podemos reducir tanto a un problema que xa foi resolto?

470
00:36:12,390 --> 00:36:20,040
Unha información: só discutiu outros dous problemas antes diso, e non vai ser shuffle.

471
00:36:20,040 --> 00:36:26,200
Podemos converter este problema do mercado de accións para o problema subarray máxima.

472
00:36:26,200 --> 00:36:40,100
Como podemos facer iso?

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

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

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

476
00:36:53,860 --> 00:36:59,940
Así, o problema subarray máxima,

477
00:36:59,940 --> 00:37:10,610
Estamos á procura de unha suma sobre un subarray continua.

478
00:37:10,610 --> 00:37:16,230
E a suxestión de Emmy para o problema stocks,

479
00:37:16,230 --> 00:37:30,720
considerar os cambios, ou os deltas.

480
00:37:30,720 --> 00:37:37,440
É un retrato diso é - este é o prezo dunha acción,

481
00:37:37,440 --> 00:37:42,610
pero se tomamos a diferenza entre cada día consecutivo -

482
00:37:42,610 --> 00:37:45,200
así vemos que o prezo máximo, o beneficio máximo que podería facer

483
00:37:45,200 --> 00:37:50,070
é comprar aquí e vender aquí.

484
00:37:50,070 --> 00:37:54,240
Pero imos ollar para a continua - imos ollar para o problema subarray.

485
00:37:54,240 --> 00:38:02,510
Entón, aquí, podemos facer - ir de aquí para alí,

486
00:38:02,510 --> 00:38:08,410
temos unha mudanza positiva, e entón ir de aquí ata aquí temos unha variación negativa.

487
00:38:08,410 --> 00:38:14,220
Pero, entón, vai aquí ata aquí temos unha gran mudanza positiva.

488
00:38:14,220 --> 00:38:20,930
E estas son as modificacións que quere sumar-se para recibir o noso beneficio final.

489
00:38:20,930 --> 00:38:25,160
Entón temos cambios máis negativas aquí.

490
00:38:25,160 --> 00:38:29,990
A clave para reducir o noso problema stock no noso problema subarray máxima

491
00:38:29,990 --> 00:38:36,630
é considerar os deltas entre días.

492
00:38:36,630 --> 00:38:40,630
Entón nós creamos unha nova matriz chamada deltas,

493
00:38:40,630 --> 00:38:43,000
arrincar a primeira entrada a 0,

494
00:38:43,000 --> 00:38:46,380
e entón para cada delta (i), deixe que sexa a diferenza

495
00:38:46,380 --> 00:38:52,830
da miña matriz de entrada (i), e matriz (i - 1).

496
00:38:52,830 --> 00:38:55,530
Entón chamamos o noso procedemento de rutina para un subarray máxima

497
00:38:55,530 --> 00:39:01,500
pasando dunha matriz delta.

498
00:39:01,500 --> 00:39:06,440
E porque subarray máxima é de tempo lineal,

499
00:39:06,440 --> 00:39:09,370
e esta redución, este proceso de creación desta matriz delta,

500
00:39:09,370 --> 00:39:11,780
É tamén tempo lineal,

501
00:39:11,780 --> 00:39:19,060
entón a solución final para as accións é O (n) O traballo, ademais de traballo (n), aínda é o traballo (n).

502
00:39:19,060 --> 00:39:23,900
Polo tanto, temos unha solución a tempo lineal para o noso problema.

503
00:39:23,900 --> 00:39:29,610
Será que todo o mundo entender esa transformación?

504
00:39:29,610 --> 00:39:32,140
>> En xeral, é unha boa idea que ten que ter sempre

505
00:39:32,140 --> 00:39:34,290
é tentar reducir un novo problema que está a ver.

506
00:39:34,290 --> 00:39:37,700
Se isto parece familiar para un problema antigo,

507
00:39:37,700 --> 00:39:39,590
tentar reduci-lo a un problema antigo.

508
00:39:39,590 --> 00:39:41,950
E se pode usar todas as ferramentas que usou no vello problema

509
00:39:41,950 --> 00:39:46,450
para resolver o problema novo.

510
00:39:46,450 --> 00:39:49,010
Entón, para pechar, entrevistas técnicas son reto.

511
00:39:49,010 --> 00:39:52,280
Estes problemas son, probablemente, algúns dos problemas máis difíciles

512
00:39:52,280 --> 00:39:54,700
que se pode ver nunha entrevista,

513
00:39:54,700 --> 00:39:57,690
por iso, se non entender todos os problemas que eu só cubertos, está todo ben.

514
00:39:57,690 --> 00:40:01,080
Estes son algúns dos problemas máis difíciles.

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

516
00:40:03,050 --> 00:40:08,170
Eu dei unha morea de problemas no folleto, entón definitivamente comprobar os para fóra.

517
00:40:08,170 --> 00:40:11,690
, E boa sorte nas súas entrevistas. Todos os meus recursos son publicados nesta ligazón,

518
00:40:11,690 --> 00:40:15,220
e un dos meus amigos seniores se ofreceu para facer simulacións de entrevistas técnicas,

519
00:40:15,220 --> 00:40:22,050
por iso, se vostede está interesado, e-mail Will Yao nese enderezo de correo-e.

520
00:40:22,050 --> 00:40:26,070
Se ten algunha dúbida, pode me preguntar.

521
00:40:26,070 --> 00:40:28,780
Vostedes teñen cuestións específicas relacionadas coa entrevistas técnicas

522
00:40:28,780 --> 00:40:38,440
ou os problemas que vimos ata agora?

523
00:40:38,440 --> 00:40:49,910
Okay. Ben, boa sorte nas súas entrevistas.

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