Améliorer vos compétences en algorithmes et structure de données

Image de Dynamo Primer.

Certaines des ressources de cet article ont paru à l'origine dans l'un de mes commentaires sur un post de reddit qui est devenu très populaire. Voici le fil original, et ma nouvelle rédaction est ci-dessous.

Fondamentaux

La première chose dont vous aurez besoin si vous souhaitez améliorer vos algorithmes et structures de données est une base solide. Cette base peut être apprise de différentes manières, soit par le biais d’un programme informatique à l’université, certains camps d’écriture de codage se concentrent un peu sur les sujets ci-dessous, ou vous pouvez apprendre par vos propres moyens à partir de livres, de vidéos ou de conférences en ligne. Il vous faut donc une compréhension de base des sujets suivants pour commencer:

Structures de données

En savoir plus sur les tableaux, les listes chaînées, les arbres binaires, les tables de hachage, les graphiques, les piles, les files d'attente, les tas et autres structures de données fondamentales.

Maths & Logique

Vous aurez besoin de connaître certains concepts mathématiques de plusieurs domaines si vous voulez exceller dans les algorithmes. En savoir plus sur la théorie des ensembles, les machines à états finis, les expressions rationnelles, la multiplication matricielle, les opérations au niveau des bits, la résolution d'équations linéaires, des concepts de combinatoire importants tels que la permutation, les combinaisons, le principe du casier.

L'architecture des ordinateurs

Découvrez comment les données sont représentées dans un ordinateur, les bases de la conception de la logique numérique, l'algèbre de Boolean, l'arithmétique des ordinateurs, la représentation en virgule flottante, la conception du cache. Essayez d’en apprendre un peu plus sur la programmation C et Assembly.

Aller de l'avant au-delà des fondamentaux

Une fois que vous sentez que vous comprenez bien la plupart des concepts énumérés ci-dessus, il est temps de vous plonger dans les algorithmes. Voici une liste de ressources et de choses que j'ai réalisées pour améliorer l'écriture et la compréhension d'algorithmes importants.

Pages extraites du manuel de conception d'algorithmes.

Big-O & Runtime

  • Découvrez ce qu'est Big-O et comment analyser les temps d'exécution des algorithmes. C'est un livre classique sur le sujet (voici le chapitre sur la croissance des fonctions).
  • Voici une bonne liste de cours en ligne qui enseignent des algorithmes.

Implémentez vous-même des algorithmes

Commencez par implémenter vous-même plusieurs algorithmes importants et en apprendre davantage sur leurs temps d'exécution. Quelques exemples sont:

  • Recherche binaire
  • Algorithme d'Euclide
  • Profondeur et largeur première recherche
  • Le plus court chemin de Dijkstra
  • Traversées d'arbres binaires
  • Tri par insertion, Mergesort, Quicksort
  • Tas min et max
  • Plus d'exemples et de listes.

Livres d'algorithmes

  • Lisez le manuel de conception d'algorithmes. C’est un excellent livre et c’est mon préféré.
  • Introduction to Algorithms est un livre classique qui couvre beaucoup de matériel.
  • Elements of Programming Interviews comporte de nombreux défis et solutions de code qui vous aideront à vous préparer aux entretiens.

Défis

  • Entraînez-vous à coder des algorithmes simples, puis plus avancés, sur des sites comme Coderbyte et HackerRank, qui fournissent des explications et des solutions vous permettant d’apprendre des autres codeurs.
  • Parcourez les défis sur ce site Web d'algorithmes interactifs python.
  • Les 10 sites Web les plus populaires en matière de codage pour 2017.
  • Les 5 défis de code les plus difficiles pour les débutants.

Algorithmes Explications & Questions d'Entrevue

  • Lisez autant d'explications sur les algorithmes et d'exemples de code que vous pouvez sur GeeksforGeeks. Voici un exemple de bon article sur les algorithmes de graphes.
  • Examinez quelques questions d’entrevue publiées sur CareerCup et essayez de comprendre comment d’autres utilisateurs ont résolu les questions. Comme cet exemple.
  • Outre les sites de test de codage, essayez de résoudre les questions courantes d'entrevue de codage que vous trouvez en ligne, telles que celles figurant sur cette liste.

Programmation dynamique

C’est un concept très important que vous devrez comprendre si vous voulez améliorer vos algorithmes, c’est la raison pour laquelle j'ai séparé ce sujet du reste. La description de Wikipedia pour cela est (le gras est à moi):

Une méthode pour résoudre un problème complexe en le décomposant en une collection de sous-problèmes plus simples, en résolvant chacun de ces sous-problèmes une seule fois et en stockant leurs solutions. La prochaine fois que le même sous-problème se produit, au lieu de recalculer sa solution, on se contente de consulter la solution précédemment calculée, ce qui permet de gagner du temps de calcul.

J'ai vu la programmation dynamique apparaître dans plusieurs entretiens de codage que j'ai eu. J'ai également constaté des problèmes nécessitant une solution de programmation dynamique sur des sites difficiles comme LeetCode, Google Code Jam et plusieurs défis sur Google Foo Bar nécessitaient une solution DP.

Je vous recommande d’essayer de résoudre le plus de problèmes possible sur cette liste. Il existe également un bon tutoriel sur TopCoder intitulé: Programmation dynamique - Du novice au avancé. De nombreux problèmes DP ont la même structure et les mêmes schémas. Par conséquent, si vous résolvez 3 problèmes DP tous les jours pendant environ 2 semaines, vous pourrez après un certain temps repérer et résoudre un problème DP sans problème.

Ressources avancées en algorithmes (facultatif)

  • Cours avancés sur les structures de données par Erik Demaine
  • Limites inférieures algorithmiques: les preuves du plaisir avec la dureté par Erik Demaine
  • Manuel du programmeur compétitif
  • Le guide de l’auto-stoppeur aux concours de programmation
  • AlgoWiki: un wiki dédié à la programmation compétitive
  • Problèmes de calcul géométrique et algorithmes (cool et amusant, mais peuvent être assez difficiles)
  • Liste des problèmes NP-complets
  • Open Data Structures Book: implémentation et analyse de structures de données pour des séquences, des files d'attente, des files d'attente de priorité, des dictionnaires non ordonnés, des dictionnaires ordonnés et des graphiques

J'espère que vous avez apprécié cette liste de ressources. N'hésitez pas à vous entraîner à coder sur Coderbyte et à commenter ci-dessous avec toute autre ressource que vous jugerez utile.