[Powered by Google Translate] [Seminario: Entrevistas Técnicos] [Kenny Yu, Harvard University] [Esta es CS50.] [CS50.TV] Hola a todos, soy Kenny. Actualmente soy un joven ciencia que estudia informática. Soy un ex TF CS, y me gustaría tener esto cuando era un underclassman, y es por eso que pongo a este seminario. Así que espero que os guste. Este seminario trata de entrevistas técnicas, y todos mis recursos se pueden encontrar en este enlace, este enlace aquí, un par de recursos. Así que hice una lista de problemas, en realidad, bastantes problemas. También una página de recursos en general donde podemos encontrar consejos sobre cómo prepararse para una entrevista, consejos sobre lo que debe hacer durante una entrevista real, así como la forma de abordar los problemas y los recursos para futuras referencias. Es todo en línea. Y sólo para prologar este seminario, un descargo de responsabilidad, como esto no debería - su preparación de la entrevista no debe limitarse a esta lista. Esto sólo pretende ser una guía, y además se debería tomar todo lo que digo con un grano de sal, sino también utilizar todo lo que solía ayudarle en su preparación de la entrevista. 

Voy a acelerar a través de las siguientes diapositivas por lo que podemos llegar a los estudios de casos reales. La estructura de una entrevista para un postion ingeniería de software, típicamente es de 30 a 45 minutos, múltiples rondas, dependiendo de la compañía. A menudo se le codificación en un tablero blanco. Así que una pizarra blanca como esta, pero a menudo en una escala más pequeña. Si tienes una entrevista telefónica, usted probablemente va a utilizar ya sea collabedit o un documento de Google Docs para que vean ustedes viven codificación mientras que usted está siendo entrevistado por teléfono. Una entrevista en sí es de 2 o 3 problemas prueba tus conocimientos de informática. Y será casi definitivamente involucrar codificación. Los tipos de preguntas que se ven son por lo general las estructuras de datos y algoritmos. Y al hacer este tipo de problemas, le preguntarán, como, ¿cuál es el tiempo y la complejidad del espacio, grande O? A menudo, también piden más alto nivel preguntas, así, el diseño de un sistema, ¿cómo diseñar el código? ¿Qué interfaces, lo que las clases, los módulos que lo que tiene en su sistema, y cómo éstas interactúan entre sí? Así que las estructuras de datos y algoritmos, así como sistemas de diseño. 

Algunos consejos generales Antes de profundizar en los estudios de casos. Creo que la regla más importante es siempre estar pensando en voz alta. La entrevista se supone que es su oportunidad para mostrar su proceso de pensamiento. El objetivo de la entrevista es que el entrevistador para evaluar cómo piensa y cómo usted va a través de un problema. La peor cosa que puedes hacer es estar en silencio durante toda la entrevista. Eso es nada bueno. Cuando se le da a una pregunta, usted también quiere asegurarse de que entiende la pregunta. Así que repito la pregunta de nuevo en sus propias palabras y tratar de trabajar a fondo algunos casos de prueba sencillos para asegurarse de que entiende la pregunta. 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. Incluso podría descubrir algunos patrones para ayudar a resolver el problema. Su gran consejo es no sentirse frustrado. No se frustre. Las entrevistas son un reto, pero lo peor que se puede hacer, además de ser silenciosa, se visiblemente frustrado. Usted no quiere dar esa impresión a un entrevistador. Una cosa que usted - así, muchas personas, cuando van a una entrevista, en su intento de tratar de encontrar la mejor solución primero, cuando en realidad, por lo general hay una solución obvia. Puede ser que sea lento, puede ser ineficiente, sino que sólo debe decirlo, sólo por lo que tiene un punto de partida para trabajar mejor. También, señalando la solución es lento, en términos de O gran complejidad de tiempo o la complejidad del espacio, mostrará al entrevistador que usted entiende estos problemas al escribir código. Así que no tenga miedo de llegar con el primer algoritmo más simple y luego trabajar mejor desde allí. Cualquier pregunta hasta ahora? Bien. 

Así que vamos a bucear en nuestro primer problema. "Dada una matriz de enteros n, escribe una función que baraja la matriz en lugar de tal manera que todas las permutaciones de los n enteros son igualmente probables. " Y se supone que tiene disponible un generador de número entero aleatorio que genera un número entero en el intervalo de 0 a i, rango medio. ¿Todo el mundo entiende esta pregunta? Te doy una matriz de enteros n, y quiero que barájalo. En mi directorio, escribí unos cuantos programas para demostrar lo que quiero decir. Voy a barajar una matriz de 20 elementos, -10 a 9, y quiero dar salida a una lista como esta. Así que esta es mi matriz ordenada de entrada, y quiero que barájalo. Vamos a hacerlo de nuevo. ¿Todo el mundo entiende la pregunta? Bien. Así que le toca a usted. ¿Cuáles son algunas ideas? ¿Puede hacerlo como n ^ 2, n log n, n? Abierto a sugerencias. Bien. Así que una idea, sugerida por el Emmy, es calcular primero un número aleatorio, entero aleatorio, en un rango de 0 a 20. Así que asumir nuestra matriz tiene una longitud de 20. En nuestro diagrama de 20 elementos, esta es nuestra matriz de entrada. Y ahora, su sugerencia es crear una nueva matriz, por lo que esta será la matriz de salida. Y basado en el i devuelto por rand - así que si yo estaba, digamos, 17, copiar el elemento 17a en la primera posición. Ahora tenemos que eliminar - tenemos que cambiar todos los elementos aquí de manera que tenemos un hueco en el extremo y no hay agujeros en el medio. Y ahora repetimos el proceso. Ahora elegimos un número entero aleatorio entre 0 y 19. Tenemos una i nuevo aquí, y copiamos este elemento en esta posición. Entonces cambiamos artículos una y repetimos el proceso hasta que tengamos nuestra nueva matriz completa. ¿Cuál es el tiempo de ejecución de este algoritmo? Bueno, vamos a considerar el impacto de esto. Estamos cambiando cada elemento. Cuando eliminar esta i, que están cambiando todos los elementos después de que a la izquierda. Y esa es una operación O (n) Coste porque lo que si se elimina el primer elemento? Así, por cada retiro, removemos - cada retiro incurre en una operación O (n), y puesto que tenemos n mudanzas, esto conduce a una operación O (n ^ 2) shuffle. Bien. Así buen comienzo. Buen comienzo. 

Otra sugerencia es usar algo conocido como el shuffle Knuth, o la confusión Fisher-Yates. Y en realidad es un shuffle tiempo lineal. Y la idea es muy similar. Una vez más, tenemos nuestra matriz de entrada, pero en lugar de utilizar dos matrices para nuestra entrada / salida, se utiliza la primera parte de la matriz para seguir la pista de nuestra parte barajado, y hacemos un seguimiento, y luego dejar el resto de nuestra gama para la parte unshuffled. Esto es lo que quiero decir. Comenzamos con - elegimos una i, una matriz a partir de 0 a 20. Nuestro actual del puntero apunta al primer índice. Elegimos algunos i aquí y ahora cambiamos. Así que si esto era 5 y esto fue 4, la matriz resultante tendrá 5 aquí y 4 aquí. Y ahora observamos un marcador de aquí. Todo a la izquierda se barajan, y todo lo que está a la derecha unshuffled. Y ahora podemos repetir el proceso. Elegimos un índice aleatorio entre 1 y 20 ahora. Así que supongamos que nuestro nuevo yo está aquí. Ahora cambiamos esto i con nuestra nueva posición actual aquí. Así que hacer un intercambio de ida y vuelta así. Permítanme que aparezca el código para que sea más concreto. Comenzamos con nuestra elección de i - empezamos con i igual a 0, elegimos un lugar al azar j en la parte unshuffled de la matriz, i a n-1. Así que si estoy aquí, elegir un índice aleatorio entre aquí y el resto de la matriz, e intercambiamos. Este es todo el código necesario para mezclar tu matriz. ¿Alguna pregunta? 

Pues bien, uno necesita pregunta es, ¿por qué es esto correcto? ¿Por qué todas las permutaciones igualmente probable? Y no voy a pasar por la prueba de ello, pero muchos problemas en ciencias de la computación puede ser probado a través de la inducción. ¿Cuántos de ustedes están familiarizados con la inducción? Bien. Cool. Así que usted puede demostrar la exactitud de este algoritmo por simple inducción, donde la hipótesis de inducción sería asumir que mi baraja vuelve cada permutación misma probabilidad a los elementos por primera vez. Ahora, consideremos i + 1. Y por la forma en que elegimos nuestro índice j para intercambiar, esto lleva a - y luego se trabaja en los detalles, por lo menos una prueba completa de por qué este algoritmo devuelve todas las permutaciones con una probabilidad igualmente probables. 

Todo problema derecha, al lado. Así que "dado un conjunto de números enteros, postive, cero, negativo, escribir una función que calcula la suma máxima de cualquier submatriz continueous de la matriz de entrada. " Un ejemplo aquí es, en el caso en que todos los números son positivos, a continuación, en la actualidad la mejor opción es tomar todo el conjunto. 1, 2, 3, 4, es igual a 10. Cuando usted tiene algunos aspectos negativos de allí, en este caso sólo queremos los dos primeros porque elegir -1 y / o -3 hará que nuestra suma hacia abajo. A veces puede que tengamos que empezar en el medio de la matriz. A veces tenemos que elegir nada en absoluto, es mejor que no tener nada. Y a veces es mejor tomar la caída, porque después de lo que es super grande. Entonces, alguna idea? (Estudiante, ininteligible) >> Si. Supongamos que yo no tomo -1. Entonces, o elijo 1.000 y 20.000, o me acaba de elegir los 3 millones de dólares. Bueno, la mejor opción es tomar todos los números. Esta -1, a pesar de ser negativo, la suma total es mejor que yo no fuera a tomar -1. Así que uno de los consejos que he mencionado antes fue a decir lo obvio claramente y la solución de fuerza bruta primero. ¿Cuál es la solución de fuerza bruta en este problema? ¿Sí? [Jane] Bueno, creo que la solución de fuerza bruta sería la de sumar todas las combinaciones posibles (ininteligible). [Yu] Bueno. Así que la idea de Jane es tomar cada posible - Estoy parafraseando - es tomar cada submatriz continuo posible, calcular su suma, y ​​luego tomar el máximo de todos los subconjuntos posibles continuas. Lo que identifica de forma exclusiva una submatriz en mi matriz de entrada? Como, ¿qué dos cosas que necesito? ¿Sí? (Estudiante, ininteligible) Derecho >>. Un límite inferior en el índice y el índice del límite superior determina de forma única una submatriz continua. [Estudiante Mujer] ¿Estamos estimando que es una serie de números únicos? [Yu] No. Así que la pregunta es, ¿estamos asumiendo nuestra amplia - es nuestra matriz todos los números únicos, y la respuesta es no. 

Si utilizamos nuestra solución de fuerza bruta, entonces los índices de inicio / fin únicamente determina nuestra subarray continua. Así que si iterar para todas las entradas de inicio posibles, y para todas las entradas finales> o = para empezar, y n <, a calcular la suma, y ​​luego tomamos la suma máxima que hemos visto hasta ahora. ¿Está claro? ¿Cuál es la gran O de esta solución? TimeWise. No del todo n ^ 2. Tenga en cuenta que iterar desde 0 a n, así que eso es un bucle for. Nos iterar de nuevo casi desde el inicio hasta el final, por otro bucle. Y ahora, dentro de eso, tenemos que resumir cada entrada, así que eso es otro bucle for. Así que tenemos tres bucles for anidados, n ^ 3. Bien. Esto va como punto de partida. Nuestra solución no es peor que n ^ 3. ¿Todos entienden la solución de fuerza bruta? 

Bien. Una solución mejor es utilizar una idea llamada de programación dinámica. Si usted toma CS124, que es Algoritmos y Estructuras de Datos, te volverás muy familiarizado con esta técnica. Y la idea es, tratar de construir soluciones a los problemas más pequeños primero. ¿Qué quiero decir con esto es que en la actualidad tiene que preocuparse de dos cosas: de inicio y fin. Y eso es molesto. ¿Y si pudiéramos deshacernos de uno de esos parámetros? Una idea es - estamos dado a nuestro problema original, encontrar la suma máxima de cualquier submatriz en un intervalo [O, n-1]. Y ahora tenemos un nuevo subproblema, donde sabemos, en nuestro actual índice i, sabemos que debemos concluir allí. Nuestra subarray debe terminar en el índice actual. Así que el problema que queda es, ¿Dónde deberíamos comenzar nuestro subarray? ¿Tiene esto sentido? Bien. Así que he codificado esto, y vamos a ver lo que esto significa. En el codirectory, hay un programa llamado subarray, y se tarda número de elementos, y devuelve la suma subarray máximo en mi lista arrastrando los pies. Así que en este caso, nuestro subarray máxima es de 3. Y eso ha tomado simplemente usando 2 y 1. Vamos a correr de nuevo. También es 3. Pero esta vez, tenga en cuenta cómo hemos llegado hasta el 3. Nos tomamos el - que acabamos de tomar la 3 se porque está rodeado de negativos en ambos lados, que aportará una suma <3. Vamos a correr en 10 artículos. Esta vez se trata de 7, tomamos el líder 3 y 4. Esta vez es 8, y obtenemos que tomando 1, 4 y 3. Así que para darle una intuición sobre cómo podemos resolver este problema transformado, vamos a echar un vistazo a este subconjunto. Nos dan la matriz de entrada, y sabemos que la respuesta es 8. Tomamos el 1, 4, y 3. Pero echemos un vistazo a cómo en realidad nos dieron esa respuesta. Echemos un vistazo a la submatriz máximo que desembocó en cada uno de estos índices. ¿Cuál es la submatriz máxima que tiene que terminar en la primera posición? [Estudiante] Zero. >> Cero. Eso sí, no se toman el -5. Aquí va a ser 0 también. ¿Sí? (Estudiante, ininteligible) [Yu] Oh, lo siento, es un -3. Así que este es un 2, este es un -3. Bien. Así -4, ¿cuál es la submatriz máximo para poner fin a esa posición donde -4 es en? Cero. Uno? 1, 5, 8. Ahora, tengo que terminar en el lugar donde se encuentra a -2. Así 6, 5, 7, y la última es 4. Sabiendo que estos son mis entradas para el problema transformado en la que debe terminar en cada uno de estos índices, entonces mi respuesta final es simplemente, tomar un barrido a través, y tomar el número máximo. Así que en este caso es 8. Esto implica que la submatriz máxima termina en este índice, y comenzó en algún lugar antes de ella. ¿Todo el mundo entiende esta submatriz transformado? 

Bien. Bueno, vamos a averiguar la recurrencia de esto. Vamos a considerar sólo las primeras entradas. Así que aquí era 0, 0, 0, 1, 5, 8. Y luego estaba un -2 aquí, y eso la llevó a 6. Así que si llamo a la entrada en la posición i subproblema (i), ¿Cómo puedo utilizar la respuesta a un subproblema anterior Para responder a esta subproblema? Si miro a, digamos, pero esta entrada. ¿Cómo puedo calcular la respuesta 6 por mirar una combinación de esta matriz y las respuestas a subproblemas anteriores de esta matriz? ¿Sí? [Estudiante Mujer] Usted toma la matriz de sumas en la posición correcta antes de ella, por lo que la 8, a continuación, agregar el subproblema actual. [Yu] Así que la sugerencia es mirar a estos dos números, este número y este número. Así que este 8 se refiere a la respuesta para el subproblema (i - 1). Y vamos a llamar a mi matriz de entrada A. Con el fin de encontrar una submatriz máxima que termina en la posición i, Tengo dos opciones: o bien puede continuar la submatriz que terminó en el índice anterior, o comenzar una nueva matriz. Si yo fuera a continuar la submatriz que se inició en el índice anterior, entonces la suma máxima que puede alcanzar es la respuesta a la anterior subproblema además de la entrada de la matriz actual. Pero, también tiene la opción de iniciar un nuevo subconjunto, en cuyo caso la suma es 0. Así que la respuesta es, como máximo de 0, subproblema i - 1, además de la entrada de la matriz actual. ¿Esta repetición tiene sentido? Nuestra recurrencia, como acabamos de descubrir, es subproblema i es igual al máximo de la subproblema anterior más mi entrada de la matriz actual, lo que significa seguir la submatriz anterior, o 0, comenzar una nueva submatriz en mi índice actual. Y una vez que hemos construido esta mesa de soluciones, entonces nuestra respuesta final, acaba de hacer un barrido lineal a través de la matriz subproblema y tomar el número máximo. Se trata de una aplicación exacta de lo que acabo de decir. Así que creamos un array subproblema nuevo subproblemas. La primera entrada es o bien 0 o la primera entrada, la máxima de las dos. Y para el resto de los subproblemas usamos la repetición exacta que acaba de descubrir. Ahora se calcula el máximo de nuestra amplia subproblemas, y esa es nuestra respuesta final. 

Entonces, ¿cuánto espacio estamos usando en este algoritmo? Si sólo has tomado CS50, entonces no podría haber discutido mucho espacio. Bueno, una cosa a tener en cuenta es que llamé a malloc aquí con tamaño n. ¿Qué es lo que te sugiere? Este algoritmo utiliza el espacio lineal. ¿Podemos hacerlo mejor? ¿Hay algo que te das cuenta que no es necesario para calcular la respuesta final? Creo que una mejor pregunta es, ¿qué información no tenemos que llevar todo el camino hasta el final? Ahora bien, si nos fijamos en estas dos líneas, que sólo se preocupan por el subproblema anterior, y que sólo se preocupan por lo máximo que he visto hasta ahora. Para calcular nuestra respuesta final, no necesitamos toda la matriz. Sólo necesitamos el último número, los dos últimos números. Del último número de la matriz subproblema, y ​​el último número de la máxima. Así, de hecho, se puede fusionar estos bucles juntos y van desde el espacio lineal al espacio constante. Suma hasta el momento actual, aquí, reemplaza el papel del subproblema, nuestra amplia subproblema. Así suma actual, hasta el momento, es la respuesta a la subproblema anterior. Y esa suma, hasta ahora, ocupa el lugar de nuestro max. Calculamos el máximo a medida que avanzamos. Y así vamos desde el espacio lineal constante con el espacio, y también tenemos una solución a nuestro problema lineal submatriz. 

Este tipo de preguntas que usted recibirá durante una entrevista. ¿Cuál es la complejidad de tiempo, lo que es la complejidad del espacio? ¿Se puede hacer mejor? ¿Hay cosas que no son necesarias para mantener en todo? Hice esto para poner de relieve los análisis que se debe tomar por su cuenta como el que está trabajando a través de estos problemas. Siempre que se esté preguntando, "¿Puedo hacerlo mejor?" De hecho, ¿podemos hacer algo mejor que esto? Una especie de pregunta capciosa. No puedes, porque hay que al menos leer la entrada al problema. Así que el hecho de que usted necesita por lo menos leer la entrada al problema significa que no se puede hacer nada mejor que el tiempo lineal, y no se puede hacer nada mejor que un espacio constante. Así que este es, de hecho, la mejor solución para este problema. ¿Preguntas? Bien. 

Stock problema del mercado: "Dada una matriz de enteros n, positivo, cero o negativo, que representan el precio de una acción más de n días, escribir una función para calcular el beneficio máximo que se puede hacer teniendo en cuenta que usted compra y venta de valores en exactamente 1 n estos días. " Esencialmente, queremos comprar barato, vender caro. Y queremos averiguar el mejor beneficio que podemos hacer. Volviendo a mi consejo, ¿cuál es el claro de inmediato, respuesta más simple, pero es lento? ¿Sí? (Estudiante, ininteligible) >> Sí. >> Por lo que se acaba de ir bien y mirar los precios de las acciones en cada punto en el tiempo, (ininteligible). [Yu] Bueno, por lo que su solución - la sugerencia de la computación el más bajo y el más alto computar no funciona necesariamente porque la más alta podría ocurrir antes de la más baja. Entonces, ¿cuál es la solución de fuerza bruta para este problema? ¿Cuáles son las dos cosas que necesito para determinar unívocamente el beneficio que hago? Derecha. La solución de fuerza bruta es - oh, por lo que, la sugerencia de George es que sólo necesitan dos días para determinar unívocamente el beneficio de esos dos días. Así que calcular cada par, como compra / venta, calcular el beneficio, que puede ser negativo o positivo o cero. Calcule la ganancia máxima que hacemos después de iterar sobre todos los pares de días. Esa será nuestra respuesta final. Y que la solución será O (n ^ 2), porque no hay n elegir dos pares - de días que se puede elegir entre los días finales. Muy bien, así que no voy a ir sobre la solución de fuerza bruta aquí. Yo te voy a decir que hay una solución log n n. ¿Qué algoritmo ve actualmente sabemos que es n log n? No es una pregunta capciosa. 

Combinar tipo. Merge sort es n log n, y, de hecho, una forma de resolver este problema es utilizar una especie de mezcla tipo de idea se llama, en general, dividir y conquistar. Y la idea es la siguiente. Quiere calcular la mejor compra / venta pareja en la mitad izquierda. Encuentra el mejor beneficio que usted puede hacer, sólo con el n primera de dos días. Entonces usted quiere oompute la mejor compra / venta pareja en la mitad derecha, por lo que el n duran más de dos días. Y ahora la pregunta es, ¿cómo podemos combinar estas soluciones de volver a estar juntos? ¿Sí? (Estudiante, ininteligible) >> Okay. Así que permítanme hacer un dibujo. ¿Sí? (George, ininteligible) >> Exactamente. Solución de George es exactamente correcto. Así que su sugerencia es, en primer lugar calcular mejor la compra / venta par, y que se produce en la mitad izquierda, así que vamos a llamar a esa izquierda, izquierda. La mejor compra / venta par que se produce en la mitad derecha. Pero si sólo se comparan estos dos números, estamos perdiendo el caso donde comprar y vender aquí en algún lugar de la mitad derecha. Compramos en la mitad izquierda, vender en la mitad derecha. Y la mejor forma de calcular mejor la compra / venta par que se extiende por las dos mitades es calcular el mínimo aquí y calcular el máximo aquí y tomar su diferencia. Así que los dos casos en que la pareja de compra / venta se produce sólo aquí, sólo aquí, o en ambas mitades está definida por estos tres números. Así que nuestro algoritmo para combinar nuestras soluciones de nuevo juntos, queremos calcular mejor la compra / venta pareja donde compramos en la mitad izquierda y vender en la mitad derecha. Y la mejor manera de hacerlo es calcular el precio más bajo en el primer tiempo, el precio más alto en la mitad derecha, y tomar su diferencia. Los beneficios resultantes tres, estos tres números, se toma el máximo de los tres, y ese es el mejor beneficio que usted puede hacer durante estos primeros días y al final. Aquí las líneas importantes están en rojo. Esta es una llamada recursiva para calcular la respuesta en la mitad izquierda. Esta es una llamada recursiva para calcular la respuesta en la mitad derecha. Estos dos bucles para calcular el mínimo y el máximo del medio en la izquierda y la derecha, respectivamente. Ahora puedo calcular el beneficio que se extiende por las dos mitades, y la respuesta final es el máximo de estos tres. Bien. 

Así que, sí, tenemos un algoritmo, pero la pregunta más grande, ¿Cuál es la complejidad de tiempo de esto? Y la razón por la que he mencionado tipo de combinación es que esta forma de dividir la respuesta en dos y luego la fusión de nuestras soluciones de nuevo juntos es exactamente el tipo de especie de mezcla. Así que déjame ir a través de la duración. Si se define una función de t (n) ser el número de pasos para n días, nuestros dos llamadas recursivas son cada uno va a costar t (n / 2), y hay dos de estas llamadas. Ahora tengo que calcular el mínimo de la mitad izquierda, que puedo hacer en n / 2 hora, más el máximo de la mitad derecha. Así que esto es sólo n. Y luego, además de un trabajo constante. Y esta ecuación de recurrencia es exactamente la ecuación de recurrencia de tipo de mezcla. Y todos sabemos que tipo de mezcla es log n n tiempo. Por lo tanto, nuestro algoritmo es también n log n tiempo. ¿Esta iteración tiene sentido? Sólo una breve recapitulación de lo siguiente: T (n) es el número de pasos para calcular el máximo beneficio en el transcurso de n días. La forma en que nos separamos nuestras llamadas recursivas está llamando a nuestra solución en los primeros días de n / 2, así que eso es una llamada, y luego llamar de nuevo en la segunda mitad. Así que eso es una llamada a otra. Y entonces nos encontramos con un mínimo en la mitad izquierda, lo que podemos hacer en el tiempo lineal, encontrar el máximo de la mitad derecha, lo que podemos hacer en tiempo lineal. Así que n / 2 + n / 2 es n. Entonces tenemos un trabajo constante, que es como hacer aritmética. Esta ecuación de recurrencia es exactamente la ecuación de recurrencia por tipo de mezcla. Por lo tanto, nuestro algoritmo de shuffle es también n log n. Entonces, ¿cuánto espacio estamos utilizando? Volvamos al código. 

Una mejor pregunta es, ¿cuántos marcos de pila es lo que siempre tienen en un momento dado? Puesto que estamos utilizando recursividad, el número de marcos de pila determina nuestro uso del espacio. Vamos a considerar n = 8. Llamamos a barajar los días 8, que llamará a barajar en las primeras cuatro entradas, que llamará a una baraja en las primeras dos entradas. Así que nuestra pila es - esta es nuestra pila. Y entonces llamamos a barajar de nuevo los días 1, y eso es lo que nuestro escenario base es, por lo que regresar de inmediato. ¿Tenemos alguna vez tiene más de marcos de pila esta gente? No. Debido a que cada vez que hacemos una invocación, una invocación recursiva para mezclar, dividimos nuestro tamaño a la mitad. Así que el número máximo de marcos de pila alguna vez tenemos en un momento dado es del orden de los marcos de registro n pila. Cada marco de pila dispone de espacio constante, y por lo tanto la cantidad total de espacio, la cantidad máxima de espacio que ha consumido alguna vez es O (log n) espacio donde n es el número de días. 

Ahora bien, siempre te preguntas, "¿Podemos hacerlo mejor?" Y en particular, ¿se puede reducir a un problema que ya hemos resuelto? Un consejo: sólo discuten dos problemas antes de esto, y que no va a ser aleatorio. Podemos convertir este problema en el mercado de valores problema subarray máxima. ¿Cómo podemos hacer esto? Uno de ustedes? Emmy? (Emmy, ininteligible) [Yu] Exactamente. Así que el problema subarray máxima, estamos buscando a una suma sobre una submatriz continua. Y Emmy sugerencia para el problema acciones, considerar los cambios o deltas. Y una foto de esto es - este es el precio de una acción, pero si tomamos la diferencia entre cada día consecutivo - así vemos que el precio máximo, el beneficio máximo que podíamos hacer es que si vamos a comprar aquí y vender aquí. Pero echemos un vistazo a la continua - vamos a ver el problema submatriz. Así que aquí, podemos hacer - ir desde aquí hasta aquí, tenemos un cambio positivo, y luego ir desde aquí hasta aquí tenemos un cambio negativo. Pero luego, al pasar de aquí hasta aquí tenemos un cambio positivo enorme. Y estos son los cambios que se quieren sumar a conseguir nuestro beneficio final. Entonces tenemos más cambios negativos aquí. La clave para reducir nuestro problema de stock en nuestro problema subarray máximo es considerar los deltas entre los días. Así que creamos una nueva matriz denominada deltas, inicializar la primera entrada sea 0, y luego para cada delta (i), deje que sea la diferencia de mi entrada array (i), y la matriz (i - 1). Entonces llamamos a nuestro procedimiento de rutina para un subconjunto maximal pasando por una serie de Delta. Y porque subarray máximo es el tiempo lineal, y esta reducción, el proceso de creación de esta matriz delta, También es un tiempo lineal, 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. Así que tenemos una solución en tiempo lineal a nuestro problema. ¿Todo el mundo entiende esta transformación? 

En general, una buena idea que usted siempre debe tener es tratar de reducir un problema nuevo que se está viendo. Si parece familiar a un viejo problema, tratar de reducirla a un viejo problema. Y si se puede utilizar todas las herramientas que he usado en el antiguo problema para resolver el nuevo problema. Así que para terminar, entrevistas técnicas son desafiantes. Estos problemas son probablemente algunos de los problemas más difíciles que se pueden ver en una entrevista, así que si usted no entiende todos los problemas que acabamos de cubrir, está bien. Estos son algunos de los problemas más difíciles. Práctica, práctica, práctica. Me dio un montón de problemas en el volante, así que definitivamente comprobar ésos hacia fuera. Y buena suerte en sus entrevistas. Todos mis recursos se publican en este enlace, y uno de mis amigos mayores se ha ofrecido a hacer simulacros de entrevistas técnicas, así que si usted está interesado, un eMail Yao en esa dirección de correo electrónico. Si tiene algunas preguntas, me puedes preguntar. ¿Ustedes tienen preguntas específicas relacionadas con entrevistas técnicas o cualquier otro problema que hemos visto hasta ahora? Bien. Bueno, buena suerte en sus entrevistas. [CS50.TV]