1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminário: 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
Oi a todos, eu sou o Kenny. Atualmente sou informática júnior estudar.

5
00:00:12,420 --> 00:00:17,310
Eu sou um ex-CS TF, e eu desejo que eu tive isso quando eu era um underclassman,

6
00:00:17,310 --> 00:00:19,380
e é por isso que eu estou dando este seminário.

7
00:00:19,380 --> 00:00:21,370
Então eu espero que você goste.

8
00:00:21,370 --> 00:00:23,470
Este seminário é de cerca de entrevistas técnicas,

9
00:00:23,470 --> 00:00:26,650
e todos os meus recursos podem ser encontrados neste link,

10
00:00:26,650 --> 00:00:32,350
este link aqui, um casal de recursos.

11
00:00:32,350 --> 00:00:36,550
Então eu fiz uma lista de problemas, na verdade, alguns problemas.

12
00:00:36,550 --> 00:00:40,800
Também uma página de recursos em geral, onde podemos encontrar dicas

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

14
00:00:42,870 --> 00:00:46,470
dicas sobre o que você deve fazer durante uma entrevista real,

15
00:00:46,470 --> 00:00:51,910
bem como a forma de abordar os problemas e recursos para referência futura.

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

17
00:00:53,980 --> 00:00:58,290
E só para prefaciar este seminário, um aviso,

18
00:00:58,290 --> 00:01:00,690
como este não deveria - sua preparação para entrevistas

19
00:01:00,690 --> 00:01:02,800
não se deve limitar a esta lista.

20
00:01:02,800 --> 00:01:04,750
Isso serve apenas para ser um guia,

21
00:01:04,750 --> 00:01:08,890
e você deve definitivamente dar tudo que eu digo com um grão de sal,

22
00:01:08,890 --> 00:01:14,620
mas também usar tudo que eu costumava ajudá-lo em sua preparação para entrevistas.

23
00:01:14,620 --> 00:01:16,400
>> Eu estou indo para acelerar através dos próximos slides

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

25
00:01:18,650 --> 00:01:23,630
A estrutura de uma entrevista para um postion engenharia 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últiplos ciclos, dependendo da empresa.

28
00:01:29,810 --> 00:01:33,090
Muitas vezes você vai ser a codificação em um quadro branco.

29
00:01:33,090 --> 00:01:35,960
Assim, um quadro branco como este, mas muitas vezes em uma escala menor.

30
00:01:35,960 --> 00:01:38,540
Se você está tendo uma entrevista por telefone, você provavelmente vai estar usando

31
00:01:38,540 --> 00:01:44,030
ou collabedit ou um Google Doc para que eles possam vê-lo ao vivo de codificação

32
00:01:44,030 --> 00:01:46,500
enquanto você está sendo entrevistado por telefone.

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

34
00:01:48,490 --> 00:01:50,620
testar o seu conhecimento de informática.

35
00:01:50,620 --> 00:01:54,490
E vai quase certamente envolvem codificação.

36
00:01:54,490 --> 00:01:59,540
Os tipos de perguntas que você verá são geralmente estruturas de dados e algoritmos.

37
00:01:59,540 --> 00:02:02,210
E, ao fazer estes tipos de problemas,

38
00:02:02,210 --> 00:02:07,830
eles vão pedir-lhe, assim, o que é o tempo ea complexidade do espaço, grande O?

39
00:02:07,830 --> 00:02:09,800
Muitas vezes, eles também pedir maior nível de perguntas,

40
00:02:09,800 --> 00:02:12,530
assim, projetar um sistema,

41
00:02:12,530 --> 00:02:14,770
como é que você colocar para fora seu código?

42
00:02:14,770 --> 00:02:18,370
Quais interfaces, o que as classes, quais módulos você tem em seu sistema,

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

44
00:02:20,900 --> 00:02:26,130
Assim estruturas de dados e algoritmos, bem como sistemas de projeto.

45
00:02:26,130 --> 00:02:29,180
>> Algumas dicas gerais, antes de mergulhar em nossos estudos de caso.

46
00:02:29,180 --> 00:02:32,300
Acho que a regra mais importante é sempre estar pensando em voz alta.

47
00:02:32,300 --> 00:02:36,980
A entrevista é suposto ser a sua chance de mostrar o seu processo de pensamento.

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

49
00:02:39,820 --> 00:02:42,660
como você pensa e como você passar por um problema.

50
00:02:42,660 --> 00:02:45,210
A pior coisa que você pode fazer é ficar em silêncio durante toda a entrevista.

51
00:02:45,210 --> 00:02:50,090
Isso é apenas não é bom.

52
00:02:50,090 --> 00:02:53,230
Quando você tem uma pergunta, você também quer ter a certeza de que você entendeu a pergunta.

53
00:02:53,230 --> 00:02:55,350
Então, repito a pergunta de volta em suas próprias palavras

54
00:02:55,350 --> 00:02:58,920
e tentativa de trabalhar completas alguns casos de teste simples

55
00:02:58,920 --> 00:03:01,530
para ter certeza de que entendeu a pergunta.

56
00:03:01,530 --> 00:03:05,510
Trabalhando através de alguns casos de teste também lhe dará uma intuição sobre como resolver este problema.

57
00:03:05,510 --> 00:03:11,210
Você pode até descobrir alguns padrões para ajudar a resolver o problema.

58
00:03:11,210 --> 00:03:14,500
Sua grande dica é não ficar frustrado.

59
00:03:14,500 --> 00:03:17,060
Não fique frustrado.

60
00:03:17,060 --> 00:03:19,060
Entrevistas são um desafio, mas a pior coisa que você pode fazer,

61
00:03:19,060 --> 00:03:23,330
para além de ser silencioso, é para ser visivelmente frustrado.

62
00:03:23,330 --> 00:03:27,410
Você não quer dar a impressão de que a um entrevistador.

63
00:03:27,410 --> 00:03:33,960
Uma coisa que você - assim, muitas pessoas, quando eles entram em uma entrevista,

64
00:03:33,960 --> 00:03:37,150
eles tentam tentar encontrar a melhor solução em primeiro lugar,

65
00:03:37,150 --> 00:03:39,950
quando, na verdade, há, normalmente, uma solução muito óbvio.

66
00:03:39,950 --> 00:03:43,500
Pode ser lento, pode ser ineficiente, mas você deve apenas afirmar que,

67
00:03:43,500 --> 00:03:46,210
Só para você ter um ponto de partida para trabalhar melhor.

68
00:03:46,210 --> 00:03:48,270
Além disso, a apontar para fora a solução é lenta, em termos de

69
00:03:48,270 --> 00:03:52,160
O grande complexidade de tempo ou a complexidade do espaço,

70
00:03:52,160 --> 00:03:54,450
irá demonstrar para o entrevistador que você entenda

71
00:03:54,450 --> 00:03:57,510
estas questões ao escrever código.

72
00:03:57,510 --> 00:04:01,440
Portanto, não tenha medo de vir para cima com o mais simples algoritmo de primeira

73
00:04:01,440 --> 00:04:04,950
e, então, trabalhar melhor a partir daí.

74
00:04:04,950 --> 00:04:09,810
Todas as perguntas até agora? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Então vamos mergulhar no nosso primeiro problema.

76
00:04:11,650 --> 00:04:14,790
"Dado um conjunto de n inteiros, escreva uma função que embaralha a matriz

77
00:04:14,790 --> 00:04:20,209
em tal lugar que todas as permutações dos n inteiros são igualmente prováveis. "

78
00:04:20,209 --> 00:04:23,470
E assumir que você tem disponível um gerador de número aleatório

79
00:04:23,470 --> 00:04:30,980
que gera um número inteiro na gama de 0 a i, gama de metade.

80
00:04:30,980 --> 00:04:32,970
Será que todo mundo entender essa questão?

81
00:04:32,970 --> 00:04:39,660
Eu dar-lhe um array de inteiros n, e eu quero que você embaralhar-lo.

82
00:04:39,660 --> 00:04:46,050
No meu diretório, escrevi alguns programas para demonstrar o que eu quero dizer.

83
00:04:46,050 --> 00:04:48,910
Eu estou indo para baralhar uma 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 eu quero que a saída de uma lista como esta.

86
00:04:57,050 --> 00:05:02,890
Então, esta é a minha matriz entrada classificada, e eu quero que você embaralhar-lo.

87
00:05:02,890 --> 00:05:07,070
Nós vamos fazer isso de novo.

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

89
00:05:13,780 --> 00:05:16,730
Então cabe a você.

90
00:05:16,730 --> 00:05:21,220
Quais são algumas idéias? Você pode fazê-lo como n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Aberto a sugestões.

92
00:05:34,400 --> 00:05:37,730
Okay. Então, uma idéia, sugerida pelo Emmy,

93
00:05:37,730 --> 00:05:45,300
é primeiro calcular um número aleatório, inteiro aleatório, em um intervalo de 0 a 20.

94
00:05:45,300 --> 00:05:49,840
Assim, assumir a nossa matriz tem um comprimento de 20.

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

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

97
00:05:58,560 --> 00:06:04,590
E agora, a sugestão é criar uma nova matriz,

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

99
00:06:08,440 --> 00:06:12,880
E baseado no i retornado por rand -

100
00:06:12,880 --> 00:06:17,580
Então, se eu era, vamos dizer, 17,

101
00:06:17,580 --> 00:06:25,640
copiar o elemento 17 para a primeira posição.

102
00:06:25,640 --> 00:06:30,300
Agora precisamos apagar - precisamos mudar todos os elementos aqui

103
00:06:30,300 --> 00:06:36,920
de forma que temos uma lacuna no final e não há buracos no meio.

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

105
00:06:39,860 --> 00:06:46,360
Agora vamos escolher um novo inteiro aleatório entre 0 e 19.

106
00:06:46,360 --> 00:06:52,510
Temos um i novo aqui, e nós copiamos este elemento para essa posição.

107
00:06:52,510 --> 00:07:00,960
Então mudamos os itens sobre os e repita o processo até que temos a nossa gama completa de novo.

108
00:07:00,960 --> 00:07:05,890
Qual é o tempo de execução deste algoritmo?

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

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

111
00:07:10,380 --> 00:07:16,800
Quando remover esta i, estamos mudando todos os elementos depois para a esquerda.

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

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

114
00:07:26,100 --> 00:07:29,670
Assim, para cada remoção, remover -

115
00:07:29,670 --> 00:07:32,170
cada remoção incorre uma operação de O (n),

116
00:07:32,170 --> 00:07:41,520
e uma vez que temos n remoções, isso leva a um baralhar O (n ^ 2).

117
00:07:41,520 --> 00:07:49,550
Okay. Então bom começo. Bom começo.

118
00:07:49,550 --> 00:07:55,290
>> Outra sugestão é usar algo conhecido 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 um shuffle tempo linear.

121
00:07:59,630 --> 00:08:02,200
E a idéia é muito semelhante.

122
00:08:02,200 --> 00:08:05,160
Mais uma vez, temos a nossa matriz de entrada,

123
00:08:05,160 --> 00:08:08,580
mas em vez de utilizar duas matrizes para a entrada / saída,

124
00:08:08,580 --> 00:08:13,590
usamos a primeira porção da matriz para controlar a porção embaralhadas,

125
00:08:13,590 --> 00:08:18,400
e estamos a acompanhar, e depois deixamos o resto da nossa matriz para a parte unshuffled.

126
00:08:18,400 --> 00:08:24,330
Então, aqui está o que eu quero dizer. Começamos com - podemos escolher um i,

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

128
00:08:30,910 --> 00:08:36,150
Nosso atual do ponteiro está apontando para o primeiro índice.

129
00:08:36,150 --> 00:08:39,590
Nós escolhemos alguns aqui i

130
00:08:39,590 --> 00:08:42,740
e agora vamos trocar.

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

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

133
00:08:57,150 --> 00:09:00,390
E agora, notamos um marcador aqui.

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

135
00:09:05,770 --> 00:09:15,160
e tudo para a direita está unshuffled.

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

137
00:09:17,260 --> 00:09:25,210
Nós escolhemos um índice aleatório entre 1 e 20 agora.

138
00:09:25,210 --> 00:09:30,650
Então suponho que o nosso novo i é aqui.

139
00:09:30,650 --> 00:09:39,370
Agora vamos trocar este i com a nossa posição atual de novo aqui.

140
00:09:39,370 --> 00:09:44,790
Então nós fazemos uma troca de e para trás como este.

141
00:09:44,790 --> 00:09:51,630
Deixe-me trazer o código para torná-lo mais concreto.

142
00:09:51,630 --> 00:09:55,290
Nós começamos com a nossa escolha de i -

143
00:09:55,290 --> 00:09:58,370
começamos com i igual a 0, nós escolhemos um local aleatório j

144
00:09:58,370 --> 00:10:02,420
na porção unshuffled da matriz, i a n-1.

145
00:10:02,420 --> 00:10:07,280
Então, se eu estou aqui, escolher um índice aleatório entre aqui 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 necessário para baralhar a sua matriz.

148
00:10:17,550 --> 00:10:21,670
Alguma pergunta?

149
00:10:21,670 --> 00:10:25,530
>> Bem, uma pergunta é necessária, por que isso é correto?

150
00:10:25,530 --> 00:10:28,360
Porque é que todas as permutações igualmente prováveis?

151
00:10:28,360 --> 00:10:30,410
E eu não vou passar pela prova disso,

152
00:10:30,410 --> 00:10:35,970
mas muitos problemas em ciência da computação pode ser comprovada através de indução.

153
00:10:35,970 --> 00:10:38,520
Como muitos de vocês estão familiarizados com a indução?

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

155
00:10:40,590 --> 00:10:43,610
Assim, você pode provar a correção do algoritmo por indução simples,

156
00:10:43,610 --> 00:10:49,540
onde a sua hipótese de indução seria, suponha que

157
00:10:49,540 --> 00:10:53,290
meu shuffle retorna todas as permutações igualmente provável

158
00:10:53,290 --> 00:10:56,120
até os elementos que eu primeiro.

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

160
00:10:58,300 --> 00:11:02,550
E pelo jeito que escolhemos o nosso índice j para trocar,

161
00:11:02,550 --> 00:11:05,230
isso leva a - e então você trabalhar os detalhes,

162
00:11:05,230 --> 00:11:07,390
pelo menos, uma prova cheia de porque este algoritmo retorna

163
00:11:07,390 --> 00:11:12,800
cada permutação com probabilidade igualmente prováveis.

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

165
00:11:15,940 --> 00:11:19,170
Assim, "dado um array de inteiros, postive, zero, negativo,

166
00:11:19,170 --> 00:11:21,290
escrever uma função que calcula a soma máxima

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

168
00:11:24,720 --> 00:11:28,370
Um exemplo aqui é, no caso em que todos os números são positivos,

169
00:11:28,370 --> 00:11:31,320
em seguida, atualmente a melhor opção é levar todo o conjunto.

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
Quando você tem alguns aspectos negativos lá,

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

173
00:11:38,690 --> 00:11:44,590
porque escolher -1 e / ou -3 trará nossa soma para baixo.

174
00:11:44,590 --> 00:11:48,120
Às vezes, pode ter de começar no meio da matriz.

175
00:11:48,120 --> 00:11:53,500
Às vezes queremos escolher nada, mas é melhor não tomar nada.

176
00:11:53,500 --> 00:11:56,490
E às vezes é melhor tomar a queda,

177
00:11:56,490 --> 00:12:07,510
porque a coisa depois que ele é super grande. Então, alguma idéia?

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

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

180
00:12:13,560 --> 00:12:16,170
Em seguida, eu escolho 1.000 e 20.000,

181
00:12:16,170 --> 00:12:18,630
ou eu apenas escolher o 3 bilhões.

182
00:12:18,630 --> 00:12:20,760
Bem, a melhor opção é levar todos os números.

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

184
00:12:24,350 --> 00:12:31,340
toda a soma é maior do que os que não a tomar -1.

185
00:12:31,340 --> 00:12:36,460
Portanto, uma das dicas que eu mencionei anteriormente era para dizer o óbvio claramente

186
00:12:36,460 --> 00:12:40,540
e a solução de força bruta em primeiro lugar.

187
00:12:40,540 --> 00:12:44,340
Qual é a solução de força bruta neste problema? Sim?

188
00:12:44,340 --> 00:12:46,890
[Jane] Bem, eu acho que a solução de força bruta

189
00:12:46,890 --> 00:12:52,600
seria somar todas as combinações possíveis (ininteligível).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Então Jane idéia é levar todos os possíveis -

191
00:12:58,250 --> 00:13:01,470
Estou parafraseando - é levar cada subarray possível, contínua,

192
00:13:01,470 --> 00:13:07,840
calcular a sua soma, em seguida, tomar o máximo de todas as possíveis subarrays contínuas.

193
00:13:07,840 --> 00:13:13,310
O que identifica um subarray na minha matriz de entrada?

194
00:13:13,310 --> 00:13:17,380
Como que duas coisas que eu preciso? Sim?

195
00:13:17,380 --> 00:13:19,970
(Estudante, ininteligível) direito. >>

196
00:13:19,970 --> 00:13:22,130
Um limite inferior no índice e um índice limite superior

197
00:13:22,130 --> 00:13:28,300
determina unicamente uma submatriz contínua.

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

199
00:13:31,400 --> 00:13:34,280
[Yu] Não. Então, a pergunta é, será que estamos assumindo a nossa matriz -

200
00:13:34,280 --> 00:13:39,000
é a nossa matriz de todos os números originais, ea resposta é não.

201
00:13:39,000 --> 00:13:43,390
>> Se usarmos a nossa solução de força bruta, então os índices de início / fim

202
00:13:43,390 --> 00:13:47,200
exclusivamente determina nossa subarray contínua.

203
00:13:47,200 --> 00:13:51,680
Então, se nós iterar para todas as entradas possíveis de início,

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

205
00:13:58,320 --> 00:14:05,570
você calcular a soma, e então tomamos o montante máximo que temos visto até agora.

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

207
00:14:07,880 --> 00:14:12,230
O que é o O grande desta solução?

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

209
00:14:16,660 --> 00:14:18,860
Não é bem N ^ 2.

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

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

212
00:14:27,520 --> 00:14:35,120
Repetimos novamente quase o começo até o fim, outro para loop.

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

214
00:14:37,640 --> 00:14:43,810
de modo que é outro para loop. Portanto, temos três aninhados loops, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Isso vale como um ponto de partida.

216
00:14:46,560 --> 00:14:53,180
Nossa solução não é pior do que n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Será que todo mundo entender a solução de força bruta?

218
00:14:55,480 --> 00:14:59,950
>> Okay. A melhor solução é usar uma idéia chamada de programação dinâmica.

219
00:14:59,950 --> 00:15:03,040
Se você tomar CS124, que é Algoritmos e Estruturas de Dados,

220
00:15:03,040 --> 00:15:05,680
você vai se tornar muito familiarizado com esta técnica.

221
00:15:05,680 --> 00:15:12,190
E a idéia é, tentar construir soluções para pequenos problemas em primeiro lugar.

222
00:15:12,190 --> 00:15:17,990
O que quero dizer com isto é, atualmente temos que se preocupar com duas coisas: início e término.

223
00:15:17,990 --> 00:15:29,340
E isso é irritante. O que se poderia se livrar de um desses parâmetros?

224
00:15:29,340 --> 00:15:32,650
Uma idéia é - nós dado o nosso problema original,

225
00:15:32,650 --> 00:15:37,470
encontrar a soma máxima de qualquer subarray no intervalo [O, n-1].

226
00:15:37,470 --> 00:15:47,400
E agora temos um novo subproblema, onde sabemos que, em nossa atual índice i,

227
00:15:47,400 --> 00:15:52,520
sabemos que devemos concluir lá. Nosso subarray deve terminar no índice atual.

228
00:15:52,520 --> 00:15:57,640
Assim, o problema restante é, por onde devemos começar a nossa subarray?

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

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

231
00:16:12,030 --> 00:16:16,230
No codirectory, há um programa chamado subarray,

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

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

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

235
00:16:29,920 --> 00:16:34,850
E que é tomada apenas usando 2 e 1.

236
00:16:34,850 --> 00:16:38,050
Vamos executá-lo novamente. É também 3.

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

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

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

240
00:16:49,980 --> 00:16:55,080
que vai trazer uma soma <3.

241
00:16:55,080 --> 00:16:57,820
Vamos correr em 10 itens.

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

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

244
00:17:09,450 --> 00:17:16,310
Então, para dar-lhe uma intuição sobre como podemos resolver este problema transformado,

245
00:17:16,310 --> 00:17:18,890
vamos dar uma olhada neste subarray.

246
00:17:18,890 --> 00:17:23,460
Nós estamos dando esta matriz de entrada, e nós 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
Mas vamos ver como é que realmente tenho essa resposta.

249
00:17:29,090 --> 00:17:34,160
Vamos olhar para o subarray máxima que terminou em cada um desses índices.

250
00:17:34,160 --> 00:17:40,780
Qual é a subarray máxima que tem que terminar na primeira posição?

251
00:17:40,780 --> 00:17:46,310
[Estudante] Zero. >> Zero. Só não tomar a -5.

252
00:17:46,310 --> 00:17:50,210
Aqui vai ser 0 também. Sim?

253
00:17:50,210 --> 00:17:56,470
(Ininteligível, estudante)

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

255
00:17:58,960 --> 00:18:03,220
Portanto, este é um grupo 2, isto é um -3.

256
00:18:03,220 --> 00:18:08,690
Okay. Então -4, o que é o subarray máxima para acabar com essa posição

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

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

259
00:18:22,570 --> 00:18:28,060
Agora, tenho que terminar no local onde está em -2.

260
00:18:28,060 --> 00:18:39,330
Então, 6, 5, 7, e o último é de 4.

261
00:18:39,330 --> 00:18:43,480
Sabendo que estas são as minhas entradas

262
00:18:43,480 --> 00:18:48,130
para o problema transformou onde deve terminar em cada um desses índices,

263
00:18:48,130 --> 00:18:51,410
então a minha resposta final é justo, fazer uma varredura em 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
Portanto, neste caso, é 8.

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

267
00:19:00,010 --> 00:19:04,970
e começou em algum lugar antes.

268
00:19:04,970 --> 00:19:09,630
Será que todo mundo entender isso subarray transformado?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Bem, vamos descobrir a recorrência para isso.

270
00:19:22,160 --> 00:19:27,990
Vamos considerar apenas as entradas primeiros.

271
00:19:27,990 --> 00:19:35,930
Então, aqui foi de 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
E então houve um -2 aqui, e que trouxe para baixo a 6.

273
00:19:39,790 --> 00:19:50,800
Então, se eu chamar a entrada na posição i subproblema (i),

274
00:19:50,800 --> 00:19:54,910
como posso usar a resposta a um 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 olhar para, vamos dizer, essa entrada.

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

278
00:20:09,190 --> 00:20:18,780
uma combinação dessa matriz e as respostas para subproblemas anteriores desta série? Sim?

279
00:20:18,780 --> 00:20:22,800
[Estudante Feminino] Você toma a matriz de somas

280
00:20:22,800 --> 00:20:25,430
na posição correcta antes de que, para que o 8,

281
00:20:25,430 --> 00:20:32,170
e então você adiciona o subproblema atual.

282
00:20:32,170 --> 00:20:36,460
[Yu] Então a sugestão é olhar para esses dois números,

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

284
00:20:40,090 --> 00:20:50,130
Portanto, este 8 refere-se à resposta para o subproblema (i - 1).

285
00:20:50,130 --> 00:20:57,300
E vamos chamar minha entrada matriz A.

286
00:20:57,300 --> 00:21:01,470
A fim de encontrar uma submatriz máxima que termina na posição i,

287
00:21:01,470 --> 00:21:03,980
Eu tenho duas escolhas: eu pode continuar a subarray

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

289
00:21:09,790 --> 00:21:14,190
Se eu fosse para continuar a subarray que começou no índice anterior,

290
00:21:14,190 --> 00:21:19,260
em seguida, o montante máximo que pode conseguir é a resposta para o subproblema anterior

291
00:21:19,260 --> 00:21:24,120
mais a entrada da matriz atual.

292
00:21:24,120 --> 00:21:27,550
Mas, eu também tem a opção de iniciar um novo subarray,

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

294
00:21:30,830 --> 00:21:42,860
Portanto, a resposta é o máximo de 0, subproblema i - 1, mais a entrada da matriz atual.

295
00:21:42,860 --> 00:21:46,150
Será que essa recorrência faz sentido?

296
00:21:46,150 --> 00:21:50,840
Nosso recorrência, como acabamos de descobrir, é subproblema i

297
00:21:50,840 --> 00:21:54,740
é igual ao máximo do subproblema anterior mais a minha entrada matriz atual,

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

299
00:22:01,490 --> 00:22:07,250
ou 0, iniciar um subarray novo em meu índice atual.

300
00:22:07,250 --> 00:22:10,060
E uma vez que nós construímos esta tabela de soluções, então a nossa resposta final,

301
00:22:10,060 --> 00:22:13,950
basta fazer uma varredura linear em 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 é uma implementação exata do que eu disse.

304
00:22:23,330 --> 00:22:27,320
Então, criamos uma matriz subproblema novo, subproblemas.

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

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

307
00:22:35,670 --> 00:22:39,810
usamos a repetição exata que acabara de descobrir.

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

309
00:22:49,960 --> 00:22:54,130
>> Então, quanto espaço estamos usando neste algoritmo?

310
00:22:54,130 --> 00:23:01,470
Se você só tomada CS50, então você pode não ter discutido muito espaço.

311
00:23:01,470 --> 00:23:07,750
Bem, uma coisa a se notar é que eu chamei malloc aqui com tamanho n.

312
00:23:07,750 --> 00:23:13,590
O que isso lhe sugere?

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

314
00:23:17,450 --> 00:23:21,030
Podemos fazer melhor?

315
00:23:21,030 --> 00:23:30,780
Existe alguma coisa que você percebe o que é desnecessário para calcular a resposta final?

316
00:23:30,780 --> 00:23:33,290
Eu acho que a melhor pergunta é, que informação

317
00:23:33,290 --> 00:23:40,680
não precisamos levar todo o caminho até o fim?

318
00:23:40,680 --> 00:23:44,280
Agora, se olharmos para estas duas linhas,

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

320
00:23:47,720 --> 00:23:50,910
e nós só se preocupam com o máximo que já vimos até agora.

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

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

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

324
00:24:02,630 --> 00:24:07,380
Então, na verdade, pode-se fundir esses laços juntos

325
00:24:07,380 --> 00:24:10,460
e ir de espaço a espaço linear constante.

326
00:24:10,460 --> 00:24:15,830
Soma atual, até agora, aqui, substitui a função do subproblema, nossa matriz subproblema.

327
00:24:15,830 --> 00:24:20,020
Soma tão atual, até agora, é a resposta para o subproblema anterior.

328
00:24:20,020 --> 00:24:23,450
E que soma, até agora, toma o lugar do nosso máximo.

329
00:24:23,450 --> 00:24:28,100
Nós calcular o valor máximo à medida que avançamos.

330
00:24:28,100 --> 00:24:30,890
E assim vamos de espaço linear para o espaço constante,

331
00:24:30,890 --> 00:24:36,650
e também temos uma solução para o nosso problema linear subarray.

332
00:24:36,650 --> 00:24:40,740
>> Esses tipos de perguntas que você vai ter durante uma entrevista.

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

334
00:24:44,450 --> 00:24:50,600
Você pode fazer melhor? Existem coisas que são desnecessários para manter em torno?

335
00:24:50,600 --> 00:24:55,270
Eu fiz isso para destacar análises que você deve tomar em seu próprio

336
00:24:55,270 --> 00:24:57,400
como você está trabalhando com esses problemas.

337
00:24:57,400 --> 00:25:01,710
Sempre estar se perguntando: "Posso fazer melhor?"

338
00:25:01,710 --> 00:25:07,800
Na verdade, podemos fazer melhor que isso?

339
00:25:07,800 --> 00:25:10,730
Uma espécie de pegadinha. Você não pode, porque você precisa

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

341
00:25:13,590 --> 00:25:15,570
Assim, o fato de que você precisa ler pelo menos a entrada para o problema

342
00:25:15,570 --> 00:25:19,580
significa que você não pode fazer melhor do que o tempo linear,

343
00:25:19,580 --> 00:25:22,870
e você não pode fazer melhor do que o espaço constante.

344
00:25:22,870 --> 00:25:27,060
Portanto, este é, de facto, a melhor solução para este problema.

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

346
00:25:33,040 --> 00:25:35,190
>> Problema do mercado de ações:

347
00:25:35,190 --> 00:25:38,350
"Dado um conjunto de n inteiros, positivo, zero ou negativo,

348
00:25:38,350 --> 00:25:41,680
que representam o preço de uma ação mais n dias,

349
00:25:41,680 --> 00:25:44,080
escrever uma função para calcular o lucro máximo que você pode fazer

350
00:25:44,080 --> 00:25:49,350
uma vez que você compra e vende exatamente um estoque dentro desses n dias. "

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

352
00:25:51,690 --> 00:25:58,580
E nós queremos descobrir o melhor lucro que podemos fazer.

353
00:25:58,580 --> 00:26:11,500
Voltando ao meu ponta, o que é a resposta mais simples imediatamente claro, mas é lento?

354
00:26:11,500 --> 00:26:17,690
Sim? (Estudante, ininteligível) >> Sim.

355
00:26:17,690 --> 00:26:21,470
>> Então você teria apenas que ir embora e olhar para os preços das ações

356
00:26:21,470 --> 00:26:30,550
em cada ponto no tempo, (ininteligível).

357
00:26:30,550 --> 00:26:33,990
[Yu] Ok, então sua solução - sua sugestão de computação

358
00:26:33,990 --> 00:26:37,380
o menor e computar o maior não significa necessariamente trabalhar

359
00:26:37,380 --> 00:26:42,470
porque o mais elevado podem ocorrer antes de mais baixa.

360
00:26:42,470 --> 00:26:47,340
Então, qual é a solução de força bruta para este problema?

361
00:26:47,340 --> 00:26:53,150
Quais são as duas coisas que eu preciso determinar de maneira única o lucro que eu faço? Direito.

362
00:26:53,150 --> 00:26:59,410
A solução de força bruta é - oh, então, a sugestão de Jorge é que só preciso dois dias

363
00:26:59,410 --> 00:27:02,880
exclusivamente para determinar o lucro desses dois dias.

364
00:27:02,880 --> 00:27:06,660
Então vamos calcular cada par, como comprar / vender,

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

366
00:27:12,850 --> 00:27:18,000
Calcule o lucro máximo que fazemos após a iteração sobre todos os pares de dias.

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

368
00:27:20,330 --> 00:27:25,730
E que a solução vai ser O (n ^ 2), porque não há n escolher dois pares -

369
00:27:25,730 --> 00:27:30,270
de dias que você pode escolher entre os dias finais.

370
00:27:30,270 --> 00:27:32,580
Ok, então eu não vou passar por cima da solução de força bruta aqui.

371
00:27:32,580 --> 00:27:37,420
Eu vou dizer-lhe que há uma solução n log n.

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

373
00:27:45,550 --> 00:27:50,730
Não é uma pergunta 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, na verdade, uma maneira de resolver esse problema é usar

376
00:27:57,760 --> 00:28:04,400
um tipo merge sort de idéia chamada, em geral, dividir e conquistar.

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

378
00:28:07,570 --> 00:28:12,400
Você quer calcular a melhor compra / venda par na meia esquerda.

379
00:28:12,400 --> 00:28:16,480
Encontre o melhor lucro que você pode fazer, apenas com o n primeiro em dois dias.

380
00:28:16,480 --> 00:28:19,780
Então você quer oompute a melhor compra / venda par na metade direita,

381
00:28:19,780 --> 00:28:23,930
para n o último dois dias.

382
00:28:23,930 --> 00:28:32,400
E agora a pergunta é, como se fundem estas soluções juntos de novo?

383
00:28:32,400 --> 00:28:36,320
Sim? (Ininteligível, estudante)

384
00:28:36,320 --> 00:28:49,890
Ok >>. Então deixe-me tirar uma foto.

385
00:28:49,890 --> 00:29:03,870
Sim? (George, ininteligível)

386
00:29:03,870 --> 00:29:06,450
>> Exatamente. Solução George é exatamente certo.

387
00:29:06,450 --> 00:29:10,040
Assim, sua sugestão é, primeiro calcular o melhor par de compra / venda,

388
00:29:10,040 --> 00:29:16,050
e que ocorre na metade esquerda, então vamos chamar isso de esquerda, à esquerda.

389
00:29:16,050 --> 00:29:20,790
Melhor comprar / vender par que ocorre na meia direita.

390
00:29:20,790 --> 00:29:25,180
Mas, se comparado apenas estes dois números, estamos perdendo o caso

391
00:29:25,180 --> 00:29:30,460
onde comprar aqui e vender em algum lugar do meia direita.

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

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

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

395
00:29:43,480 --> 00:29:45,580
e tomar a sua diferença.

396
00:29:45,580 --> 00:29:50,850
Assim, os dois casos em que o par de compra / venda ocorre somente aqui,

397
00:29:50,850 --> 00:30:01,910
Apenas aqui, ou em ambas as metades é definida por estas três números.

398
00:30:01,910 --> 00:30:06,450
Assim, o nosso algoritmo para fundir nossas soluções de volta,

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

400
00:30:08,350 --> 00:30:13,120
onde comprar na metade esquerda e vender na meia direita.

401
00:30:13,120 --> 00:30:16,740
E a melhor maneira de fazer isso é calcular o menor preço no primeiro semestre,

402
00:30:16,740 --> 00:30:20,360
o preço mais alto na meia direita, e tomar a sua diferença.

403
00:30:20,360 --> 00:30:25,390
Os lucros resultantes três, esses três números, você tirar o máximo de três,

404
00:30:25,390 --> 00:30:32,720
e que é o melhor lucro que você pode fazer sobre estes primeiros dias e fim.

405
00:30:32,720 --> 00:30:36,940
Aqui as linhas importantes estão em vermelho.

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

407
00:30:41,160 --> 00:30:44,760
Esta é uma chamada recursiva para calcular a resposta na meia direita.

408
00:30:44,760 --> 00:30:50,720
Estes dois circuitos para calcular o mínimo eo máximo na metade esquerda e direita, respectivamente.

409
00:30:50,720 --> 00:30:54,970
Agora eu calcular o lucro que abrange as duas metades,

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

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

412
00:31:04,120 --> 00:31:06,420
>> Então, com certeza, temos um algoritmo, mas a grande questão é,

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ão pela qual eu mencionei merge sort é que essa forma de dividir a resposta

415
00:31:16,190 --> 00:31:19,200
em dois e, em seguida, fundindo nossas soluções juntos novamente

416
00:31:19,200 --> 00:31:23,580
é exatamente a forma de classificação por intercalação.

417
00:31:23,580 --> 00:31:33,360
Então deixe-me passar o tempo.

418
00:31:33,360 --> 00:31:41,340
Se nós definimos uma função t (n) para ser o número de etapas

419
00:31:41,340 --> 00:31:50,010
de n dias,

420
00:31:50,010 --> 00:31:54,350
nossas duas chamadas recursivas

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

422
00:32:00,460 --> 00:32:03,540
e há duas dessas ligações.

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

424
00:32:10,020 --> 00:32:17,050
que I pode fazer em n / 2 hora, mais o máximo da metade direita.

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

426
00:32:20,820 --> 00:32:25,050
E depois mais algum trabalho constante.

427
00:32:25,050 --> 00:32:27,770
E esta equação recorrência

428
00:32:27,770 --> 00:32:35,560
é exatamente a equação de recorrência para merge sort.

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

430
00:32:39,170 --> 00:32:46,880
Portanto, nosso algoritmo é também n log n tempo.

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

432
00:32:52,220 --> 00:32:55,780
Apenas uma breve recapitulação do presente:

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

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

435
00:33:02,750 --> 00:33:06,010
A maneira como nos separamos nossas chamadas recursivas

436
00:33:06,010 --> 00:33:11,980
é chamando a nossa solução nos primeiros dias n / 2,

437
00:33:11,980 --> 00:33:14,490
de modo que é uma chamada,

438
00:33:14,490 --> 00:33:16,940
e, em seguida, chamamos novamente no segundo semestre.

439
00:33:16,940 --> 00:33:20,440
Então, isso é duas chamadas.

440
00:33:20,440 --> 00:33:25,310
E, então, encontrar um mínimo na metade esquerda, o que podemos fazer em tempo linear,

441
00:33:25,310 --> 00:33:29,010
encontrar o máximo da meia direita, o que podemos fazer em tempo linear.

442
00:33:29,010 --> 00:33:31,570
Então n / 2 + n / 2 é apenas n.

443
00:33:31,570 --> 00:33:36,020
Então nós temos um trabalho constante, que é como fazer aritmética.

444
00:33:36,020 --> 00:33:39,860
Esta equação de recorrência é exatamente a equação de recorrência para merge sort.

445
00:33:39,860 --> 00:33:55,490
Por isso, nosso algoritmo shuffle é também n log n.

446
00:33:55,490 --> 00:33:58,520
Então, quanto espaço estamos usando?

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

448
00:34:04,910 --> 00:34:09,420
>> A melhor pergunta é, quantos quadros de pilha que nós já temos em 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 quadros de pilha determina a nossa utilização do espaço.

451
00:34:23,530 --> 00:34:29,440
Vamos 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 irá chamar embaralhe as quatro primeiras entradas,

454
00:34:41,580 --> 00:34:46,250
que irá chamar um shuffle nas duas primeiras entradas.

455
00:34:46,250 --> 00:34:51,550
Portanto, a nossa pilha é - esta é a nossa pilha.

456
00:34:51,550 --> 00:34:54,980
E então nós chamamos baralhar novamente em 1,

457
00:34:54,980 --> 00:34:58,070
e é isso que o nosso caso base é, por isso, retornar imediatamente.

458
00:34:58,070 --> 00:35:04,700
Será que já tem mais que esta pilha de quadros muitos?

459
00:35:04,700 --> 00:35:08,880
Não. Porque cada vez que fazemos uma invocação,

460
00:35:08,880 --> 00:35:10,770
uma invocação recursiva para shuffle,

461
00:35:10,770 --> 00:35:13,950
dividimos nosso tamanho pela metade.

462
00:35:13,950 --> 00:35:17,020
Assim, o número máximo de quadros de pilha que já têm a qualquer momento

463
00:35:17,020 --> 00:35:28,460
é da ordem de quadros de log n pilha.

464
00:35:28,460 --> 00:35:42,460
Cada quadro de pilha tem espaço constante,

465
00:35:42,460 --> 00:35:44,410
e, portanto, a quantidade de espaço total,

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

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

468
00:36:03,040 --> 00:36:07,230
>> Agora, sempre pergunte a si mesmo: "Podemos fazer melhor?"

469
00:36:07,230 --> 00:36:12,390
E, em particular, podemos reduzir isso a um problema que já foi resolvido?

470
00:36:12,390 --> 00:36:20,040
Uma dica: só discutiu dois outros problemas antes disso, e não vai ser shuffle.

471
00:36:20,040 --> 00:36:26,200
Podemos converter este problema do mercado de ações para o problema subarray máxima.

472
00:36:26,200 --> 00:36:40,100
Como podemos fazer isso?

473
00:36:40,100 --> 00:36:42,570
Um de vocês? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, ininteligível)

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

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

477
00:36:59,940 --> 00:37:10,610
estamos à procura de uma soma sobre um subarray contínua.

478
00:37:10,610 --> 00:37:16,230
E a sugestão de Emmy para o problema stocks,

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

480
00:37:30,720 --> 00:37:37,440
E um retrato disso é - este é o preço de uma ação,

481
00:37:37,440 --> 00:37:42,610
mas se tomamos a diferença entre cada dia consecutivo -

482
00:37:42,610 --> 00:37:45,200
assim vemos que o preço máximo, o lucro máximo que poderia fazer

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

484
00:37:50,070 --> 00:37:54,240
Mas vamos olhar para a contínua - vamos olhar para o problema subarray.

485
00:37:54,240 --> 00:38:02,510
Então, aqui, nós podemos fazer - indo daqui para ali,

486
00:38:02,510 --> 00:38:08,410
temos uma mudança positiva, e então ir daqui até aqui temos uma variação negativa.

487
00:38:08,410 --> 00:38:14,220
Mas, então, vai daqui até aqui temos uma grande mudança positiva.

488
00:38:14,220 --> 00:38:20,930
E estas são as mudanças que deseja somar-se para receber o nosso lucro final.

489
00:38:20,930 --> 00:38:25,160
Então nós temos mudanças mais negativas aqui.

490
00:38:25,160 --> 00:38:29,990
A chave para reduzir nosso problema estoque em nosso problema subarray máxima

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

492
00:38:36,630 --> 00:38:40,630
Então nós criamos uma nova matriz chamada deltas,

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

494
00:38:43,000 --> 00:38:46,380
e então para cada delta (i), deixe que seja a diferença

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

496
00:38:52,830 --> 00:38:55,530
Então chamamos o nosso procedimento de rotina para um subarray máxima

497
00:38:55,530 --> 00:39:01,500
passando em uma matriz delta.

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

499
00:39:06,440 --> 00:39:09,370
e esta redução, este processo de criação dessa matriz delta,

500
00:39:09,370 --> 00:39:11,780
É também tempo linear,

501
00:39:11,780 --> 00:39:19,060
então a solução final para as ações é O (n) O trabalho, além de trabalho (n), ainda é O trabalho (n).

502
00:39:19,060 --> 00:39:23,900
Portanto, temos uma solução em tempo linear para o nosso problema.

503
00:39:23,900 --> 00:39:29,610
Será que todo mundo entender essa transformação?

504
00:39:29,610 --> 00:39:32,140
>> Em geral, é uma boa idéia que você deve ter sempre

505
00:39:32,140 --> 00:39:34,290
é tentar reduzir um novo problema que você está vendo.

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

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

508
00:39:39,590 --> 00:39:41,950
E se você pode usar todas as ferramentas que você usou no velho 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ão, para encerrar, entrevistas técnicas são desafiadoras.

511
00:39:49,010 --> 00:39:52,280
Estes problemas são, provavelmente, alguns dos problemas mais difíceis

512
00:39:52,280 --> 00:39:54,700
que você pode ver em uma entrevista,

513
00:39:54,700 --> 00:39:57,690
por isso, se você não entender todos os problemas que eu só cobertos, está tudo bem.

514
00:39:57,690 --> 00:40:01,080
Estes são alguns dos problemas mais difíceis.

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

516
00:40:03,050 --> 00:40:08,170
Eu dei um monte de problemas no folheto, então definitivamente verificar os para fora.

517
00:40:08,170 --> 00:40:11,690
E boa sorte em suas entrevistas. Todos os meus recursos são postados neste link,

518
00:40:11,690 --> 00:40:15,220
e um dos meus amigos seniores se ofereceu para fazer simulações de entrevistas técnicas,

519
00:40:15,220 --> 00:40:22,050
por isso, se você estiver interessado, e-mail Will Yao nesse endereço de e-mail.

520
00:40:22,050 --> 00:40:26,070
Se você tem alguma dúvida, você pode me perguntar.

521
00:40:26,070 --> 00:40:28,780
Vocês têm questões específicas relacionadas com entrevistas técnicas

522
00:40:28,780 --> 00:40:38,440
ou quaisquer problemas que vimos até agora?

523
00:40:38,440 --> 00:40:49,910
Okay. Bem, boa sorte em suas entrevistas.

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