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

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

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

4
00:00:08,910 --> 00:00:12,420
Hola a todos, soy Kenny. Actualmente soy un joven ciencia que estudia informática.

5
00:00:12,420 --> 00:00:17,310
Soy un ex TF CS, y me gustaría tener esto cuando era un underclassman,

6
00:00:17,310 --> 00:00:19,380
y es por eso que pongo a este seminario.

7
00:00:19,380 --> 00:00:21,370
Así que espero que os guste.

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

9
00:00:23,470 --> 00:00:26,650
y todos mis recursos se pueden encontrar en este enlace,

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

11
00:00:32,350 --> 00:00:36,550
Así que hice una lista de problemas, en realidad, bastantes problemas.

12
00:00:36,550 --> 00:00:40,800
También una página de recursos en general donde podemos encontrar consejos

13
00:00:40,800 --> 00:00:42,870
sobre cómo prepararse para una entrevista,

14
00:00:42,870 --> 00:00:46,470
consejos sobre lo que debe hacer durante una entrevista real,

15
00:00:46,470 --> 00:00:51,910
así como la forma de abordar los problemas y los recursos para futuras referencias.

16
00:00:51,910 --> 00:00:53,980
Es todo en línea.

17
00:00:53,980 --> 00:00:58,290
Y sólo para prologar este seminario, un descargo de responsabilidad,

18
00:00:58,290 --> 00:01:00,690
como esto no debería - su preparación de la entrevista

19
00:01:00,690 --> 00:01:02,800
no debe limitarse a esta lista.

20
00:01:02,800 --> 00:01:04,750
Esto sólo pretende ser una guía,

21
00:01:04,750 --> 00:01:08,890
y además se debería tomar todo lo que digo con un grano de sal,

22
00:01:08,890 --> 00:01:14,620
sino también utilizar todo lo que solía ayudarle en su preparación de la entrevista.

23
00:01:14,620 --> 00:01:16,400
>> Voy a acelerar a través de las siguientes diapositivas

24
00:01:16,400 --> 00:01:18,650
por lo que podemos llegar a los estudios de casos reales.

25
00:01:18,650 --> 00:01:23,630
La estructura de una entrevista para un postion ingeniería de software,

26
00:01:23,630 --> 00:01:26,320
típicamente es de 30 a 45 minutos,

27
00:01:26,320 --> 00:01:29,810
múltiples rondas, dependiendo de la compañía.

28
00:01:29,810 --> 00:01:33,090
A menudo se le codificación en un tablero blanco.

29
00:01:33,090 --> 00:01:35,960
Así que una pizarra blanca como esta, pero a menudo en una escala más pequeña.

30
00:01:35,960 --> 00:01:38,540
Si tienes una entrevista telefónica, usted probablemente va a utilizar

31
00:01:38,540 --> 00:01:44,030
ya sea collabedit o un documento de Google Docs para que vean ustedes viven codificación

32
00:01:44,030 --> 00:01:46,500
mientras que usted está siendo entrevistado por teléfono.

33
00:01:46,500 --> 00:01:48,490
Una entrevista en sí es de 2 o 3 problemas

34
00:01:48,490 --> 00:01:50,620
prueba tus conocimientos de informática.

35
00:01:50,620 --> 00:01:54,490
Y será casi definitivamente involucrar codificación.

36
00:01:54,490 --> 00:01:59,540
Los tipos de preguntas que se ven son por lo general las estructuras de datos y algoritmos.

37
00:01:59,540 --> 00:02:02,210
Y al hacer este tipo de problemas,

38
00:02:02,210 --> 00:02:07,830
le preguntarán, como, ¿cuál es el tiempo y la complejidad del espacio, grande O?

39
00:02:07,830 --> 00:02:09,800
A menudo, también piden más alto nivel preguntas,

40
00:02:09,800 --> 00:02:12,530
así, el diseño de un sistema,

41
00:02:12,530 --> 00:02:14,770
¿cómo diseñar el código?

42
00:02:14,770 --> 00:02:18,370
¿Qué interfaces, lo que las clases, los módulos que lo que tiene en su sistema,

43
00:02:18,370 --> 00:02:20,900
y cómo éstas interactúan entre sí?

44
00:02:20,900 --> 00:02:26,130
Así que las estructuras de datos y algoritmos, así como sistemas de diseño.

45
00:02:26,130 --> 00:02:29,180
>> Algunos consejos generales Antes de profundizar en los estudios de casos.

46
00:02:29,180 --> 00:02:32,300
Creo que la regla más importante es siempre estar pensando en voz alta.

47
00:02:32,300 --> 00:02:36,980
La entrevista se supone que es su oportunidad para mostrar su proceso de pensamiento.

48
00:02:36,980 --> 00:02:39,820
El objetivo de la entrevista es que el entrevistador para evaluar

49
00:02:39,820 --> 00:02:42,660
cómo piensa y cómo usted va a través de un problema.

50
00:02:42,660 --> 00:02:45,210
La peor cosa que puedes hacer es estar en silencio durante toda la entrevista.

51
00:02:45,210 --> 00:02:50,090
Eso es nada bueno.

52
00:02:50,090 --> 00:02:53,230
Cuando se le da a una pregunta, usted también quiere asegurarse de que entiende la pregunta.

53
00:02:53,230 --> 00:02:55,350
Así que repito la pregunta de nuevo en sus propias palabras

54
00:02:55,350 --> 00:02:58,920
y tratar de trabajar a fondo algunos casos de prueba sencillos

55
00:02:58,920 --> 00:03:01,530
para asegurarse de que entiende la pregunta.

56
00:03:01,530 --> 00:03:05,510
Trabajando a través de un par de casos de prueba también le dará una intuición acerca de cómo resolver este problema.

57
00:03:05,510 --> 00:03:11,210
Incluso podría descubrir algunos patrones para ayudar a resolver el problema.

58
00:03:11,210 --> 00:03:14,500
Su gran consejo es no sentirse frustrado.

59
00:03:14,500 --> 00:03:17,060
No se frustre.

60
00:03:17,060 --> 00:03:19,060
Las entrevistas son un reto, pero lo peor que se puede hacer,

61
00:03:19,060 --> 00:03:23,330
además de ser silenciosa, se visiblemente frustrado.

62
00:03:23,330 --> 00:03:27,410
Usted no quiere dar esa impresión a un entrevistador.

63
00:03:27,410 --> 00:03:33,960
Una cosa que usted - así, muchas personas, cuando van a una entrevista,

64
00:03:33,960 --> 00:03:37,150
en su intento de tratar de encontrar la mejor solución primero,

65
00:03:37,150 --> 00:03:39,950
cuando en realidad, por lo general hay una solución obvia.

66
00:03:39,950 --> 00:03:43,500
Puede ser que sea lento, puede ser ineficiente, sino que sólo debe decirlo,

67
00:03:43,500 --> 00:03:46,210
sólo por lo que tiene un punto de partida para trabajar mejor.

68
00:03:46,210 --> 00:03:48,270
También, señalando la solución es lento, en términos de

69
00:03:48,270 --> 00:03:52,160
O gran complejidad de tiempo o la complejidad del espacio,

70
00:03:52,160 --> 00:03:54,450
mostrará al entrevistador que usted entiende

71
00:03:54,450 --> 00:03:57,510
estos problemas al escribir código.

72
00:03:57,510 --> 00:04:01,440
Así que no tenga miedo de llegar con el primer algoritmo más simple

73
00:04:01,440 --> 00:04:04,950
y luego trabajar mejor desde allí.

74
00:04:04,950 --> 00:04:09,810
Cualquier pregunta hasta ahora? Bien.

75
00:04:09,810 --> 00:04:11,650
>> Así que vamos a bucear en nuestro primer problema.

76
00:04:11,650 --> 00:04:14,790
"Dada una matriz de enteros n, escribe una función que baraja la matriz

77
00:04:14,790 --> 00:04:20,209
en lugar de tal manera que todas las permutaciones de los n enteros son igualmente probables. "

78
00:04:20,209 --> 00:04:23,470
Y se supone que tiene disponible un generador de número entero aleatorio

79
00:04:23,470 --> 00:04:30,980
que genera un número entero en el intervalo de 0 a i, rango medio.

80
00:04:30,980 --> 00:04:32,970
¿Todo el mundo entiende esta pregunta?

81
00:04:32,970 --> 00:04:39,660
Te doy una matriz de enteros n, y quiero que barájalo.

82
00:04:39,660 --> 00:04:46,050
En mi directorio, escribí unos cuantos programas para demostrar lo que quiero decir.

83
00:04:46,050 --> 00:04:48,910
Voy a barajar una matriz de 20 elementos,

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

85
00:04:52,490 --> 00:04:57,050
y quiero dar salida a una lista como esta.

86
00:04:57,050 --> 00:05:02,890
Así que esta es mi matriz ordenada de entrada, y quiero que barájalo.

87
00:05:02,890 --> 00:05:07,070
Vamos a hacerlo de nuevo.

88
00:05:07,070 --> 00:05:13,780
¿Todo el mundo entiende la pregunta? Bien.

89
00:05:13,780 --> 00:05:16,730
Así que le toca a usted.

90
00:05:16,730 --> 00:05:21,220
¿Cuáles son algunas ideas? ¿Puede hacerlo como n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Abierto a sugerencias.

92
00:05:34,400 --> 00:05:37,730
Bien. Así que una idea, sugerida por el Emmy,

93
00:05:37,730 --> 00:05:45,300
es calcular primero un número aleatorio, entero aleatorio, en un rango de 0 a 20.

94
00:05:45,300 --> 00:05:49,840
Así que asumir nuestra matriz tiene una longitud de 20.

95
00:05:49,840 --> 00:05:54,800
En nuestro diagrama de 20 elementos,

96
00:05:54,800 --> 00:05:58,560
esta es nuestra matriz de entrada.

97
00:05:58,560 --> 00:06:04,590
Y ahora, su sugerencia es crear una nueva matriz,

98
00:06:04,590 --> 00:06:08,440
por lo que esta será la matriz de salida.

99
00:06:08,440 --> 00:06:12,880
Y basado en el i devuelto por rand -

100
00:06:12,880 --> 00:06:17,580
así que si yo estaba, digamos, 17,

101
00:06:17,580 --> 00:06:25,640
copiar el elemento 17a en la primera posición.

102
00:06:25,640 --> 00:06:30,300
Ahora tenemos que eliminar - tenemos que cambiar todos los elementos aquí

103
00:06:30,300 --> 00:06:36,920
de manera que tenemos un hueco en el extremo y no hay agujeros en el medio.

104
00:06:36,920 --> 00:06:39,860
Y ahora repetimos el proceso.

105
00:06:39,860 --> 00:06:46,360
Ahora elegimos un número entero aleatorio entre 0 y 19.

106
00:06:46,360 --> 00:06:52,510
Tenemos una i nuevo aquí, y copiamos este elemento en esta posición.

107
00:06:52,510 --> 00:07:00,960
Entonces cambiamos artículos una y repetimos el proceso hasta que tengamos nuestra nueva matriz completa.

108
00:07:00,960 --> 00:07:05,890
¿Cuál es el tiempo de ejecución de este algoritmo?

109
00:07:05,890 --> 00:07:08,110
Bueno, vamos a considerar el impacto de esto.

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

111
00:07:10,380 --> 00:07:16,800
Cuando eliminar esta i, que están cambiando todos los elementos después de que a la izquierda.

112
00:07:16,800 --> 00:07:21,600
Y esa es una operación O (n) Coste

113
00:07:21,600 --> 00:07:26,100
porque lo que si se elimina el primer elemento?

114
00:07:26,100 --> 00:07:29,670
Así, por cada retiro, removemos -

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

116
00:07:32,170 --> 00:07:41,520
y puesto que tenemos n mudanzas, esto conduce a una operación O (n ^ 2) shuffle.

117
00:07:41,520 --> 00:07:49,550
Bien. Así buen comienzo. Buen comienzo.

118
00:07:49,550 --> 00:07:55,290
>> Otra sugerencia es usar algo conocido como el shuffle Knuth,

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

120
00:07:57,540 --> 00:07:59,630
Y en realidad es un shuffle tiempo lineal.

121
00:07:59,630 --> 00:08:02,200
Y la idea es muy similar.

122
00:08:02,200 --> 00:08:05,160
Una vez más, tenemos nuestra matriz de entrada,

123
00:08:05,160 --> 00:08:08,580
pero en lugar de utilizar dos matrices para nuestra entrada / salida,

124
00:08:08,580 --> 00:08:13,590
se utiliza la primera parte de la matriz para seguir la pista de nuestra parte barajado,

125
00:08:13,590 --> 00:08:18,400
y hacemos un seguimiento, y luego dejar el resto de nuestra gama para la parte unshuffled.

126
00:08:18,400 --> 00:08:24,330
Esto es lo que quiero decir. Comenzamos con - elegimos una i,

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

128
00:08:30,910 --> 00:08:36,150
Nuestro actual del puntero apunta al primer índice.

129
00:08:36,150 --> 00:08:39,590
Elegimos algunos i aquí

130
00:08:39,590 --> 00:08:42,740
y ahora cambiamos.

131
00:08:42,740 --> 00:08:47,690
Así que si esto era 5 y esto fue 4,

132
00:08:47,690 --> 00:08:57,150
la matriz resultante tendrá 5 aquí y 4 aquí.

133
00:08:57,150 --> 00:09:00,390
Y ahora observamos un marcador de aquí.

134
00:09:00,390 --> 00:09:05,770
Todo a la izquierda se barajan,

135
00:09:05,770 --> 00:09:15,160
y todo lo que está a la derecha unshuffled.

136
00:09:15,160 --> 00:09:17,260
Y ahora podemos repetir el proceso.

137
00:09:17,260 --> 00:09:25,210
Elegimos un índice aleatorio entre 1 y 20 ahora.

138
00:09:25,210 --> 00:09:30,650
Así que supongamos que nuestro nuevo yo está aquí.

139
00:09:30,650 --> 00:09:39,370
Ahora cambiamos esto i con nuestra nueva posición actual aquí.

140
00:09:39,370 --> 00:09:44,790
Así que hacer un intercambio de ida y vuelta así.

141
00:09:44,790 --> 00:09:51,630
Permítanme que aparezca el código para que sea más concreto.

142
00:09:51,630 --> 00:09:55,290
Comenzamos con nuestra elección de i -

143
00:09:55,290 --> 00:09:58,370
empezamos con i igual a 0, elegimos un lugar al azar j

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

145
00:10:02,420 --> 00:10:07,280
Así que si estoy aquí, elegir un índice aleatorio entre aquí y el resto de la matriz,

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

147
00:10:12,410 --> 00:10:17,550
Este es todo el código necesario para mezclar tu matriz.

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

149
00:10:21,670 --> 00:10:25,530
>> Pues bien, uno necesita pregunta es, ¿por qué es esto correcto?

150
00:10:25,530 --> 00:10:28,360
¿Por qué todas las permutaciones igualmente probable?

151
00:10:28,360 --> 00:10:30,410
Y no voy a pasar por la prueba de ello,

152
00:10:30,410 --> 00:10:35,970
pero muchos problemas en ciencias de la computación puede ser probado a través de la inducción.

153
00:10:35,970 --> 00:10:38,520
¿Cuántos de ustedes están familiarizados con la inducción?

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

155
00:10:40,590 --> 00:10:43,610
Así que usted puede demostrar la exactitud de este algoritmo por simple inducción,

156
00:10:43,610 --> 00:10:49,540
donde la hipótesis de inducción sería asumir que

157
00:10:49,540 --> 00:10:53,290
mi baraja vuelve cada permutación misma probabilidad

158
00:10:53,290 --> 00:10:56,120
a los elementos por primera vez.

159
00:10:56,120 --> 00:10:58,300
Ahora, consideremos i + 1.

160
00:10:58,300 --> 00:11:02,550
Y por la forma en que elegimos nuestro índice j para intercambiar,

161
00:11:02,550 --> 00:11:05,230
esto lleva a - y luego se trabaja en los detalles,

162
00:11:05,230 --> 00:11:07,390
por lo menos una prueba completa de por qué este algoritmo devuelve

163
00:11:07,390 --> 00:11:12,800
todas las permutaciones con una probabilidad igualmente probables.

164
00:11:12,800 --> 00:11:15,940
>> Todo problema derecha, al lado.

165
00:11:15,940 --> 00:11:19,170
Así que "dado un conjunto de números enteros, postive, cero, negativo,

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

167
00:11:21,290 --> 00:11:24,720
de cualquier submatriz continueous de la matriz de entrada. "

168
00:11:24,720 --> 00:11:28,370
Un ejemplo aquí es, en el caso en que todos los números son positivos,

169
00:11:28,370 --> 00:11:31,320
a continuación, en la actualidad la mejor opción es tomar todo el conjunto.

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

171
00:11:34,690 --> 00:11:36,780
Cuando usted tiene algunos aspectos negativos de allí,

172
00:11:36,780 --> 00:11:38,690
en este caso sólo queremos los dos primeros

173
00:11:38,690 --> 00:11:44,590
porque elegir -1 y / o -3 hará que nuestra suma hacia abajo.

174
00:11:44,590 --> 00:11:48,120
A veces puede que tengamos que empezar en el medio de la matriz.

175
00:11:48,120 --> 00:11:53,500
A veces tenemos que elegir nada en absoluto, es mejor que no tener nada.

176
00:11:53,500 --> 00:11:56,490
Y a veces es mejor tomar la caída,

177
00:11:56,490 --> 00:12:07,510
porque después de lo que es super grande. Entonces, alguna idea?

178
00:12:07,510 --> 00:12:10,970
(Estudiante, ininteligible) >> Si.

179
00:12:10,970 --> 00:12:13,560
Supongamos que yo no tomo -1.

180
00:12:13,560 --> 00:12:16,170
Entonces, o elijo 1.000 y 20.000,

181
00:12:16,170 --> 00:12:18,630
o me acaba de elegir los 3 millones de dólares.

182
00:12:18,630 --> 00:12:20,760
Bueno, la mejor opción es tomar todos los números.

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

184
00:12:24,350 --> 00:12:31,340
la suma total es mejor que yo no fuera a tomar -1.

185
00:12:31,340 --> 00:12:36,460
Así que uno de los consejos que he mencionado antes fue a decir lo obvio claramente

186
00:12:36,460 --> 00:12:40,540
y la solución de fuerza bruta primero.

187
00:12:40,540 --> 00:12:44,340
¿Cuál es la solución de fuerza bruta en este problema? ¿Sí?

188
00:12:44,340 --> 00:12:46,890
[Jane] Bueno, creo que la solución de fuerza bruta

189
00:12:46,890 --> 00:12:52,600
sería la de sumar todas las combinaciones posibles (ininteligible).

190
00:12:52,600 --> 00:12:58,250
[Yu] Bueno. Así que la idea de Jane es tomar cada posible -

191
00:12:58,250 --> 00:13:01,470
Estoy parafraseando - es tomar cada submatriz continuo posible,

192
00:13:01,470 --> 00:13:07,840
calcular su suma, y ​​luego tomar el máximo de todos los subconjuntos posibles continuas.

193
00:13:07,840 --> 00:13:13,310
Lo que identifica de forma exclusiva una submatriz en mi matriz de entrada?

194
00:13:13,310 --> 00:13:17,380
Como, ¿qué dos cosas que necesito? ¿Sí?

195
00:13:17,380 --> 00:13:19,970
(Estudiante, ininteligible) Derecho >>.

196
00:13:19,970 --> 00:13:22,130
Un límite inferior en el índice y el índice del límite superior

197
00:13:22,130 --> 00:13:28,300
determina de forma única una submatriz continua.

198
00:13:28,300 --> 00:13:31,400
[Estudiante Mujer] ¿Estamos estimando que es una serie de números únicos?

199
00:13:31,400 --> 00:13:34,280
[Yu] No. Así que la pregunta es, ¿estamos asumiendo nuestra amplia -

200
00:13:34,280 --> 00:13:39,000
es nuestra matriz todos los números únicos, y la respuesta es no.

201
00:13:39,000 --> 00:13:43,390
>> Si utilizamos nuestra solución de fuerza bruta, entonces los índices de inicio / fin

202
00:13:43,390 --> 00:13:47,200
únicamente determina nuestra subarray continua.

203
00:13:47,200 --> 00:13:51,680
Así que si iterar para todas las entradas de inicio posibles,

204
00:13:51,680 --> 00:13:58,320
y para todas las entradas finales> o = para empezar, y n <,

205
00:13:58,320 --> 00:14:05,570
a calcular la suma, y ​​luego tomamos la suma máxima que hemos visto hasta ahora.

206
00:14:05,570 --> 00:14:07,880
¿Está claro?

207
00:14:07,880 --> 00:14:12,230
¿Cuál es la gran O de esta solución?

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

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

210
00:14:18,860 --> 00:14:25,250
Tenga en cuenta que iterar desde 0 a n,

211
00:14:25,250 --> 00:14:27,520
así que eso es un bucle for.

212
00:14:27,520 --> 00:14:35,120
Nos iterar de nuevo casi desde el inicio hasta el final, por otro bucle.

213
00:14:35,120 --> 00:14:37,640
Y ahora, dentro de eso, tenemos que resumir cada entrada,

214
00:14:37,640 --> 00:14:43,810
así que eso es otro bucle for. Así que tenemos tres bucles for anidados, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Bien. Esto va como punto de partida.

216
00:14:46,560 --> 00:14:53,180
Nuestra solución no es peor que n ^ 3.

217
00:14:53,180 --> 00:14:55,480
¿Todos entienden la solución de fuerza bruta?

218
00:14:55,480 --> 00:14:59,950
>> Bien. Una solución mejor es utilizar una idea llamada de programación dinámica.

219
00:14:59,950 --> 00:15:03,040
Si usted toma CS124, que es Algoritmos y Estructuras de Datos,

220
00:15:03,040 --> 00:15:05,680
te volverás muy familiarizado con esta técnica.

221
00:15:05,680 --> 00:15:12,190
Y la idea es, tratar de construir soluciones a los problemas más pequeños primero.

222
00:15:12,190 --> 00:15:17,990
¿Qué quiero decir con esto es que en la actualidad tiene que preocuparse de dos cosas: de inicio y fin.

223
00:15:17,990 --> 00:15:29,340
Y eso es molesto. ¿Y si pudiéramos deshacernos de uno de esos parámetros?

224
00:15:29,340 --> 00:15:32,650
Una idea es - estamos dado a nuestro problema original,

225
00:15:32,650 --> 00:15:37,470
encontrar la suma máxima de cualquier submatriz en un intervalo [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Y ahora tenemos un nuevo subproblema, donde sabemos, en nuestro actual índice i,

227
00:15:47,400 --> 00:15:52,520
sabemos que debemos concluir allí. Nuestra subarray debe terminar en el índice actual.

228
00:15:52,520 --> 00:15:57,640
Así que el problema que queda es, ¿Dónde deberíamos comenzar nuestro subarray?

229
00:15:57,640 --> 00:16:05,160
¿Tiene esto sentido? Bien.

230
00:16:05,160 --> 00:16:12,030
Así que he codificado esto, y vamos a ver lo que esto significa.

231
00:16:12,030 --> 00:16:16,230
En el codirectory, hay un programa llamado subarray,

232
00:16:16,230 --> 00:16:19,470
y se tarda número de elementos,

233
00:16:19,470 --> 00:16:25,550
y devuelve la suma subarray máximo en mi lista arrastrando los pies.

234
00:16:25,550 --> 00:16:29,920
Así que en este caso, nuestro subarray máxima es de 3.

235
00:16:29,920 --> 00:16:34,850
Y eso ha tomado simplemente usando 2 y 1.

236
00:16:34,850 --> 00:16:38,050
Vamos a correr de nuevo. También es 3.

237
00:16:38,050 --> 00:16:40,950
Pero esta vez, tenga en cuenta cómo hemos llegado hasta el 3.

238
00:16:40,950 --> 00:16:46,690
Nos tomamos el - que acabamos de tomar la 3 se

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

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

241
00:16:55,080 --> 00:16:57,820
Vamos a correr en 10 artículos.

242
00:16:57,820 --> 00:17:03,200
Esta vez se trata de 7, tomamos el líder 3 y 4.

243
00:17:03,200 --> 00:17:09,450
Esta vez es 8, y obtenemos que tomando 1, 4 y 3.

244
00:17:09,450 --> 00:17:16,310
Así que para darle una intuición sobre cómo podemos resolver este problema transformado,

245
00:17:16,310 --> 00:17:18,890
vamos a echar un vistazo a este subconjunto.

246
00:17:18,890 --> 00:17:23,460
Nos dan la matriz de entrada, y sabemos que la respuesta es 8.

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

248
00:17:26,359 --> 00:17:29,090
Pero echemos un vistazo a cómo en realidad nos dieron esa respuesta.

249
00:17:29,090 --> 00:17:34,160
Echemos un vistazo a la submatriz máximo que desembocó en cada uno de estos índices.

250
00:17:34,160 --> 00:17:40,780
¿Cuál es la submatriz máxima que tiene que terminar en la primera posición?

251
00:17:40,780 --> 00:17:46,310
[Estudiante] Zero. >> Cero. Eso sí, no se toman el -5.

252
00:17:46,310 --> 00:17:50,210
Aquí va a ser 0 también. ¿Sí?

253
00:17:50,210 --> 00:17:56,470
(Estudiante, ininteligible)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, lo siento, es un -3.

255
00:17:58,960 --> 00:18:03,220
Así que este es un 2, este es un -3.

256
00:18:03,220 --> 00:18:08,690
Bien. Así -4, ¿cuál es la submatriz máximo para poner fin a esa posición

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

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

259
00:18:22,570 --> 00:18:28,060
Ahora, tengo que terminar en el lugar donde se encuentra a -2.

260
00:18:28,060 --> 00:18:39,330
Así 6, 5, 7, y la última es 4.

261
00:18:39,330 --> 00:18:43,480
Sabiendo que estos son mis entradas

262
00:18:43,480 --> 00:18:48,130
para el problema transformado en la que debe terminar en cada uno de estos índices,

263
00:18:48,130 --> 00:18:51,410
entonces mi respuesta final es simplemente, tomar un barrido a través,

264
00:18:51,410 --> 00:18:53,580
y tomar el número máximo.

265
00:18:53,580 --> 00:18:55,620
Así que en este caso es 8.

266
00:18:55,620 --> 00:19:00,010
Esto implica que la submatriz máxima termina en este índice,

267
00:19:00,010 --> 00:19:04,970
y comenzó en algún lugar antes de ella.

268
00:19:04,970 --> 00:19:09,630
¿Todo el mundo entiende esta submatriz transformado?

269
00:19:09,630 --> 00:19:22,160
>> Bien. Bueno, vamos a averiguar la recurrencia de esto.

270
00:19:22,160 --> 00:19:27,990
Vamos a considerar sólo las primeras entradas.

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

272
00:19:35,930 --> 00:19:39,790
Y luego estaba un -2 aquí, y eso la llevó a 6.

273
00:19:39,790 --> 00:19:50,800
Así que si llamo a la entrada en la posición i subproblema (i),

274
00:19:50,800 --> 00:19:54,910
¿Cómo puedo utilizar la respuesta 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
Si miro a, digamos, pero esta entrada.

277
00:20:04,550 --> 00:20:09,190
¿Cómo puedo calcular la respuesta 6 por mirar

278
00:20:09,190 --> 00:20:18,780
una combinación de esta matriz y las respuestas a subproblemas anteriores de esta matriz? ¿Sí?

279
00:20:18,780 --> 00:20:22,800
[Estudiante Mujer] Usted toma la matriz de sumas

280
00:20:22,800 --> 00:20:25,430
en la posición correcta antes de ella, por lo que la 8,

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

282
00:20:32,170 --> 00:20:36,460
[Yu] Así que la sugerencia es mirar a estos dos números,

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

284
00:20:40,090 --> 00:20:50,130
Así que este 8 se refiere a la respuesta para el subproblema (i - 1).

285
00:20:50,130 --> 00:20:57,300
Y vamos a llamar a mi matriz de entrada A.

286
00:20:57,300 --> 00:21:01,470
Con el fin de encontrar una submatriz máxima que termina en la posición i,

287
00:21:01,470 --> 00:21:03,980
Tengo dos opciones: o bien puede continuar la submatriz

288
00:21:03,980 --> 00:21:09,790
que terminó en el índice anterior, o comenzar una nueva matriz.

289
00:21:09,790 --> 00:21:14,190
Si yo fuera a continuar la submatriz que se inició en el índice anterior,

290
00:21:14,190 --> 00:21:19,260
entonces la suma máxima que puede alcanzar es la respuesta a la anterior subproblema

291
00:21:19,260 --> 00:21:24,120
además de la entrada de la matriz actual.

292
00:21:24,120 --> 00:21:27,550
Pero, también tiene la opción de iniciar un nuevo subconjunto,

293
00:21:27,550 --> 00:21:30,830
en cuyo caso la suma es 0.

294
00:21:30,830 --> 00:21:42,860
Así que la respuesta es, como máximo de 0, subproblema i - 1, además de la entrada de la matriz actual.

295
00:21:42,860 --> 00:21:46,150
¿Esta repetición tiene sentido?

296
00:21:46,150 --> 00:21:50,840
Nuestra recurrencia, como acabamos de descubrir, es subproblema i

297
00:21:50,840 --> 00:21:54,740
es igual al máximo de la subproblema anterior más mi entrada de la matriz actual,

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

299
00:22:01,490 --> 00:22:07,250
o 0, comenzar una nueva submatriz en mi índice actual.

300
00:22:07,250 --> 00:22:10,060
Y una vez que hemos construido esta mesa de soluciones, entonces nuestra respuesta final,

301
00:22:10,060 --> 00:22:13,950
acaba de hacer un barrido lineal a través de la matriz subproblema

302
00:22:13,950 --> 00:22:19,890
y tomar el número máximo.

303
00:22:19,890 --> 00:22:23,330
Se trata de una aplicación exacta de lo que acabo de decir.

304
00:22:23,330 --> 00:22:27,320
Así que creamos un array subproblema nuevo subproblemas.

305
00:22:27,320 --> 00:22:32,330
La primera entrada es o bien 0 o la primera entrada, la máxima de las dos.

306
00:22:32,330 --> 00:22:35,670
Y para el resto de los subproblemas

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

308
00:22:39,810 --> 00:22:49,960
Ahora se calcula el máximo de nuestra amplia subproblemas, y esa es nuestra respuesta final.

309
00:22:49,960 --> 00:22:54,130
>> Entonces, ¿cuánto espacio estamos usando en este algoritmo?

310
00:22:54,130 --> 00:23:01,470
Si sólo has tomado CS50, entonces no podría haber discutido mucho espacio.

311
00:23:01,470 --> 00:23:07,750
Bueno, una cosa a tener en cuenta es que llamé a malloc aquí con tamaño n.

312
00:23:07,750 --> 00:23:13,590
¿Qué es lo que te sugiere?

313
00:23:13,590 --> 00:23:17,450
Este algoritmo utiliza el espacio lineal.

314
00:23:17,450 --> 00:23:21,030
¿Podemos hacerlo mejor?

315
00:23:21,030 --> 00:23:30,780
¿Hay algo que te das cuenta que no es necesario para calcular la respuesta final?

316
00:23:30,780 --> 00:23:33,290
Creo que una mejor pregunta es, ¿qué información

317
00:23:33,290 --> 00:23:40,680
no tenemos que llevar todo el camino hasta el final?

318
00:23:40,680 --> 00:23:44,280
Ahora bien, si nos fijamos en estas dos líneas,

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

320
00:23:47,720 --> 00:23:50,910
y que sólo se preocupan por lo máximo que he visto hasta ahora.

321
00:23:50,910 --> 00:23:53,610
Para calcular nuestra respuesta final, no necesitamos toda la matriz.

322
00:23:53,610 --> 00:23:57,450
Sólo necesitamos el último número, los dos últimos números.

323
00:23:57,450 --> 00:24:02,630
Del último número de la matriz subproblema, y ​​el último número de la máxima.

324
00:24:02,630 --> 00:24:07,380
Así, de hecho, se puede fusionar estos bucles juntos

325
00:24:07,380 --> 00:24:10,460
y van desde el espacio lineal al espacio constante.

326
00:24:10,460 --> 00:24:15,830
Suma hasta el momento actual, aquí, reemplaza el papel del subproblema, nuestra amplia subproblema.

327
00:24:15,830 --> 00:24:20,020
Así suma actual, hasta el momento, es la respuesta a la subproblema anterior.

328
00:24:20,020 --> 00:24:23,450
Y esa suma, hasta ahora, ocupa el lugar de nuestro max.

329
00:24:23,450 --> 00:24:28,100
Calculamos el máximo a medida que avanzamos.

330
00:24:28,100 --> 00:24:30,890
Y así vamos desde el espacio lineal constante con el espacio,

331
00:24:30,890 --> 00:24:36,650
y también tenemos una solución a nuestro problema lineal submatriz.

332
00:24:36,650 --> 00:24:40,740
>> Este tipo de preguntas que usted recibirá durante una entrevista.

333
00:24:40,740 --> 00:24:44,450
¿Cuál es la complejidad de tiempo, lo que es la complejidad del espacio?

334
00:24:44,450 --> 00:24:50,600
¿Se puede hacer mejor? ¿Hay cosas que no son necesarias para mantener en todo?

335
00:24:50,600 --> 00:24:55,270
Hice esto para poner de relieve los análisis que se debe tomar por su cuenta

336
00:24:55,270 --> 00:24:57,400
como el que está trabajando a través de estos problemas.

337
00:24:57,400 --> 00:25:01,710
Siempre que se esté preguntando, "¿Puedo hacerlo mejor?"

338
00:25:01,710 --> 00:25:07,800
De hecho, ¿podemos hacer algo mejor que esto?

339
00:25:07,800 --> 00:25:10,730
Una especie de pregunta capciosa. No puedes, porque hay que

340
00:25:10,730 --> 00:25:13,590
al menos leer la entrada al problema.

341
00:25:13,590 --> 00:25:15,570
Así que el hecho de que usted necesita por lo menos leer la entrada al problema

342
00:25:15,570 --> 00:25:19,580
significa que no se puede hacer nada mejor que el tiempo lineal,

343
00:25:19,580 --> 00:25:22,870
y no se puede hacer nada mejor que un espacio constante.

344
00:25:22,870 --> 00:25:27,060
Así que este es, de hecho, la mejor solución para este problema.

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

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

347
00:25:35,190 --> 00:25:38,350
"Dada una matriz de enteros n, positivo, cero o negativo,

348
00:25:38,350 --> 00:25:41,680
que representan el precio de una acción más de n días,

349
00:25:41,680 --> 00:25:44,080
escribir una función para calcular el beneficio máximo que se puede hacer

350
00:25:44,080 --> 00:25:49,350
teniendo en cuenta que usted compra y venta de valores en exactamente 1 n estos días. "

351
00:25:49,350 --> 00:25:51,690
Esencialmente, queremos comprar barato, vender caro.

352
00:25:51,690 --> 00:25:58,580
Y queremos averiguar el mejor beneficio que podemos hacer.

353
00:25:58,580 --> 00:26:11,500
Volviendo a mi consejo, ¿cuál es el claro de inmediato, respuesta más simple, pero es lento?

354
00:26:11,500 --> 00:26:17,690
¿Sí? (Estudiante, ininteligible) >> Sí.

355
00:26:17,690 --> 00:26:21,470
>> Por lo que se acaba de ir bien y mirar los precios de las acciones

356
00:26:21,470 --> 00:26:30,550
en cada punto en el tiempo, (ininteligible).

357
00:26:30,550 --> 00:26:33,990
[Yu] Bueno, por lo que su solución - la sugerencia de la computación

358
00:26:33,990 --> 00:26:37,380
el más bajo y el más alto computar no funciona necesariamente

359
00:26:37,380 --> 00:26:42,470
porque la más alta podría ocurrir antes de la más baja.

360
00:26:42,470 --> 00:26:47,340
Entonces, ¿cuál es la solución de fuerza bruta para este problema?

361
00:26:47,340 --> 00:26:53,150
¿Cuáles son las dos cosas que necesito para determinar unívocamente el beneficio que hago? Derecha.

362
00:26:53,150 --> 00:26:59,410
La solución de fuerza bruta es - oh, por lo que, la sugerencia de George es que sólo necesitan dos días

363
00:26:59,410 --> 00:27:02,880
para determinar unívocamente el beneficio de esos dos días.

364
00:27:02,880 --> 00:27:06,660
Así que calcular cada par, como compra / venta,

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

366
00:27:12,850 --> 00:27:18,000
Calcule la ganancia máxima que hacemos después de iterar sobre todos los pares de días.

367
00:27:18,000 --> 00:27:20,330
Esa será nuestra respuesta final.

368
00:27:20,330 --> 00:27:25,730
Y que la solución será O (n ^ 2), porque no hay n elegir dos pares -

369
00:27:25,730 --> 00:27:30,270
de días que se puede elegir entre los días finales.

370
00:27:30,270 --> 00:27:32,580
Muy bien, así que no voy a ir sobre la solución de fuerza bruta aquí.

371
00:27:32,580 --> 00:27:37,420
Yo te voy a decir que hay una solución log n n.

372
00:27:37,420 --> 00:27:45,550
¿Qué algoritmo ve actualmente sabemos que es n log n?

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

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

375
00:27:54,790 --> 00:27:57,760
y, de hecho, una forma de resolver este problema es utilizar

376
00:27:57,760 --> 00:28:04,400
una especie de mezcla tipo de idea se llama, en general, dividir y conquistar.

377
00:28:04,400 --> 00:28:07,570
Y la idea es la siguiente.

378
00:28:07,570 --> 00:28:12,400
Quiere calcular la mejor compra / venta pareja en la mitad izquierda.

379
00:28:12,400 --> 00:28:16,480
Encuentra el mejor beneficio que usted puede hacer, sólo con el n primera de dos días.

380
00:28:16,480 --> 00:28:19,780
Entonces usted quiere oompute la mejor compra / venta pareja en la mitad derecha,

381
00:28:19,780 --> 00:28:23,930
por lo que el n duran más de dos días.

382
00:28:23,930 --> 00:28:32,400
Y ahora la pregunta es, ¿cómo podemos combinar estas soluciones de volver a estar juntos?

383
00:28:32,400 --> 00:28:36,320
¿Sí? (Estudiante, ininteligible)

384
00:28:36,320 --> 00:28:49,890
>> Okay. Así que permítanme hacer un dibujo.

385
00:28:49,890 --> 00:29:03,870
¿Sí? (George, ininteligible)

386
00:29:03,870 --> 00:29:06,450
>> Exactamente. Solución de George es exactamente correcto.

387
00:29:06,450 --> 00:29:10,040
Así que su sugerencia es, en primer lugar calcular mejor la compra / venta par,

388
00:29:10,040 --> 00:29:16,050
y que se produce en la mitad izquierda, así que vamos a llamar a esa izquierda, izquierda.

389
00:29:16,050 --> 00:29:20,790
La mejor compra / venta par que se produce en la mitad derecha.

390
00:29:20,790 --> 00:29:25,180
Pero si sólo se comparan estos dos números, estamos perdiendo el caso

391
00:29:25,180 --> 00:29:30,460
donde comprar y vender aquí en algún lugar de la mitad derecha.

392
00:29:30,460 --> 00:29:33,810
Compramos en la mitad izquierda, vender en la mitad derecha.

393
00:29:33,810 --> 00:29:38,490
Y la mejor forma de calcular mejor la compra / venta par que se extiende por las dos mitades

394
00:29:38,490 --> 00:29:43,480
es calcular el mínimo aquí y calcular el máximo aquí

395
00:29:43,480 --> 00:29:45,580
y tomar su diferencia.

396
00:29:45,580 --> 00:29:50,850
Así que los dos casos en que la pareja de compra / venta se produce sólo aquí,

397
00:29:50,850 --> 00:30:01,910
sólo aquí, o en ambas mitades está definida por estos tres números.

398
00:30:01,910 --> 00:30:06,450
Así que nuestro algoritmo para combinar nuestras soluciones de nuevo juntos,

399
00:30:06,450 --> 00:30:08,350
queremos calcular mejor la compra / venta pareja

400
00:30:08,350 --> 00:30:13,120
donde compramos en la mitad izquierda y vender en la mitad derecha.

401
00:30:13,120 --> 00:30:16,740
Y la mejor manera de hacerlo es calcular el precio más bajo en el primer tiempo,

402
00:30:16,740 --> 00:30:20,360
el precio más alto en la mitad derecha, y tomar su diferencia.

403
00:30:20,360 --> 00:30:25,390
Los beneficios resultantes tres, estos tres números, se toma el máximo de los tres,

404
00:30:25,390 --> 00:30:32,720
y ese es el mejor beneficio que usted puede hacer durante estos primeros días y al final.

405
00:30:32,720 --> 00:30:36,940
Aquí las líneas importantes están en rojo.

406
00:30:36,940 --> 00:30:41,160
Esta es una llamada recursiva para calcular la respuesta en la mitad izquierda.

407
00:30:41,160 --> 00:30:44,760
Esta es una llamada recursiva para calcular la respuesta en la mitad derecha.

408
00:30:44,760 --> 00:30:50,720
Estos dos bucles para calcular el mínimo y el máximo del medio en la izquierda y la derecha, respectivamente.

409
00:30:50,720 --> 00:30:54,970
Ahora puedo calcular el beneficio que se extiende por las dos mitades,

410
00:30:54,970 --> 00:31:00,530
y la respuesta final es el máximo de estos tres.

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

412
00:31:04,120 --> 00:31:06,420
>> Así que, sí, tenemos un algoritmo, pero la pregunta más grande,

413
00:31:06,420 --> 00:31:08,290
¿Cuál es la complejidad de tiempo de esto?

414
00:31:08,290 --> 00:31:16,190
Y la razón por la que he mencionado tipo de combinación es que esta forma de dividir la respuesta

415
00:31:16,190 --> 00:31:19,200
en dos y luego la fusión de nuestras soluciones de nuevo juntos

416
00:31:19,200 --> 00:31:23,580
es exactamente el tipo de especie de mezcla.

417
00:31:23,580 --> 00:31:33,360
Así que déjame ir a través de la duración.

418
00:31:33,360 --> 00:31:41,340
Si se define una función de t (n) ser el número de pasos

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

420
00:31:50,010 --> 00:31:54,350
nuestros dos llamadas recursivas

421
00:31:54,350 --> 00:32:00,460
son cada uno va a costar t (n / 2),

422
00:32:00,460 --> 00:32:03,540
y hay dos de estas llamadas.

423
00:32:03,540 --> 00:32:10,020
Ahora tengo que calcular el mínimo de la mitad izquierda,

424
00:32:10,020 --> 00:32:17,050
que puedo hacer en n / 2 hora, más el máximo de la mitad derecha.

425
00:32:17,050 --> 00:32:20,820
Así que esto es sólo n.

426
00:32:20,820 --> 00:32:25,050
Y luego, además de un trabajo constante.

427
00:32:25,050 --> 00:32:27,770
Y esta ecuación de recurrencia

428
00:32:27,770 --> 00:32:35,560
es exactamente la ecuación de recurrencia de tipo de mezcla.

429
00:32:35,560 --> 00:32:39,170
Y todos sabemos que tipo de mezcla es log n n tiempo.

430
00:32:39,170 --> 00:32:46,880
Por lo tanto, nuestro algoritmo es también n log n tiempo.

431
00:32:46,880 --> 00:32:52,220
¿Esta iteración tiene sentido?

432
00:32:52,220 --> 00:32:55,780
Sólo una breve recapitulación de lo siguiente:

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

434
00:32:59,170 --> 00:33:02,750
en el transcurso de n días.

435
00:33:02,750 --> 00:33:06,010
La forma en que nos separamos nuestras llamadas recursivas

436
00:33:06,010 --> 00:33:11,980
está llamando a nuestra solución en los primeros días de n / 2,

437
00:33:11,980 --> 00:33:14,490
así que eso es una llamada,

438
00:33:14,490 --> 00:33:16,940
y luego llamar de nuevo en la segunda mitad.

439
00:33:16,940 --> 00:33:20,440
Así que eso es una llamada a otra.

440
00:33:20,440 --> 00:33:25,310
Y entonces nos encontramos con un mínimo en la mitad izquierda, lo que podemos hacer en el tiempo lineal,

441
00:33:25,310 --> 00:33:29,010
encontrar el máximo de la mitad derecha, lo que podemos hacer en tiempo lineal.

442
00:33:29,010 --> 00:33:31,570
Así que n / 2 + n / 2 es n.

443
00:33:31,570 --> 00:33:36,020
Entonces tenemos un trabajo constante, que es como hacer aritmética.

444
00:33:36,020 --> 00:33:39,860
Esta ecuación de recurrencia es exactamente la ecuación de recurrencia por tipo de mezcla.

445
00:33:39,860 --> 00:33:55,490
Por lo tanto, nuestro algoritmo de shuffle es también n log n.

446
00:33:55,490 --> 00:33:58,520
Entonces, ¿cuánto espacio estamos utilizando?

447
00:33:58,520 --> 00:34:04,910
Volvamos al código.

448
00:34:04,910 --> 00:34:09,420
>> Una mejor pregunta es, ¿cuántos marcos de pila es lo que siempre tienen en un momento dado?

449
00:34:09,420 --> 00:34:11,449
Puesto que estamos utilizando recursividad,

450
00:34:11,449 --> 00:34:23,530
el número de marcos de pila determina nuestro uso del espacio.

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

452
00:34:29,440 --> 00:34:36,889
Llamamos a barajar los días 8,

453
00:34:36,889 --> 00:34:41,580
que llamará a barajar en las primeras cuatro entradas,

454
00:34:41,580 --> 00:34:46,250
que llamará a una baraja en las primeras dos entradas.

455
00:34:46,250 --> 00:34:51,550
Así que nuestra pila es - esta es nuestra pila.

456
00:34:51,550 --> 00:34:54,980
Y entonces llamamos a barajar de nuevo los días 1,

457
00:34:54,980 --> 00:34:58,070
y eso es lo que nuestro escenario base es, por lo que regresar de inmediato.

458
00:34:58,070 --> 00:35:04,700
¿Tenemos alguna vez tiene más de marcos de pila esta gente?

459
00:35:04,700 --> 00:35:08,880
No. Debido a que cada vez que hacemos una invocación,

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

461
00:35:10,770 --> 00:35:13,950
dividimos nuestro tamaño a la mitad.

462
00:35:13,950 --> 00:35:17,020
Así que el número máximo de marcos de pila alguna vez tenemos en un momento dado

463
00:35:17,020 --> 00:35:28,460
es del orden de los marcos de registro n pila.

464
00:35:28,460 --> 00:35:42,460
Cada marco de pila dispone de espacio constante,

465
00:35:42,460 --> 00:35:44,410
y por lo tanto la cantidad total de espacio,

466
00:35:44,410 --> 00:35:49,240
la cantidad máxima de espacio que ha consumido alguna vez es O (log n) espacio

467
00:35:49,240 --> 00:36:03,040
donde n es el número de días.

468
00:36:03,040 --> 00:36:07,230
>> Ahora bien, siempre te preguntas, "¿Podemos hacerlo mejor?"

469
00:36:07,230 --> 00:36:12,390
Y en particular, ¿se puede reducir a un problema que ya hemos resuelto?

470
00:36:12,390 --> 00:36:20,040
Un consejo: sólo discuten dos problemas antes de esto, y que no va a ser aleatorio.

471
00:36:20,040 --> 00:36:26,200
Podemos convertir este problema en el mercado de valores problema subarray máxima.

472
00:36:26,200 --> 00:36:40,100
¿Cómo podemos hacer esto?

473
00:36:40,100 --> 00:36:42,570
Uno de ustedes? Emmy?

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

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

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

477
00:36:59,940 --> 00:37:10,610
estamos buscando a una suma sobre una submatriz continua.

478
00:37:10,610 --> 00:37:16,230
Y Emmy sugerencia para el problema acciones,

479
00:37:16,230 --> 00:37:30,720
considerar los cambios o deltas.

480
00:37:30,720 --> 00:37:37,440
Y una foto de esto es - este es el precio de una acción,

481
00:37:37,440 --> 00:37:42,610
pero si tomamos la diferencia entre cada día consecutivo -

482
00:37:42,610 --> 00:37:45,200
así vemos que el precio máximo, el beneficio máximo que podíamos hacer

483
00:37:45,200 --> 00:37:50,070
es que si vamos a comprar aquí y vender aquí.

484
00:37:50,070 --> 00:37:54,240
Pero echemos un vistazo a la continua - vamos a ver el problema submatriz.

485
00:37:54,240 --> 00:38:02,510
Así que aquí, podemos hacer - ir desde aquí hasta aquí,

486
00:38:02,510 --> 00:38:08,410
tenemos un cambio positivo, y luego ir desde aquí hasta aquí tenemos un cambio negativo.

487
00:38:08,410 --> 00:38:14,220
Pero luego, al pasar de aquí hasta aquí tenemos un cambio positivo enorme.

488
00:38:14,220 --> 00:38:20,930
Y estos son los cambios que se quieren sumar a conseguir nuestro beneficio final.

489
00:38:20,930 --> 00:38:25,160
Entonces tenemos más cambios negativos aquí.

490
00:38:25,160 --> 00:38:29,990
La clave para reducir nuestro problema de stock en nuestro problema subarray máximo

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

492
00:38:36,630 --> 00:38:40,630
Así que creamos una nueva matriz denominada deltas,

493
00:38:40,630 --> 00:38:43,000
inicializar la primera entrada sea 0,

494
00:38:43,000 --> 00:38:46,380
y luego para cada delta (i), deje que sea la diferencia

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

496
00:38:52,830 --> 00:38:55,530
Entonces llamamos a nuestro procedimiento de rutina para un subconjunto maximal

497
00:38:55,530 --> 00:39:01,500
pasando por una serie de Delta.

498
00:39:01,500 --> 00:39:06,440
Y porque subarray máximo es el tiempo lineal,

499
00:39:06,440 --> 00:39:09,370
y esta reducción, el proceso de creación de esta matriz delta,

500
00:39:09,370 --> 00:39:11,780
También es un tiempo lineal,

501
00:39:11,780 --> 00:39:19,060
entonces la solución final para las acciones es O (n) el trabajo más O (n) el trabajo, sigue siendo O (n) el trabajo.

502
00:39:19,060 --> 00:39:23,900
Así que tenemos una solución en tiempo lineal a nuestro problema.

503
00:39:23,900 --> 00:39:29,610
¿Todo el mundo entiende esta transformación?

504
00:39:29,610 --> 00:39:32,140
>> En general, una buena idea que usted siempre debe tener

505
00:39:32,140 --> 00:39:34,290
es tratar de reducir un problema nuevo que se está viendo.

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

507
00:39:37,700 --> 00:39:39,590
tratar de reducirla a un viejo problema.

508
00:39:39,590 --> 00:39:41,950
Y si se puede utilizar todas las herramientas que he usado en el antiguo problema

509
00:39:41,950 --> 00:39:46,450
para resolver el nuevo problema.

510
00:39:46,450 --> 00:39:49,010
Así que para terminar, entrevistas técnicas son desafiantes.

511
00:39:49,010 --> 00:39:52,280
Estos problemas son probablemente algunos de los problemas más difíciles

512
00:39:52,280 --> 00:39:54,700
que se pueden ver en una entrevista,

513
00:39:54,700 --> 00:39:57,690
así que si usted no entiende todos los problemas que acabamos de cubrir, está bien.

514
00:39:57,690 --> 00:40:01,080
Estos son algunos de los problemas más 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
Me dio un montón de problemas en el volante, así que definitivamente comprobar ésos hacia fuera.

517
00:40:08,170 --> 00:40:11,690
Y buena suerte en sus entrevistas. Todos mis recursos se publican en este enlace,

518
00:40:11,690 --> 00:40:15,220
y uno de mis amigos mayores se ha ofrecido a hacer simulacros de entrevistas técnicas,

519
00:40:15,220 --> 00:40:22,050
así que si usted está interesado, un eMail Yao en esa dirección de correo electrónico.

520
00:40:22,050 --> 00:40:26,070
Si tiene algunas preguntas, me puedes preguntar.

521
00:40:26,070 --> 00:40:28,780
¿Ustedes tienen preguntas específicas relacionadas con entrevistas técnicas

522
00:40:28,780 --> 00:40:38,440
o cualquier otro problema que hemos visto hasta ahora?

523
00:40:38,440 --> 00:40:49,910
Bien. Bueno, buena suerte en sus entrevistas.

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