Mejora tus habilidades de algoritmos y estructura de datos

Imagen de Dynamo Primer.

Algunos de los recursos en este artículo aparecieron originalmente en uno de mis comentarios en una publicación de reddit que se hizo bastante popular. Aquí está el hilo original, y mi nueva reseña está debajo.

Fundamentos

Lo primero que necesitará si desea mejorar los algoritmos y las estructuras de datos es una base sólida. Esta base se puede aprender de varias maneras, ya sea a través de un programa de ciencias de la computación en la universidad, algunos campamentos de codificación se centran un poco en los temas a continuación, o puede aprender por su cuenta de libros, videos o conferencias en línea. Para comenzar, necesitará una comprensión básica de los siguientes temas:

Estructuras de datos

Aprenda sobre matrices, listas vinculadas, árboles binarios, tablas hash, gráficos, pilas, colas, montones y otras estructuras de datos fundamentales.

Matemáticas y Lógica

Necesitará conocer algunos conceptos matemáticos de varias áreas diferentes si desea sobresalir en algoritmos. Aprenda sobre teoría de conjuntos, máquinas de estado finito, expresiones regulares, multiplicación de matrices, operaciones bit a bit, resolución de ecuaciones lineales, conceptos combinatorios importantes como permutaciones, combinaciones, principio de casillero.

Arquitectura de Computadores

Aprenda cómo se representan los datos en una computadora, los conceptos básicos del diseño de la lógica digital, el álgebra booleana, la aritmética de la computadora, la representación de punto flotante, el diseño de caché. Pruebe y aprenda un poco sobre la programación en C y ensamblaje.

Avanzando más allá de los fundamentos

Una vez que sienta que comprende bien la mayoría de los conceptos enumerados anteriormente, es hora de comenzar a sumergirse en la parte de algoritmos. Aquí hay una lista de recursos y cosas que hice para mejorar en la escritura y comprensión de algoritmos importantes.

Páginas tomadas del Manual de diseño de algoritmos.

Big-O y tiempo de ejecución

  • Aprenda qué es Big-O y cómo analizar los tiempos de ejecución de los algoritmos. Este es un libro clásico sobre el tema (aquí está el capítulo sobre el crecimiento de las funciones).
  • Aquí hay una buena lista de cursos en línea que enseñan algoritmos.

Implemente algunos algoritmos usted mismo

Comience implementando varios algoritmos importantes usted mismo y conozca sus tiempos de ejecución. Algunos ejemplos son:

  • Búsqueda binaria
  • Algoritmo de Euclides
  • Profundidad y amplitud primera búsqueda
  • El camino más corto de Dijkstra
  • Recorridos binarios de árboles
  • Tipo de inserción, Mergesort, Quicksort
  • Min y max montones
  • Más ejemplos y listas.

Libros de algoritmos

  • Lea el Manual de diseño de algoritmos. Es un gran libro y es mi favorito.
  • Introducción a los algoritmos es un libro clásico que cubre mucho material.
  • Elements of Programming Interviews contiene muchos desafíos y soluciones de código que lo ayudarán a prepararse para las entrevistas.

Desafíos

  • Practique la codificación de algoritmos simples y luego más avanzados en sitios como Coderbyte y HackerRank que proporcionan explicaciones y soluciones para que también pueda aprender de otros codificadores.
  • Repase los desafíos en este sitio web interactivo de algoritmos de Python.
  • Los 10 sitios web de desafío de codificación más populares para 2017.
  • Los 5 desafíos de código más difíciles para principiantes.

Algoritmos Explicaciones y preguntas de la entrevista

  • Lea tantas explicaciones de algoritmos y ejemplos de código como pueda en GeeksforGeeks. Aquí hay un ejemplo de una buena publicación en algoritmos gráficos.
  • Mire algunas preguntas de la entrevista publicadas en CareerCup e intente comprender cómo otros usuarios resolvieron las preguntas. Me gusta este ejemplo.
  • Además de codificar sitios de desafío, intente y resuelva preguntas comunes de entrevistas de codificación que encuentre en línea, como las de esta lista.

Programación dinámica

Este es un concepto muy importante que deberá comprender si desea mejorar los algoritmos, razón por la cual separé este tema del resto. La descripción de Wikipedia es (negrita es mía):

Un método para resolver un problema complejo dividiéndolo en una colección de subproblemas más simples, resolviendo cada uno de esos subproblemas una sola vez y almacenando sus soluciones. La próxima vez que ocurra el mismo subproblema, en lugar de volver a calcular su solución, uno simplemente busca la solución calculada previamente, ahorrando así tiempo de cálculo.

He visto la programación dinámica aparecer en varias entrevistas de codificación que he tenido. También he visto problemas que requieren una solución de programación dinámica en sitios de desafío como LeetCode, Google Code Jam, y varios desafíos en Google Foo Bar requieren una solución DP.

Recomiendo intentar resolver tantos problemas en esta lista como sea posible. También hay un buen tutorial sobre TopCoder titulado: Programación dinámica: de principiante a avanzado. Muchos problemas de DP tienen la misma estructura y patrones, por lo que si resuelve 3 problemas de DP todos los días durante 2 semanas más o menos, después de un tiempo podrá detectar y resolver un problema de DP sin problemas.

Recursos avanzados en algoritmos (opcional)

  • Conferencias de estructuras de datos avanzadas por Erik Demaine
  • Límites inferiores algorítmicos: diversión con pruebas de dureza por Erik Demaine
  • Manual del programador competitivo
  • La guía del autoestopista para los concursos de programación
  • AlgoWiki: un wiki dedicado a la programación competitiva
  • Problemas y algoritmos de geometría computacional (genial y divertido, pero puede ser bastante difícil)
  • Lista de problemas NP-completos
  • Libro de estructuras de datos abiertos: implementación y análisis de estructuras de datos para secuencias, colas, colas de prioridad, diccionarios sin ordenar, diccionarios ordenados y gráficos

Espero que hayan disfrutado esta lista de recursos. Siéntase libre de practicar la codificación en Coderbyte y comente a continuación con cualquier otro recurso que considere útil.