Transcripciones
1. ¿Listo? Set. Vamos.: [ MÚSICA] Las entrevistas de codificación
son realmente intimidantes. Hay preguntas difíciles, acertijos
complicados e incluso problemas
irresolubles. Hay planes de ataque
para cada escenario, pero nos centraremos en
el más obvio cuando la pregunta
sea sencilla. Donde no hay bolas
curvas, ni trucos. Quiero asegurarme de
que as la entrevista. Hola. Soy Alvin, un científico investigador
en la industria. Esta primavera pasada,
recibí ofertas de Meta, Apple, Amazon, Tesla y más. En los últimos años, también
he recibido
ofertas de ingeniería de Google, NVIDIA, Facebook y Lyft. La experiencia que he adquirido de estas entrevistas fue invaluable. Realmente me senté a
entender ¿cuáles son todas las piezas que hicieron que
mis entrevistas fueran exitosas? ¿ Cuáles son los fundamentos
y los trucos? Este curso es un paso
hacia direcciones importantes, un paso adelante en la preparación de una
entrevista y un paso adelante en el dominio de la
codificación. Para lograr ambas cosas,
aprenderemos sobre las estructuras de datos. Las estructuras de datos son una forma organizar los datos y
en este curso, verás ejemplos,
cómo funcionan y cómo usarlos. Al final del curso,
tendrás dos habilidades, una para cada objetivo. Podrás elegir estructuras de
datos para
usar en la codificación de entrevistas.
Estoes un gran problema. En lugar de inventar algoritmos
eficientes, solo para el algoritmo eficiente
listo para sondeo de llamadas. También podrás implementar
estas estructuras de datos, combinando y mezclando
implementaciones según sea necesario. Este también
es uno. Conocer las implementaciones de
manera efectiva
te da código de inicio
en la entrevista, una ventaja libre. Espero que estés emocionado. Sé que
lo soy. Empecemos.
2. Por qué necesitas estructuras de datos: Permítame explicarle por qué necesita estructuras de datos,
en particular, por qué este curso sobre estructuras de
datos es tan crítico para su
crecimiento como codificador, y cómo puede aprovechar
este curso de manera efectiva. Golpearemos tres puntos de
conversación principales: primero, discutiremos los beneficios de dominar este tema, segundo, discutiremos objetivos específicos de
aprendizaje en el curso para
agilizar su dominio, y tercero, te
presentaremos un ejercicio para ayudarte a ganar dominio una
vez que termine el curso. Aquí está nuestro primer punto de conversación, por qué debería importarle, por qué
estoy impartiendo este curso, los beneficios que obtendrá. El mayor beneficio de tomar este curso es estar más
preparado para las entrevistas. Hay dos tipos de entrevistas
técnicas: Primero, hay preguntas de codificación, estos son
problemas específicos como, ¿cómo se invierte una cadena? ¿ Cómo se eliminan todos los números
duplicados? Segundo, hay preguntas de
diseño de sistemas. Estas son
preguntas más amplias como, ¿cómo construirías
un clon de Airbnb? Básicamente, cómo diseñar infraestructura y software
para un producto completo. Ambas entrevistas pueden
ser desafiantes, pero las estructuras de datos
te ayudan enormemente con ambas
entrevistas técnicas, y así te explicamos cómo hacerlo. Aquí hay dos beneficios específicos para conocer las estructuras de datos. Beneficio Número 1 es para su primera
entrevista técnica, entrevistas de codificación. Una parte significativa,
probablemente más de un tercio de las preguntas de codificación están
relacionadas con las estructuras de datos. Si conoces tus estructuras de
datos, a menudo
puedes aplicar algoritmos en lugar de diseñar
en tus entrevistas. Esto es enorme. No hace falta que se le
ocurran ideas desde cero. Si conoces la estructura de datos A
satisface exactamente estas necesidades, simplemente
dices eso: “Sé que los HashMaps son
ideales para este caso de uso; aquí te explicamos por qué y cómo lo
usaría”. Esa es una respuesta de
entrevista asesina. Beneficio Número 2 es para su entrevista de diseño de
sistemas, pudiendo optimizar los sistemas para su aplicación
específica, tanto en sus entrevistas
como en la práctica. No estoy
hablando de un sistema 10 por ciento o 25 por ciento más rápido, estoy hablando de un sistema
que opera órdenes de
magnitudes de manera más eficiente al elegir la base de datos, servidor o
infraestructurasin servidor, y más. Dirías: “Necesitamos gráficos acíclicos
dirigidos. Las bases de datos gráficas están optimizadas específicamente para este tipo de
relación, y he aquí por qué”. Ahora esa es una decisión de diseño bien informada y convincente. El Beneficio Número 3 está más allá
del proceso de entrevista. Con una comprensión
de las estructuras de datos, podrá abordar temas
más avanzados más
allá de sus entrevistas. En la informática en general, estos temas te dan nuevas
habilidades como hacer un juego. Una de las herramientas de creación de
juegos más populares, Unity, utiliza lo que se llama un paradigma de
programación orientada a datos. Como su nombre indica, comprender sus
estructuras de datos es bastante crítico. Para resumir, aquí hay tres beneficios para
comprender las estructuras de datos. Ser capaz de aplicar en lugar de diseñar desde cero
en entrevistas de codificación, ser capaz de optimizar para la aplicación en entrevistas de
diseño de sistemas, y poder abordar temas
más avanzados para abrir nuevas puertas más
allá de las entrevistas. En este curso, nos
centraremos en el beneficio Número 1. En todas las demás lecciones, practicarás la aplicación de estructuras de
datos
a las preguntas de la entrevista de codificación. Para realizar estos beneficios, deberás enfocarte en dos objetivos de aprendizaje
en este curso. El objetivo número 1 es
conocer cómo
funciona cada estructura de datos y practicar la implementación de
cada estructura de datos. Esto es clave porque en
el futuro, posible
que tenga que
implementar partes de estas estructuras de datos o combinar estructuras de
datos para
diferentes propósitos. Al igual que en mis otras clases, te
recomiendo mucho que
codifiques a mi lado, coloques este video en un lado de tu pantalla y tu editor de
código favorito en el otro lado. Copia mi código exactamente, y no hay necesidad de apresurarse, pausar el video
siempre que sea necesario. Lo más importante es que
construyas memoria muscular. Objetivo Número 2 es saber cómo y cuándo usar
cada estructura de datos. Específicamente, recuerde los pros
y los contras de cada estructura de datos. En la siguiente lección, compartiremos
elementos de rúbrica específicos por los que juzgará cada estructura de
datos. Los pros y los contras
no son débiles, son muy precisos
y están bien definidos. Para resumir, tus dos objetivos principales de
aprendizaje
son saber cómo funcionan las estructuras de
datos practicando implementaciones y
codificando junto a mí, segundo, saber cómo y cuándo usar los datos estructuras recordando los pros y los contras que repasamos. Nuestro último
punto de conversación aquí es cómo
solidificar su
comprensión de la estructura de datos más allá de este curso. Claro, es para practicar, pero en realidad no es
lo que esperas. Tenemos que dar
la vuelta a las tornas, fingir que eres el entrevistador, decir que estás escribiendo las preguntas de
estructura de datos ahora. Tu tarea es
practicar el diseño preguntas de estructura de
datos y hacerlo diariamente durante tres días. El objetivo es hacerte
pensar en las estructuras de datos solo unas cuantas veces después de
una buena noche de descanso. Haga esto durante su tiempo de inactividad,
durante su viaje, mientras se
cepilla los dientes o mientras espera en la fila. Agrega esto a tu lista de hacer esto
cuando me aburra. Cuanto más hagas esto, cuantas más preguntas
surjas, mejor
dominarás las estructuras de datos. Para recapitular, hemos discutido los beneficios de conocer las estructuras de
datos, mejor preparación para la entrevista y un paso adelante hacia temas
avanzados, hemos discutido sus objetivos de
aprendizaje, saber cómo implementar estructuras de
datos y cómo usar estructuras de datos, finalmente
hemos discutido una manera reforzar sus conocimientos, durante tres días después del curso, diseñar una
pregunta de estructura de datos cada día. También te animo a que
publiques tu pregunta en la sección de discusión, mi mala. De veras, en serio me refiero a esto. Es increíblemente gratificante para mí ver las
preguntas que publicas, ya sea una pregunta que hiciste o una pregunta sobre el curso, así que por favor sube.
Loespero con ansias. Eso es todo para la visión general. Para obtener una copia de estas diapositivas
y más recursos, asegúrese de consultar
el sitio web del curso. Hemos terminado la
descripción general y, a continuación, hablaremos sobre cómo
comparar las estructuras de datos.
3. ¿Qué es una estructura de datos "buena"?: ¿ Qué es una buena estructura de datos? Esto es clave para que entendamos porque uno de nuestros objetivos de
aprendizaje es saber cómo y cuándo
usar cada estructura de datos. Pero incluso antes de
hacer esa pregunta, primero
tenemos que preguntarnos ¿qué es
incluso una estructura de datos? Podemos comenzar con la definición
simple. Una estructura de datos es simplemente
una recopilación de datos. Eso suena sencillo así que ahora
vamos a expandirnos un poco sobre eso. Ampliemos esta
definición agregando algunas expectativas para
una estructura de datos. En particular,
deberíamos poder modificar y acceder a
los datos contenidos. Una estructura de datos
es una colección de datos a los que se puede
modificar y acceder. Para modificar la estructura de datos, debemos poder insertar
datos y eliminar datos. Para acceder a los datos, deberíamos poder
buscar y obtener datos. Estas son las cuatro acciones que toda estructura de datos
debe soportar. Cada una de estas acciones
puede ser muy lenta o muy rápida
dependiendo de la estructura de datos. Esto nos lleva a
nuestra siguiente sección, que es ¿cómo cuantificamos
muy rápido o muy lento? ¿ Qué tan eficiente o ineficiente
es cada una de estas acciones? Es decir, ¿cómo
evaluamos la eficiencia? Para evaluar la eficiencia
de un algoritmo, contaremos el número de operaciones que un algoritmo
toma para ejecutar. Por ejemplo, digamos que
tenemos esta lista de frutas y digamos que estamos
buscando aguacate. Para buscar en la lista, necesitamos recorrer
la lista uno por uno hasta que encontremos el artículo que
estamos buscando. En este caso, tomamos tres “operaciones” para
buscar aguacate. Sin embargo, si
el aguacate está al final o si no está
en la lista en absoluto, su algoritmo de búsqueda
tendría que atravesar todos los
elementos de la lista. Para una lista con n elementos, búsqueda de un valor en la lista
toma hasta n operaciones. Ahora bien, la definición de
operación es vaga. A lo mejor un acceso a memoria
es una operación, tal vez verificar la igualdad de cadenas
es otra operación. Digamos que el número
de operaciones necesarias para un solo elemento es c. Entonces la búsqueda
toma cn operaciones. Sin embargo, esta constante c
no nos interesa a la hora de
comparar algoritmos. Simplemente decimos que el
algoritmo toma O de n operaciones donde la
notación O oculta cualquier constante. esto le llamamos estadística O of n, el tiempo de ejecución o complejidad
computacional. Aquí hay otra manera de ver
lo que significa O de n complejidad. Lo que sabemos es que a medida que
la lista se alarga, el número de operaciones, sea que la cuentes, crece linealmente. Esto significa que la complejidad
computacional de nuestros algoritmos puede estar delimitada arriba y abajo
por funciones lineales. Cualquier algoritmo cuya
complejidad se encuentre dentro estos límites es O
de n. Como resultado, búsqueda en su lista tiene O de n complejidad computacional. Ahora sabemos que para una lista, que también se llama array, toma O de n veces una búsqueda. Para ser específicos,
buscamos un valor cuando no sabemos dónde está un
cierto valor en la lista. Sin embargo, digamos que queremos
buscar exactamente el i-ésimo ítem. Sabemos que queremos el i-ésimo artículo y no necesitamos
buscar un valor. Esa búsqueda lleva
tiempo constante u O de uno, porque simplemente
accedemos al i-ésimo ítem de la lista sin
mirar otros valores. Más específicamente, a medida que crece
la longitud de
la lista, el esfuerzo necesario para buscar
un elemento no cambia. Esto es genial. Obtener
un artículo es barato. Para maximizar la eficiencia, esto significa que debemos
usar una matriz cuando tenemos que
obtener más datos con
más frecuencia de lo que buscamos. Este es un ejemplo de
una comida para llevar práctica, y veremos muchos de
estos en el curso. Cada una de estas decisiones tiene como
objetivo maximizar la eficiencia. Deberíamos modificar nuestra definición
de estructura de datos. Una estructura de datos es
una recopilación de datos que se pueden
modificar y acceder de manera eficiente. En función de cada aplicación, necesitaremos elegir estructuras de
datos para garantizar esta eficiencia. Analizaremos la complejidad de algunas estructuras de datos
en este curso. A medida que realizamos estos análisis, nos encontraremos con varios órdenes
comunes de crecimiento. Los órdenes de crecimiento son la O de algo que
vimos antes. Ya vimos dos ejemplos de
órdenes de crecimiento. Crecimiento de tiempo constante O de uno
y crecimiento lineal O de n. Estos son seis órdenes comunes de crecimiento que se muestran
aquí en esta diapositiva. Pero para las estructuras de datos
y algoritmos
que estamos cubriendo solo veremos
cuatro órdenes de crecimiento, O
constante de uno, O
logarítmica de log n, O
lineal de n y O de n al cuadrado. Veremos cómo se
ve O de log n más adelante pero por ahora, ten en cuenta que tienes
una nueva herramienta para analizar complejidad
algorítmica
y que estos cuatro son los
órdenes de crecimiento más comunes que encontrarás. Para obtener una copia de estas diapositivas
y más recursos, asegúrese de consultar
el sitio web del curso. Ahora, tienes una nueva herramienta en tu haber y órdenes
de análisis de crecimiento, que te permite evaluar la complejidad
computacional para cualquier algoritmo. Más importante aún,
le permite elegir estructuras de
datos para
diferentes aplicaciones en
función de qué tan lenta o rápida
es una estructura de datos para la inserción, eliminación, extracción
y búsqueda. En la siguiente sección,
practicaremos análisis de órdenes de crecimiento.
4. Órdenes de práctica de crecimiento: Bienvenido a algunas prácticas de
estructuras de datos. En esta lección, vamos
a evaluar las estructuras de datos. En otras palabras,
evaluaremos algoritmos y estructuras de
datos utilizando un sistema
llamado órdenes de crecimiento. Esto es de lo que hablamos
en la lección anterior. La notación Big O nos
dirá qué tan rápido o lento tarda un algoritmo en
ejecutarse en función de su tamaño de entrada. Dejaremos a un lado
las tácticas de entrevista por ahora, al
menos tácticas
específicas de entrevista. Sin duda tendremos consejos relacionados con
entrevistas, pero primero debemos enfocarnos en
los fundamentos. Comience navegando
a esta URL, alvinwan.com/data
structures101/oog. Una vez que veas esta página, bifurca el proyecto para obtener
tu propia copia editable. Para ello, haz clic en el nombre del proyecto en la
parte superior izquierda para obtener un desplegable. Luego haga clic en los puntos suspensivos en la parte superior derecha para obtener
otro desplegable. Por último, haga clic en
el botón “Tenedor”. Entonces te sugiero colocar
tus ventanas Skillshare y Repl.it
lado a lado como se muestra aquí. Entonces deberías
ver una ventana
igual que la mía en el lado
derecho. Antes de
sumergirnos realmente en los problemas, revisemos los órdenes de
crecimiento de los que
hablamos anteriormente. Hay cuatro
órdenes de crecimiento relevantes. Como recordatorio, lo que estoy escribiendo
aquí es una función de n, donde n es el
tamaño de la entrada. Estas órdenes de crecimiento
nos dirán cuánto más lenta se
ejecutará
la función si aumentamos el tamaño de
entrada n Como resultado, queremos que los tiempos de ejecución crezcan más
lentamente a medida que la entrada
crezca en tamaño. Subir esta lista
de tiempos de ejecución es bueno. Cuanto más lento es el orden de crecimiento, más eficiente y preferido es el algoritmo
o estructura de datos. Un consejo que tengo para ti es que conozcas estos tiempos de ejecución de memoria, estos son los cuatro tiempos de ejecución centrales que necesitas conocer para
cada entrevista. El primero O (1)
o tiempo constante significa que no importa
cuál sea el tamaño de entrada, nuestra función siempre toma
la misma cantidad de tiempo. Segundo, O (log n)
en realidad hablará más adelante. Esto es un poco más complicado
de explicar. tercero O (n), o tiempo de ejecución lineal significa que
si nuestro tamaño de entrada se duplica, nuestro tiempo de ejecución también se duplica. Si nuestro tamaño de entrada se triplica entonces
nuestro tiempo de ejecución también se triplica. En otras palabras, nuestro tiempo de
ejecución de función en realidad crece linealmente con respecto a n. O (n) cuadrado aquí
significa cuadrático. Si duplicamos el tamaño de entrada, entonces nuestra función en tiempo de ejecución cuadruplica o cuadruplica el tiempo de
ejecución del algoritmo. Si nuestro tamaño de entrada se triplica entonces nuestro tiempo de ejecución
crecerá nueve veces, y así sucesivamente y así sucesivamente. Ahora vamos a sumergirnos directamente
en los ejercicios. En el lado derecho aquí, tengo nuestro primer ejercicio. ¿ Cuál es la
complejidad del tiempo de ejecución para lo siguiente? Aquí tenemos solo un
bucle for para i en rango n. Recuerda que rango
de n te da un entreable de n artículos
diferentes. ¿ Cuál es la
complejidad del tiempo de ejecución de esta función? Pausa el video aquí y
pruébalo y aquí está la respuesta. Esta función vuelve a
iterar una vez sobre cada elemento individual en este
iterable de n ítems. En otras palabras, itera
una vez por cada n elementos, iterará n veces. El tiempo de ejecución para esta función
o este algoritmo es O (n). [ Risas] Olvidé mostrarte. Aquí está la lista
de cuatro opciones de tiempo de
ejecución diferentes que tiene. guardaré aquí a medida que
avanzamos por estos ejercicios. Ahora pasemos
al segundo ejercicio. Cuál es la complejidad
del tiempo de ejecución de esta función, nuevamente, función de n. Aquí
tenemos dos, for loops. Cada uno de ellos
itera hasta n. Otra forma de ver
esto sería
preguntar ¿cuántas veces ha llamado la función
print? Pausa el video aquí e
intenta y aquí está la respuesta. Aquí iteramos sobre i n veces. Entonces por cada i, también
iteramos sobre j n veces. Eso lo convierte en un total
de n veces n carreras. Este algoritmo es O (n) al cuadrado. Pasemos al
siguiente ejercicio. ¿ Cuál es la
complejidad del tiempo de ejecución de esta función en función de n? Aquí empezamos con n.
Luego en este bucle while, por cada paso
tendremos ese valor. ¿ Cuál es la
complejidad del tiempo de ejecución de esta función? Puedes usar un proceso
de eliminación para averiguar cuál es el tiempo de ejecución. Pausa el video aquí y dale una oportunidad y aquí está la respuesta. La respuesta para esta función, que podemos deducir
por proceso de eliminación es O (logn). Así es como podría funcionar ese proceso de
eliminación. Aquí vemos que la función definitivamente no
es constante. Definitivamente toma un poco
más de tiempo cada vez n aumenta. Definitivamente no es O (1). Sin embargo, no es
tan lento como O (n), porque O (n) iteraría una vez. Iteraría sobre todos
los elementos uno por uno, hasta n. Sin embargo, no
hacemos eso. Nosotros la mitad del valor
cada vez. Sólo estamos
saltando un poco. No es tan lento como O (n), y no es tan rápido como O (1). El único tiempo de ejecución
intermedio es O (log n). Esto lo haremos más
precisamente más adelante para explicar cómo surge O (logn). Pero por ahora,
hablemos de una explicación visual. ¿ Qué aspecto tiene
el crecimiento logarítmico y qué significa
tener crecimiento logarítmico? crecimiento logarítmico es
realmente lento. Para darte una idea de cuán lenta considera la función de registro. Recuerde, n es el tamaño de entrada, el valor de log
n es el tiempo de ejecución. Digamos que nuestra entrada tiene tamaño dos, luego el tiempo de ejecución tiene
unidad uno tiempo de ejecución. Digamos que nuestra entrada
duplica el tamaño cuatro, el tiempo de ejecución aumenta en uno. Si nuestra entrada se duplica
nuevamente al tamaño ocho, el tiempo de ejecución aumenta en uno. Finalmente, si tu entrada
se duplica nuevamente al tamaño 16, el tiempo de ejecución aún solo
aumenta en uno. Observe que nuestro
tamaño de entrada debe seguir duplicándose para aumentar
el tiempo de ejecución en uno. Eso significa que nuestro algoritmo
es bastante eficiente. Visualmente, así es como se ve
eso. Trazamos el tamaño de entrada
a lo largo del eje x, trazamos tiempo de ejecución
a lo largo del eje
y, luego, trazamos todos los
puntos anteriores. Observe que nuestra función
crece bastante lentamente. De hecho, aquí hay una
parcela más grande con más valores de x. Puedes ver que nuestra gráfica
se vuelve plana muy rápidamente. En otras palabras, las
funciones logarítmicas crecen muy lentamente. Tengan esto en mente. Volvamos a nuestra función. Ahora podemos ver que yo aquí esto, o i o n, digamos que n necesita duplicar para aumentar el número de while loop itera por uno. Si n es dos, el bucle while itera una vez. Si n es cuatro, esto itera dos veces. Si n es ocho, esto itera tres veces, y así sucesivamente y así sucesivamente. Este valor n necesita
duplicarse cada vez para aumentar el tiempo de
ejecución en solo uno. Esto es crecimiento logarítmico. La otra forma de
ver esto es que nuestra función logarítmica reduce a
la mitad el tamaño de entrada en cada paso. Como puedes ver aquí, tenemos la mitad en cada paso, así que estamos dividiendo a la mitad nuestra carga cada paso.
Estaes la propina. Las funciones logarítmicas reducen la
mitad del tamaño de entrada en cada paso. Aquí tienes un resumen de
los tres ejemplos que
acabamos de repasar y
sus tiempos de ejecución. Eso es todo para los
“ejemplos básicos”. No me refiero básico, ya que en estos son fáciles. Estos ejemplos son
bastante confusos, sobre todo cuando
lo ves por primera vez. Digo básico para significar que
todos los demás ejemplos
serán alguna modificación de
esta estructura básica. Para averiguar los tiempos de ejecución
en el futuro, hay dos pasos. Primero, empieza por memorizar cómo son estos “
ejemplos básicos”. Segundo, una vez que
conozcas estos ejemplos, podrás memorizar las diferentes
modificaciones posibles. Ese es nuestro consejo. Ahora pasemos a
esas modificaciones, esos ejemplos complicados. Estas son nuevamente modificaciones
de los ejemplos anteriores para parecer confusos
o para cambiar el tiempo de ejecución. Aquí están los cuatro
tiempos de ejecución anteriores. Pasemos ahora a los
ejemplos, los ejemplos complicados. ¿ Cuántas veces se llama print
en la siguiente función? Aquí tenemos un bucle for anidado. Entonces tenemos esta condición if, si i es igual a j. Observe esta declaración if y ¿cómo afecta a
la complejidad en su caso? Pausa el video aquí y vuelve
a darle una toma, ¿cuántas veces se llama print? Aquí está la respuesta. Imprimir solo
se llama n veces. Esto se debe a que nuestro bucle
for interno solo se ejecuta una vez. Si i es igual a cero, entonces esta condición si solo pasa si j
también es igual a cero. Si i es igual a uno, nuevamente, esta condición si solo pasa
si j es igual a uno. Eso significa que por
cada bucle externo,
el bucle interno solo se ejecuta una vez, así que eso es n veces
una iteración, esto es un total de O (n). Pasemos ahora a nuestro
siguiente ejemplo complicado. ¿ Cuántas veces se
llama print en función de n? Aquí tenemos un bucle for anidado,
pero observe que el
bucle for interno solo cuenta hasta i. Nuevamente, ¿cómo
afecta eso al tiempo de ejecución si es que lo hace? Pausa el video aquí
y dale una oportunidad. Aquí está ahora la respuesta. Resulta que, aunque solo
estamos iterando hasta i, parece que podríamos tener
una complejidad de tiempo de ejecución más rápida. Resulta que no lo hacemos. Esto sigue siendo O (n) al cuadrado. Aquí está la razón por la que. Voy a tener que explicarte
mostrándote una foto. Aquí, digamos que tenemos un bucle for
normal en
el lado izquierdo. Entonces por cada valor
único de i, pasamos por j n veces. Haremos esto porque
i es igual a uno, iteramos a través de
todos los valores de j, i es igual a dos todos los valores de j y así sucesivamente y así
sucesivamente. Sigue haciendo esto. Lo que esto significa es que hay un total de n cuadrados diferentes
tiempos que imprimimos. Digamos que imprimimos i j. Ahora digamos que
tenemos este nuevo bucle for donde solo iteramos
solo hasta i. Entonces lo que eso significa es
aquí en esta primera fila, cuando i es igual a uno, nosotros solo corre j una vez. Cuando i es igual a dos
en la segunda fila, solo
corremos j dos veces. Cuando i es igual a tres, solo
corremos j tres veces, y así sucesivamente y así sucesivamente. Aquí, en lugar de n veces totales al cuadrado
que llamamos impresión, tenemos 1/2 veces n
veces al cuadrado que llamamos impresión. Sin embargo, 1/2 de n cuadrado todavía está en el
orden de n al cuadrado, razón por la
cual esta
función sigue siendo O de n cuadrada en complejidad
algorítmica. Con eso concluye este
complicado ejemplo. Si tiene alguna pregunta o
si aún está confundido, no dude en dejar una pregunta
en la sección de discusión. Estos son los cuatro
temas diferentes que cubrimos. Órdenes de crecimiento recuperamos
algunos ejemplos fundamentales, crecimiento
logarítmico y algunos ejemplos complicados
junto con cómo
modificaron esos ejemplos básicos
para un ejemplo más complicado. Para obtener una copia de estas diapositivas y el código terminado
de esta lección, asegúrese de consultar
el sitio web del curso. Con esto concluye esta lección para
evaluar las estructuras de datos.
5. Secuencias: pila vs. cola: Un formato común para
los datos es una secuencia, y en particular, hay dos tipos comunes de secuencias. Hay pilas, como una pila de ropa o una pila de rocas. También hay colas como una fila de personas o
un túnel de autos. Una vez que hayamos analizado
tanto las pilas como las colas, luego discutiremos
sus pros y sus contras. Primero arriba es una pila. Al igual que con una pila de rocas, agregas elementos a la
parte superior de la pila. Después para quitar una
roca o un artículo, también
lo retiras de
la parte superior de la pila. Resumimos esto como último en entrar, primero en salir; el último elemento que
agregues es el primero que eliminas. La
operación de inserción según esta lógica es entonces simple. Tomamos el valor
que queremos agregar, empujamos ese valor a
la pila y eso es todo. Se necesita constante u O
de una vez para insertar un nuevo valor en la pila ya que no importa
cuánto tiempo sea la pila, el esfuerzo de simplemente insertar
un elemento es el mismo. Tenga en cuenta que por definición, solo
podemos insertar valores
en la parte superior de la pila. La operación de eliminación también
es sencilla. Tomamos el último
valor que se muestra aquí en gris y hacemos pop el valor. Esto toma constante u
O de una vez también. Dado que la longitud de la
lista no cambia el número de operaciones, la eliminación amasa. Tomados en conjunto,
ahora sabemos que las pilas cuentan con
inserción y eliminación de tiempo constante, por lo que la modificación es barata. Pero ¿qué pasa con el acceso? ¿ Qué tan caro es buscar
un valor en la pila? Desafortunadamente, bastante lento. Digamos que estamos
buscando el valor 8. Hacemos pop un artículo, comprobamos su valor. ¿ 7 es igual a ocho? No lo es, entonces
sacamos otro valor, luego verificamos su valor. ¿ 2 es igual a 8? No es así que volamos una vez
más y luego comprobamos su valor. ¿ Es igual a 8? Absolutamente lo es, así que nuestra búsqueda está completa. Sin embargo, si hay
n artículos en la pila, necesitamos realizar
hasta n comprobaciones. Esto significa que la búsqueda toma
lineal u O de n tiempo. Obtener un
artículo específico es similar. Digamos que queremos buscar el
segundo elemento con el valor 8. Hacemos pop un artículo, ese es un artículo, hacemos pop otro artículo, son dos artículos, luego sacamos otro artículo,
son tres artículos. Por fin hemos buscado
el valor que queremos. Como antes, si hay
n artículos en la pila, es posible que necesitemos hasta n pops. Esto hace que fetch O de n tiempo. Para resumir, podemos insertar
y eliminar de una pila
en tiempo constante. La modificación es
eficiente. Sin embargo, búsqueda y la búsqueda
toman tiempo lineal. El acceso es ineficiente. Pero, ¿y si en lugar
de una pila de rocas, tuviéramos una fila de gente? La primera persona en unirse
a la línea debe ser la primera en dejarla. Esto se llama cola. Esta vez insertamos un valor
al final de la cola y eliminamos un valor del
frente de la cola. A esto lo llamamos una secuencia de primero en
entrar, primero en salir o una cola. Como mencionamos antes,
la inserción es sencilla. Consideramos un valor para agregar, luego poner en cola ese
elemento en la cola. No importa la
longitud de la lista, la simplicidad de
inserción no se ve afectada. Se trata de una O de una operación. La eliminación es similar. Consideramos un valor para
eliminar en la foto en gris, luego eliminar de la cola ese
valor de la cola. Esto también es una O
de una operación. Para resumir, la inserción
y eliminación una cola son, por lo
tanto, O de una vez. Una vez más, la búsqueda es
bastante lenta, sin embargo. Digamos que estamos buscando en la cola
el valor 8, otra vez, retiramos de cola, entonces check
es 7 igual a 8? No es así que
volvamos a retirar la cola, luego verificamos. ¿ 2 es igual a 8? No lo es. Descolamos y verificamos. ¿ 8 es igual a 8? Lo es. Nuestra búsqueda está hecha. Sin embargo, si hay
n artículos en la cola, podríamos necesitar hasta n cheques. Esto hace que la búsqueda y
las colas sean un algoritmo O of n. Fetch vuelve a ser similar. Digamos que estamos buscando buscar el
3er artículo con el valor 8. Descolamos un elemento, es
decir 1, retiramos la cola de
otro elemento, es
decir 2, y retiramos la cola otro elemento para finalmente recuperar el 3er item
is value, que es ocho. Para una cola con n elementos, necesitamos n decolas, por lo que la obtención es O de
n. Para resumir, una cola es eficiente de modificar, pero ineficiente para acceder al
igual que con las pilas. Analicemos ahora los pros y los
contras de las pilas y colas. En el extremo izquierdo, tenemos las cuatro operaciones que nos
importan: inserción, eliminación, búsqueda
y búsqueda. En la 2da columna, tenemos
los tiempos de ejecución para una pila, y en la 3ª columna, tenemos los tiempos de ejecución
para una cola. Desafortunadamente, los
tiempos de ejecución en sí no son súper interesantes
así que tenemos
que saber cuál usar
en función de la aplicación y cómo se definió cada
estructura de datos. Por ejemplo, una
pila es ideal para rastrear cambios como
deshacer una operación y luego rehacer esa operación. Se trata de una pila, ya que el último cambio agregado
es el primero que deshaces. Una cola es ideal para el procesamiento
secuencial, como procesar autos en una línea en un puente de peaje o
solicitudes de descarga en un servidor. Tenga en cuenta esta diapositiva ya que resume toda la lección. Para obtener una copia de estas diapositivas
y más recursos, asegúrese de consultar
el sitio web del curso. Veamos ahora estas
estructuras de datos en acción. En la siguiente lección, practicaremos tanto el uso
como implementación de estas estructuras de
datos, abordando nuestros dos
objetivos de aprendizaje para este curso.
6. Práctica de secuencias: Bienvenido a otra lección de
práctica. En esta lección,
cubriremos secuencias, decir,
pilas y colas. Al igual que antes, dejaremos de
lado las tácticas de
entrevista esenciales, primero
tenemos que dominar estos
fundamentos. Tenga en cuenta que estas preguntas
son bastante difíciles. Esta no es una aplicación genial. Estos son los fundamentos
que necesitarías para las entrevistas y es
un material técnicamente desafiante. Así que al igual que antes, navega a esta URL,
alvinwan.com/datastructures101/sequences. Una vez que veas esta página, bifurca el proyecto para obtener
tu propia copia editable. Para ello, haga clic
en el nombre del proyecto en la parte superior izquierda para
obtener un desplegable, haga clic en los puntos suspensivos para
obtener otro desplegable, y finalmente haga clic
en el botón Horquilla. Entonces sugiero colocar
sus ventanas de
edición Skillshare y Replit una al lado de la otra
como se muestra aquí. Hablaremos de palmas en
tres categorías diferentes. Primero hablaremos de problemas
de implementación. Estos son problemas
que implementan funcionalidad
central
para una estructura de datos. Segundo es el uso, implementaremos
alguna funcionalidad y elegiremos la estructura de
datos correcta para usar, esa es la parte clave. Vamos a aprender a elegir las estructuras de datos
en función de sus pros y sus contras. Para el tercero, vamos a combinar estructuras de
datos en posiblemente una nueva estructura de
datos o
una nueva aplicación que
requiera que hagamos malabarismos con múltiples estructuras de datos para
cada una de sus fortalezas. Independientemente de qué
categoría de problemas, aquí hay un consejo profesional que siempre
debes tener en cuenta. De hecho, vamos a
seguir este consejo profesional para toda
esta lección y todas las
lecciones de práctica que siguen. Vamos a llevar a cabo todas
nuestras
preguntas de resolución de acertijo de esta manera. También debes realizar todas tus entrevistas para resolver
acertijos de esta manera. Primero, diseñaremos el
algoritmo sin codificación. Diseña verbal o visualmente el algoritmo con
tu entrevistador. Esto es para que tu
entrevistador pueda
guiarte a ti y a tu pensamiento
hacia la respuesta correcta. Segundo, informar el tiempo de ejecución y la complejidad de la memoria.
Estoes importante. Primero para demostrar
comprensión, pero también para ver si
su entrevistador quiere una solución más eficiente. Tercero, y finalmente,
luego codificas. Estructuraremos tu
práctica de esta manera. Diseñe el algoritmo, luego repasaré la solución, reportaré la complejidad, y luego
repasaré la solución, y finalmente codificaré el algoritmo, y luego nuevamente
repasaremos la solución. La idea es que
aunque arruines alguna parte de este proceso de
tres pasos, aún
podrás
practicar los otros pasos. Aquí está nuestra primera pregunta. Vamos a implementar
colas pero usando pilas. Sin embargo, antes de que empieces, déjame hablar de un consejo. Recuerda que un stack
es último en entrar, primero en salir. Lo que eso significa es que es como una pila de rocas o
una pila de cajas. El último artículo que pongas
en esa pila va a ser el primero que te
quites, eso es stack. Ahora la cola es como una línea, una cola de autos digamos. Eso significa primero en entrar, primero en salir. Entonces el primer auto que se
alineó es el primer auto que saldrá de esta
cola. Tengan esto en mente. Que lo que escribí aquí, una cola es primero en entrar, primero en salir, un stack es último en salir, primero en entrar. Ahora, concedido, nunca
recuerdo este primero en entrar,
primero en salir, último en salir, primero en entrar. Lo que recuerdo
en cambio es más que estoy trabajando con la
pila, como una pila de rocas, pila de ropa,
pila de cajas, y luego pienso en una
cola como solo una línea. Si lo tienes en
mente, eso empezará a decirte en qué dirección
te mueves. Ahora de nuevo, el
ejercicio aquí es
implementar una cola usando pilas. Si te desplazas hacia abajo
en tu ripl.it, verás esto aquí mismo. Esto es lo que
necesitas implementar. Entonces, pausa el video
aquí y primero, piensa en el algoritmo. ¿ Cómo vas a hacer esto conceptualmente? Así que dale una oportunidad. Aquí está la respuesta. Entonces
vamos a hacer lo siguiente. Digamos que tenemos esta
lista aquí en negro. Tenemos 9, 8, 2, 7. Nueve es nuestro primer ítem. Nuestro último ítem es siete. Para emular una cola, necesitamos eliminar
el primer ítem, que es nueve, con esa flecha
roja justo ahí. Nuestro objetivo, que se muestra aquí en rojo
es quitar el valor nueve y devolver o mantener el stack
restante, 8, 2, 7. Entonces sabiendo que ese es nuestro objetivo, lo único que podemos
hacer con una pila aunque, es eliminar del último elemento. Sólo podemos reventar siete. Bueno, eso está bien.
Podemosseguir haciendo eso. Haremos pop siete, haremos pop dos, haremos pop ocho y
finalmente, haremos pop nueve. Ahí vamos.
Yapodemos regresar nueve. Ahora podemos sacar de cola de una pila. Sin embargo, hemos perdido todos los artículos que se hicieron
estallar antes, todos los 8, 2 y 7. Entonces necesitamos otra pila
para sostenerlos a todos. Entonces aquí lo que vamos
a hacer es sacar siete, pero empujarlo a
la otra pila. Entonces vamos a reventar dos, ocho, y luego finalmente
regresaremos nueve. Eso es genial. Ya
casi estamos ahí. Sin embargo, necesitamos 8, 2, 7 en nuestra pila. Ahora mismo tenemos
el reverso 7, 2, 8. Entonces lo que vamos
a hacer es hacer pop de la segunda pila y empujarla nuevo a la pila original. Así que vamos a hacer
retroceder eso, y ahí vamos. Tenemos ambos objetivos. Podemos devolver
nueve como si fuera una cola y podemos
retener una pila restante 8,
2, 7 como quisiéramos. Ahora bien, esto parece
una solución inteligente. Probablemente me diría a mí mismo, ninguna manera se me
ocurre esa solución. Si estás pensando lo
mismo, estoy completamente contigo y estoy aquí para decirte
que eso no es problema. En realidad no hay necesidad de
llegar a esa solución. En cambio,
entenderlo a fondo. En tus entrevistas
o en los trabajos, simplemente recuerda las tácticas
disponibles para ti. Así que realmente enfoca
tu energía mental en entender la solución. Si algo no tiene sentido, solo pregunte en la sección de
discusión. Sabiendo que este
es el algoritmo, pasemos
al segundo paso. ¿ Cuál es la
complejidad algorítmica? ¿ Cuál es la complejidad del tiempo de ejecución y cuál es la complejidad
de la memoria? Pausa el video aquí
e intenta
averiguarlo . Aquí está la respuesta. La
complejidad algorítmica o de tiempo de ejecución aquí es O (n). Tenemos que
realizar básicamente dos n operaciones, que es O (n) tiempo. Tenemos que hacer estallar cada elemento en
la segunda pila, y luego tenemos que hacer estallar cada elemento
de la segunda pila de nuevo a la primera. Entonces eso es O (n) para la complejidad del tiempo de
ejecución, para la complejidad de la memoria también
es O (n) simplemente porque tuvimos que
mantener esta otra pila, y esta otra pila requería
hasta n elementos diferentes. Entonces tenemos O (n) complejidad de tiempo de
ejecución,
O (n) complejidad de memoria. Ahora, intentemos
implementar esto en código. Nuevamente, pausa el video aquí
y pruébalo tú mismo primero. Ahora implementemos
esta solución. Empezaremos
escribiendo un constructor. Este constructor
tomará en un iterable. Entonces aquí podemos ver que este constructor
toma un iterable, que es una lista
de solo un elemento. A partir de lo iterable,
construiremos una pila. [ NOISE] Ahora para poner en cola, [NOISE] simplemente vamos
a empujar a la pila. [RUIDO] Sin embargo, quiero quitar de la cola
o eliminar de la pila, ahí es donde entra la lógica
especial. Ese es todo el
algoritmo del que hemos hablado aquí en
el lado izquierdo. Primero vamos a
comenzar vaciando la pila original
en una nueva pila. Aquí vamos a tener el nuevo stack. Entonces mientras tengamos
artículos en la pila vieja, los
empujaremos a la nueva pila y los moveremos
de la anterior. Ahora que ya tenemos
todos estos artículos, ahora
vamos a
sacar finalmente del último artículo. Esto nos dará el valor que necesitamos para realmente regresar. Ahora vamos a vaciar la nueva pila nuevo en la pila original. Recuerden que ese fue el último paso aquí donde teníamos
todo a la inversa. Tenemos que empujarlos a todos de nuevo
a la pila original. Ahora aquí vamos a tener, mientras que la pila tiene artículos, empujará de nuevo a
la pila original. Por último, vamos a
devolver el valor. Aquí vamos. Hemos implementado nuestro algoritmo
de tres pasos desde antes. Comprobemos ahora si
esta función pasa o no nuestras doctests. Para ello, pulsa el botón Ejecutar, el botón verde en la
parte superior de tu archivo. Aquí podemos ver que tuvimos fallas en todas las demás
funciones, pero no en esta. Recuerda, nuestra función
aquí es cola vía pila, que falta en esta lista. Estamos bien para irnos. Hemos pasado nuestros doctests para esta función. Pasemos ahora a
la siguiente pregunta. En nuestra siguiente pregunta,
vamos a hacer lo contrario. Vamos a implementar
una pila usando colas. Nuevamente aquí implementamos
una cola usando pilas. Ahora en nuestro próximo problema, vamos a hacer lo contrario. Adelante y tómate
un segundo para pausar el video y considera qué algoritmo
construirías para hacer esto. Aquí hay una solución. Esto es muy similar
al último problema. Al igual que antes, vamos a instanciar
una segunda cola. Entonces vamos a
tomar cada elemento nuestra primera cola y
empujarlo a la segunda cola. Una vez que lleguemos al último artículo, luego
devolveremos ese
elemento de la lista tal como lo haría una pila. Eso es más o menos. Ahora
que tenemos el algoritmo, sigamos adelante y
pensemos en la complejidad de memoria y tiempo
de ejecución del algoritmo. Vuelve a pausar el video. Ahora aquí hay una solución
conceptualmente. Aquí queremos implementar
una pila sin embargo, solo
tenemos una cola. Recordemos que una cola
solo se puede quitar de
la cola desde el principio mientras que
para emular una pila, necesitamos poder
hacer estallar desde el final. Tenemos este dilema,
pero lo resolveremos la misma
manera o similar como lo hacíamos antes. Crearemos una segunda cola. Después sacaremos de cola nueve y lo pondremos en cola en
la segunda cola. Después retiraremos de la cola ocho
y agregaremos una segunda cola, luego retiraremos de la cola dos, y la agregaremos a la segunda cola. Por último, sacaremos de cola
siete y lo devolveremos. Aquí hemos logrado
realmente “reventar siete”. Aquí hay algo
nuevo, a diferencia de antes de que nuestra segunda cola ya esté
en el orden correcto. Recuerda que de
antes nuestra cola era 9, 8, 2, 7 y ahora es 9, 8, 2. Este es el orden exacto y
correcto. No necesitamos moverlo de nuevo a la cola original
como lo hicimos antes. Sabiendo que ahora podemos saber exactamente cómo vamos
a implementar este algoritmo. Sin embargo, antes de hacer eso, reportemos el tiempo de ejecución
y la complejidad
de la memoria de la función. Pausa el video aquí e
intenta resolverlo. Ahora aquí está la solución. El tiempo de ejecución y la complejidad de la
memoria es o de n, al igual que antes. Para la complejidad del tiempo de ejecución,
tenemos que dejar de cola cada elemento de la lista y ponerlos en cola en
la segunda cola, por lo que es o de n Ahora
para la complejidad de la memoria, tenemos que mantener
la segunda cola. Segunda cola incurre
básicamente en o de n memoria hasta n artículos.
Ahílo tienes. Tanto el tiempo de ejecución como la
complejidad de la memoria son o de n Ahora, pasemos finalmente
al tercer paso. Intentemos codificar este algoritmo. Pausa el video aquí
e intenta codificarlo. Ahora, sigamos adelante y
hablemos de la solución. Implementemos la
pila usando colas. Al igual que antes vamos
a crear un constructor. Este constructor va
a tomar un iterable. Ese iterable será nuestro valor inicial de
colas. Entonces vamos a implementar
push para esta pila. Esto solo será una llamada de
cola y cola. Toda la magia
pasará ahora en el método pop. En este método pop, primero
vaciaremos n menos uno elementos en la
cola original en la nueva cola. Para ello, vamos a
crear una cola. Esta es nuestra nueva cola. Entonces, mientras nuestra vieja cola
tiene al menos un artículo, vamos a seguir
quitando de ella. Aquí realmente retirará
la cola de la cola anterior y la
agregará a la nueva cola. Ahora que hemos eliminado
casi todos ellos, ahora
eliminemos el último
elemento de la cola anterior. Vaya, entonces esto es
cola, descola. Este último ítem
sería siete, por ejemplo. Entonces devolveríamos ese valor. Tal como dijimos antes, nuestra nueva cola tiene todos los elementos que
necesitamos en el orden correcto. Simplemente reemplazaremos nuestra
vieja cola por nuestra nueva. Ahora podemos devolver un valor. Sigamos adelante e
intentemos ejecutar todas nuestras pruebas y ver qué
pasa. Ahí vamos. Podemos ver que nuestra pila vía cola
ya no está en la lista de fallas. Tada, hemos
pasado estas pruebas. Pasemos ahora
al siguiente problema. El siguiente problema, vamos
a usar una estructura de datos. No
te voy a decir cuál usar, y habrá hasta que
tú decidas cuál. Vamos a usar,
ya sea pilas o colas. En particular para imprimir todas las combinaciones de
las letras a y b. Vamos a
imprimir todas las combinaciones de longitud k. He aquí un ejemplo, print_baba de 2 nos
dará aa, ab, bb. Ahora bien, si llamamos a imprimir baba de 3, entonces esto nos dará a todas las “palabras” de
tres letras que
tienen las letras a y b. Nuevamente, son todas las combinaciones
posibles. Observe que no
hay repeticiones. Observe que cada
valor aquí tiene longitud tres. Sabiendo eso,
volvamos a pasar por ese proceso de tres pasos del que
hemos hablado antes. En el primer paso,
diseñemos el algoritmo. Pausa el video aquí e
intenta diseñar el algoritmo. Nuevamente, querrás usar
ya sea una pila o una cola. Hablemos ahora conceptualmente de la
solución. Aquí en esta solución en
particular, vamos a usar una cola. Voy a denotar
la cola usando solo una lista básica aquí primero para visualizar
lo que está pasando. Para empezar, digamos que
tengo la letra a aquí. Lo que vamos a hacer es
primero quitarle la cola a. Ahora tenemos una y
vamos a poner en cola las únicas dos formas posibles de extender la letra
a.
Para pasar de una secuencia de una letra
de todas las posibles a's y b a todas las
secuencias posibles de dos letras de a y b. Vamos a agregar aa y ab. Esto dará cuenta de
todas las formas posibles de
crear una secuencia a y b a
partir de este punto de partida. Ahora podemos hacer esto un
poco más extenso. Vamos a empezar
con la cadena vacía. Entonces vamos a quitar de
la cola esa cadena vacía. Entonces agregaremos las únicas dos formas posibles
de extender esto, que son agregar una a al final o agregar
a b al final. Después retiraremos la cola y luego
agregaremos a más a más b, así aa ab. Entonces volveremos a
hacer esto. Sacaremos de cola el primer ítem
aquí mismo, que será b. Luego extenderemos
con ba y bb. Vamos a seguir haciendo esto. Ahora aquí vamos a tener
aa lo sacamos de cola, y luego agregaremos
aa más aa más b, así aaa, aab. Vamos a seguir haciendo esto. Al detenernos en el momento
correcto, nos
aseguraremos de haber cubierto todas las
secuencias posibles de k longitudes de A y B. Sabiendo que este
es el algoritmo, hablemos ahora de la complejidad de la
memoria y del tiempo de ejecución. Pausa el video
aquí y mira si
puedes llegar a esas dos
complejidades. Hablemos de la complejidad computacional
y de memoria. La complejidad computacional y de
memoria es realmente complicada en
este escenario en particular, pero de todos modos
hablaremos de ello. Dado lo que has sabido hasta ahora, tal vez no pueda
llegar a este, pero eso está completamente bien. Nuevamente, tu objetivo es
sólo entender la solución que ahora
estoy presentando. Hablemos de
cuántas veces se necesita, o hablemos primero de
cuántos resultados hay aquí. Todas las
secuencias posibles de tres longitudes de a y b. Aquí vamos a tener dos opciones por
cada letra, a o b por 2 veces 2. Eso significa que aquí hay
dos al poder de tres opciones diferentes. Si queremos todas las secuencias de
k longitudes posibles, vamos a generar dos a
las k respuestas diferentes. Ahora, para producir
dos a las k respuestas
diferentes, en realidad
tuvimos que generar todas las soluciones de dos longitudes y una
longitud también. En realidad, lo que tenemos es generar de dos a las
tres opciones diferentes. Tuvimos que pasar por
dos a dos, y luego dos a uno también. Esto es cierto en general. Si quisiéramos generar
las cuatro secuencias de longitud, habríamos generado dos
a la una dos a las dos las tres y dos a las cuatro combinaciones diferentes
y así sucesivamente y así sucesivamente. En realidad, lo que eso
significa es que esto es realidad una suma de hasta, digamos j valores donde
a lo sumo j es igual a k Aquí tenemos esta
sumatoria desagradable de un montón de términos. Sin embargo, afortunadamente para nosotros, el análisis de orden de magnitud solo se preocupa por el término de mayor
magnitud. Aquí podemos simplemente
resumir esto como o de 2 a la n, o supongo k, ya que hemos estado usando k. sabiendo que este
algoritmo es bastante lento, esta es la
complejidad computacional. Afortunadamente para nosotros, la complejidad de la
memoria es, bueno en realidad,
desafortunadamente para nosotros, complejidad
numérica también
es la misma. O de 2 a la k. Este es
un algoritmo bastante lento. También es un algoritmo bastante
caro, pero vamos a dejar eso, que es un bonito,
es complejo. Pero al menos dado lo que
hemos dicho hasta ahora, esta es una forma de hacerlo, y lo
haremos de esta manera por ahora. Adelante, pausa el video
aquí e intenta codificarlo. Ahora aquí hay una solución. Para empezar,
vamos a crear una cola. Al igual que
hablamos antes, vamos a agregar
en la cadena vacía. Esta cadena vacía es todos los conjuntos posibles de secuencias de longitud
cero. A partir de esto,
generaremos todos los conjuntos posibles de secuencias de una longitud,
y así sucesivamente, así sucesivamente. Si bien hay
algo en la cola, seguiremos generando
una y otra y otra vez. Sigamos adelante y hagamos
estallar o quitar de la cola esa primera cadena. Si nuestra palabra aquí es
exactamente longitud k, entonces simplemente vamos a imprimir esa palabra, y estamos bien para ir. No obstante, si la palabra aún
no es de longitud k, entonces la extenderemos. Lo extenderemos
con la letra a y lo extenderemos con la letra b. Ahí vamos. Esto es para nuestra función. Esto nos dará todas las secuencias Kalign
posibles porque esto asegura que nos extenderemos con
todas las posibilidades, y b, y esto asegura que atraparán todas las
secuencias de Kalign a medida que surjan. Si hay algo
más largo que una secuencia Kalign, entonces, bueno,
no va a ninguna parte. No vamos
a seguir trabajando con ello. De hecho, en realidad puedes
demostrar que
no habrá longitud mayor que k, pero eso no es súper importante. El punto es que esta función nos
debe dar lo que queremos. Sigamos adelante y pruébalo ya. Pulsa el botón verde “Ejecutar”
en la parte superior y deberías ver que print_baba
desaparecerá de esta lista
de fallas. Ahí vamos. Print_baba ahora se ha ido
de la lista de fallas. También hemos pasado esta prueba. Pasemos a
la siguiente pregunta. En esta siguiente pregunta,
usemos ahora pilas o colas para imprimir escaleras. En particular, imprime la
cantidad de formas en las que
podemos subir k escaleras si
puedes dar uno o dos
pasos a la vez. Si tienes una escalera, solo
puedes subirla de una manera. Si tienes dos escaleras, puedes subirla de dos maneras, o das un
paso a la vez, o das ambos pasos a la vez. Si hay tres escaleras, entonces puedes subir 1,1,1, o puedes subir dos
escalones y luego un escalón, o puedes subir un
escalón y luego dos escalones, así que es 1,1,1; 1,2, o 2,1. Hay tres formas de
subir tres escalones. Se supone que esta función calcula el número
de formas que se necesitan para subir k escaleras si puedes
dar uno o dos pasos. Ahora, antes de considerar el
algoritmo, aquí hay una pista. Bueno, puedes pausar el video aquí si no quieres la pista, pero la pista es la siguiente; antes de nuestras, entre comillas, acciones, por cada palabra que aún no tenía longitud k, tuvimos dos acciones diferentes. Puedes agregar a o puedes agregar b. aquí, tienes
algo similar. Si aún no has
subido todas las k escaleras, tienes dos acciones diferentes. Puedes subir un escalón o
puedes subir dos escalones. Sabiendo eso y sabiendo que anteriormente
usamos la cola para representar todas las
formas posibles de construir una palabra, también
puedes usar esa
cola ahora para construir todas las formas posibles de
subir escaleras. Pausa el video aquí y mira si puedes
averiguar el algoritmo. Ahora aquí hay una solución. La solución
en realidad va a reflejar bastante de cerca la
solución anterior. Lo que vamos a hacer es por cada juego de escaleras, digamos que tenemos una cola ahora, nuestro objetivo será, porque cada elemento
de la cola
será otra forma de llegar a
eso cierto número de pasos. Aquí hay una manera de decirlo.
Digamosque tenemos cero. Eso significa que esta es una manera de
llegar a cero escaleras. Entonces vamos
a descolar ese 0. Entonces vamos a agregar
a la cola dos elementos. Puedes dar un paso
o puedes dar dos pasos. Tomaremos 0 más
1 y 0 más 2. Después quitarás la cola
del primer ítem. Entonces volveremos a poner en cola. Digamos, hay
dos posibilidades, puedes dar un paso, puedes dar 1 más
1, que es 2, o puedes dar dos
pasos, que son tres. Después volveremos a sacar de la cola. Vamos a sacar de cola a estos dos. Entonces diremos, aquí hay dos. Puedes dar uno o dos
pasos a partir de ese momento. Puedes tomar 2 más 1
o tres, o 2 más 2, que es 4, y luego así sucesivamente y así sucesivamente.
Puedesseguir haciendo esto. Básicamente, lo que sucederá es si cuentas el número de veces que k ocurre
en esta cola, eso te dirá
cuántas formas hay para llegar a ese número de escaleras. Eso es todo para la
solución conceptual para el algoritmo. De hecho, vamos a saltarnos la memoria y la complejidad en tiempo de
ejecución para este problema en particular solo porque es bastante
difícil de calcular. Hay una manera de calcularlo. Vamos a saltarlo por ahora. Incluiré una versión
escrita de la solución en el archivo de soluciones
finales. Mientras tanto,
pasemos a codificar
realmente esta función. Nuevamente, pausa el video aquí, e intenta codificar la solución. Ahora vamos a codificar la solución. Comenzaremos
creando una cola
aquí mismo con solo cero elementos. Esta cola ahora tiene cero elementos. También inicializaremos
el número de formas en las que podemos
subir hasta k escaleras es cero. Si bien tenemos algo
en la cola, así que mientras hay
formas de subir las escaleras,
retiraremos de la cola de una
manera subiendo las escaleras. Esto sacará de cola de una
manera subiendo las escaleras. Entonces, si
lo hemos hecho hasta k pasos, incrementaremos el número de formas
posibles de subir a k pasos en uno. Si aún no lo hemos
hecho hasta k escalones, así que la escalera es menor que k, entonces consideraremos
formas de subir ahí. Consideraremos ya sea
más 1 escaleras o consideraremos dar dos pasos. Entonces, finalmente, devolveremos
el número total de formas que se necesitaron para
subir a k pasos. Ahora que ya tienes esto, sigamos adelante y
peguemos a “Corre”. Ahí vamos. Ya podemos ver que print_stairs ya no está
en nuestra lista de fallas. Hemos superado todos los casos de prueba. Antes de pasar a
la siguiente pregunta, sí
quería sacar a colación este consejo. El consejo es resolver
el problema central, luego considerar los casos de borde. Nos hemos estado saltando algunos de los consejos aquí para los casos de borde y puedes verlos si
vuelves a las diapositivas, pero la idea básica es, nuevamente, enfocarte en el problema central antes de abordar edge casos. Esto no es súper
relevante en este momento, pero a medida que trabajemos a través de problemas, veremos cada vez más
de estos casos de borde, y a veces
pueden ser una distracción. Nuevamente, enfócate primero en resolver
el problema central. Aquí ahora vamos a usar pilas y colas para
verificar paréntesis. En realidad, este es el primer problema donde
veremos un montón de casos extremos
aleatorios.
Aquíestá el problema. Ve y desplázate un
poco hacia abajo en tu archivo y verás que nuestro objetivo es
verificar si la cadena proporcionada contiene paréntesis coincidentes. [ Risas] En realidad
ya te he dado una pista aquí. Deberías usar una pila, pero entremos, y desplázate hacia abajo aquí,
y veamos qué significa eso. Paréntesis coincidentes significa que por cada paréntesis
inicial, tiene un paréntesis de
cierre correspondiente. Sin embargo, no es
solo si existe, tiene
que estar en el orden correcto. Por ejemplo, vea, aquí tiene un paréntesis de
inicio. En realidad, a esto solo
le falta un paréntesis final, pero aquí hay un caso en el que
tienes paréntesis inválidos. Aquí tienes paréntesis final
y luego inicia paréntesis. Éstas están inadecuadamente cerradas. Lo que esto significa es que antes de cada paréntesis
cerrado, se necesita un paréntesis
inicial correspondiente. Eso es lo que significa igualar. Este es en realidad un problema
muy común que verás tanto como
ejercicio como posiblemente incluso
en la entrevista misma. Esto es bueno saberlo, bueno entender cuál es la
premisa del problema. Nuevamente, queremos verificar si la cadena proporcionada contiene paréntesis
coincidentes. Nuevamente, la pista es
usar una pila. Sigue adelante y pausa
el video aquí y mira si puedes llegar
al algoritmo. Hablemos ahora
de la solución. Nuestra solución, como
mencionamos anteriormente en
la punta o en la pista, es usar realmente una pila. Digamos que tenemos
esta pila aquí mismo. Esta pila va a representar cuántos
paréntesis de inicio o cuán profundos estamos entre paréntesis. Digamos que
iteramos a través la cadena y vimos
este paréntesis de inicio, vamos a agregar un paréntesis de
inicio aquí. Entonces ahora vemos un paréntesis
cerrado. Cada vez que veamos un paréntesis
cerrado, vamos a
salir de la pila. Nos salimos de la pila, eliminamos un nivel más alto, eliminamos ese grupo. Ahora que vemos otro paréntesis de
inicio, vamos a volver a agregar, vemos otro paréntesis de inicio que vamos a volver a agregar, y luego aquí vemos
un paréntesis cerrado, así que vamos a seguir adelante
y eliminar eso, y luego vemos otro
inicio paréntesis, así que vamos a agregar eso de nuevo en. Por último, vamos
a cerrar esto de nuevo. Ahora podemos ver al final de la
función todavía tenemos uno paréntesis sin cerrar,
que es éste. Este grupo no está cerrado. Lo que eso significa es que esto
no es un conjunto coincidente
de paréntesis, podemos devolver false. En esencia, esta pila en realidad
representa cuán profundos
somos en este
conjunto anidado de paréntesis. Cada vez que salgas, significa que volvemos a subir de nivel. Nos hemos deshecho de un conjunto
anidado de paréntesis. Si no hemos vuelto subir y salir de los paréntesis, entonces no es coincidente. Al mismo tiempo, si
ves algo como esto, que parte de un paréntesis
cerrado, entonces al principio mismo
de la cadena la
pila está vacía, así que no hay nada que hacer estallar. Esto inmediatamente nos
dirá que de nuevo, se
trata de un
conjunto de paréntesis inválido. Eso es conceptualmente, cómo
vamos a hacer esto. Ahora, continuemos
y hablemos sobre cuál es la complejidad
del tiempo de ejecución
y la complejidad de la memoria. Pausa el video aquí e
intenta resolverlo. Aquí está la respuesta.
Tantopara el tiempo de ejecución
como para la complejidad de memoria,
ambos son lineales. Tenemos como iteramos
por aquí, bueno, básicamente solo iteramos sobre la cadena una vez. Cada artículo solo
se ve una vez. Segundo, para comprender la complejidad
lineal de la memoria, imagina si tuvieras una cadena
que se viera así, entonces nuestra pila simplemente
serían todos estos paréntesis de
inicio. Tenemos hasta N
elementos diferentes en nuestra pila, eso significa que nuestra
complejidad de memoria es O de N. Ahora
pasemos finalmente al tercer paso, comencemos a codificar
este algoritmo. Pausa el video aquí
e intenta codificarlo. Entremos y
codifiquemos este algoritmo ahora. Aquí vamos a crear
una pila para empezar, y por cada
letra de la cadena, vamos a
comprobar si la letra inicia un nuevo conjunto de paréntesis, vamos a empujar
sobre la pila. De lo contrario, podemos suponer que la letra es un paréntesis de
cierre. Esto es algo que
acabo de escribir antes. Básicamente, en una entrevista, deberías preguntar si la cadena podría contener otros caracteres,
como números, o
letras, y lo que sea. Ahora, aunque solo por simplicidad, vamos a suponer que solo
hay paréntesis
en la cadena. Aquí, si no es un paréntesis de
apertura, es un paréntesis de cierre. Por cada paréntesis de
cierre, vamos a
salir de la pila. Entonces finalmente, si a la
pila no le queda nada, entonces volveremos true. Si a la pila le queda algo, significa que no hemos cerrado
todos nuestros paréntesis, así que deberíamos devolver false. Ahora bien, sabiendo esto, aquí en realidad hay un
consejo que mencioné antes o en las diapositivas de antes, pero no
mencioné. Aquí considera una secuencia vacía. ¿ Qué sucede cuando tu
stack está realmente vacío? ¿ Hay algún lugar en tu código donde tu código se rompería? En este
caso particular, sí, stack.pop. Aquí, no comprobamos si la pila ya está
vacía, así que hagámoslo. Si la pila ya está vacía, bueno, ¿qué hacemos aquí? Si la pila ya está
vacía y estamos tratando de eliminar un paréntesis de
apertura, esto significa que vimos un paréntesis de cierre antes ver los paréntesis
iniciales correspondientes. Sabiendo eso, esto significa, de nuevo, la cadena no es válida, por lo que debemos devolver false. Eso es todo para los casos de
borde realmente. Aquí
no se aplican entradas inválidas, así que eso concluye este problema, sigamos adelante y veamos
si pasa todas nuestras pruebas. Al ejecutar el código, notarás que is_valid_parentheses no está en esta lista de fallas, por lo que hemos pasado
estas pruebas de funciones. Pasemos al
siguiente problema. Aquí está el consejo, en realidad
considera personajes extraños. Eso fue aquí arriba, la propina, en una entrevista asegúrate de
preguntar si la cadena podría contener otros caracteres para
este problema en particular. Ahora deberías probar
esto por tu cuenta. Utilice pilas o colas
para verificar si hay paréntesis
coincidentes
y corchetes coincidentes. Aquí tenemos paréntesis
que se abren y cierran, y también tenemos paréntesis
que se abren y cierran. Esta es una agrupación válida porque cada par de paréntesis
está perfectamente emparejado. Pero hay un reto
adicional. Observe aquí que si solo
considera corchetes, emparejan correctamente. Si solo consideras
los paréntesis, también se
emparejan. Sin embargo, notarás
que este conjunto de corchetes y paréntesis se cruzan entre sí, es
decir, una agrupación no válida. Sabiendo esto,
intentemos diseñar un algoritmo
para este problema. Pausa el video aquí e intenta ver cómo usarías
tus estructuras de datos, pilas o colas para
resolver este problema. Nuevamente, puedes usar tu
problema anterior como inspiración. Pausa el video aquí
y pruébalo. Aquí hay una solución.
Aligual que antes, vamos a usar una
pila, excepto que esta vez, la pila contendrá ya sea paréntesis
iniciales
o corchetes iniciales. Siempre contendrá básicamente la puntuación
inicial. Sabiendo eso,
en cualquier momento que queramos, digamos que vemos un paréntesis de
cierre, luego intentaremos hacer
estallar de la pila. En este caso, saltaremos este
corchete cuadrado. Actualmente estamos viendo
paréntesis de cierre. Los paréntesis de cierre y este
corchete de apertura no coinciden, por lo que eso significa que esta es
una agrupación no válida Eso ocurriría en
este caso particular. Verías en la pila
algo así. Verías un corchete, verías un paréntesis, y luego cuando saltes, verás este paréntesis de
apertura
versus este corchete de cierre. Entonces, cuando esos dos no
coincidan, ahora no es válido. De lo contrario el algoritmo
se ve más o menos igual que antes. Cada vez que vea una puntuación
inicial, agréguela a la pila
, cada vez que vea una puntuación de
cierre, intente hacer estallar y
asegúrese de que está haciendo
estallar la puntuación de
apertura correcta. Eso es todo para el algoritmo. Nuevamente, consideremos ahora cuál es el tiempo de ejecución
y la complejidad de la memoria. Pausa el video aquí y mira
si puedes resolverlo. Ahora, aquí está la respuesta. Tanto para el tiempo de ejecución como para la complejidad de la
memoria, tenemos O de N. Al igual antes, para la
complejidad computacional, simplemente
iteramos una vez sobre
cada carácter, así que eso es O de N. Para la complejidad de la
memoria, nosotros otra vez, podríamos
tener una cadena con solo un montón de
puntuación de apertura como esta. Si tienes un montón de
puntuación de apertura como esta, entonces tu pila es más o menos
tan larga como tu cadena de entrada. Aquí nuestra
complejidad de memoria también es O de N. Ahora que hemos pasado
estos dos primeros pasos, probemos ahora el tercer paso. Intentemos codificar este algoritmo. Pausa el video aquí y
mira si puedes codificar. Ahora intentemos codificar
esta función. Vamos a comenzar
creando una pila, y luego vamos
a iterar sobre la pila tal como lo
hicimos antes. Si nuestro carácter actual es
un signo de puntuación inicial, entonces lo empujaremos
a la pila. Entonces si vemos un paréntesis de
cierre, verificar que
la pila actual tenga un paréntesis inicial
y luego devuelva false, si los dos no coinciden. De lo contrario, si se trata de
un corchete de cierre, asegura de que tu stack esté
actualmente dentro de un soporte, lo contrario, devuelve false. Por último, asegúrate de que tu stack haya cerrado
todos los grupos posibles. Si has cerrado todos los grupos, entonces tu stack no
tendría nada en él. Todos los
grupos correspondientes habrían
sido reventados. Ahora que tenemos nuestra función, sigamos adelante y ejecutemos. Da clic en el “
botón Ejecutar”, la parte superior, el botón verde que
ejecutará todas las pruebas. Aquí podemos ver que falta
is_valid_agrupamiento en nuestra lista de fallas, por lo que hemos
superado con éxito todas estas pruebas. Con eso concluyen los
ejercicios de esta lección. Una punta más de cierre, pila es como una pila de rocas, pila de ropa,
pila de cajas, el último artículo que agregas es
el primer artículo que te quitas. Una cola es como una
fila, una cola de autos, de cola de pájaros,
supongo , no creo que los
pájaros hagan cola. Colas de personas, cola de cajas, cualquier línea, el primer ítem que agregues es el
primer ítem que se desprende. Nuevamente, ten esto en mente. Con eso concluye este
consejo final y esta nota final. Para obtener una copia de estas diapositivas y el código terminado
de esta lección, asegúrese de consultar
el sitio web del curso. Finalmente, esto concluye
nuestra práctica de secuencias. He mencionado algunos consejos para
entrevistas, pero no gastes demasiada energía
mental en
memorizarlos. Deja que la práctica que
hemos estado haciendo te
ponga en el hábito de
seguir esos tres pasos. Esa es la parte más importante, acostumbrarse a
hacer esas tres cosas, para que cuando estés
extremadamente nervioso, cuando estés
enloquecido, cuando
no estés pensando del todo con
claridad en un entrevista, pasarás por defecto a esos
tres pasos. Eso es.
7. Listas: Array vs. Lista vinculada: Nuestra primera categoría es
para listas de artículos. Analizaremos dos estructuras de
datos, en particular, arrays
y listas enlazadas. Luego cubriremos sus pros y sus contras con base en nuestro análisis. Empecemos por terminar
nuestro análisis de arreglos. Una matriz es simplemente
una lista de elementos. En la memoria, los elementos de la matriz se
colocan uno al
lado del otro. Anteriormente encontramos que la
búsqueda de una matriz toma O de n tiempo ya
que tenemos que atravesar toda la lista un elemento a la vez
para encontrar el valor. También encontramos que la búsqueda
toma O de 1 tiempo constante. Ahora terminemos este
análisis y veamos cuánto tiempo
lleva insertar un
elemento en la matriz. Digamos que tiene esta
matriz de tres elementos. Ahora estamos visualizando un pedazo de tu memoria en tu computadora. Nos gustaría insertar un
nuevo ítem, un valor de cuatro. Podríamos en teoría simplemente asignar un espacio para cuatro así. Sin embargo, es
posible que su computadora ya haya asignado ese espacio
a otros datos. Como resultado, la
operación de inserción asignará un nuevo trozo de memoria para
su nueva longitud para la matriz, luego el algoritmo copiará
cada elemento uno por uno. Por último, actualizará
el valor del nuevo artículo. Para una matriz con n elementos, la inserción hace n copias. Por lo tanto, la inserción es una operación de
O de n. Para resumir, la inserción
lleva tiempo lineal. Veamos cuánto tiempo lleva
la eliminación. Digamos que tiene una
matriz de seis elementos, le gustaría eliminar el
3er ítem, el número 2 aquí. Para hacer eso, el algoritmo de
eliminación
desplazará todos los
números después de él hacia arriba. Copiará 3 hacia adelante, copiará 4 hacia adelante, copiará 7 hacia adelante, luego desasignará el último lugar. Como resultado, para una
matriz de longitud n, la eliminación toma n copias. Esto hace que la eliminación O de n. Esto completa nuestra tabla de complejidades en tiempo de
ejecución
para la matriz. Notarás inmediatamente que la matriz es muy eficiente para obtener pero ineficiente
en todo lo demás. Nuestra matriz es ineficiente para la
modificación en particular solo porque tenemos que mantener todos los datos
contiguos en la memoria. En otras palabras,
todos los artículos deben estar uno al lado del
otro así. Pero podemos cambiar esto. Coloquemos cada elemento en una lista donde queramos en la memoria. Para conectar todos los
elementos juntos en una lista, necesitamos agregar enlaces. cada uno de estos enlaces
también se les llama punteros. Cada puntero apunta a una ubicación para el
siguiente elemento de la lista. También necesitamos agregar un marcador que indique que
la lista ha terminado. Esto es lo que
llamamos una lista enlazada por todos los
enlaces que insertamos. Esta lista enlazada viene con
algunas propiedades realmente agradables. Analicemos ahora
esta lista enlazada. Digamos que queremos insertar un nuevo valor 3 al
final de la lista, luego simplemente
asignamos dos nuevos spots y nos aseguramos de 2 puntos a 3. No importa cuántos elementos
haya en la lista enlazada, tenemos una
cantidad constante de trabajo por
hacer para insertar un nuevo ítem, asignar dos espacios y
cambiar un puntero. Como resultado, la inserción para listas
enlazadas es O
de 1 tiempo constante. La historia es similar, incluso si queremos insertar un valor en el
medio de la lista, asignar dos nuevos espacios para
el nuevo valor y un puntero, luego señalar el valor
anterior 8 a 3, luego señalar el nuevo valor 3 a 2. Ahí lo tenemos.
Lainserción es completa. No importa la longitud
de la lista enlazada, solo
necesitamos asignar dos espacios y
cambiar dos punteros. Esto sigue siendo tiempo
constante O de 1. Para resumir hasta el momento, una lista enlazada tiene inserción de tiempo
constante. Veamos ahora cómo funciona la eliminación
o eliminación. Digamos que queremos eliminar
3, el último ítem. Esto es simple. Simplemente invertimos lo que
hicimos para la inserción. Eliminar el puntero del 2do al último. Ahora el ítem 3 ya no forma parte
de la lista enlazada. Para eliminar el último elemento, solo
necesitas un cambio
de un puntero. Este es tiempo constante u O de 1. Eliminar un elemento en el medio
de la lista también es simple. Digamos que quieres eliminar
3, el 3er ítem, cambia el puntero por
ocho para saltarte 3. Ahora bien, en efecto, 3 ya no forma parte de la
lista enlazada, y eso es todo. Para eliminar un elemento, sin importar dónde se encuentre, simplemente
cambiamos un puntero. Esto es tiempo constante
otra vez o O de 1. Para resumir hasta el momento, una lista enlazada tiene
tiempo constante de inserción y eliminación. Veamos ahora cuánto tiempo lleva acceder a
la lista enlazada. Digamos que estamos
buscando el valor 4. Tenemos que recorrer toda
la lista enlazada una
por una hasta que encontremos 4. Primero, verificaremos el primer artículo. ¿ Esto es 4? 9 no es 4 así que
accede al siguiente ítem. ¿ Esto es 4? 8 no es 4 así que
accede al siguiente ítem. ¿ Esto es 4? 3 no es 4, siguiente, 2 no es 4. Entonces, para una
lista enlazada de longitud n, necesitamos hasta n verificaciones. La búsqueda de una lista enlazada
toma O de n tiempo. Para resumir, una lista enlazada tiene tiempo
constante de inserción
y eliminación, pero un tiempo de búsqueda lineal. Desafortunadamente,
buscar elementos de una lista enlazada también es
bastante lento. Digamos que queremos verificar o recuperar el 3er ítem
en la lista enlazada. No hay manera de saber dónde está
el 3er ítem en la memoria así que necesitamos comenzar
desde el principio. Accederemos al primer ítem, luego seguiremos su puntero
al siguiente ítem. Acceda al siguiente ítem, luego siga su puntero
al siguiente ítem. Por último, accede a este ítem. Dado que este es el 3er
ítem, devuelva su valor. Para una lista enlazada de longitud n, necesitamos atravesar
hasta n nodos. Obtener el i-ésimo elemento de una lista enlazada toma O de n tiempo. Para resumir, ya hemos completado el análisis de la
lista enlazada. Modificar la lista, insertar o eliminar es eficiente. Acceder a la lista, buscar o buscar es ineficiente. Ahora que hemos analizado tanto
arrays como listas enlazadas, veamos cuándo usar cuál. Esta es la
parte más importante de esta lección. Aunque te olvides de
todo lo que dije antes, guarda esta siguiente diapositiva metida en tu bolsillo trasero. Esta
es tu comida para llevar. Aquí hay un resumen de las complejidades del tiempo de
ejecución. la izquierda, tenemos las
cuatro operaciones que analizamos. En la segunda columna, tenemos
complejidades de tiempo de ejecución de matrices anteriores. la derecha, hemos vinculado las complejidades de tiempo de ejecución de la
lista. Para una matriz,
la modificación es lenta, pero la recuperación es rápida. Esto significa que las matrices son ideales para muchos accesos aleatorios para
un conjunto fijo de datos. Para una lista enlazada, el
acceso es lento, pero la modificación es rápida. Esto significa que las listas enlazadas
son ventajosas por su tamaño dinámico ideal para mantener datos en constante
cambio. Eso es. Esta es la
diapositiva de resumen de esta lección. Para obtener una copia de estas diapositivas
y más recursos, asegúrese de consultar
el sitio web del curso. Veamos ahora estas
estructuras de datos en acción. En la siguiente lección,
practicaremos tanto el
uso como la implementación de
estas estructuras de datos, abordando nuestros dos
objetivos de aprendizaje para este curso.
8. Práctica de listas: Bienvenido a otra lección de
práctica. Aquí vamos
a practicar listas. En particular, vamos a
cubrir mayormente listas enlazadas. Al igual que antes, navega a esta URL
alvinwan.com/datastructures101/listas. Una vez que veas esta página, bifurca el proyecto para obtener
tu propia copia editable. Para ello, da clic
en el nombre del proyecto en la parte superior izquierda para
obtener un desplegable, clic en los puntos suspensivos para
obtener otro desplegable, y finalmente, dar clic en
el botón “Tenedor”. Entonces sugiero colocar su
Skillshare y onduló en él ventanas lado a lado
como se muestra aquí. Aquí están los diferentes subtemas por los que
quiero pasar. Vamos a
comenzar con el prompt. Este es el código que tu entrevistador te
proporcionará. Luego hablaremos de
tres categorías de indicaciones: implementación, uso y luego combinar
diferentes estructuras de datos. Para comenzar, en el
lado derecho, deberías ver el código que probablemente te proporcionaría
tu entrevistador. Aquí, tendrías una pila, tendrías una cola. Bueno, supongo que stack and tail probablemente no te
proporcionaría, pero ciertamente podrías
usarlos si es necesario. Este es el código
que se te daría, básicamente una implementación de
lista enlazada. Tendrás algo que
se parece a lo siguiente. Tendrías el valor
para el enlace y
también tendrías una conexión
con el siguiente enlace. Esta de aquí es
una utilidad que he proporcionado para que realmente
puedas visualizar tu lista enlazada. Esto puede o no ser proporcionado. Pero si no lo fuera, también
podrías usar
esta implementación. Empecemos ahora con
nuestro primer ejercicio. Ahora, para todos nuestros ejercicios,
incluido este, vamos a seguir
los mismos tres pasos de los que hablamos antes. Nuevamente, esto es muy importante a tener en cuenta y a practicar. Primero, diseñaremos
el algoritmo sin código verbal o visualmente. En segundo lugar, reportaremos el
tiempo de ejecución y la complejidad de la memoria. Tercero, luego empezaremos a codificar. Aquí está la lista enlazada anexando. Lo que vamos a hacer es agregar un ítem a la lista enlazada. Entonces aquí vamos a tener, digamos una lista enlazada
que tiene 1, 2 y 3. Queremos añadir
el valor cuatro. Después después de agregarlo, entonces
tendremos una
lista enlazada que es 1, 2, 3, 4. Ahora adelante y pausa el video aquí para determinar
qué algoritmo estás usando. Conceptualmente, cuáles son los
pasos que van a ser. Aquí está la respuesta. Conceptualmente, lo que vamos a hacer es de nuevo, sólo
tenemos un puntero al inicio de
la lista enlazada. Vamos a seguir ese
puntero igual que lo se muestra aquí en el lado izquierdo con esta flecha izquierda en negro. Vamos a empezar desde ese puntero luego
vamos a navegar
al siguiente enlace y continuar hasta que hayas llegado al final de nuestra lista enlazada. Luego, al final
de nuestra lista enlazada, simplemente
crearemos un nuevo enlace
y lo adjuntaremos a la lista. Eso es conceptualmente
lo que vamos a hacer. Vamos a
atravesar hasta el final de la lista enlazada y luego
vamos a agregar un nuevo enlace. Sabiendo que ahora, de nuevo, tendremos que considerar
el segundo paso en nuestro proceso de tres pasos. ¿ Cuál es la complejidad de memoria y tiempo de ejecución de
este algoritmo de append? Pausa el video aquí y mira
si puedes averiguarlo. Ahora aquí está la solución. Este algoritmo es lineal en complejidad
computacional
simplemente porque hay
que atravesar
toda la lista enlazada, que podría ser de hasta longitud N. Eso es O de N complejidad
computacional. Para la complejidad de la memoria,
tenemos O de 1 complejidad de memoria
simplemente porque
no usamos ninguna
memoria adicional que no sea almacenamiento para el elemento actual y la lista enlazada existente. En realidad no creamos
ninguna nueva estructura de datos. Apenas tenemos este enlace
que es O de 1 costo. Sabiendo eso, ahora
en realidad vamos a codificar el algoritmo. De nuevo, pausa el video aquí y mira si puedes codificarlo. Ahora aquí hay una solución. Aquí vamos a atravesar
hasta el final de la lista. Aquí diremos mientras
link.next no es ninguno. Esto significa que mientras tengamos otro enlace en
nuestra lista actual, vamos a seguir atravesando
hasta llegar al final. Entonces finalmente, al
final de la lista, por lo que este enlace será ahora
después de este bucle while, el último elemento, por lo que será 3. Ahora tenemos 3, vamos a escribir link.next
es igual a nuestro nuevo enlace, que contiene un valor 4. Sabiendo esto, ahora sigamos
adelante y hagamos nuestras pruebas. Podemos ver ahora que append
falta en esta lista de fallas por lo que hemos
pasado nuestra prueba anexada. Pasemos ahora a
la siguiente pregunta. Ahora, antes de pasar
a la siguiente pregunta, en realidad también para la siguiente
pregunta, memorizar cómo
atravesar una lista enlazada. Siempre será
casi lo mismo. Vas a tener
algún bucle while, vas a verificar para
asegurarte de que no estás accediendo a algún objeto de tipo none, entonces solo
accederás al siguiente enlace. Así es como
prácticamente siempre recorrerás una lista enlazada. Ten esto en cuenta porque el siguiente problema va
a usar algo similar. Sigue adelante y desplázate hacia abajo en tu archivo y verás ahora
aquí está la pregunta de inserción. Nuestro objetivo es insertar después
del índice proporcionado I. En particular, digamos que
tenías esta lista enlazada 1, 2, 3 y queremos insertar
un enlace justo aquí después del índice 0 y
queremos insertar el valor 4. Aquí insertaremos después del
índice 0, el valor 4. Aquí tenemos 1, 4, 2, 3. Si estás mirando en
el lado izquierdo, en realidad
hemos visualizado
cómo será esto para
ayudarte un poco. [ Risas] Sigue adelante y
pausa el video aquí, y mira si puedes
determinar cómo sería
el algoritmo. Ahora, aquí está la respuesta. Lo que haremos es primero
recorrer la lista hasta llegar al enlace
correcto para modificarlo. En este caso, digamos que
estamos insertando H después de las 9, igual que estamos
insertando 4 después de 1. Aquí vamos
a navegar a 9. Una vez que hayamos alcanzado el valor 9, entonces crearemos un nuevo enlace. Volveremos a vincular 9 a 8
y luego volveremos vincular 8 a 2.
Haytres pasos. Navegue hasta el elemento correcto, vuelva a vincular al enlace actual y luego use el
enlace actual para conectarse
al siguiente enlace. Ese es
el algoritmo. Ahora, sabiendo que este
es el algoritmo, sigue
adelante y pausa
el video aquí y
averigua cuál es el tiempo de ejecución
y la complejidad de la memoria. La
complejidad de memoria y tiempo de ejecución aquí. La complejidad computacional
va a ser lineal. Puede que tengamos que recorrer
todo el camino hasta el final de la lista
para insertar algo. complejidad de
la memoria
es constante porque lo único que estamos creando
es este enlace en sí mismo, que es O de 1 costo de memoria
constante. Sabiendo eso,
pasemos ahora al código. Pausa el video aquí
e intenta codificar. Ahora aquí hay una solución. Al igual que antes,
vamos a comenzar
navegando usando un bucle while. En realidad, en lugar de
usar un bucle while, vamos a usar un
for-loop porque sabemos exactamente cuántos pasos
vas a dar. Para link en rango i, link es igual a link.next. He usado subrayado aquí para denotar que no vamos
a usar esa variable. Todo lo que nos importa es que accedamos.next.next.next
básicamente i veces hasta que llegues
al elemento correcto. Una vez que estés ahí, vamos
a reasignar algunas cosas. Primero vamos a reasignar el siguiente
atributo del valor actual al nuevo valor. Pero entonces, también
necesitamos conectar este nuevo enlace al
resto de la lista enlazada. Vamos a usar esto para conectarnos al link.next
original. Nuevamente, en este ejemplo del
lado izquierdo, 9 apuntaba originalmente a 2. Ahora vamos al punto 9 al 8. Eso es justo aquí. Link.next
es igual a nuestro nuevo objeto. Entonces vamos
al punto 8 al 2, y eso es justo aquí
en la segunda parte. Tenemos el link.next original y lo sustituimos
por el nuevo link.next. Eso es. Esta es
nuestra función Insertar. Sigue adelante y vuelve a ejecutar tus pruebas
pulsando el
botón verde “Ejecutar” en la parte superior. Ahora podemos ver que
hay una falla menos. Tenemos inserto no en
nuestra lista de fallas, hemos
superado con éxito las pruebas. Pasemos al
siguiente problema. Aquí, un consejo que
teníamos para este problema y para los futuros es verificar
siempre valores ninguno. Entonces, un error común
que obtendrás con
los problemas de listas enlazadas es que obtendrás, por ejemplo, en este link.next, obtendrás link es
un objeto NoneType. Next no es un atributo
de un objeto NoneTipo. Eso es súper común. Cuando estás depurando, e
incluso antes de depurar, incluso antes de ejecutar el código mientras
hablas con el entrevistador, asegúrate de que estás
revisando tu código y verificando cualquier lugar
donde puede que no haya ninguno y
asegúrese de que no está llamando.next o.value
en un valor NoneType. En esta
función en particular
aquí mismo en la línea 83 y 84, es muy posible
que no fuera válida. Digamos que aquí estaba un 100. Entonces alcanzábamos
en algún momento el valor de
NoneType y habíamos
intentado llamar a continuación en él. Para que esta función sea
más robusta, tendrías que verificarla. Tendrías que dar cuenta de eso. En esta particular implementación
simple, no
hicimos eso, sino algo a
tener en cuenta siempre,
siempre verifique ninguno de los valores en sus entrevistas y cualquier
poema que esté escribiendo. Pasemos ahora
al siguiente problema. Nuestro objetivo ahora es implementar
una pila usando una lista enlazada. Aquí tenemos una lista enlazada, tenemos una, dos. Nuestro objetivo es poder tratar esto como si fuera una pila. Si le llamamos punto pop, nos daría el
último ítem que es dos. Si llamamos push, aquí empujamos 2, empujamos 3, entonces si hacemos estallar, recuperaremos el último ítem que
empujamos, que es tres. Pop otra vez,
obtendrás el segundo al último artículo que empujes,
que son dos. Nuestro objetivo es implementar una pila pero usando una
lista enlazada en el backend. Sigue adelante y pausa el
video aquí y mira si puedes averiguar
debería el algoritmo, en este caso, el algoritmo es, ¿cómo vas a empujar y
cómo vas a hacer pop? Pausa el video aquí.
Aquíestá la respuesta. Conceptualmente hablando, esto
en realidad es bastante similar
al principio. Cuando decimos push aquí, vamos a escribir más o menos la función append de la que
hablamos anteriormente. Podemos decir pop aquí, vamos a escribir una
nueva función, eliminar. Todavía no hemos escrito
una función de eliminación, pero será
prácticamente como cualquier otra función que
elimine de una lista de enlaces. Entonces ahora que conocemos
el algoritmo, sigue
adelante y pausa el video aquí y mira si
puedes averiguar la complejidad computacional y de
memoria. La solución para esta parte, ejecución y la complejidad de la
memoria en realidad la complejidad del tiempo de ejecución
va a ser lineal Vamos a recorrer
todo el camino hasta el final de la
lista enlazada y luego agregarla. En caso de pops, vamos
a recorrer todo el camino hasta el final de la
lista enlazada para eliminar de ella. Ahora, sabiendo eso, la complejidad de la memoria
es constante. La complejidad de la memoria, todo lo
que estás haciendo es crear un nuevo enlace y así eso
es O de un costo de memoria. No estás creando
una lista completamente nueva. No está creando
otra estructura de datos que almacene un elemento. Sólo estás creando un enlace. El costo de la memoria es O de uno. Ahora, pausa el video aquí
e intenta codificarlo. Ahora escribamos el código. Así que aquí vamos a
implementar push más o menos igual que re-implementado
append antes. Primero vamos a definir
un enlace variable local que es nuestra lista enlazada actual comenzando y luego mientras
link.next no es ninguno. Entonces mientras tenemos algo que enlazó la lista, vamos a atravesarla. [ RUIDO] Entonces finalmente
al final, vamos a agregar un nuevo enlace. Eso es más o menos para el método
push de la función push. Pasemos ahora
al siguiente. Para eliminar algo,
vamos a volver a establecer este enlace de variable local a nuestro inicio con
la lista enlazada. Entonces mientras estamos
a uno del final, así que en realidad no
queremos el último enlace, queremos el penúltimo enlace porque esa va
a ser nuestra nueva cola. Vamos a atravesar de nuevo. Entonces lo que vamos a hacer
en este punto es primero agarrar el valor del último artículo antes de que realmente lo eliminemos. Aquí, queríamos obtener el
valor del último enlace. Después a continuación,
vamos a desvincularlo. Entonces ahora nuestro penúltimo
eslabón no apunta a nada. Este es ahora nuestro último enlace
flamante, y luego finalmente
devolver el valor. Así es como eliminamos realmente desde el final
de la lista enlazada. adelante y hagamos
clic en el botón verde, la parte superior para ejecutar
nuestro archivo y revisar nuestras pruebas. Ahí vamos. Ahora podemos ver que nuestra pila vía Linked
list en realidad se ha ido. Ya no hay en
nuestra lista de fallas, por lo que hemos pasado estas pruebas. Pasemos al
siguiente problema. Antes de pasar a ese
problema, tenemos una propina más. Quieres hacer fácilmente una de tus propias preguntas
prácticamente solo mezclar y
combinar cualquiera de estas. Has hablado de tres estructuras de datos
diferentes, listas
enlazadas,
pilas y colas. Para crear
una nueva pregunta, simplemente implemente, elija una
usando y luego elija otra. Cualquiera de estas
combinaciones
te dará un problema completamente nuevo
que podrás probar. Siempre y cuando puedas pasar las mismas pruebas que
has escrito para una pila excepto usar tu nueva estructura de datos,
entonces estás listo para comenzar. Esto va para
cualquier otra cosa. Si tienes pruebas para la cola, entonces solo asegúrate de que eres
nueva estructura de datos puede pasar esas pruebas, y luego las pruebas se vincularon
lista, y así sucesivamente, así sucesivamente. Es mezclar y combinar cualquiera
de estas combinaciones para obtener un problema completamente nuevo. Ahora, implementemos la
eliminación de ciclos para una lista enlazada. En particular, busque y elimine un ciclo en una
lista enlazada si está presente. Por ahora, por simplicidad, se
puede suponer que todos los valores de
enlace son distintos. Esto es muy importante porque la primera pregunta
que vas a considerar cuando veas encontrar y quitar ciclo es ¿cómo
vas a detectar un ciclo? Una forma de detectar un
ciclo sería si ya he visto este valor antes, entonces sé que he acertado a un ciclo.
Supongoque para aclararlo. Digamos que te estás
moviendo de izquierda a
derecha a lo largo de esta lista enlazada. A medida que avanzas, si de
repente ves tres dos veces, entonces sabes que
has acertado a un ciclo. Pero eso sólo se puede decir si se sabe que todos los valores de
enlace son distintos. Es por ello que el hecho de que los valores de enlace sean distintos es
cuestión muy importante para este problema. Escribí que aquí están
todos los valores únicos. Esa va a ser una de tus primeras preguntas es para
tu entrevistador. Su segunda pregunta,
y esta es una pregunta un
poco más
avanzada. Quieres preguntar, ¿hay
una duración máxima del ciclo? Esto tiene que ver con
la implementación,
porque si quieres hacer un seguimiento de todos los valores
que has visto hasta ahora, y luego
quieres decir: “Está bien, ¿ya
he visto este valor?” Entonces potencialmente
nunca se podría ver un ciclo. Toda esta lista enlazada
podría tener un millón largo y que
no haya un ciclo en ninguna parte, entonces básicamente la has guardado
esta enorme tienda de un millón de artículos esperando a ver si alguno de esos millones
los artículos aparecen de nuevo. Esta es una buena pregunta para hacer sería ¿hay
una duración máxima del ciclo? Porque de esa manera no
tendrías que quedarte con todos los millones de artículos si sabes que la
duración máxima del ciclo es de solo cinco. Estas son buenas
preguntas a tener en cuenta para este problema. A medida que avanzas y
practicas estos problemas, comenzarás a entender
qué preguntas hacer. Entonces, por ahora, si estás pensando que estas son
preguntas locas de la nada, no hay forma de
pensar en ellas, está bien. Así como veas cada
vez más de ellas, te
familiarizarás más con qué tipo de preguntas hacer. Por ahora, veamos si
se te ocurre un algoritmo. Le regalé partes de él pero pausa el video
aquí y vea si se le puede llegar
a una manera de eliminar ciclos , y aquí está la respuesta. Básicamente, lo que
vas a hacer es mantener una colección de todos los
valores que ya has visto. Si ya has visto el
valor, entonces sabes que
este es un ciclo y puedes romper el ciclo simplemente reasignando
link.next en consecuencia. Sabiendo eso, ese es
ahora el algoritmo. ¿ Cuál es el tiempo de ejecución y complejidad
de la memoria?
Pausael video aquí. Para la complejidad de memoria y
tiempo de ejecución, para la
complejidad computacional en particular, vas a tener O
de N. Vamos a recorrer
toda esta lista uno por uno. Tenemos que hacer eso para averiguar si hay
un ciclo o no. Para la segunda pregunta es, ¿qué hace la complejidad de la memoria? Para la complejidad de la memoria,
vamos a volver a mantener una colección de todos los diferentes valores
que hemos visto hasta ahora. Eso es una O de N complejidad de
memoria. O de N complejidad de memoria y O de N
complejidad computacional. Sabiendo eso, intentemos
ahora codificarlo. Pausa el video aquí. Ahora, sigamos adelante y codifiquemos esto. Aquí vamos a comenzar
creando un conjunto de valores. Entonces, si aún no lo has
visto, un conjunto es una estructura de datos
que te permite verificar la membresía
en tiempo constante. decir, que puedes hacer algo
como éste en escena, y esto por mucho tiempo que sea
tu set, siempre
se ejecutará
en tiempo constante. Eso es un set. Vamos a usar
el set para rastrear todos los valores que
has visto hasta ahora. Si bien hay
algo más en nuestra lista enlazada, vamos a comprobar
si ese siguiente valor está en nuestra lista de valores de escena. Si es así, entonces vamos a romper la conexión con
el siguiente enlace. Nuevamente, si el siguiente
enlace está en nuestra lista, he visto valores,
vamos a romper ese vínculo y
vamos a terminar aquí. Estamos asumiendo que
solo hay un ciclo en nuestra lista. Nuevamente, esa sería una gran pregunta para hacerle a
su entrevistador. ¿ Habrá
más de un ciclo? En esta
pregunta en particular
vamos a fingir que sólo
hay un ciclo. Ver.add y luego habremos
vinculado hasta el valor aquí mismo. Lo que estamos haciendo aquí es que
estamos diciendo, bien, hemos considerado que aquí no
hay ciclo. Debido a que no hay
ciclo, agreguemos el valor de los enlaces actuales a
nuestra lista de valores de visualización. Por último, este es el estándar
un recorrido de lista enlazada, solo
vamos a acceder al
siguiente ítem y
seguirá adelante. Eso es. Sigamos adelante y
ejecutemos esta función y asegurémonos de que
nuestras pruebas pasen. Ahí vamos, podemos
ver que elimina ciclo ya no está en nuestra
lista de funciones fallidas. Pasemos a
la siguiente pregunta. Para la siguiente pregunta,
y también para esta,
un consejo es dibujar siempre tus listas enlazadas y
verificar si hay enlaces rotos. Lo que quiero decir con dibujar son básicamente las ilustraciones que tenía antes aquí mismo. Si es necesario mezclar, dibuja estos para entender
si está vinculando todos de la
manera correcta. Me moví bastante rápido a través de
algunas de estas preguntas porque ya
escribí la solución y conozco las soluciones. Pero básicamente, si te
dan un problema completamente nuevo, las probabilidades de hacer un enlace
incorrecto son muy altas. Eso está completamente bien
siempre y cuando lo dibujes. Si lo dibujas,
puedes elaborar
los enlaces correctos para conectarte. Ese es uno de mis consejos aquí. Dibuja tu lista enlazada y
comprueba si hay enlaces rotos. Ahora bien, para este problema
en particular, sólo
vamos a
discutirlo conceptualmente. De hecho, he escrito una solución
totalmente funcional en código para ti pero
como es bastante compleja, solo
vamos a
hablar de esto algorítmicamente. Para esta pregunta,
nuestro objetivo es usar o crear un nuevo objeto de archivo mediante el uso de las estructuras de datos
que ya hemos visto. Nuestro objeto file va a
ser fusionado con otros archivos. [ Risas] Acabo de
mostrarte una parte de la
descripción de la solución. Pero tu objetivo es crear un objeto de archivo que pueda
fusionarse oficialmente con otros archivos. La idea es que hay
muchos de estos archivos. Lo que eso significa es que no
quieres copiar todos los datos
en un archivo masivo. Si haces toda esa copia, va a llevar
mucho tiempo. ¿ Cómo podemos combinar un montón de
archivos sin copiarlos? Si no quieres la pista, entonces sigue adelante y
pausa el video aquí. Pero una pista que tengo para ti es que no queremos copiar, así que en vez de copiar, almacenemos un puntero
al siguiente archivo. Tendremos el archivo 1
y después diremos, del archivo 1, sabemos cuál es
el siguiente archivo 2. Todo lo que vas a hacer es almacenar una conexión o un puntero. Eso debería sonar muy parecido
a una de las estructuras de datos que acabamos de
cubrir y que he estado usando. Ahora pausa el video
aquí y mira si puedes averiguar
el algoritmo. Ahora aquí está la solución. Básicamente vamos
a usar una lista enlazada. Cada archivo
va a ser un enlace. Cada archivo entonces
apuntará al siguiente archivo y dirá que es el siguiente valor de
archivo a atravesar. Así es como vas a almacenar este archivo masivo fusionado. Pero eso no es todo,
hay un poco más porque necesitamos soportar
esta función merge. Saber cómo los vamos
a almacenar es genial. No tenemos que hacer
copias, pero ¿cómo se fusiona
realmente un nuevo archivo? Bueno, el nuevo archivo emergente, es igual que lo agregarías
a cualquier otra lista enlazada. Prácticamente recorres hasta
el final de la lista enlazada y agregas el nuevo archivo.
Esoes más o menos. Para este problema
o este ejercicio, la única dificultad conceptual es darse cuenta de que hay que
usar una lista enlazada. Ese era realmente el problema
del puntero. Ahora que hemos cubierto
el problema del puntero, vamos a
seguir adelante solo porque tengo una solución escrita para
esto y hay anotaciones
línea por línea
para lo que cada uno es haciendo y como funciona pero los detalles
no son super importantes. Pasemos a
la siguiente pregunta. Otra vez, no otra nave aquí. Listas enlazadas que utilizamos para colecciones de tamaño
dinámico. En este caso particular, este conjunto de archivos es un
conjunto de colecciones de tamaño dinámico. No sabemos qué tan grande es, podríamos agregarle
un montón de veces, e incluso podríamos
quitarle un montón de veces. Las listas enlazadas son excelentes para
esas colecciones porque
no tienes que copiar
datos cada vez que quieras agregar o eliminar un objeto. que quieras
agregar o eliminar enlace, es tiempo constante. Ahora sin embargo, las matrices son
perfectas para el acceso aleatorio. Hablamos de
esto un poco antes pero básicamente lo que esto significa es que si quieres acceder
al i-ésimo elemento en una matriz, sabes exactamente dónde
está en la memoria. Vas directo a
esa parte de la memoria. Sin embargo, para una
lista enlazada si quieres el i-ésimo ítem como viste antes, necesitas recorrer toda
la lista, así que no es tan eficiente.
Esaes la propina. Las listas enlazadas son para colecciones de tamaño
dinámico, las
matrices son para acceso aleatorio. Para nuestra última pregunta aquí, tu objetivo es combinar estructuras de
datos para encontrar un palíndromo
en una lista enlazada. Un palíndromo es una palabra que se cría igual al revés
que es deportes como el de carreras. Si volteas un auto de carreras, aún
obtienes un auto de carrera. Aquí, tu palabra va a ser representada
como una lista enlazada. Aquí tenemos un enlace
que tiene r en él, y que apunta al siguiente
enlace que tiene a en él, apunta al siguiente
enlace que tiene c, y luego apunta a
e, apunta a c, apunta a a, así sucesivamente y así sucesivamente. Nuestra lista enlazada representa
la palabra racecar. Queremos comprobar si esta lista
enlazada es un palíndromo. Considera qué otras
estructuras de datos puedes usar para ver
también en esta
lista enlazada es un palíndromo. Pausa el video aquí y mira
si puedes averiguarlo. La solución conceptualmente para esto bastante desafiante es que quieres tanto una
pila como una cola. A medida que avanza y
recorre esta lista enlazada, agrega tanto a la
pila como a la cola. Luego, una vez que haya terminado dar servicio a
toda la lista enlazada, simplemente elimine la cola de barras, simplemente elimine de cada una de las colas de apilamiento y luego verifique si cada una de
esas es igual entre sí. Eso es genial porque la
pila elimina del final,
la cola se elimina
desde el principio así que básicamente te estás moviendo a lo largo la cadena en reversa
y hacia adelante
al mismo tiempo por solo quitando de la
pila y de la cola. Eso es perfecto para nosotros
porque en un palíndromo, una forma de comprobar si es
un palíndromo es comprobar si el primer personaje
es tú eres el último. En el segundo se
va a la segunda última y así sucesivamente y así sucesivamente. Al quitar de la pila
y de la cola, se obtiene eso. Hagamos una pausa aquí mismo. A ver, ese es el algoritmo. ¿ Cuál es el tiempo de ejecución
y la complejidad de la memoria? Aquí está la respuesta.
Tantopara el tiempo de ejecución
como para la complejidad de la memoria, tenemos complejidad lineal. Porque la complejidad de la memoria
es lineal porque estamos almacenando una pila y una cola que cada una podría tener hasta la longitud n, y también tenemos complejidad computacional
lineal porque estamos iterando sobre cada una
de estas letras. De hecho, estamos iterando dos veces, pero no importa, es o de n Ahora que conocemos el
algoritmo y conocemos la complejidad,
intentemos codificarlo. Pausa el video aquí
e intenta codificarlo. Ahora vamos a cubrir la solución. Vamos a
comenzar inicializando tanto la pila como una cola. Ahora que tenemos ambas estructuras
de datos, recorremos la lista enlazada, tal como dijimos, y por cada
enlace vamos a agregarlo a ambas estructuras de
datos. Aquí voy a
añadir a la pila. Voy a empujar la
pila y luego pondré en cola también en la cola. Entonces atravesaré
al siguiente enlace. Justo como dije antes,
este código transversal es prácticamente siempre el mismo. Ahora habiendo terminado eso, ahora
vamos a recorrer ambas estructuras
de datos, la pila y la
cola, y nos
aseguramos de que por
cada elemento que eliminemos, sean exactamente iguales. Si bien hay algo
en la pila, pop de la pila
y retire de la cola. Siempre y cuando coincidan,
estamos bien para irnos. Si no coinciden en ningún
momento, devolvemos false. Si nada devuelve falso, todo el partido y
podemos devolver verdadero. Eso es. Ahora sigamos
adelante y evaluemos esto. Pulsa el
botón verde Ejecutar en la parte superior y comprueba que
todas tus pruebas pasen. Aquí podemos ver que
nuestra función es enlace
palíndromo no se encuentra por ningún lado en la
lista de fallas. Hemos
superado con éxito esa prueba. Estas tres
funciones restantes son funciones bonus. También he incluido soluciones
completamente elaboradas para ellos y explicaciones también en el código,
así que también puedes probarlas en
tu propio tiempo. Si tienes alguna
duda, no dudes publicarlas en la sección de
discusión. Eso es todo para esta lección. Siga adelante para las diapositivas, para el código
completamente desarrollado y la naturaleza de
soluciones para visitar
el sitio web del curso. Eso es todo para listas, tanto arrays como listas enlazadas.
9. Mappings: Hashmaps: En esta lección, presentaremos una estructura de datos para asignaciones. Un mapeo es
lo que parece, un mapeo de un
elemento a otro. Aquí mapeamos gato
al número cinco. En este caso, digamos que
estamos mapeando animal a edad. Animal es lo que llamamos
la clave en el mapeo, y la edad es lo que llamamos
el valor en el mapeo. También podemos tener pares de valores
clave adicionales en el mapeo. Observe que este mapeo no
tiene sentido del orden, cada par de valores clave está completamente
separado entre sí. La estructura de datos que almacena este mapeo se
llama HashMap. Explicaremos cómo funciona
un HashMap, discutiremos sus pros y sus contras, luego discutiremos brevemente
un concepto de bonificación. He aquí por qué esta estructura de datos
se llama un mapa Hash. En el núcleo, un HashMap usa una función llamada
función hash. Esta función hash toma algún valor con longitud
arbitraria, como cat, luego transforma esa entrada para producir una salida de tamaño
fijo como dos. Esta función hash es importante, y así como esa salida también, veamos cómo se usan ambas
. Digamos que queremos
insertar algunas claves y valores en una tabla hash. la derecha,
tenemos una tabla hash donde cero es la primera dirección de memoria de
ranuras, una es la segunda dirección de memoria de
ranuras, y así sucesivamente y así sucesivamente. Queremos mapear el
gato clave al valor cinco, para ello vamos a
hash el valor cat. Esto nos da la Dirección de
Memoria 2, por lo que en la posición dos
colocan el valor cinco. Vamos a repetir esto para más datos, mapear perro a tres, perro hachís. Esto nos da la Dirección de
Memoria 3, así que en la posición tres, colocar el valor tres. Repetimos esto una vez más, para mapear cerdo a cuatro, cerdo hachís. Esto nos da la dirección de
memoria cero, por lo que en la posición cero
coloque el valor cuatro. Este proceso toma
solo constante u O de una vez por cada par de
valores clave que insertamos. Para eliminar del HashMap, pasamos por pasos similares. Para eliminar cat del hashMap, primero hash cat para obtener dos, luego en la posición
dos eliminar el valor. Esta operación también es
constante u O de una vez. Para resumir, la inserción
y eliminación de un HashMap son ambas
O de una vez. Muy rápido. Digamos que ahora
queremos buscar en el HashMap, cuyo valor corresponde a cat. Casi el mismo proceso, hash al gato para obtener su dirección de
memoria, que es dos. Después en la posición dos, agarra el valor cinco
y devuélvalo. Como resultado, decimos que buscar un HashMap toma O constante, otra vez O de una vez. Para resumir, la
búsqueda de un HashMap toma O constante de una vez. Para un HashMap, search
y fetch son lo mismo, así que omitimos analizar
fetch por separado. Ahora entendamos los pros
y los contras de estos HashMaps. HashMaps en resumen, tienen algunos tiempos de ejecución
muy impresionantes, tiempo
constante, modificación y acceso, debido a
cómo funcionan los HashMaps, son ideales para cualquier dato
con identificadores únicos. Por definición, los HashMaps
no están diseñados para datos de pedidos. Como dijimos antes, cada uno de estos pares de valores clave
están completamente separados. No hay sentido de orden, no
hay relación entre pares de valores
clave separados. Ya hemos discutido las
dos primeras secciones, qué es un HashMap y para
qué es ideal. Discutiremos la sección de bonificación después de terminar
el contenido principal. Para obtener una copia de estas diapositivas
y más recursos, asegúrese de consultar
el sitio web del curso. Esto concluye nuestra
discusión central de HashMaps. Si estás satisfecho con
este nivel de detalle, no dudes en pasar a la próxima lección
con la práctica de HashMap. De lo contrario,
hablemos ahora de la sección de bonos. En particular,
discutimos una advertencia para HashMaps llamada colisiones
hash. Anteriormente dijimos
que los HashMaps son tiempo
constante de
modificación y acceso. Sin embargo, esto no siempre es cierto. ejecución en realidad depende de cómo se implementó
un HashMap
y este es el motivo. En ocasiones se produce este fenómeno
cuando se menciona anteriormente, llamado colisión hash. Por ejemplo, digamos que queremos
insertar dos pares de valores clave, mapas de
gatos a cinco y mapas de
perros a tres. Como antes, hash
cat para conseguir dos. En la posición dos,
colocamos entonces el valor cinco, esto es igual que antes. Ahora, para insertar nuestro
segundo par de valores clave, hacemos hash dog para obtener dos, en la posición dos, ahora
tenemos un problema. No podemos anular
los datos existentes, así que tenemos dos opciones. La primera opción se
llama direccionamiento abierto. En el direccionamiento abierto,
simplemente encontramos otra
ranura en el HashMap, si esta siguiente ranura está vacía, coloca ahí tu nuevo valor. Una forma de encontrar una ranura
vacía es simplemente atravesar las ranuras
hasta encontrar una vacía, y allí colocar su valor. También hay estrategias
para encontrar franjas horarias, que no discutiremos aquí. Otra técnica completamente
diferente para manejar colisiones hash
se llama encadenamiento. En esta técnica, tratamos cada ranura como una
estructura de datos propia. Por ejemplo, podríamos tratar
cada ranura como una lista enlazada, luego para
insertar en la posición dos, simplemente
insertamos tres
en la lista enlazada. También podemos tratar cada
ranura como un HashMap, cualquier estructura de datos que hagamos cada uno con sus propias
compensaciones una vez más. En resumen, definimos
una colisión hash y también vimos dos formas de
manejar una colisión hash. Abrir direccionamiento o encontramos
otras ranuras vacías para usar o encadenar donde tratamos cada ranura como su
propia estructura de datos. Con eso concluye nuestra sección de bonificación aquí sobre colisiones hash, asegúrate de
revisar nuestra siguiente lección para practicar con HashMaps.
10. Práctica de aplicaciones: Bienvenido a la práctica de estructura de
datos de mapeos. Aquí, nuevamente,
practicaremos más ejercicios y repasaremos algunos consejos de entrevistas relacionados con la estructura de
datos de mapeo. En particular, estas estructuras
de datos también
se llaman Hashmaps. Entonces usaremos mucho esos
nombres, Hashmaps. Al igual que antes navega a esta URL
alvinwan.com/datastructures101/mapings. Eso te traerá a repl.it. Sé que ya hemos hablado varias veces de
estas instrucciones. Voy a repasarlo una vez
más por si acaso, una vez que veas esta página, bifurca el proyecto para obtener
tu propia copia editable. Haga clic en el nombre del proyecto en la parte superior izquierda para obtener un menú desplegable. Haga clic en los puntos suspensivos para
obtener otro desplegable, y luego haga clic en
el botón “Horquilla”. Entonces sugiero colocar
tu Skillshare y las ventanas
repl.it
lado a lado como se muestra aquí. Entonces deberías ver
algo que se
parezca a lo que tienes en
el lado derecho. Entonces hablemos ahora los tipos de ejercicios
que verás. Tendrás los ejercicios de implementación, uso y combinación. Si te desplazas hacia abajo,
verás que nuestro primer ejercicio aquí es implementar una pila. Vamos a hacer
esto en tres pasos, igual que lo hemos hecho en
todas las demás lecciones. Primero vamos a diseñar el algoritmo sin ningún código. Vamos a reportar el tiempo de
ejecución y la complejidad de la memoria. Entonces en realidad vamos a
codificar el algoritmo. Apliquemos estos tres pasos al
primer algoritmo, o nuestro primer ejercicio aquí. Implementar una pila que limite todos los valores de la pila a
solo tres ocurrencias. Si se está
empujando un valor que tiene
más de tres ocurrencias, simplemente ignore ese valor. Entonces en este caso en particular, tenemos un ejemplo aquí. Inicializamos
primero una pila y luego
empujamos el valor uno,10 veces. Sin embargo, solo los tres
primeros valores se agregan realmente a la pila. Todo lo demás es ignorado. Luego puede empujar otros
valores distintos de uno y se agregará
a la pila normalmente. Adelante, prueba esto. Primero, diseñe el algoritmo
que realmente
implementará esta
pila con un límite. Pausa el video aquí e
intenta averiguar un algoritmo. Aquí está la solución
algorítmicamente. Lo que vamos
a hacer es
usar primero la implementación de la pila de referencia. Entonces puedes ver aquí que
mi clase de pila tapada en realidad hereda de
la clase de pila base. Sabiendo eso,
vamos a imponer restricciones sobre cuándo puedes realmente empujar a una
pila, y eso es todo. Para ello, vamos
a mantener un HashMap, mapeando todos los valores a
sus recuentos en la pila. Cada vez que empujes,
incrementarás ese valor. Si ese valor excede el límite, simplemente
ignoraremos el valor, y luego pop realmente se asegurará de
disminuir ese conteo. En push, revisas el conteo, lo
agregas si el conteo está bien, y luego incrementas el conteo. En pop, decrementas el conteo. Entonces ese es el algoritmo. Ahora, analicemos el tiempo de ejecución
y la complejidad de la memoria. Pausa el video aquí y mira
si puedes averiguarlo. Para la complejidad del tiempo de ejecución, es cualquiera que sea
la complejidad del algoritmo original. En este caso particular, push es lineal y el pop es la forma en que
lo implementamos, también lineal. Entonces tanto push como pop
son operaciones lineales. Ahora por la complejidad real de la
memoria,
entonces, ¿qué aspecto tiene eso? Bueno, aquí tenemos que crear
un nuevo valor. No es exactamente o
de n. Tenemos un valor agregado al
HashMap por cada nuevo valor, pero eso no es tanto como el número de
valores totales que agregamos. Solo tenemos el número de valores
únicos en nuestro HashMap. Tenemos que inventar una nueva carta. En lugar de o de n, diremos
que es o de k por ejemplo, y definiremos k
como el número de valores
únicos que
se han agregado a la pila. Si realmente tuvieras
esto en una entrevista, dirías
algo así. En realidad necesitamos
definir una nueva variable, k, donde k es el número
de valores únicos, y nuestro algoritmo, nuestra complejidad de memoria para
nuestro algoritmo es o de. Eso es todo por la complejidad. Pasemos ahora al código. Así que pausa el video
aquí e intenta codificar. En el constructor
vamos a inicializar un nuevo contador. De colecciones,
import, default, dict. Este es un
tipo diferente de diccionario. Lo que
hace este diccionario es que si
accedes a una clave que no
tiene un valor actual, inicializará ese
valor usando esta función. En este
caso particular, para este contador, si digamos que
accedemos al contador 0, 0 no es actualmente una
clave válida para este diccionario, por lo que lo inicializará
con esta función int. El valor predeterminado para la función
int es cero. Por defecto, auto contador
de 0 me dará 0. De hecho, auto
contador de cualquier cosa, también me
va a dar 0. Así es como funciona este
diccionario predeterminado, y esto solo hará que parte
del código se vea un
poco más simple. Ahora que tengo esto, implementemos ahora la función push. Como dijimos antes,
lo primero que vamos a hacer es verificar si el conteo actual
está por debajo del límite. Si está por debajo del límite,
entonces procederemos. Si está por debajo del límite, entonces en realidad
incrementaremos el conteo, y luego lo
empujaremos a la pila. En pop todo lo que haremos es
simplemente decrementar el conteo. Aquí primero encontraremos el valor. Aquí saltaremos de la pila, y luego una vez que hagamos pop ese valor disminuirá el
conteo para ese valor, y luego devolveremos el valor. Veamos ahora si nuestras
pruebas de pila de topes pasan. En la parte superior, pulsamos el
botón verde, y ahí vamos, cap snack ya no está
en la lista de fracasos, por lo que hemos pasado esta prueba. Pasemos a
la siguiente pregunta. Un consejo es que los Hashmaps son ideales para datos
con ID únicos. En este caso particular, sabemos que cada valor único, o la premisa del
problema es que estamos guardando si debemos o no
empujar sobre la pila
por el valor. Entonces el valor en sí
es el ID único. Debido a que tenemos esta identificación única, Hashmaps fueron perfectos
para este problema. Sin embargo, los Hashmaps son
peores para los datos ordenados. Si hay una relación
entre tus datos, digamos que tengo una secuencia
de números, uno hasta 10, y necesito saber
ese orden. O otra forma de
decirlo sería, digamos que tengo 10 valores y
los inserto en
una estructura de datos. Si necesito recordar el
orden en el que lo inserté, Hashmaps no son la estructura de
datos a usar, porque los Hashmaps olvidan
todo el orden. Todo lo que hacen es mantener un
mapeo de claves a valores. No recuerdan
nada sobre qué orden
insertas las llaves. Entonces eso es importante. hashmaps son ideales para
datos con ID únicos, pero no son tan buenos para los datos donde el pedido
es importante. Para nuestra siguiente pregunta, desplácese hacia abajo para ver
la siguiente pregunta. Devuelve un histograma de todas las letras únicas y
sus números de ocurrencias. Supongo que esto debería
haber ido primero. Este es un subconjunto
del problema anterior. Pero de todos modos, pausa el video aquí y mira si puedes
averiguar el algoritmo. La solución
conceptualmente es que
vamos a inicializar un
HashMap como contador, y cada vez que vamos a
iterar sobre la cadena, y por cada nuevo valor, vamos a
acceder a nuestro contador. Si ya hemos
visto este valor, vamos a sumar
uno al conteo. Si no hemos visto antes
este valor, inicializaremos el conteo a uno. Entonces ese es el algoritmo. ¿ Cuál es el tiempo de ejecución
y complejidad de la memoria? Pausa el video aquí.
Aquíestá la respuesta. La
complejidad del tiempo de ejecución es lineal. Tenemos que iterar sobre cada letra
de la cadena. No hay forma de evitar eso. El segundo, la complejidad
de la memoria. Nuevamente, necesitamos inventar
una variable completamente nueva. Esa variable es el
número de valores únicos, digamos k Este
algoritmo es o de k, donde k es el número de valores
únicos que
están en la cadena. Eso es todo para la serie
combine, intentemos ahora codificarlo. Pausa el video aquí
y prueba el código. Ahora vamos a cubrir la
solución en código. Aquí vamos a
crear un contador. Este contador va
a ser un diccionario. De hecho, lo que voy a hacer es usar el
diccionario predeterminado de antes. De esa manera el diccionario
se inicializa a cero. Aquí tendremos desde
colecciones, import, defaultdict. Entonces aquí por cada
letra de la cadena, vamos a incrementar
el conteo correspondiente. Aquí vamos a incrementar el conteo correspondiente y
finalmente devolver el contador. Ahora, también quiero
mostrar la implementación sin este defaultdict. Supongamos que
no usaste el defaultdict. Supongamos que solo
creas un diccionario normal. Entonces aquí comprobaríamos si
la carta está en el mostrador. Si ya hemos visto
esta carta antes, entonces simplemente
incrementaremos en uno. Si no hemos visto esto antes, entonces lo inicializaremos a uno. La letra de contador es igual a uno. Ahora sigamos adelante y
ejecutemos esto para comprobar si único es ahora una
prueba que pasa. Ahí vamos. Único ahora ha pasado
todas sus pruebas. También hemos completado
este ejercicio. Pasemos ahora
al siguiente ejercicio. Un consejo es asegurarse de que su clave
existe antes de acceder a ella. Eso lo hicimos aquí mismo. En la línea 103, comprobamos si la carta estaba
en el mostrador. Es decir, si
hubiéramos visto esta carta antes y ya había
una clave válida en nuestro mapeo. Entonces sabiendo eso,
pasemos a la pregunta que viene después. Usando nuestra estructura de datos para encontrar el valor más frecuente en
una lista de números enteros. He especificado números enteros para que esto sea un
poco más sencillo. Pero hay varias preguntas que querrías hacerle a
tu entrevistador. La primera pregunta sería, si no hubieran especificado
los números enteros, más probable es
que no lo hicieran. Lo más
probable es que digan números. Entonces querrías preguntar, ¿puede haber valores negativos? ¿ Puede haber valores decimales? ¿ Cuáles son las gamas? ¿ Cuál es el conjunto de posibles
valores que podría ver? La segunda pregunta
que querrías
hacer es ¿y si hay corbata? Que la pregunta en sí
no está bien definida
si hay empate. Ahora bien, en caso de empate
en esta descripción del problema, reportar cualquiera de los números empatados para mayor frecuencia. Eso suele ser lo que va a pasar. Pero estas son buenas
preguntas para hacer y te da algunos
puntos brownie en tu entrevista. En esta pregunta en particular, tenemos una lista de números, y quiero averiguar cuál es
la más frecuente, pausar el video aquí y
ver si puedes averiguar el algoritmo.
Aquíestá la solución. Vamos a hacer algo
muy parecido a antes. Vamos a usar un HashMap para almacenar realmente los recuentos cada valor en nuestra lista. Una vez que tengas ese contador, bueno entonces usa el
contador para
averiguar cuál fue el más grande. Esa sería una forma de hacerlo. Otra forma de hacer esto que no requiere
dos pasadas de los datos, sería en realidad, como estás agregando al contador, mantener una variable que represente
el valor más frecuente. Si ves un valor que de
repente tiene más instancias entonces
reemplaza esa variable. Verás esto en
acción en tan solo un segundo. Pero conceptualmente, la idea
principal es mantener un contador de todos
los valores únicos y luego usar ese contador. Ahora que conocemos el algoritmo, pausar el video aquí y ver si puede
averiguar el tiempo de ejecución y la complejidad de la
memoria.
Aquíestá la respuesta. Al igual que antes,
tenemos exactamente la misma complejidad de memoria de tiempo de ejecución y las funciones anteriores. complejidad en tiempo de ejecución
va a ser lineal. Tienes que recorrer cada elemento de la lista. No hay forma de evitar eso. El segundo es O de k, donde k es el número
de valores únicos. Eso es supongo que ahora
se está convirtiendo en un motivo. Pero al menos para
estos ejercicios, O de k es la correcta una
vez, así que tenlo en cuenta. Es lineal en el
número de valores únicos. Ahora que hemos cubierto
la complejidad, hemos cubierto el algoritmo, pausar el video aquí
y probar el código. Aquí está la solución. Vamos a escribir esto ahora. Vamos a
empezar con contador
y contador va a
ser un diccionario vacío. El mayor valor va
a ser ninguno, digamos. Para el valor en números, vamos a verificar si el
valor está en el contador. Si hemos visto este valor antes, en realidad voy a cambiar
esto un poco. Si el valor no está
en el contador, entonces inicializaremos
eso a cero. Independientemente de cuál
sea su valor, incrementaremos en uno. Si el contador es
mayor que el valor mayor, entonces si el conteo actual es mayor que el conteo mayor, entonces reasignaremos, y luego devolveremos
el mayor valor. Antes de ejecutar esta función, debes tener en cuenta
algo que es, bueno, una de las tácticas
que voy a plantear en un curso futuro es que siempre debes ejecutar
virtualmente tu código. qué me refiero con eso
es simplemente ejecutar el código en tu cabeza como si
fueras el intérprete. Si captas algún error
antes de ejecutar el código, ese suele ser otro punto
límite para ti. En este caso en particular, en realidad
veríamos un error aquí debido al
contador mayor. más grande aquí no es
ninguno y Lomás grande aquí no es
ninguno yninguno aún no
existe en el mostrador. Esto se remonta a
nuestro consejo anterior, siempre asegúrate de que la clave existe antes de
intentar acceder a ella. En este caso en particular, voy a agregar la clave
none aquí mismo, y voy a
ponerla en negativo. De esa manera, cada
otro valor con un conteo será
mayor que éste. En la primera iteración, reemplace el mayor valor
por el valor actual. Eso es todo para esta función. Ahora intentemos ejecutar las
pruebas y asegurarnos de que las más frecuentes ya no
aparezcan como una prueba fallida. Haga clic en el
botón verde “Ejecutar” en la parte superior. Ahí vas. Ahora se puede ver que lo más frecuente ya no es
una prueba faltante. Aquí queremos
considerar entrada vacía. Hay un caso
aquí mismo en el que podrías tener algo extraño
pasando si
pasaste una lista vacía
a la más frecuente, entonces simplemente
recuperarías ninguno, lo cual es un incumplimiento razonable. Pero solo debes asegurarte de
que tu función no se rompa si obtienes entrada vacía. En este caso, nuestra función
no se rompe. No devuelve ninguno. Entonces, siempre y cuando declaremos
que la función no
devolverá ninguno
sobre la entrada vacía, entonces eso es perfectamente válido. Para nuestra siguiente pregunta. Este es bastante
desafiante conceptualmente. Vamos a usar
una estructura de datos o
cualquier estructura de datos para
ordenar un montón de viajes. Un montón de pasos están formateados
como origen y destino. Se puede pensar en estas como ciudades
de origen y destino. Una vez que tenemos eso, queremos
calcular la ruta completa. Queremos encontrar la posición inicial
real
y la posición final real o definitiva. Se puede suponer por
ahora que
sólo hay un camino y que
hay un camino tan completo. Eso quiere decir que no
hay brechas. Nunca termines en alguna
posición aleatoria en el medio con un montón de pasos no relacionados
y no hay ciclos. Nunca pasarás de
uno a dos de nuevo a uno. Si vas de uno a dos, siempre se
procederá a tres, cuatro, así sucesivamente, así sucesivamente. Tu objetivo es imprimir
la secuencia de pasos en orden del primero al último. Aquí tenemos un montón de pasos. Pasamos de tres a dos, uno a tres, y dos a cinco. Tu objetivo es averiguar cuál es
la secuencia correcta
de pasos. Aquí aquí la
secuencia correcta es de uno a tres, luego tres a dos,
luego dos a cinco. Pausa el video aquí, mira qué estructuras de datos quieres usar y cómo las usarías. Aquí está la solución.
Conceptualmente, lo que vamos a hacer es primero averiguar cuál es la posición de
partida definitiva. Para ello,
vamos a crear un conjunto de Hashmaps. Estos Hashmaps mapearán desde el destino
hasta el origen. Entonces lo que
haremos es
partir de cualquier destino arbitrario. Desde ese destino
comprobaremos, ¿está la fuente en el HashMap? ¿ La fuente actual es
otro destino de pasos? Si es así, entonces vamos a ese paso destino y fuente, y tú sigues haciendo esto. Digamos por ejemplo, partimos de dos y luego decimos, ¿hay tres en nuestro mapeo? Lo es, tres está en nuestro mapeo. Busquemos la fuente
correspondiente. Uno, ¿está uno en nuestro mapeo? No, no está en nuestro mapeo. Entonces eso significa que uno es la posición de partida definitiva. Eso es lo que vamos a hacer. Vamos a crear un
mapeo desde el destino hasta el origen.. Entonces
vamos a seguir atravesándolo hasta llegar
a la fuente definitiva. Una vez que hayas llegado ahí,
ese es el primer paso. Hemos conseguido la fuente
definitiva. Ahora necesitamos
imprimir realmente esta serie de pasos. Tenemos que ir hacia atrás,
tenemos que partir de la fuente y seguir atravesando. Empezaremos de uno,
iremos a tres, luego buscaremos tres. Vemos tres, luego vamos a dos. Buscamos dos, dos está aquí.
Entoncesseguimos haciendo eso. Sigues atravesando en dirección
hacia adelante. Necesitas un conjunto de Hashmaps que te
den la dirección inversa. Entonces necesitas
configurar HashMap que te
dé la dirección hacia adelante. Eso lo vamos a hacer.
Voya crear dos Hashmaps. Un HashMap siempre enlaza
de destino a origen. Uno siempre enlaza de
origen a destino, así que ese es nuestro algoritmo. Ahora ¿cuál es el tiempo de ejecución y complejidad de la
memoria
Pausael video aquí. Aquí está la respuesta.
Nuestracomplejidad de memoria es lineal en el
número de pasos, ya que por cada
paso la agregamos a ambos Hashmaps o a
ambos diccionarios. Ahora para nuestra
complejidad de tiempo de ejecución, lo mismo. Es lineal en el número
de pasos porque tenemos que
acceder a cada uno de
estos pasos al menos una vez, y afortunadamente
para nosotros solo una vez. Sabiendo eso, ahora escribamos realmente la
función, el código. Pausa el video aquí
y prueba el código. Ahora vamos a cubrir la solución. Aquí vamos a inicializar dos Hashmaps o
dos diccionarios. Uno va a estar adelante, uno va a estar al revés. Por cada
par de origen y destino en nuestros pasos, vamos a poblar
ambos. El mapeo hacia adelante irá
de origen a destino. El mapeo hacia atrás irá
de destino a origen. Ahora que hemos poblado
ambas asignaciones, recorremos desde
cualquier fuente
arbitraria hasta
la fuente definitiva. Si bien la fuente está en retroceso, y esto supongo que no está un
poco claro, pero aquí solo lo
dejaré claro. Aquí vamos a tener fuente es
igual al primer paso, y luego será
el primer paso fuente. Mientras la fuente está al revés
seguiremos atravesando. Una vez hecho este bucle while, source ya no está en
el mapeo hacia atrás, eso significa que source es
la fuente definitiva, el primer lugar al que
fuimos. Entonces, siempre y cuando source esté en el diccionario forward o en el forward mapping,
entonces lo imprimiremos. Aquí vamos a usar cadenas
f en Python. Puedes imprimir esto como
quieras y luego
atravesaremos por esta vía. Mientras nuestra fuente esté
en el mapeo hacia adelante, accederemos a ese elemento en el mapeo hacia adelante
para su destino. Eso es más o menos. Ahora vamos a ejecutar esta función
y asegurarnos de que pasamos esta función, obtener ruta de las pruebas. Ahí vamos, solo
tenemos un conjunto de pruebas
fallidas que están
en otra función, así que hemos
superado con éxito este ejercicio. No hablemos de
esta pregunta de reto. Esta pregunta también es
bastante difícil, así que solo vamos a
hablar de ello algorítmicamente, en realidad no
vamos a codificarla. De nuevo, sí he escrito
soluciones para ti, sin embargo, simplemente no vamos a
hablar del código aquí. He anotado cada línea en las soluciones para
que puedas atravesarla y
entenderla y la parte más importante aquí,
sin embargo, es el algoritmo. Para este problema, vamos a hacer
un diccionario con un tamaño máximo que opere como efectivo menos recientemente usado. En este diccionario,
cada vez que insertes, actualices o accedas a una clave, eso cuenta como usar esa clave, y si el diccionario tiene más claves que el tamaño máximo, caerás la menos
recientemente llave usada. Veamos un ejemplo de esto. Digamos que tengo este
nuevo diccionario e inserto el Valor
1 con la clave a, así que solo
veremos las claves aquí, los valores no
importan demasiado. Hemos insertado un valor para la clave y luego insertamos
un valor para la clave b. En este punto, b es el valor usado más recientemente y 1 es el valor menos utilizado
recientemente. Sin embargo, aquí accedo a a. ahora a se convierte en el valor usado más
recientemente , aquí lo hemos intercambiado. Uno corresponde a a, por lo que a es el usado más recientemente y el otro valor se utiliza
menos recientemente. Ahora asignamos un nuevo valor a la clave c y
notarás que en este punto, b era el valor menos
usado recientemente aquí mismo, así que b se cae y ahora
solo nos queda a y c. En este diccionario en particular, el tamaño máximo era de dos. Ahora, así es como realmente vimos caer
una de las llaves. Tenga en cuenta que
cada vez que acceda, actualice o inserte
un valor para una clave que cuente como acceder
o usar ese valor, y cada vez que
inserte si excede el tamaño máximo, pierdes el menos
recientemente valor usado. Sabiendo todo esto,
pensemos ahora en cómo diseñar
esto algorítmicamente. Pausa el video aquí y mira si puedes llegar
a un algoritmo. Aquí está la solución. Para implementar realmente
este caché, lo que vamos a hacer es mantener en realidad una lista doblemente enlazada. Antes de hablar de
una lista enlazada, una lista enlazada mantiene un
enlace a su siguiente enlace, por lo que se vería
algo así. Tendrías uno que vincula
a dos, enlaces a tres. No obstante, una lista doblemente enlazada en realidad incluye
ambas direcciones, tres sabe que su valor
anterior es dos, dos sabe que su valor
anterior es uno. La razón por la que quieres
esta lista doblemente enlazada es porque queremos que
la lista enlazada realice un
seguimiento del orden entre todos nuestros datos y
este pedido
nos dirá que el más recientemente utilizado y los valores menos
utilizados recientemente son. Afortunadamente con una lista enlazada, es muy fácil
insertar un valor y eliminar un
valor a la vez. Ambas son operaciones de
tiempo constante. Tenga en cuenta que esto no es
cierto para una matriz. En una matriz, si
quisieras moverte, digamos tres.
Digamosque tuvimos esto. Digamos que teníamos 1, 2, 3, 4, 5 y digamos que cinco es ahora el valor usado más
recientemente. Tu nueva lista tendría que
ser 5, 1, 2, 3, 4. Con una lista doblemente enlazada, esta es una operación de
tiempo constante, todo lo que haces es reasignar las conexiones como
ya hablamos antes. Sin embargo, para una matriz, tendrías que
copiar realmente la posición de 1-2, 2-3, 3-4, 4-5, y luego copiar
cinco al principio. Tendrías que hacer n copias, n operaciones
para reordenar esta lista. Sin embargo, con una lista
doblemente enlazada, no
tienes que
hacer nada de eso. Es una operación de tiempo constante. Es por eso que queremos una lista
doblemente enlazada para combinar con nuestro mapeo o un HashMap para implementar esta caché de uso
menos reciente. Sabiendo que queremos
una lista doblemente enlazada, ¿cómo la vamos a usar
realmente? Hablemos de las dos
funciones que realmente necesitamos. Tenemos dos funciones diferentes. En realidad no voy a desarrollar
completamente estas funciones, pero voy a agregar algo de
pseudo código aquí solo para que
sepas cómo sería la estructura general del código. Aquí, tendríamos
la capacidad de obtener un artículo y
también tendríamos otra función aquí que nos daría la
posibilidad de establecer un ítem. La idea básica aquí es que debajo
de ambas funciones, actualizaríamos la clave,
diríamos algo así como, hacer la clave más reciente, y
luego lo mismo aquí. También haremos la clave más reciente, y eso es prácticamente todo
para la lógica de alto nivel. La mayor parte del
meollo habría ocurrido aquí. En la
función make most recent aquí mismo, realidad
harías
toda la reasignación necesaria tanto para
eliminar un elemento de la lista enlazada como para
luego reinsertarlo desde
el principio y eso es. Esta es la
solución conceptual a este problema. Usarías una lista
doblemente enlazada y también usarás un mapa. Esto parece bastante complejo, no
voy a codificar, al
menos no aquí en la lección. Ya escribí
las soluciones y las soluciones
estarán disponibles para usted con código completamente
anotado. Sin embargo, la parte más importante de esta pregunta fue que se le
ocurrió usar la lista
doblemente enlazada. Habrá bastantes
preguntas como esta en tus entrevistas
donde tienes que
idear alguna
combinación novedosa de diferentes estructuras de datos para
lograr tus objetivos. En este caso particular, queríamos una caché usada menos
recientemente, y queremos que
sea muy eficiente, uso de esta lista doblemente enlazada nos
permite mantener esta
función eficiente. Eso nos lleva a nuestra segunda
parte de la pregunta. ¿ Cuál es el tiempo de ejecución y complejidad
de la
memoria de nuestro algoritmo? En particular, ¿cuál es el tiempo de ejecución de su complejidad de
memoria de insertar y luego
acceder realmente a un valor? Pausa el video aquí,
y aquí está la solución. Obtener el valor
es bastante sencillo. Obtener el valor en sí, solo acceder a algún valor en un HashMap es todo de uno,
es tiempo constante. Pero la verdadera pregunta es, ¿cuánto tiempo se tarda en
actualizar el valor más reciente? Porque eso implica
quitar e
insertar de nuevo en una lista
doblemente enlazada. Bueno, afortunadamente, la inserción y eliminación de una
lista enlazada es tiempo constante. Dado eso, sabemos
que este algoritmo, esta estructura de datos es tiempo
constante para
acceder. Eso es genial. Hemos mantenido
la eficiencia de un HashMap y ahora ¿qué
pasa con la asignación? ¿ Qué están actualizando este HashMap? Bueno, afortunadamente, ese
también sigue siendo tiempo constante. Es tiempo constante para actualizar
un HashMap en sí y otra vez, para hacer que ese
par clave y valor sea el más reciente. Esa operación en sí
es de nuevo tiempo constante, tal como ya
hablamos antes. Debido a que esa operación de
tiempo constante, hacer algo
lo más reciente es simplemente insertar y eliminar
de una lista doblemente enlazada. Todo esto para decir, se nos ocurrió una buena combinación de estructuras de datos para
mantener constante el tiempo, inserción y el acceso
para una estructura de datos. Eso es lo más eficiente
que puedas conseguir. Supongo que la conclusión
aquí es que conocer las
estructuras de datos correctas realmente puede significar una diferencia de orden de
magnitud,
una diferencia de orden de crecimiento
entre una implementación que es
eficiente e ineficientes. En este caso, usar
lista doblemente enlazada es lo que nos consiguió una eficiencia y esta es una habilidad
útil para entrevistas, tal vez menos para en el trabajo, pero si tuvieras un sistema de
producción masivo, si tuvieras un aplicación
crítica del sistema que estaba usando estructuras de
datos ineficientes, entonces tendría
la oportunidad de
crear un impacto masivo en el
negocio. Eso es todo para este ejercicio. Nuevamente, para acceder a todas estas diapositivas gruesas
a todas las soluciones, asegúrese de acceder al sitio web
del curso. Finalmente, con eso
concluye la lección de práctica de mapeos de
barra de HashMap .
11. Árboles: anchura vs. profundidad: En esta lección, discutiremos una manera de almacenar datos
jerárquicamente. Una estructura de datos llamada árbol. Vamos a explicar cómo funciona un árbol, cómo atravesar un árbol, cómo organizar un árbol, qué significa O (logn) tiempo. Finalmente,
discutiremos los pros y los contras de esta nueva estructura de datos. Empecemos por lo que es un árbol. Un árbol consiste en un nodo raíz. Ese nodo raíz tiene
dos nodos hijos. Cada uno de esos nodos tiene entonces
dos nodos hijos más cada uno. Esta estructura es
lo que llamamos un árbol. De hecho, debido a que cada
nodo tiene dos hijos, lo
llamamos un árbol binario. Digamos que quieres buscar un valor o queremos
modificar este árbol, necesitamos saber
cómo atravesar un árbol. Aquí hay dos
formas diferentes de lograrlo. El primer método se llama
Breadth First Traversal, o BFS para abreviar. En BFS, atravesamos los nodos izquierda a derecha nivel por nivel. Primero accedemos a tres. Terminamos el primer nivel, así que pasemos
al siguiente nivel. Entonces accedemos al 7, luego al 2, hemos terminado
el segundo nivel. Entonces pasemos
al último nivel. Accedemos a cero, uno, nueve y ocho. Hemos terminado el último nivel, así que terminamos con BFS. Nuestra segunda forma de
atravesar este árbol se llama Depth-First Traversal, o DFS para abreviar. Aquí accedemos desde
el nodo raíz, tres, también accedemos a siete. Seguimos atravesando más profundo, así accedemos a dos. Ahora que hemos llegado a un callejón sin salida, volvemos a siete, y exploramos lo más
profundamente posible. Entonces accedemos a uno. De nuevo, hemos llegado a un callejón sin salida. Entonces volvemos a siete,
volvemos a tres, y otra vez, exploramos lo más
profundamente posible. Accedemos a dos y luego a nueve.
Hemosllegado a un callejón sin salida. Así que vuelve a dos y
finalmente accede a ocho. Y esas son las dos
formas de atravesar un árbol, primera en la anchura o
la primera en profundidad. Ahora vamos a explicar una manera de
organizar los datos en un árbol. Esto se llama el árbol de búsqueda
binaria. Observe que hemos
reorganizado los valores. En particular, hemos
arreglado en ellos para que el niño izquierdo sea siempre
menor que el padre. Por ejemplo, tres aquí es menos de cinco y dos
es menos de tres. También hemos arreglado
estos valores para que el niño adecuado sea siempre
mayor que el padre. Por ejemplo, ocho es
mayor que cinco. Entonces el niño adecuado siempre es mayor y el
niño izquierdo siempre es menor. Esta estructura ordenada nos
permite
gestionar los datos de manera muy eficiente. Digamos que queremos
insertar datos en el árbol. Aquí, queremos insertar seis. Para ello, empieza desde
el nodo raíz cinco. A partir de aquí
buscaremos iterativamente un hogar para seis. Ya que seis es mayor que cinco, sabemos que seis deben
pertenecer a la derecha. Ahora tenemos el valor ocho. Ya que seis es menos de ocho, sabemos que seis deben
pertenecer a la izquierda. Aquí no hay nodo, así que este es ahora el hogar de seis. Esto concluye el algoritmo
de inserción. Digamos que la profundidad
del árbol es d, entonces este algoritmo toma
hasta d operaciones. Como resultado, la inserción
toma O de d tiempo para ejecutarse. Para resumir, la inserción
toma O (d) tiempo. Veamos ahora cómo funciona
la eliminación. Digamos que estamos eliminando
seis que se muestran en rojo. Bueno, eso es bastante sencillo. Simplemente elimine ese nodo y
el puntero de su padre. No obstante, digamos que
borramos de la
mitad del árbol. En particular,
queremos eliminar cinco. Intentemos lo que hicimos la última
vez, solo bajemos cinco. Sin embargo, ahora hay
un agujero en el árbol. Podemos usar cualquiera de los
niños para llenar
el vacío, tres u ocho. Aquí, usaremos al niño ocho
adecuado. Entonces, cambia ocho hacia arriba. No obstante, ahora hay una brecha
donde solían estar ocho. Para ser consistentes, usaremos el hijo correcto de
ocho, nueve. Nuevamente, turno nueve hacia arriba. Ahora hay un todo donde
solían estar nueve , pero está bien. no hay niños. Así que simplemente podemos eliminar
el puntero extra. Al igual que con el algoritmo
anterior. Este algoritmo toma
hasta d operaciones. Así que la eliminación toma O de d tiempo. Para resumir la inserción
y eliminación para un árbol de búsqueda binaria
ambos toman O de d tiempo. Nuestro objetivo es
buscar el valor seis. Partimos del nodo raíz
cinco, al igual que con la inserción, comparamos nuestro valor deseado seis con el nodo actual cinco. Seis es mayor que
cinco, así que vamos a la derecha. Ahora accedemos a ocho. Comparamos, seis es
menos de ocho, así que vamos a la izquierda. Ahora accedemos a
seis, seis es el valor que
estamos buscando. Entonces ya terminamos de buscar.
Estealgoritmo puede tomar hasta d operaciones. Entonces la búsqueda es O de
d. para resumir, un
árbol de búsqueda binario presenta O de d modificación y acceso. Tenga en cuenta que en un árbol
no existe tal cosa como
recuperar directamente el octavo nodo, porque no hay un
orden global de nodos, y no se sabe dónde está alguno
de los nodos en la memoria. Como resultado, no hay análisis de tiempo de ejecución de
fetch. Esto concluye nuestro
análisis de árboles. No obstante, tenemos una más que hacer. Nos gustaría traducir
estos tiempos de ejecución. Todos nuestros tiempos de ejecución se
expresan en función de la profundidad del árbol o d. Visualizado, aquí hay un árbol y aquí está
la profundidad del árbol. En este caso tenemos
una profundidad de cuatro. Nos gustaría expresar
estos tiempos de ejecución en términos de n, el número de nodos, en este caso hay 15 nodos. Esto se debe a que los
tiempos de ejecución para todas nuestras estructuras de datos anteriores se expresaron en términos de n, el número de ítems. Como resultado, también deberíamos expresar nuestros nuevos tiempos de ejecución en
n para
asegurarnos de que estos tiempos de ejecución sean
comparables. Aquí está el mismo árbol. Tratemos de entender
la relación entre d y n. Consideremos
la primera capa. Esta es la Profundidad 1 con un nodo. Considera las dos primeras capas. Esta es la Profundidad 2
con tres nodos. Las tres primeras capas, esta es Profundidad 3
con siete nodos. Considera todas las capas. Esto es Profundidad 4 con 15 nodos. Puede ser difícil
notar un patrón. Entonces, en lugar de contar
el número de nodos, voy a contar el número
de nodos más uno. Ahora bien, si miras los números en rojo,
¿ves un patrón? Como habrás notado,
el número de rojos, número de nodos se duplica aproximadamente. Como resultado, podemos
afirmar que n es aproximadamente dos
a la potencia de d. Ahora tenemos una
relación matemática entre d y n. Como queremos conectar
d a nuestras
complejidades de tiempo de ejecución, vamos a resolver para d.
Para resolver para d, primero
reescribiremos
la ecuación, luego aplicaremos logaritmos
a ambos lados. Recuerda que con los registros, podemos mover el exponente d fuera del registro
como coeficiente. Entonces simplemente ignoramos
el registro constante dos. Así que ahora obtenemos ese registro de n es aproximadamente d. Ahora
podemos enchufar. Anteriormente teníamos estos
tiempos de ejecución
expresos en términos de d. enchufar
d es igual a logn. Ahora obtenemos O de log n para todas las modificaciones y tiempos de ejecución de
acceso. Usando este análisis,
discutamos ahora los pros y
los contras de los árboles de búsqueda
binarios. Los árboles de búsqueda binarios en algunos tienen tiempos de ejecución
impresionantes,
solo O (logn). En la práctica, O de log n está muy cerca de o de
un tiempo constante. Por diseño, los árboles de
búsqueda binarios son ideales para secuencias aleatorias. Cuanto más uniformemente
extendido, mejor. Sin embargo, los árboles de
búsqueda binarios son los peores para
los datos secuenciales, y he aquí por qué. Digamos que tengo una secuencia
de números del 0-10. Primero creamos el nodo raíz 0, luego respondimos uno, luego dos, luego tres, luego cuatro, luego cinco. La lista continúa,
y como puedes ver, básicamente
tenemos
una línea recta en lugar de un árbol de búsqueda
binario relleno. Esto significa que ahora la
profundidad ya no es log n, sino que la profundidad es exactamente igual al
número de nodos. Es decir, todos nuestros algoritmos ahora toman O de n o tiempo lineal. Entonces, en resumen, los árboles de búsqueda
binarios son realmente ineficientes
para los datos secuenciales. En resumen, hemos
discutido qué es un árbol, primer ancho versus
primer recorrido de profundidad, qué es un árbol de búsqueda binario, qué significa la O del tiempo log n, y algunos pros y contras
de los árboles de búsqueda binarios. Para obtener una copia de estas
diapositivas y recursos, asegúrese de consultar
el sitio web del curso. Veamos ahora estas
estructuras de datos en acción. En la siguiente lección,
practicaremos uso e implementación de
estas estructuras de datos, abordando nuestros dos
objetivos de aprendizaje para este curso.
12. Práctica de árboles: Bienvenido a la
lección de práctica final de este curso. En esta lección, vamos
a practicar con árboles, en particular con búsqueda de amplitud
versus profundidad primero. Sigamos adelante y
comencemos aquí. Al igual que antes, navega a
alvinwan.com/datastructures101/trees. En ese enlace, verás
algo como esto. Reenvíe el proyecto
para obtener su propia copia, haga clic en el nombre del proyecto, haga clic en los puntos suspensivos y haga clic en tenedor. Te sugiero colocar tu ventana de
Skillshare y responder lado a lado para que puedas
codificar mientras estoy codificando. Entonces deberías ver una
pantalla igual a esta, seguir
adelante y desplazarte hacia
abajo y llegarás
al primer ejercicio aquí mismo llamado bfs o búsqueda en
amplitud. Entonces, un consejo antes de
comenzar es memorizar cómo realizar la búsqueda en amplitud primero
y profundidad primero, abreviada aquí como bfs y dfs, porque
siempre será la misma. En este
caso particular, no estamos usando una técnica
llamada recursión. Entonces sin recursión, la forma de
hacer bfs y dfs siempre
se ve así. Sabiendo eso,
intentemos ahora implementar la búsqueda a
lo ancho primero. Así es como se ve un
recorrido de búsqueda en
primer lugar en la anchura de un árbol. Aquí tenemos un
árbol, 1, 2, 3, 4. Déjame ir e ilustrar
cómo es esto. Aquí tendrías uno, y entonces
tendrías un hijo
aquí mismo que serían dos, y luego tendrías otro hijo
ahí mismo, serían tres. Entonces también tendrás
un árbol como este. Así es como se ve ese
árbol. Tendrías básicamente
uno de la raíz, es niño izquierdo
va a ser dos, y luego el hijo izquierdo de dos
va a ser tres. Entonces este es el hijo
adecuado de uno. Así es como se ve el
árbol. Sabiendo que así es como se ve ese
árbol, aquí está el aspecto del recorrido de
búsqueda primero en lo ancho. recorrido en amplitud primero nos
dará uno primero, y luego nos dará dos, y luego cuatro, y luego tres. Está atravesando y
también se le llama recorrido de
orden de nivel, así que aquí básicamente estamos
bajando niveles a la vez, 1, 2, 4, 3. Si hubiéramos tenido aquí abajo
cinco por ejemplo, entonces tendríamos 1, 2, 4, 3, 5 y así sucesivamente y así sucesivamente. Eso es lo que parece. Sabiendo que esto es
ahora un
recorrido en primer plano, aquí hay una pista. Pausa el video ahora y prueba este problema por tu cuenta
si no quieres la pista. El indicio es que necesitarás
usar una de las
estructuras de datos de las que
hablamos antes. En particular,
tendrás que usar una pila o una cola para poder hacer esto. Sigue adelante y pausa
el video aquí e intenta diseñar el algoritmo para un recorrido a lo
ancho primero. Ahora aquí está la solución. La solución va a
implicar el uso de una cola. Lo que vamos a
hacer es en esta cola, vamos a empezar
añadiendo la raíz. Una vez que hayamos agregado la raíz, entonces lo que vamos
a hacer es tomar la raíz y poner en cola a todos los
hijos para esa raíz. Una vez que hayamos hecho eso, entonces vamos a quitar la cola. Deshacer cola
nos va a dar el primer artículo aquí. Entonces vamos a poner en cola a
todos sus hijos. Eso va a ser
tres y cualquier otra cosa es hijo de dos. En realidad, una forma
de
hacerlo sería incluir una visualización. Aquí tenemos uno,
vamos a quitar de cola uno, y vamos a sumar todos
sus hijos dos y cuatro. Entonces vamos a descolar dos y luego vamos a
encola de sus hijos, que son apenas tres. Entonces digamos que tal vez
haya otro, digamos que hay cinco. Aquí tendríamos
tres y cinco. Entonces finalmente tomaríamos nuestro. Entonces cuatro pondríamos cola a
todos sus hijos, que no es nada
y así sucesivamente para adelante. La idea es que te darás cuenta de que el orden de descolar
fue de 1, 2, 4. Entonces después de eso, van
a ser tres y cinco, que es exactamente lo que es bfs. La cola nos da exactamente un recorrido de
árbol a lo ancho primero. Sabiendo eso,
veamos ahora cuál es el tiempo de ejecución
en la complejidad de la memoria.
Pausael video aquí. Aquí está la solución.
Eltiempo de ejecución y la complejidad
de la
memoria van a ser ambos o de n. Puede que estés
pensando, ¿qué hay n aquí? Bueno, n es el número de nodos. Eso es importante. Antes teníamos este caso donde definíamos
una variable por nuestra cuenta. Definimos una variable
como un número de valores
únicos que
se están ingresando. En este caso, por
defecto para un árbol, esa variable n
va a ser el número
de nodos en el árbol. También podrías redefinirlo, podrías redefinir la
n como la altura
del árbol o puedes definirlo como otra cosa pero normalmente, n es número de
nodos en el árbol. Sabiendo que, cuando reportas tu
complejidad de memoria de tiempo de ejecución para un árbol, debes informar en términos
del número de nodos, que para nosotros
va a ser o de n, porque tienes que
atravesar cada nodo, eso es lo que es un
recorrido de amplitud primero y segundo, tienes que agregar todos
estos nodos a tu cola. En algún momento, en realidad, lo siento, mentí un poco, tu cola nunca
superará el
ancho máximo del árbol. Veremos qué
significa ancho más adelante, pero solo diremos
por ahora que o de n es la complejidad de la memoria. Podemos jugar con
ese matiz más adelante, voy a explicar por qué, hay una mejor respuesta. Por ahora, sigue adelante y pausa el video e
intenta codificar esto para arriba. Escribamos la solución. Aquí vamos a
definir una cola y el primer valor de la cola
va a ser la raíz en realidad. Si bien hay algo
en la cola, vamos a quitar de la cola. Entonces vamos a extender, así que vamos a
poner en cola en realidad. Por cada rama en
las ramas del árbol, vamos a poner en cola, así que cola encola la rama. Entonces finalmente,
imprimiremos el valor actual. Esto nos dará un recorrido a lo
ancho primero. Comprobemos ahora para ver si
esto pasa nuestras pruebas. Da clic en el botón Ejecutar, verde en la
parte superior y podrás ver ahora que bfs ya no está en nuestra
lista de funciones fallidas. Has
superado satisfactoriamente esta prueba. Pasemos a
la siguiente pregunta. En realidad, antes
de pasar a la siguiente pregunta, un consejo es que
siempre debes usar nuevo, aguanta. Uno de los consejos es
que siempre debes usar una cola para el recorrido a lo
ancho primero. Eso lo viste en el ejemplo aquí. Ya viste cómo usarlo.
Tenganesto en mente. Esto prácticamente siempre
será como
implementas bfs sin recursión. Hablaremos de recursión
en un curso futuro. Sabiendo eso,
implementemos ahora la búsqueda en profundidad primero. búsqueda en profundidad primero se
verá como la siguiente. Digamos que teníamos este árbol y este árbol es más o menos
la misma estructura. realidad es una
estructura un poco diferente. Déjame sacar esto por ti. Aquí tenemos la raíz 1. Es niño dejado va a ser 2 y el hijo izquierdo de 2
va a ser 3. Entonces no hay
otros niños aquí. El hijo adecuado de 1 va
a ser 4, aquí mismo. Entonces el hijo izquierdo de 4
va a ser 5. Aquí vamos a golpear. Una cosa a tener en cuenta es
que sigo diciendo que el
niño izquierdo y derecho es porque generalmente los problemas del árbol se construyen alrededor de tu
árbol binario donde
solo tienes un hijo izquierdo
y uno derecho. La forma en que hemos
implementado un árbol aquí, podemos tener ramas ilimitadas. No estás limitado
a una izquierda y a una derecha. Técnicamente hablando, 5
no es un hijo izquierdo de 4, 5 es la única rama de 4. Sólo he estado diciendo de izquierda
a derecha por costumbre, pero en realidad no importa. El punto es que así es como se ve aproximadamente
el árbol. Tenemos 1 en la raíz, son niños son 2 y 4 y
luego el único hijo de 2 es 3, hijo único de
4 es 5. Sabiendo eso, un recorrido de
profundidad primero o primero ir por uno
de estos caminos. En la forma en que lo hemos
implementado, 1 primero bajará por
este camino por aquí
4 y luego
bajaremos hasta 5 antes volver a subir y
explorar otros caminos. Así será el
recorrido de profundidad primero. Explorará todo el
camino hasta llegar a una hoja. Nuevamente, una hoja es un nodo en el árbol que no tiene
hijos, ni ramas. Primero explorará todo el
camino hacia abajo y luego
volverá a subir y comenzará a explorar otras avenidas. Así es como se ve el
recorrido de profundidad primero. Ves aquí abajo va a ir 1, 4, 5, y luego volverá a subir
y explorar 2 y luego 3. Eso es un recorrido de profundidad primero. Tratemos de llegar
a un algoritmo. Pausa el video aquí.
Aquíestá la solución. Para el recorrido de profundidad primero, bueno, anteriormente
usamos una cola
para el recorrido de primer ancho. Para el recorrido de profundidad primero,
vamos a usar una pila. El stack va a operar de
manera muy similar. Vamos a seguir agregando
elementos a la pila, y vamos a seguir
apareciendo de la pila. Esto es lo que
va a parecer. Cuando empiezo con 1,
vamos a hacer pop 1 y luego vamos a
agregar sus hijos 2 y 4. Ahora que tenemos 2 y 4, vamos a hacer pop el
último elemento que es 4. Entonces vamos a sumar
sus hijos, que es 5. Entonces vamos a hacer pop 5. Se puede ver a dónde va esto. Hasta el momento hemos pasado
por 1, 4, 5. Una vez que hayamos terminado con 5,
vamos a hacer pop 2. Esto nos dará nuestro
primer recorrido de profundidad usando una pila. Sabiendo que ese es
el algoritmo, vamos a
hablar de la complejidad de la memoria y del tiempo de ejecución. ¿ Cuál es el tiempo de ejecución
en la complejidad de la memoria? Pausa el video aquí,
y aquí está la respuesta. La complejidad de la memoria
aquí va a ser lineal en el
número de nodos. Para la complejidad de la memoria,
vamos
a digerir la complejidad de la memoria. Para la complejidad computacional,
vamos a tener complejidad computacional
lineal porque tenemos que iterar a través de
todos estos nodos. Misma advertencia que mencioné antes para la complejidad de la memoria, realidad no
es lineal
en el número de nodos, pero hablaremos de
eso más adelante. Ahora sigamos adelante e
intentemos codificar esta función. Pausa el video aquí
y dale una oportunidad. Sigamos adelante y
codifiquemos esta función. Aquí en nuestro recorrido de
profundidad primero, vamos a comenzar
inicializando una pila. Esta pila va a tener
nuestro nodo raíz dentro de ella. Entonces vamos a iterar. Siempre y cuando tengamos
algo en la pila, luego
saltaremos de la pila. Entonces por cada
rama de nuestro nodo actual. Para la sucursal en las ramas
superiores actuales, luego
empujaremos esa rama en nuestra pila y luego imprimiremos
nuestro valor actual. Eso es más o menos para
nuestro recorrido de profundidad primero. Sigamos adelante y
comprobemos que esto funciona. Pulsa el
botón verde “Ejecutar” en la parte superior. Ahí tienes, dfs
ya no está en nuestra lista
de fallas por lo que hemos
superado con éxito las pruebas dfs. El consejo aquí es que deberías usar una pila para el recorrido de
profundidad primero. Pasemos ahora a
la siguiente pregunta. Por cada
nodo en el árbol, agregue un nuevo atributo llamado parent que apunte
a su padre. Aquí vamos a usar bfs
o dfs para la asignación de padres. Este atributo parent
apuntará al
padre del nodo en el árbol. Sigamos adelante y
dibujemos de nuevo ese árbol. Digamos que tenemos
este árbol aquí mismo. Tenemos aquí 1, y es hijo único es 2
y 2 tiene dos hijos, que son 3 y 4. Se va a quedar
algo así y no hay otras
ramas, solo estos tipos. Ahora que tienes esto, realidad
vamos a
poblar a los padres. Íbamos a
implementar esto para que cada árbol aquí
apunte de nuevo a su padre. Por lo que 2 apuntará a 1, 3 apuntará a 2,
4 apuntará a 2. Sabiendo eso, pensemos esto y diseñemos un algoritmo para ello. Pausa el video aquí. Hablemos de la solución. Para esta pregunta,
en realidad no importa si usas bfs o dfs. En cualquier caso,
puedes hacer que esto funcione. Básicamente el algoritmo
va a ser, vamos a realizar algún recorrido y
si miras arriba, en realidad
iteramos sobre todos los hijos o todas las ramas para
su actual nodo. Mientras haces
esa iteración, actualizarás esta rama para que apunte de nuevo al
nodo actual, que es el padre. Realmente no importa
qué recorrido uses. Ese es el algoritmo
y de hecho, esa es más o menos
la solución de código. Sigue adelante y considera ahora, ¿cuál es la complejidad de la memoria y el tiempo de
ejecución?
Pausael video aquí. Al igual que antes, porque estamos usando DFS y BFS de
manera efectiva, el tiempo de ejecución y la complejidad
computacional son los mismos que antes. La complejidad computacional es O de N y la complejidad de la memoria,
digamos por ahora, es básicamente O de
N. Sabiendo eso, ahora sigamos adelante
y
probemos el código. Pausa el video aquí y
dale una oportunidad primero. Ahora repasemos la solución. Voy a hacer trampa un poco. En realidad solo voy a copiar y pegar de la función
anterior, que ya realizaba DFS. Sigamos adelante y
peguemos eso abajo. Voy a quitar
esta declaración print y luego voy a asignar branch.parent es
igual a actual. Eso es. Sigamos adelante y comprobemos que
esta función es correcta. Vamos a darle al botón
verde “Ejecutar” en la parte superior. Ahí vamos. Podemos ver ahora que poblar padres ya no está en
la lista de pruebas reprobables. Hemos
superado con éxito todas estas pruebas. Como dije antes, BFS, DFS, siempre y cuando memorices
esa implementación, lo vas a ver
muy a menudo. Al menos sin recursión, así es como
va a verse,
así que asegúrate de conocer
esa implementación. Consejo de antes, siempre considere entrada
vacía también. En este caso particular, si nuestro árbol estuviera vacío, entonces nuestra función fallaría porque aquí vamos a hacer pop, vamos a ponernos
actuales, actuales va a ser ninguno, y luego vamos para intentar acceder
a las ramas de la misma. De nuevo, para todas tus entrevistas y para
todas tus preguntas,
asegúrate de considerar qué
harías con entrada vacía. En este caso en particular, deberíamos haber dicho
si el árbol no es ninguno, entonces simplemente
no haremos nada, solo regresaremos. Eso es importante
tener en cuenta. Pasemos a
la siguiente pregunta. Aquí vamos a usar
BFS o DFS para calcular el valor máximo en un árbol
extremadamente ancho pero poco profundo. Sigamos adelante y
consideremos lo siguiente. Considera lo que esto significa para
tu elección de recorrido. Cuál es la máxima complejidad
espacial de la búsqueda en primer plano o de la
búsqueda en profundidad. Adelante. Esto en realidad está relacionado con el matiz del que
hablamos antes. Pausa el video aquí y considera primero antes de
poder considerar el algoritmo. En realidad como estás
considerando el algoritmo. [ RUIDO] Aquí está la
siguiente pregunta. Vamos a obtener el valor
máximo de un árbol extremadamente ancho
pero poco profundo. La parte importante de esta
pregunta es considerar lo que un árbol extremadamente ancho
pero poco profundo le hace a tu algoritmo. ¿ Por qué es importante esto?
¿Qué significa esto para su elección
de recorrido? Hablamos antes de un
matiz sutil sobre la complejidad
de espacio o memoria de tu modo de recorrido. Esta pregunta está realmente
afinando en eso, para tratar de entender lo que significa ese matiz
para tu algoritmo. Pausa el video aquí y mira
si puedes resolverlo. Cuál es la diferencia entre árbol
extremadamente ancho pero
poco profundo versus un árbol profundo pero muy estrecho para BFS o
DFS. Pausa el video aquí. Aquí está la respuesta. Para un árbol extremadamente ancho
pero poco profundo, vas a querer usar DFS. La razón es porque BFS
o el recorrido de amplitud primero, es la complejidad del espacio o el número máximo de
elementos en la cola o pila o cualquier
colección que esté usando va a ser
el ancho del árbol. Mientras que para la
búsqueda de profundidad primero o DFS, el espacio máximo que
usaremos es equivalente a
la profundidad del árbol. Si tengo un árbol
extremadamente poco profundo, entonces querrás que DFS minimice
tu consumo de espacio. Porque si tienes
un árbol muy poco profundo, tendrás una
colección muy corta a considerar. Sabiendo eso, sigamos adelante y diseñemos el algoritmo
para obtener el máximo valor. Pausa el video aquí e
intenta diseñar el algoritmo. Aquí está la solución.
Parael algoritmo, simplemente
vamos a tomar el valor máximo cada vez
que atraviese un nodo. Cada vez que atraviese un nodo, compare el valor de ese nodo con
un valor global más grande. Si tu
valor actual es mayor, entonces simplemente reemplázalo. Esto es muy similar
al ejemplo de frecuencia máxima que hablamos antes. En este caso, estamos
considerando el valor máximo. Ahora que hemos considerado
el algoritmo, hemos considerado el
modo de recorrido, pausar el video aquí
y ver si puedes llegar a la complejidad de memoria y
tiempo de ejecución. Aquí está la respuesta. Para la complejidad del tiempo de
ejecución ,
nuevamente, es lineal en
el número de nodos, es O de N. Para la
complejidad de la memoria, bueno, ya
hablamos de esto antes, que es exactamente la razón por la que
elegimos DFS para este problema. Tu complejidad espacial o complejidad de
memoria va
a ser la profundidad del árbol. Esto no es exactamente O de N.
También está, al menos por ahora, no está claro exactamente cuál sería la
profundidad del árbol. Sólo vamos a asignarle
una nueva variable. Vamos a decir D es
la profundidad del árbol, así que nuestro algoritmo es o de d. Ahora intentemos
codificarlo. Pausa el video aquí. Ahora como tenemos una implementación
DFS, nuevamente
voy a ser perezoso. Sólo voy a
copiarlo y pegarlo. Vamos a desplazarnos hacia arriba aquí, y luego vamos a copiar
esta implementación de DFS, y luego vamos
a desplazarnos hacia abajo y vamos a pegarla. Ahora que tenemos esta implementación de
DFS, en realidad
vamos a
eliminar la declaración print. Como dijimos antes, por cada nodo
que
consideremos, vamos a actualizar
el valor máximo. Digamos que el valor máximo al principio es
solo el valor de raíces. Entonces, cuando exploramos
cada nodo, vamos a tomar
el máximo entre el valor actual y
el mayor valor. Por último, vamos a
devolver el valor máximo. Intentemos ejecutar esta
función y
asegurarnos de que pasa todas las pruebas. Adelante y pulsa el botón
verde “Correr” en la parte superior. Ahí vamos. Podemos ver ahora que obtener máximo ya no está en
la lista de pruebas faltas. Pasemos ahora a
la siguiente pregunta. Vamos a combinar estructuras de
datos para calcular el ancho del árbol. Veamos ahora cuál es
el ancho del árbol. El ancho del árbol es el número
máximo de nodos en cualquier profundidad dada o
cualquier nivel dado. Volvamos a garabear este árbol. Aquí tenemos uno y
uno tiene un hijo, que son solo dos, y
dos tienen dos hijos, que son tres y cuatro. Aquí tenemos tres, y luego aquí tenemos cuatro. Así es como se ve este
árbol. El ancho de este
árbol entonces es dos porque este nivel tiene
dos elementos en él. Ahora bien, si tuviéramos
otro aquí, digamos que teníamos cinco, y luego tuvimos
otro, seis, digamos, entonces el
ancho de este árbol
sería tres porque
tienes como máximo tres
enun solo nivel. Sabiendo eso, sigamos
adelante y actualicemos. Vamos a discutir el algoritmo. Continúa y pausa el video
aquí y mira cómo
calcularías el ancho de este árbol. Aquí hay una solución. Afortunadamente para nosotros,
tenemos un modo de recorrido que nos
facilita mucho el cálculo de la profundidad, que va a ser recorrido de
orden de nivel o BFS. Hay dos formas en las
que puedes hacer esto. Una es que puedes usar
otra estructura de datos para realizar un seguimiento de cuántos nodos
hay a cierta profundidad. El segundo es el BFS
modificado para
que atraviese un
nivel a la vez y realice un
seguimiento básicamente de
cuándo inicia el siguiente nivel. Esas
son tus dos opciones. Esos son dos algoritmos
diferentes. Vamos a implementar
el primero donde vamos a usar
otra estructura de datos, cuando se usa un mapeo. Ahora que ya has
hablado de esto, hablemos del tiempo de ejecución
y la complejidad de la memoria. Pausa el video aquí y mira
si puedes averiguarlo. Aquí está la respuesta. Para la complejidad del tiempo de ejecución,
ambos algoritmos, independientemente de
cuál haya elegido, van a ser O de N, donde n es el número de nodos. Ambas
complejidades computacionales son lineales en el número de nodos. Ahora bien, si decides perseguir
múltiples estructuras de datos, donde guardas un mapeo
desde la profundidad hasta los recuentos, esa va a ser una complejidad espacial
adicional de O de D en la profundidad. Vas a ser lineal
en la profundidad porque estás almacenando un valor por
cada profundidad. Sin embargo, si usa
el algoritmo
donde modifica BFS en su lugar, entonces su algoritmo
sería O de ancho. Ambos algoritmos son al
menos O de ancho, porque la línea base,
así es como funciona el BFS original. Sin embargo, el algoritmo que usa
adicionalmente un
HashMap para almacenar ese mapeo de profundidad
a conteo va a ser O de ancho más O de profundidad. Vamos a implementar
el menos eficiente, lo que parecería al revés
pero ya he implementado el eficiente ya
en la solución así podrás
comprobarlo si quieres ver la
implementación más eficiente. Pero por ahora, voy a implementar la
menos eficiente. Sigue adelante y pausa
el video aquí y mira si puedes llegar
tú mismo al código. Aquí está nuestra solución.
Sigamosadelante y escribamos. Vamos a usar nuestra estructura de datos
favorita aquí. Vamos a usar un diccionario
predeterminado. Vamos a comenzar
inicializando una cola. Cada elemento en esta
cola va a ser una profundidad del nodo actual además del nodo
en sí, porque necesitamos hacer un seguimiento de la profundidad para saber cuál cuenta en nuestro contador de
anchuras para actualizar realmente. Aquí está nuestro contador, anchos, y va a inicializar
todos los anchos a cero. Si bien tenemos algo
en la cola, vamos a eliminar la cola
y luego vamos a actualizar el
diccionario de anchos incrementando
ese valor en uno. Finalmente, para cada rama, vamos a poner en cola la profundidad incrementada en
uno y el propio nodo. Cada vez que vayas de
padre a hijo, incrementaremos
la profundidad en uno. Por último, devolveremos el ancho
máximo que veamos. Esto nos dará
el ancho máximo y todos los anchos
que contabilizamos. Ahora ejecutemos esto
y asegurémonos de que pase todas nuestras
pruebas. Ahí vamos. La falta de salida significa que
todas nuestras pruebas de doc pasaron. Finalmente has terminado todos los ejercicios
para esta lección. Para todas estas diapositivas, soluciones
completas y más ejercicios de
práctica, no dejes de visitar este sitio web. Eso es todo para nuestra
práctica para árboles, anchura versus profundidad
versus recorrido. Has visto un montón
de problemas aquí. También has visto un montón
de problemas en las clases de práctica
anteriores. Espero que estos hayan
sido muy útiles. Pasemos ahora a
nuestra última lección donde concluiremos todo esto.
13. Conclusión: Enhorabuena por
terminar el curso. Hemos cubierto un montón de
temas, órdenes de crecimiento, pilas y colas, listas enlazadas, mapas
hash, árboles. Ese fue un curso bastante
difícil con un montón de contenido y algunas preguntas
realmente brutales. Has terminado 20
ejercicios en profundidad, 20 consejos para entrevistas y practicas el
método de tres pasos para resolver acertijos una y
otra y otra vez. Eso fue mucho contenido y las diapositivas de resumen son
excelentes herramientas para memorizar. Sin embargo, la comida para llevar más
importante es en realidad el proceso
de tres pasos. respecta a las entrevistas, esa es la clave. Aquí está el proceso de tres pasos una vez: diseñar
algoritmos sin código, informes de complejidad de tiempo de ejecución y
memoria, y finalmente, codificar el algoritmo. Ahora para solidificar realmente su comprensión durante tres
días después del curso, diseñe una
pregunta de estructura de datos cada día. También te animo a que publiques tu pregunta en la sección de
discusión. Solo necesitas dormir un poco entre
pensar en estructuras de datos. No tiene que ser el mejor trabajo de
tu vida. Cualquier duda servirá y la
publicará en la sección de discusión. Tengo muchas ganas de
verlas y eso es todo. Fantástico trabajo. Este es el
comienzo de la preparación de tu entrevista y estás
en una base sólida. Echa un vistazo a mi Skillshare para
más cursos sobre ciencia de datos, aprendizaje
automático y otros conceptos
importantes de programación. Para más preparación de entrevistas, sígueme en Skillshare para
obtener más actualizaciones, ya que cubriremos acertijos de
codificación
más utilizados y trucos específicos de entrevistas. Enhorabuena una vez
más llegar al final del curso
y hasta la próxima vez.
Alvin Wan, Research Scientist
