Estructuras de datos fundamentales, técnicas algorítmicas y algoritmos de grafos para la preparación de entrevistas técnicas y un curso universitario equivalente.
Cada habilidad que el diagnóstico puede evaluar, agrupada como en el mapa. Abre cualquier tema para empezar una lección.
Fundamentos
Análisis de complejidad: Describir cómo crece el tiempo de ejecución o la memoria de un algoritmo a medida que crece el tamaño de la entrada, usando notación O grande.
Recursión: Una función que resuelve un problema llamándose a sí misma sobre una versión más pequeña del mismo problema.
Estructuras lineales
Arreglos: Un bloque de memoria contiguo de diseño fijo, donde cualquier índice se alcanza en tiempo constante.
Listas enlazadas: Nodos dispersos en memoria, cada uno apuntando al siguiente, cambiando indexación rápida por inserción barata.
Pilas y colas: Dos ordenamientos de acceso restringido, último en entrar primero en salir y primero en entrar primero en salir.
Búsqueda y ordenamiento
Búsqueda binaria: Reducir a la mitad repetidamente un rango ordenado para encontrar un objetivo en tiempo logarítmico.
Ordenamientos elementales por comparación: Los ordenamientos simples de O(n al cuadrado), burbuja, inserción, selección, que comparan e intercambian pares de elementos.
Ordenamiento por divide y vencerás: Los ordenamientos de divide y vencerás, ordenamiento por mezcla y quicksort, que superan al O(n al cuadrado) dividiendo el problema.
Ordenamiento sin comparación: Ordenar explotando una estructura conocida en los propios valores, por conteo o radix, en lugar de comparaciones.
Hashing
Tablas hash: Mapear claves a espacios de un arreglo mediante una función hash para una búsqueda casi en tiempo constante.
Árboles
Árboles binarios: Una estructura jerárquica donde cada nodo tiene como máximo dos hijos.
Árboles binarios de búsqueda: Un árbol binario mantenido ordenado de modo que el subárbol izquierdo de cada nodo es menor y el derecho es mayor.
Árboles de búsqueda balanceados: Un ABB que se reequilibra activamente, rotaciones AVL o coloración rojo-negro, para que nunca degenere en una línea.
Montículos y colas de prioridad: Una estructura en forma de árbol que siempre mantiene fácil de encontrar el elemento más pequeño, o el más grande.
Tries: Un árbol donde cada camino desde la raíz deletrea un prefijo, construido para búsqueda rápida de cadenas.
Grafos
Representaciones de grafos: Almacenar los vértices y aristas de un grafo como una matriz de adyacencia o una lista de adyacencia.
Recorrido de grafos (BFS y DFS): Visitar cada vértice alcanzable, ya sea nivel por nivel (BFS) o profundizando primero (DFS).
Ordenamiento topológico: Ordenar los vértices de un grafo dirigido acíclico para que cada arista apunte hacia adelante.
Union-find: Una estructura que rastrea qué elementos pertenecen al mismo grupo y fusiona grupos rápidamente.
Algoritmo de Dijkstra: Encontrar el camino más barato desde un vértice hacia todos los demás cuando ningún peso de arista es negativo.
Algoritmo de Bellman-Ford: Encontrar caminos más cortos que sigue funcionando cuando algunos pesos de arista son negativos, a costa de la velocidad.
Árboles de segmentos: Un árbol binario sobre un arreglo que responde consultas de rango, como suma o mínimo, en tiempo logarítmico.
Árboles de Fenwick: Una estructura compacta basada en arreglos que responde consultas de suma de prefijos en tiempo logarítmico.
Técnicas
Divide y vencerás: Dividir un problema en copias independientes más pequeñas de sí mismo, resolver cada una, y luego combinar.
Algoritmos voraces: Tomar la mejor decisión local en cada paso confiando en que lleva a la mejor respuesta global.
Programación dinámica: Resolver un problema guardando en caché las respuestas a subproblemas superpuestos en lugar de recalcularlas.
Backtracking: Probar una elección, recurrir, y deshacerla si no lleva a ningún lado, para explorar todas las posibilidades.
Dos punteros: Recorrer dos índices a través de una secuencia a la vez para evitar un bucle anidado.
Ventana deslizante: Agrandar y reducir un rango contiguo sobre una secuencia para seguir una condición en curso en una sola pasada.
Manipulación de bits: Usar directamente los bits binarios individuales de un número, por ejemplo para representar un conjunto pequeño o activar una bandera.
Cadenas de texto
Algoritmos de coincidencia de cadenas: Encontrar todas las apariciones de un patrón dentro de un texto más grande más rápido que revisando cada posición.