coding interview university
1.0.0
Originalmente creé esto como una breve lista de temas de estudio para convertirse en ingeniero de software, pero creció hasta convertirse en la lista grande que ve hoy. Después de completar este plan de estudios, ¡me contrataron como ingeniero de desarrollo de software en Amazon! Probablemente no tendrás que estudiar tanto como yo. De todos modos, todo lo que necesitas está aquí.
Estudié entre 8 y 12 horas al día durante varios meses. Esta es mi historia: Por qué estudié a tiempo completo durante 8 meses para una entrevista en Google
Tenga en cuenta: no necesitará estudiar tanto como yo. Perdí mucho tiempo en cosas que no necesitaba saber. Más información al respecto está a continuación. Te ayudaré a llegar allí sin perder tu valioso tiempo.
Los elementos enumerados aquí lo prepararán bien para una entrevista técnica en casi cualquier empresa de software, incluidos los gigantes: Amazon, Facebook, Google y Microsoft.
¡Mucha suerte para ti!
Bahasa Indonesia
búlgaro
Español
Alemán
Japonés (日本語)
marathi
Polaco
Português Brasileiro
ruso
Tiếng Việt - Vietnamita
Urdu - اردو
uzbeko
বাংলা - bengalí
ខ្មែរ - jemer
简体中文
繁體中文
africaans
árabe
Francés
Griego
italiano
Coreano (한국어)
malayalam
Persa - Farsi
telugu
tailandés
turco
Ucrania
עברית
हिन्दी
¡Conviértase en patrocinador y apoye a Coding Interview University!
Este es mi plan de estudio de varios meses para convertirme en ingeniero de software para una gran empresa.
Requerido:
Un poco de experiencia con codificación (variables, bucles, métodos/funciones, etc.)
Paciencia
Tiempo
Tenga en cuenta que este es un plan de estudio para ingeniería de software , no para ingeniería frontend o desarrollo full-stack. Realmente existen excelentes hojas de ruta y cursos para esas trayectorias profesionales en otros lugares (consulte https://roadmap.sh/ para obtener más información).
Hay mucho que aprender en un programa universitario de Ciencias de la Computación, pero solo saber alrededor del 75% es suficiente para una entrevista, así que eso es lo que cubro aquí. Para un programa autodidacta de informática completo, los recursos para mi plan de estudio se han incluido en la hoja de ruta de informática de Kamran Ahmed: https://roadmap.sh/computer-science
¿Qué es?
¿Por qué usarlo?
como usarlo
No sientas que no eres lo suficientemente inteligente
Una nota sobre los recursos de vídeo
Elija un lenguaje de programación
Libros sobre estructuras de datos y algoritmos.
Libros de preparación para entrevistas
No cometas mis errores
Lo que no verás cubierto
El plan diario
Práctica de preguntas de codificación
Problemas de codificación
Complejidad algorítmica / Big-O / Análisis asintótico
Estructuras de datos
matrices
Listas enlazadas
Pila
Cola
tabla hash
Más conocimiento
búsqueda binaria
Operaciones bit a bit
Árboles
Árboles - Introducción
Árboles de búsqueda binaria: BST
Montón / Cola de prioridad / Montón binario
árboles de búsqueda equilibrados (concepto general, no detalles)
recorridos: preorden, inorden, postorden, BFS, DFS
Clasificación
selección
inserción
ordenar en montón
clasificación rápida
fusionar
Graficos
dirigido
no dirigido
matriz de adyacencia
lista de adyacencia
recorridos: BFS, DFS
Aún más conocimiento
recursividad
Programación dinámica
Patrones de diseño
Combinatoria (n elija k) y probabilidad
Algoritmos NP, NP-completo y de aproximación
Cómo las computadoras procesan un programa
cachés
Procesos e hilos
Pruebas
Búsqueda y manipulación de cadenas.
Intenta
Números de coma flotante
Unicódigo
Endianidad
Redes
Revisión final
Actualiza tu currículum
Encontrar el trabajo
Proceso de entrevista y preparación general para la entrevista
Estar pensando para cuando llegue la entrevista.
Tener preguntas para el entrevistador.
Una vez que tengas el trabajo
---------------- Todo lo que se encuentra debajo de este punto es opcional ----------------
Libros adicionales
Diseño de sistemas, escalabilidad, manejo de datos (si tiene más de 4 años de experiencia)
Aprendizaje adicional
árboles AVL
árboles extendidos
Árboles rojos/negros
2-3 árboles de búsqueda
2-3-4 árboles (también conocidos como 2-4 árboles)
Árboles N-arios (K-ary, M-ary)
Árboles B
Compiladores
Emacs y vi(m)
Herramientas de línea de comandos de Unix
Teoría de la información
Código de paridad y Hamming
entropía
Criptografía
Compresión
Seguridad informática
Recolección de basura
Programación paralela
Sistemas de mensajería, serialización y colas
A*
Transformada rápida de Fourier
Filtro de floración
HyperLogLog
Hashing sensible a la localidad
van Emde Boas Árboles
Estructuras de datos aumentadas
Árboles de búsqueda equilibrados
kD árboles
Saltar listas
Flujos de red
Conjuntos disjuntos y búsqueda de unión
Matemáticas para un procesamiento rápido
Tragar
Programación lineal
Geometría, casco convexo.
matematicas discretas
Detalles adicionales sobre algunos temas
Serie de vídeos
Cursos de informática
Papeles
Si quieres trabajar como ingeniero de software para una gran empresa, estas son las cosas que debes saber.
Si no pudo obtener una licenciatura en informática, como lo hice yo, esto lo pondrá al día y le salvará cuatro años de su vida.
Cuando comencé este proyecto, no sabía distinguir una pila de un montón, no sabía nada de Big-O, ni nada sobre árboles, ni cómo recorrer un gráfico. Si tuviera que codificar un algoritmo de clasificación, puedo decirles que habría sido terrible. Todas las estructuras de datos que había usado alguna vez estaban integradas en el lenguaje y no sabía en absoluto cómo funcionaban internamente. Nunca tuve que administrar la memoria a menos que un proceso que estaba ejecutando diera un error de "memoria insuficiente" y entonces tuviera que encontrar una solución. Utilicé algunas matrices multidimensionales en mi vida y miles de matrices asociativas, pero nunca creé estructuras de datos desde cero.
Es un plan largo. Puede que te lleve meses. Si ya está familiarizado con gran parte de esto, le llevará mucho menos tiempo.
⬆ volver arriba
Todo lo que aparece a continuación es un esquema y debes abordar los elementos en orden de arriba a abajo.
Estoy usando el tipo de rebajas especial de GitHub, que incluye listas de tareas para realizar un seguimiento del progreso.
Más sobre las rebajas con sabor a GitHub
En esta página, haga clic en el botón Código cerca de la parte superior, luego haga clic en "Descargar ZIP". Descomprima el archivo y podrá trabajar con los archivos de texto.
Si está abierto en un editor de código que comprende Markdown, verá todo bien formateado.
Crea una nueva rama para que puedas verificar elementos como este, solo coloca una x entre paréntesis: [x]
Bifurque el repositorio de GitHub: https://github.com/jwasham/coding-interview-university haciendo clic en el botón Bifurcar.
Clona en tu repositorio local:
git clone https://github.com/<YOUR_GITHUB_USERNAME>/coding-interview-university.gitcd coding-interview-university git remoto agregar ascendente https://github.com/jwasham/coding-interview-university.git git remoto set-url --push upstream DISABLE # para no enviar tu progreso personal al repositorio original
Marque todas las casillas con una X después de completar los cambios:
git commit -am "Progreso personal marcado"git pull upstream main # mantén tu bifurcación actualizada con los cambios desde el repogit push # simplemente empuja a tu bifurcación
⬆ volver arriba
Los ingenieros de software exitosos son inteligentes, pero muchos tienen la inseguridad de no ser lo suficientemente inteligentes.
Los siguientes vídeos pueden ayudarte a superar esta inseguridad:
El mito del genio programador
Es peligroso ir solo: luchar contra los monstruos invisibles en la tecnología
⬆ volver arriba
Algunos videos están disponibles solo al inscribirse en una clase de Coursera o EdX. Estos se llaman MOOC. A veces las clases no están en sesión por lo que tienes que esperar un par de meses, por lo que no tienes acceso.
Sería fantástico reemplazar los recursos de los cursos en línea con fuentes públicas gratuitas y siempre disponibles, como videos de YouTube (preferiblemente conferencias universitarias), para que ustedes puedan estudiarlos en cualquier momento, no solo cuando un curso en línea específico esté en sesión.
⬆ volver arriba
Deberá elegir un lenguaje de programación para las entrevistas de codificación que realice, pero también deberá encontrar un lenguaje que pueda utilizar para estudiar conceptos de informática.
Preferiblemente el idioma sería el mismo, de modo que sólo sea necesario dominar uno.
Cuando hice el plan de estudio, utilicé 2 lenguajes para la mayor parte: C y Python.
C: Nivel muy bajo. Le permite lidiar con punteros y asignación/desasignación de memoria, para que sienta las estructuras de datos y los algoritmos en sus huesos. En lenguajes de nivel superior como Python o Java, estos están ocultos para usted. En el trabajo diario, eso es fantástico, pero cuando aprendes cómo se construyen estas estructuras de datos de bajo nivel, es fantástico sentirte cerca del metal.
Este es un libro breve, pero le dará un gran manejo del lenguaje C y si lo practica un poco, rápidamente lo dominará. Comprender C le ayuda a comprender cómo funcionan los programas y la memoria.
No es necesario profundizar mucho en el libro (ni siquiera terminarlo). Simplemente llegue a donde se sienta cómodo leyendo y escribiendo en C.
C está en todas partes. Verás ejemplos en libros, conferencias, videos, en todas partes mientras estudias.
El lenguaje de programación C, segunda edición
Python: moderno y muy expresivo, lo aprendí porque es súper útil y también me permite escribir menos código en una entrevista.
Esta es mi preferencia. Haces lo que quieres, por supuesto.
Puede que no lo necesites, pero aquí tienes algunos sitios para aprender un nuevo idioma:
ejercicio
Guerras de códigos
Tierra hacker
Temas de escalador (Java, C++)
Retos Comunitarios Programiz PRO)
Puede utilizar un lenguaje con el que se sienta cómodo para realizar la parte de codificación de la entrevista, pero para las grandes empresas, estas son opciones sólidas:
C++
Java
Pitón
También puedes usarlos, pero lee primero. Puede haber advertencias:
javascript
Rubí
Aquí hay un artículo que escribí sobre cómo elegir un idioma para la entrevista: Elija un idioma para la entrevista de codificación. Este es el artículo original en el que se basó mi publicación: Elegir un lenguaje de programación para entrevistas
Debes sentirte muy cómodo con el idioma y tener conocimientos.
Lea más sobre las opciones:
Elija el idioma adecuado para su entrevista de codificación
Vea recursos específicos del idioma aquí
⬆ volver arriba
Este libro formará su base para la informática.
Simplemente elija uno, en un idioma con el que se sienta cómodo. Estarás leyendo y codificando mucho.
Algoritmos en C, partes 1 a 5 (paquete), tercera edición
Fundamentos, estructuras de datos, algoritmos de clasificación, búsqueda y gráficos
Estructuras de datos y algoritmos en Python
por Goodrich, Tamassia, Goldwasser
Me encantó este libro. Cubrió todo y más.
código pitónico
mi brillante informe de libro: https://startupnextdoor.com/book-report-data-structures-and-algorithms-in-python/
Tu elección:
Goodrich, Tamassia, Goldwasser
Estructuras de datos y algoritmos en Java
Sedgewick y Wayne:
Algoritmos I
Algoritmos II
Algoritmos
Curso gratuito de Coursera que cubre el libro (¡impartido por los autores!):
Tu elección:
Goodrich, Tamassia y Mount
Estructuras de datos y algoritmos en C++, segunda edición
Sedgewick y Wayne
Algoritmos en C++, Partes 1-4: Fundamentos, estructura de datos, clasificación, búsqueda
Algoritmos en C++ Parte 5: Algoritmos de gráficos
⬆ volver arriba
No es necesario comprar muchos de estos. Sinceramente, "descifrar la entrevista de codificación" probablemente sea suficiente, pero compré más para tener más práctica. Pero siempre hago demasiado.
Compré ambos. Me dieron mucha práctica.
Programación de entrevistas expuestas: Codificando su camino a través de la entrevista, cuarta edición
Respuestas en C++ y Java
Este es un buen calentamiento para la entrevista de Cracking the Coding
No demasiado difícil. La mayoría de los problemas pueden ser más fáciles de lo que verá en una entrevista (según lo que he leído)
Descifrando la entrevista de codificación, sexta edición
respuestas en java
Elige uno:
Elementos de entrevistas de programación (versión C++)
Elementos de programación de entrevistas en Python
Elementos de entrevistas de programación (versión Java): proyecto complementario: resumen de métodos y casos de prueba para cada problema del libro
⬆ volver arriba
Esta lista creció a lo largo de muchos meses y sí, se salió de control.
Aquí hay algunos errores que cometí para que tengas una mejor experiencia. Y ahorrarás meses de tiempo.
Vi horas de videos y tomé muchas notas, y meses después había muchas cosas que no recordaba. Pasé 3 días revisando mis notas y haciendo tarjetas didácticas para poder revisarlas. No necesitaba todo ese conocimiento.
Por favor, lee para no cometer mis errores:
Conservación de conocimientos en informática.
Para resolver el problema, creé un pequeño sitio de tarjetas donde podía agregar tarjetas de 2 tipos: generales y de código. Cada tarjeta tiene un formato diferente. Creé un sitio web para dispositivos móviles, para poder revisar en mi teléfono o tableta, dondequiera que esté.
Haz el tuyo gratis:
Repositorio del sitio de tarjetas didácticas
NO RECOMIENDO usar mis flashcards. Hay demasiadas y la mayoría son trivialidades que no necesitas.
Pero si no quieres escucharme aquí tienes:
Mi base de datos de tarjetas flash (1200 tarjetas):
Mi base de datos de tarjetas flash (extrema - 1800 tarjetas):
Tenga en cuenta que me excedí y tengo tarjetas que cubren todo, desde lenguaje ensamblador y trivia de Python hasta aprendizaje automático y estadísticas. Es demasiado para lo que se requiere.
Nota sobre las tarjetas didácticas: la primera vez que reconozcas que sabes la respuesta, no la marques como conocida. Tienes que ver la misma tarjeta y responderla varias veces correctamente antes de darte cuenta. La repetición hará que ese conocimiento se arraigue más profundamente en tu cerebro.
Una alternativa al uso de mi sitio de tarjetas didácticas es Anki, que me han recomendado numerosas veces. Utiliza un sistema de repetición para ayudarte a recordar. Es fácil de usar, está disponible en todas las plataformas y tiene un sistema de sincronización en la nube. Cuesta $25 en iOS pero es gratis en otras plataformas.
Mi base de datos de tarjetas flash en formato Anki: https://ankiweb.net/shared/info/25173560 (gracias @xiewenya).
Algunos estudiantes han mencionado problemas de formato con espacios en blanco que se pueden solucionar haciendo lo siguiente: abra la plataforma, edite la tarjeta, haga clic en las tarjetas, seleccione el botón de opción "estilo" y agregue el miembro "espacio en blanco: pre;" a la clase de tarjeta.
ESTO ES MUY IMPORTANTE.
Comience a codificar preguntas de entrevistas mientras aprende estructuras de datos y algoritmos.
Necesitas aplicar lo que estás aprendiendo para resolver problemas o lo olvidarás. Cometí este error.
Una vez que haya aprendido un tema y se sienta algo cómodo con él, por ejemplo, listas vinculadas :
Abra uno de los libros de entrevistas de codificación (o sitios web sobre problemas de codificación, que se enumeran a continuación)
Haga 2 o 3 preguntas sobre listas vinculadas.
Pase al siguiente tema de aprendizaje.
Luego, regrese y resuelva otros 2 o 3 problemas de listas vinculadas.
Haga esto con cada nuevo tema que aprenda.
Sigue resolviendo problemas mientras aprendes todo esto, no después.
No te contratan por el conocimiento, sino por cómo aplicas el conocimiento.
Hay muchos recursos para esto, que se enumeran a continuación. Sigue adelante.
Hay muchas distracciones que pueden consumir un tiempo valioso. El enfoque y la concentración son difíciles. Pon algo de música sin letra y podrás concentrarte bastante bien.
⬆ volver arriba
Estas son tecnologías predominantes pero no forman parte de este plan de estudio:
JavaScript
HTML, CSS y otras tecnologías front-end
SQL
⬆ volver arriba
Este curso abarca muchos temas. Probablemente cada uno le llevará unos días, o tal vez incluso una semana o más. Depende de tu horario.
Cada día, tome el siguiente tema de la lista, mire algunos videos sobre ese tema y luego escriba una implementación de esa estructura de datos o algoritmo en el idioma que eligió para este curso.
Puedes ver mi código aquí:
do
C++
Pitón
No es necesario memorizar todos los algoritmos. Sólo necesita poder entenderlo lo suficiente como para poder escribir su propia implementación.
⬆ volver arriba
Why is this here? I'm not ready to interview.
Entonces regresa y lee esto.
Por qué necesitas practicar resolviendo problemas de programación:
Reconocimiento de problemas y dónde encajan las estructuras de datos y algoritmos correctos
Reunir requisitos para el problema.
Hablar del problema como lo hará en la entrevista.
Codificar en una pizarra o papel, no en una computadora
Proponer complejidad de tiempo y espacio para sus soluciones (consulte Big-O a continuación)
Probando sus soluciones
Hay una excelente introducción para la resolución de problemas metódica y comunicativa en una entrevista. También obtendrás esto de los libros de entrevistas de programación, pero encontré esto excelente: Lienzo de diseño de algoritmos
Escriba código en una pizarra o papel, no en una computadora. Pruebe con algunas entradas de muestra. Luego escríbalo y pruébelo en una computadora.
Si no tienes una pizarra en casa, compra un bloc de dibujo grande en una tienda de arte. Puedes sentarte en el sofá y practicar. Esta es mi "pizarra de sofá". Agregué el bolígrafo en la foto solo para escalar. Si usas un bolígrafo, desearás poder borrar. Se ensucia rápidamente. Yo uso lápiz y borrador.
La práctica de preguntas de codificación no se trata de memorizar respuestas a problemas de programación.
⬆ volver arriba
No olvide sus libros clave de entrevistas sobre codificación aquí.
Resolviendo problemas:
Cómo encontrar una solución
Cómo analizar una declaración de problema de Topcoder
Vídeos de preguntas de entrevistas de codificación:
Merezco (88 videos)
Tushar Roy (5 listas de reproducción)
Súper para tutoriales de soluciones a problemas
Nick White - Soluciones LeetCode (187 vídeos)
Buenas explicaciones de la solución y el código.
Puedes ver varios en poco tiempo.
FisherCoder - Soluciones LeetCode
Sitios de desafío/práctica:
Código Leet
Mi sitio favorito de problemas de codificación. Vale la pena el dinero de la suscripción durante los 1 o 2 meses que probablemente se estará preparando.
Vea los videos de Nick White y FisherCoder arriba para ver tutoriales sobre el código.
HackerRank
Codificador superior
Fuerzas de código
Codilidad
Frikis para frikis
AlgoExperto
Creado por ingenieros de Google, este también es un excelente recurso para perfeccionar sus habilidades.
Proyecto Euler
Muy centrado en las matemáticas y no muy adecuado para codificar entrevistas.
⬆ volver arriba
Muy bien, basta de hablar, ¡aprendamos!
¡Pero no olvides resolver los problemas de codificación anteriores mientras aprendes!
No hay nada que implementar aquí, ¡solo estás viendo videos y tomando notas! ¡Hurra!
Hay muchos vídeos aquí. Simplemente mira lo suficiente hasta que lo entiendas. Siempre puedes volver y revisar.
No te preocupes si no entiendes todas las matemáticas detrás de esto.
Sólo necesitas entender cómo expresar la complejidad de un algoritmo en términos de Big-O.
Harvard CS50 - Notación asintótica (vídeo)
Big O Notations (tutorial rápido general) (vídeo)
Notación Big O (y Omega y Theta): la mejor explicación matemática (vídeo)
Skiena (vídeo)
UC Berkeley Big O (vídeo)
Análisis Amortizado (video)
TopCoder (incluye relaciones de recurrencia y teorema maestro):
Complejidad computacional: Sección 1
Complejidad Computacional: Sección 2
hoja de trucos
[Reseña] Análisis de algoritmos (lista de reproducción) en 18 minutos (vídeo)
Bueno, ya es suficiente.
Cuando revisa "Descifrar la entrevista de codificación", hay un capítulo sobre esto y al final hay una prueba para ver si puede identificar la complejidad del tiempo de ejecución de diferentes algoritmos. Es una súper revisión y prueba.
⬆ volver arriba
contiguos en la memoria, por lo que la proximidad ayuda al rendimiento
espacio necesario = (capacidad de la matriz, que es >= n) * tamaño del elemento, pero incluso si es 2n, sigue siendo O(n)
O(1) para agregar/eliminar al final (amortizado para asignaciones de más espacio), indexar o actualizar
O(n) para insertar/eliminar en otro lugar
Practique la codificación usando matrices y punteros, y matemáticas de punteros para saltar a un índice en lugar de utilizar la indexación.
Nueva matriz de datos sin procesar con memoria asignada
tamaño() - número de artículos
capacidad() - número de elementos que puede contener
está_vacío()
at(index): devuelve el elemento en un índice determinado, explota si el índice está fuera de límites
empujar (artículo)
insertar(índice, elemento): inserta un elemento en el índice, desplaza el valor de ese índice y los elementos finales hacia la derecha
anteponer (elemento): puede usar insertar arriba en el índice 0
pop() - eliminar del final, valor de retorno
eliminar (índice): elimina el elemento en el índice, desplazando todos los elementos finales hacia la izquierda
remove(item) - busca valor y elimina el índice que lo contiene (incluso si está en varios lugares)
buscar (elemento): busca un valor y devuelve el primer índice con ese valor, -1 si no se encuentra
cambiar tamaño (nueva_capacidad) // función privada
Puede asignar una matriz int bajo el capó, pero no usar sus funciones.
comience con 16, o si el número inicial es mayor, use la potencia de 2 - 16, 32, 64, 128
cuando alcance la capacidad, cambie el tamaño para duplicar el tamaño
al abrir un artículo, si el tamaño es 1/4 de la capacidad, cambie el tamaño a la mitad
Matrices CS50 Universidad de Harvard
Matrices (vídeo)
UC Berkeley CS61B: matrices lineales y multidimensión (vídeo) (comience a mirar desde 15 m 32 s)
Matrices dinámicas (vídeo)
Matrices irregulares (vídeo)
Acerca de las matrices:
Implementar un vector (matriz mutable con cambio de tamaño automático):
Tiempo
Espacio
Descripción (vídeo)
No es necesario implementar
size() - devuelve el número de elementos de datos en la lista
vacío() - bool devuelve verdadero si está vacío
value_at(index): devuelve el valor del enésimo elemento (comenzando en 0 el primero)
push_front(valor): agrega un elemento al frente de la lista
pop_front() - elimina el elemento frontal y devuelve su valor
push_back(valor): agrega un elemento al final
pop_back() - elimina el elemento final y devuelve su valor
front() - obtiene el valor del elemento frontal
back() - obtiene el valor del elemento final
insertar(índice, valor): inserta el valor en el índice, de modo que el nuevo elemento en el índice apunte al elemento actual en ese índice.
borrar(índice) - elimina el nodo en el índice dado
value_n_from_end(n): devuelve el valor del nodo en la enésima posición desde el final de la lista
inversa() - invierte la lista
remove_value(valor): elimina el primer elemento de la lista con este valor
Punteros a punteros
Listas enlazadas principales frente a matrices (vídeo)
En el mundo real, listas enlazadas frente a matrices (vídeo)
Listas enlazadas CS50 Universidad de Harvard: esto fortalece la intuición.
Listas enlazadas individualmente (vídeo)
CS 61B - Listas enlazadas 1 (vídeo)
CS 61B - Listas enlazadas 2 (vídeo)
[Revisión] Listas enlazadas en 4 minutos (vídeo)
Descripción:
Código C (video): no el video completo, solo partes sobre la estructura del nodo y la asignación de memoria
Lista enlazada frente a matrices:
Por qué deberías evitar las listas enlazadas (vídeo)
Te tengo: necesitas conocimientos de puntero a puntero: (para cuando pasas un puntero a una función que puede cambiar la dirección a la que apunta ese puntero) Esta página es solo para comprender ptr a ptr. No recomiendo este estilo de recorrido de lista. La legibilidad y la mantenibilidad se ven afectadas debido a la inteligencia.
Implementar (lo hice con puntero de cola y sin):
Lista doblemente enlazada
Pilas (vídeo)
[Revisión] Se acumula en 3 minutos (video)
No se implementará. Implementar con la matriz es trivial.
una mala implementación usando una lista enlazada donde se pone en cola al principio y se retira de la cola al final sería O(n) porque necesitaría el penúltimo elemento, lo que provocaría un recorrido completo de cada retirada de la cola.
en cola: O(1) (amortizado, lista enlazada y matriz [sondeo])
quitar de la cola: O(1) (lista y matriz vinculadas)
vacío: O(1) (lista y matriz vinculadas)
enqueue(valor): agrega un elemento al final del almacenamiento disponible
dequeue(): devuelve el valor y elimina el elemento agregado menos recientemente
vacío()
lleno()
enqueue(valor): agrega valor en una posición en la cola
dequeue(): devuelve el valor y elimina el elemento agregado menos recientemente (frente)
vacío()
Cola (vídeo)
Búfer circular/FIFO
[Reseña] Colas en 3 minutos (vídeo)
Implementar usando lista enlazada, con puntero de cola:
Implementar usando una matriz de tamaño fijo:
Costo:
hash(k, m) - m es el tamaño de la tabla hash
agregar (clave, valor): si la clave ya existe, actualiza el valor
existe (clave)
obtener (clave)
eliminar (clave)
Tablas hash principales (vídeo)
Estructuras de datos (vídeo)
Problema con la agenda telefónica (vídeo)
tablas hash distribuidas:
Cargas instantáneas y optimización del almacenamiento en Dropbox (vídeo)
Tablas hash distribuidas (vídeo)
Hashing con encadenamiento (vídeo)
Duplicación de tablas, Karp-Rabin (vídeo)
Direccionamiento abierto, hash criptográfico (vídeo)
PyCon 2010: El poderoso diccionario (vídeo)
PyCon 2017: El diccionario aún más poderoso (vídeo)
Aleatorización (avanzada): hash universal y perfecto (vídeo)
(Avanzado) Hashing perfecto (vídeo)
[Revisión] Tablas hash en 4 minutos (vídeo)
Vídeos:
Cursos en línea:
Implemento con matriz mediante palpado lineal.
⬆ volver arriba
búsqueda binaria (en una matriz ordenada de números enteros)
búsqueda binaria usando recursividad
Búsqueda binaria (vídeo)
Búsqueda binaria (vídeo)
detalle
cianotipo
[Revisión] Búsqueda binaria en 4 minutos (vídeo)
Implementar:
Entero absoluto
Intercambio
4 formas de contar bits en un byte (video)
Contar bits
Cómo contar el número de bits establecidos en un entero de 32 bits
Binario: pros y contras (por qué usamos el complemento a dos) (vídeo)
complemento a 1s
complemento a 2s
palabras
Buena introducción: manipulación de bits (vídeo)
Tutorial de programación en C 2-10: Operadores bit a bit (vídeo)
Manipulación de bits
Operación bit a bit
Bithacks
El pequeño bromista
El Bit Twiddler Interactivo
Trucos de bits (vídeo)
Operaciones de práctica
deberías conocer muchas de las potencias de 2 de (2^1 a 2^16 y 2^32)
Hoja de trucos de bits
Obtenga una muy buena comprensión de la manipulación de bits con: &, |, ^, ~, >>, <<
complemento a 2 y 1
Contar bits establecidos
Valores de intercambio:
Valor absoluto:
⬆ volver arriba
Notas de BFS:
Notas del DFS:
orden de nivel (BFS, usando cola)
complejidad del tiempo: O (n)
complejidad del espacio: mejor: O(1), peor: O(n/2)=O(n)
complejidad del tiempo: O (n)
complejidad del espacio: mejor: O(log n) - promedio. altura del árbol peor: O(n)
orden (DFS: izquierda, auto, derecha)
postorder (DFS: izquierda, derecha, yo)
preorden (DFS: yo, izquierda, derecha)
Introducción a los árboles (vídeo)
Recorrido de árboles (vídeo)
BFS (búsqueda primero en amplitud) y DFS (búsqueda primero en profundidad) (vídeo)
[Reseña] Búsqueda en amplitud en 4 minutos (vídeo)
[Revisión] Búsqueda en profundidad en 4 minutos (vídeo)
[Reseña] Tree Traversal (lista de reproducción) en 11 minutos (vídeo)
insertar // insertar valor en el árbol
get_node_count // obtiene el recuento de valores almacenados
print_values // imprime los valores en el árbol, del mínimo al máximo
eliminar_árbol
is_in_tree // devuelve verdadero si existe un valor determinado en el árbol
get_height // devuelve la altura en nodos (la altura de un solo nodo es 1)
get_min // devuelve el valor mínimo almacenado en el árbol
get_max // devuelve el valor máximo almacenado en el árbol
es_binary_search_tree
eliminar_valor
get_successor // devuelve el siguiente valor más alto en el árbol después del valor dado, -1 si no hay ninguno
Árbol de búsqueda binaria - Implementación en C/C++ (vídeo)
Implementación de BST: asignación de memoria en pila y montón (video)
Encuentre los elementos mínimo y máximo en un árbol de búsqueda binario (video)
Encuentra la altura de un árbol binario (video)
Recorrido de árbol binario: estrategias de primero en amplitud y primero en profundidad (vídeo)
Árbol binario: recorrido de orden de nivel (vídeo)
Recorrido de árbol binario: pedido anticipado, orden posterior, orden posterior (vídeo)
Comprobar si un árbol binario es un árbol binario de búsqueda o no (vídeo)
Eliminar un nodo del árbol de búsqueda binaria (vídeo)
Sucesor de orden en un árbol de búsqueda binario (vídeo)
Revisión del árbol de búsqueda binaria (vídeo)
Introducción (vídeo)
MIT (vídeo)
C/C++:
Implementar:
insertar
sift_up - necesario para insertar
get_max: devuelve el elemento máximo, sin eliminarlo
get_size() - devuelve el número de elementos almacenados
is_empty(): devuelve verdadero si el montón no contiene elementos
extract_max: devuelve el elemento máximo, eliminándolo
sift_down - necesario para extract_max
remove(x) - elimina el elemento en el índice x
heapify: crea un montón a partir de una serie de elementos, necesarios para heap_sort
heap_sort(): toma una matriz sin clasificar y la convierte en una matriz ordenada usando un montón máximo o mínimo
visualizado como un árbol, pero generalmente es lineal en el almacenamiento (matriz, lista vinculada)
Montón
Introducción (vídeo)
Árboles binarios (vídeo)
Observación sobre la altura del árbol (vídeo)
Operaciones básicas (vídeo)
Árboles binarios completos (vídeo)
Pseudocódigo (vídeo)
Heap Sort: salta al inicio (vídeo)
Ordenación del montón (vídeo)
Construyendo un montón (video)
MIT 6.006 Introducción a los algoritmos: montones binarios
CS 61B Conferencia 24: Colas prioritarias (vídeo)
Montón de compilación de tiempo lineal (montón máximo)
[Reseña] Montón (lista de reproducción) en 13 minutos (vídeo)
Implementar un montón máximo:
⬆ volver arriba
Notas:
No recomendaría ordenar una lista vinculada, pero la ordenación por combinación es factible.
Combinar orden para lista enlazada
Estabilidad del algoritmo de clasificación
Estabilidad en los algoritmos de clasificación
Estabilidad en los algoritmos de clasificación
Algoritmos de clasificación: estabilidad
sin clasificación de burbujas - es terrible - O(n^2), excepto cuando n <= 16
Implemente clasificaciones y conozca el mejor/peor caso, la complejidad promedio de cada uno:
Estabilidad en los algoritmos de clasificación ("¿Quicksort es estable?")
¿Qué algoritmos se pueden utilizar en listas vinculadas? ¿Cuál en matrices? ¿Cuál de ambos?
Para ordenar el montón, consulte la estructura de datos del montón más arriba. La clasificación del montón es excelente, pero no estable
Sedgewick - Mergesort (5 vídeos)
1. Combinar ordenación
2. Clasificación de fusión ascendente
3. Complejidad de clasificación
4. Comparadores
5. Estabilidad
Sedgewick - Clasificación rápida (4 vídeos)
1. Clasificación rápida
2. Selección
3. Claves duplicadas
4. Clasificación del sistema
Universidad de Berkeley:
CS 61B Conferencia 29: Clasificación I (vídeo)
CS 61B Conferencia 30: Clasificación II (vídeo)
CS 61B Conferencia 32: Clasificación III (vídeo)
CS 61B Conferencia 33: Clasificación V (vídeo)
CS 61B 2014-04-21: Clasificación por base (vídeo)
Clasificación de burbujas (vídeo)
Análisis de clasificación de burbujas (vídeo)
Ordenar por inserción, ordenar por combinación (vídeo)
Ordenación por inserción (vídeo)
Combinar orden (vídeo)
Clasificación rápida (vídeo)
Ordenación por selección (vídeo)
Combinar código de clasificación:
Usando la matriz de salida (C)
Usando matriz de salida (Python)
In situ (C++)
Código de clasificación rápida:
Implementación (C)
Implementación (C)
Implementación (Python)
[Revisión] Clasificación (lista de reproducción) en 18 minutos
Clasificación rápida en 4 minutos (vídeo)
Clasificación de montón en 4 minutos (vídeo)
Combinar clasificación en 3 minutos (vídeo)
Clasificación de burbujas en 2 minutos (vídeo)
Clasificación de selección en 3 minutos (vídeo)
Clasificación por inserción en 2 minutos (vídeo)
Implementar:
Mergesort: O (n log n) promedio y peor
