Structures de données fondamentales, techniques algorithmiques et algorithmes de graphes pour la préparation aux entretiens techniques et un cours de licence équivalent.
Chaque compétence que le diagnostic peut vérifier, regroupée comme sur la carte. Ouvrez une notion pour commencer une leçon.
Fondamentaux
Analyse de complexité: Décrire comment le temps d'exécution ou la mémoire d'un algorithme croît avec la taille des données, en utilisant le grand O.
Récursivité: Une fonction qui résout un problème en s'appelant elle-même sur une version plus petite du même problème.
Structures linéaires
Tableaux: Un bloc de mémoire contigu à disposition fixe, où n'importe quel index est atteint en temps constant.
Listes chaînées: Des nœuds dispersés en mémoire, chacun pointant vers le suivant, échangeant un accès indexé rapide contre une insertion peu coûteuse.
Piles et files: Deux ordonnancements à accès restreint : dernier entré, premier sorti et premier entré, premier sorti.
Recherche et tri
Recherche binaire: Diviser en deux, de façon répétée, une plage triée pour trouver une cible en temps logarithmique.
Tris par comparaison élémentaires: Les tris simples en O(n carré), à bulles, par insertion, par sélection, qui comparent et échangent des paires d'éléments.
Tris diviser-pour-régner: Les tris diviser-pour-régner, tri fusion et tri rapide, qui battent le O(n carré) en découpant le problème.
Tri sans comparaison: Trier en exploitant une structure connue dans les valeurs elles-mêmes, par dénombrement ou par base, plutôt que par comparaisons.
Hachage
Tables de hachage: Associer des clés à des cases d'un tableau via une fonction de hachage pour une recherche quasi en temps constant.
Arbres
Arbres binaires: Une structure hiérarchique où chaque nœud a au plus deux enfants.
Arbres binaires de recherche: Un arbre binaire maintenu ordonné pour que le sous-arbre gauche de chaque nœud soit plus petit et le droit plus grand.
Arbres de recherche équilibrés: Un ABR qui se rééquilibre activement, rotations AVL ou coloration rouge-noir, pour ne jamais dégénérer en une ligne.
Tas et files de priorité: Une structure en arbre qui garde toujours l'élément le plus petit, ou le plus grand, rapide à trouver.
Arbres tries: Un arbre où chaque chemin depuis la racine épelle un préfixe, conçu pour une recherche rapide de chaînes.
Graphes
Représentations de graphes: Stocker les sommets et arêtes d'un graphe sous forme de matrice d'adjacence ou de liste d'adjacence.
Parcours de graphes (BFS et DFS): Visiter chaque sommet accessible, soit niveau par niveau (BFS), soit en creusant en profondeur d'abord (DFS).
Tri topologique: Ordonner les sommets d'un graphe orienté acyclique pour que chaque arête pointe vers l'avant.
Union-find: Une structure qui suit quels éléments appartiennent au même groupe et fusionne les groupes rapidement.
Algorithme de Dijkstra: Trouver le chemin le moins coûteux d'un sommet vers tous les autres quand aucun poids d'arête n'est négatif.
Algorithme de Bellman-Ford: Trouver les plus courts chemins tout en fonctionnant encore lorsque certains poids d'arêtes sont négatifs, au prix de la vitesse.
Arbres de segments: Un arbre binaire sur un tableau qui répond à des requêtes sur une plage, comme une somme ou un minimum, en temps logarithmique.
Arbres de Fenwick: Une structure compacte basée sur un tableau qui répond à des requêtes de somme préfixe en temps logarithmique.
Techniques
Diviser pour régner: Découper un problème en copies indépendantes plus petites de lui-même, résoudre chacune, puis combiner.
Algorithmes gloutons: Faire le meilleur choix local à chaque étape en faisant confiance que cela mène à la meilleure réponse globale.
Programmation dynamique: Résoudre un problème en mettant en cache les réponses à des sous-problèmes qui se chevauchent plutôt que de les recalculer.
Retour sur trace (backtracking): Essayer un choix, récurer, puis l'annuler s'il ne mène nulle part, pour explorer toutes les possibilités.
Deux pointeurs: Faire avancer deux indices à travers une séquence en même temps pour éviter une boucle imbriquée.
Fenêtre glissante: Agrandir et rétrécir une plage contiguë sur une séquence pour suivre une condition en cours en un seul passage.
Manipulation de bits: Utiliser directement les bits binaires individuels d'un nombre, par exemple pour représenter un petit ensemble ou activer un indicateur.
Chaînes de caractères
Algorithmes de recherche de motifs: Trouver toutes les occurrences d'un motif dans un texte plus grand plus rapidement qu'en vérifiant chaque position.