Algoritmos y estructuras de datos
Tengo la intención de usar este repositorio como un patio de recreo de práctica (KATA), así como un recordatorio de algunos algoritmos comunes, simples pero potentes. Donde elegante usaré transductores Clojure, que son excelentes herramientas eléctricas para procesar secuencias. Si bien este documento puede parecer exhaustivo, tengo la intención de usarlo como una lista a la que puedo volver en cualquier momento en que necesite estudiar. No he implementado todo lo que figura aquí.
Estilo de escritura
El código aquí no está formado en el estilo que usaría para la codificación profesional. Cada equipo tiene algo de cultura y opiniones sobre el estilo de código y es mejor cumplir con estas pautas comunes. Además, el código está escrito principalmente para ser leído por otras personas, o todos nosotros codificaríamos en el ensamblaje para el máximo rendimiento si tuviéramos que apuntar solo a los lectores de una máquina. El código que escribo como parte de un equipo pretende haber sido escrito por cualquier otra persona en este equipo.
El código aquí está escrito en programación litucada gracias a Emacs y Org-Mode. Significa que el código escrito en Clojure se deriva de los archivos de texto que explican el razonamiento detrás de él. Espero que haga que sea más fácil de leer.
Pitón
Preparándose para un nuevo problema
./dev-resources/new-problem.sh
--problem-path neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups
Ver --help .
Cuando se complete el script de inicialización, aparecerá un comando sugerido para las pruebas al final:
poetry run ptw -- --
src/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups.py
tests/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups_test.py
Interactuando con poesía y pytest
Por ejemplo, ver las pruebas mientras se desarrolla:
poetry run ptw
poetry run ptw -- -- --memray
poetry run ptw -- -- --benchmark-only
poetry run ptw -- -- --benchmark-skip
El pequeño baile alrededor -- -- probablemente podría evitarse, pero prefiero ser muy explícito sobre lo que corre, así que mantengo poetry como el argumento delantero más izquierdo.
Para obtener una memoria de memoria:
poetry run memray run -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4 "
poetry run python -m memray flamegraph memray-neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate.554244.bin
Para obtener un FlameGraph de CPU (u otros gráficos):
poetry run python -m cProfile -o program.prof -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4, 4 "
poetry run snakeviz program.prof
Para ejecutar puntos de referencia y obtener un resumen gráfico:
poetry run pytest --benchmark-only --benchmark-histogram
Lista de estudio
Algoritmos de clasificación
- Implementar desde cero: clasificación de burbujas, clasificación de fusión, clasificación rápida, clasificación de montón.
- Dada una matriz de enteros, encuentre el elemento más pequeño KTH usando el algoritmo de selección rápido.
- Implemente el algoritmo de clasificación de conteo para ordenar una matriz de enteros con un rango de valores conocido.
- Resuelva el problema de la "partición de tres vías" utilizando el orden rápido para ordenar eficientemente una matriz con valores duplicados.
Algoritmos de búsqueda
- Implementar desde cero: búsqueda binaria (para una matriz ordenada), búsqueda lineal.
- Dada una matriz clasificada girada, encuentre el elemento de destino utilizando la búsqueda binaria modificada.
Gráfico, árbol y algoritmos de transversal del mismo
- Implementar desde cero: búsqueda de amplitud (BFS), búsqueda de profundidad (DFS), algoritmo de Dijkstra, algoritmo de Bellman-Ford.
- Implementar diferentes representaciones: matriz de adyacencia, lista de adyacencia.
- Encuentre la ruta más corta entre dos nodos en un gráfico ponderado usando el algoritmo de Dijkstra.
- Implemente un árbol de búsqueda binario y realice operaciones básicas como inserción, eliminación y búsqueda.
- Dado un gráfico dirigido, verifique si hay una ruta entre dos nodos.
- Encuentre el número de componentes conectados en un gráfico no dirigido.
- Implemente la clasificación topológica para un gráfico acíclico dirigido (DAG).
- Encuentre el ancestro común más bajo (LCA) de dos nodos en un árbol binario.
- Dado un árbol binario, verifique si es un árbol de búsqueda binario válido (BST).
- Dado un gráfico, encuentre todos los componentes fuertemente conectados (SCC) usando el algoritmo de Kosaraju o el algoritmo de Tarjan.
- Implemente el algoritmo Floyd-Warshall para encontrar los caminos más cortos de todos los pares en un gráfico ponderado.
- Dado un árbol N-ARY, realice una transversal de orden de nivel o una transversal de profundidad (por ejemplo, pre-pedido, orden posterior).
Programación dinámica
- Comprender el concepto de romper un problema en subproblemas superpuestos más pequeños y usar memoización o tabulación.
- Resuelva el clásico problema de "fibonacci" utilizando enfoques de programación recursivos y dinámicos.
- Dado un conjunto de elementos con pesos y valores, encuentre el valor máximo que se puede obtener con un peso máximo dado usando un problema de mochila 0-1.
Algoritmos codiciosos
- Comprender problemas en los que tomar opciones localmente óptimas conduce a una solución globalmente óptima.
- Implemente una solución para el "problema de selección de actividad" donde necesita seleccionar el número máximo de actividades que no se superponen.
- Dado un conjunto de monedas con diferentes denominaciones y una cantidad, encuentre el número mínimo de monedas necesarias para hacer esa cantidad utilizando un enfoque codicioso.
Algoritmos de retroceso
- Resuelva el problema de "N-Ceaens" para colocar n reinas en un tablero de ajedrez N × N sin atacarse entre sí.
- Implemente un solucionador de Sudoku para resolver un rompecabezas de Sudoku parcialmente lleno.
Algoritmos de manipulación de cadenas
- Coincidencia de cadenas
- Inversión de cadena
- Cheques de palíndromo
- Dadas dos cadenas, verifique si uno es una permutación de la otra.
- Implemente el algoritmo "Rabin-Karp" para encontrar un patrón en un texto dado.
Algoritmos de manipulación de bits
- Operaciones bit a bit, encontrando el elemento único único en una matriz.
- Dada una matriz donde todos los números ocurren dos veces, excepto por un número, encuentre el único número único.
- Implemente una función para contar el número de bits que se establecen en 1 en un entero.
Algoritmos de división y conquistar
- Búsqueda binaria, encontrando la suma máxima de la subarray.
- Implemente el algoritmo Karatsuba para la multiplicación rápida de enteros grandes.
- Encuentre el par de puntos más cercano entre un conjunto de puntos en el espacio 2D utilizando el enfoque Divide and Conquer.
Algoritmos aleatorios
- Arrasear una matriz al azar en el lugar.
- Implemente el algoritmo "Seleccionar aleatorio" para encontrar el elemento más pequeño KTH en una matriz.
Técnica de ventana corredera
- Dada una variedad de enteros, encuentre la suma máxima de cualquier subarría contigua de tamaño k.
- Encuentre la subcadena más larga con la mayoría de los caracteres distintos en una cadena dada.
Problemas de intervalo
- Dada una lista de intervalos, fusione los intervalos superpuestos.
- Encuentre el número mínimo de salas de reuniones necesarias para programar una lista de intervalos.
Intentos
- Implemente una estructura de datos de TRIE para una búsqueda y recuperación de cadenas eficientes.
- Dada una lista de palabras, encuentre el prefijo común más largo usando un trie.
- Implemente una característica de autocompletar usando un TRIE para un conjunto dado de palabras.
- Dada una lista de palabras, encuentre todos los pares de palabras de tal manera que la concatenación forma un palíndromo.
Chava
- Implementación de funciones hash, técnicas de resolución de colisión y casos de uso.
- Implemente una tabla hash con resolución de colisión (por ejemplo, encadenamiento o direccionamiento abierto).
- Encuentre el primer personaje no repetido en una cadena usando un mapa hash.
- Implemente el algoritmo Rabin-Karp para la coincidencia de cadenas con múltiples patrones.
- Encuentre la subcadena más larga sin repetir caracteres usando un mapa hash para la frecuencia de caracteres.
Muchísimo
- Implementación de mínimas de mínima y máximo-tomas y sus aplicaciones (por ejemplo, colas prioritarias).
- Implemente un mínimo-montón o un máximo de trabajo desde cero.
- Dada una variedad de elementos, encuentre el elemento más grande de KTH utilizando un enfoque basado en el montón.
Manipulación de matriz
- Dada una matriz M × N, gírela en 90 grados en el lugar.
- Dada una matriz de 0s y 1s, encuentre el cuadrado más grande de 1s (subatriz cuadrado de tamaño máximo) y devuelva su área.
Árboles rojos negros o árboles AVL
- Implemente operaciones de inserción y eliminación para un árbol rojo-negro o un árbol AVL.
- Realice rotaciones para equilibrar un árbol de búsqueda binario desequilibrado.
Implementaciones de la estructura de datos
- Matrices y listas: Implementación de matrices, listas vinculadas y sus operaciones.
- Pilas y colas: implementación de estructuras de datos de pila y cola y sus aplicaciones.
- Mapas hash: implementación de mapas hash y comprensión de su complejidad de tiempo.
Herramientas
Los algoritmos y las estructuras de datos están expuestas por una API simple simple para una configuración más realista y para una prueba más robusta:
(Las herramientas enumeradas aquí pueden ser específicas para algunos idiomas)
