1. Expliquez la notation Big O et les complexites les plus courantes.
La notation Big O décrit le comportement asymptotique d'un algorithme en fonction de la taille de l'entrée (n). Complexites courantes (de la meilleure à la pire) : O(1) constant (accès array par index, hashmap lookup). O(log n) logarithmique (recherche binaire, opérations sur arbre équilibre). O(n) linéaire (parcours de liste, recherche sequentielle). O(n log n) linearithmique (tri merge sort, quick sort en moyenne). O(n2) quadratique (tri par sélection, deux boucles imbriquées). O(2^n) exponentiel (sous-ensembles, certains problèmes de backtracking). O(n!) factoriel (permutations). En entretien, analyser le pire cas et le cas moyen. L'espace mémoire (space complexity) est aussi important que le temps.
2. Comment fonctionne une table de hachage (HashMap) ?
Une HashMap stocke des paires cle-valeur avec un accès O(1) en moyenne. Fonctionnement : la fonction de hachage convertit la cle en un index du tableau interne. Les collisions (deux clés donnant le même index) sont gérées par chainage (liste chaînée à chaque index) ou adressage ouvert (probing linéaire, quadratique ou double hashing). Le facteur de charge (nombre d'éléments / taille du tableau) determine quand redimensionner (généralement à 0.75). Le redimensionnement double la taille et re-hache toutes les entrées. Une bonne fonction de hachage distribue uniformement les clés. En Java, les clés doivent implémenter hashCode() et equals() de manière cohérente.
3. Expliquez les algorithmes de tri les plus importants.
Quick Sort : pivot + partitionnement, O(n log n) moyen, O(n2) pire cas, in-place. Le plus utilise en pratique. Merge Sort : diviser-fusionner, O(n log n) garanti, stable, mais O(n) espace supplémentaire. Préfère quand la stabilité est requise. Heap Sort : O(n log n) garanti, in-place, mais pas stable et mauvaise localite de cache. Counting Sort : O(n+k) pour les entiers dans un range connu, non-comparatif. Radix Sort : O(d*(n+k)) pour les entiers, tri par chiffre. Tim Sort : hybride merge+insertion, utilise par Python et Java. Le tri optimal par comparaison est borne par O(n log n). En pratique, les constantes et la localite de cache importent autant que la complexité asymptotique.
4. Qu'est-ce qu'un arbre binaire de recherche (BST) et ses variantes ?
Un BST est un arbre ou pour chaque nœud : les descendants gauches sont inferieurs et les descendants droits sont superieurs. Opérations : recherche, insertion, suppression en O(h) ou h est la hauteur. Problème : un BST desequilibre degenere en liste chaînée (O(n)). Solutions : AVL (strictement équilibre, hauteur max log n, rotations après chaque insertion/suppression). Red-Black Tree (moins strictement équilibre que AVL, rotations et recoloration, utilise par Java TreeMap). B-Tree : arbre n-aire équilibre, optimise pour les accès disque, utilise par les bases de données et systèmes de fichiers. Trie : arbre prefixe pour les chaînes, recherche en O(m) ou m est la longueur du mot, utilise pour l'autocomplete.
5. Expliquez le BFS et le DFS sur les graphes.
BFS (Breadth-First Search) : explore niveau par niveau avec une file (queue). Trouve le chemin le plus court dans un graphe non-pondere. Complexité : O(V+E). Utilisation : plus court chemin, composantes connexes, détection de bipartite. DFS (Depth-First Search) : explore en profondeur avec une pile (stack ou récursion). Complexité : O(V+E). Utilisation : détection de cycles, tri topologique, composantes fortement connexes, backtracking. Le DFS a trois ordres de visite dans les arbres : pre-order (nœud, gauche, droite), in-order (gauche, nœud, droite), post-order (gauche, droite, nœud). BFS utilise plus de mémoire que DFS pour les graphes larges, DFS peut causer un stack overflow pour les graphes profonds.
6. Qu'est-ce que la programmation dynamique et comment l'appliquer ?
La programmation dynamique (DP) optimise les problèmes en decomposant en sous-problemes chevauchants. Deux conditions : sous-structure optimale (la solution optimale contient les solutions optimales des sous-problemes) et chevauchement des sous-problemes (les mêmes sous-problemes sont résolus plusieurs fois). Deux approches : top-down (memoization, récursion + cache) et bottom-up (tabulation, itération). Étapes : identifier l'état, définir la relation de recurrence, déterminer le cas de base. Exemples classiques : Fibonacci, knapsack (sac a dos), longest common subsequence, edit distance, coin change. Astuce : souvent l'espace peut être optimise (garder seulement la ligne précédente au lieu de la table complete).
7. Comment fonctionne l'algorithme de Dijkstra ?
L'algorithme de Dijkstra trouve le plus court chemin depuis un nœud source vers tous les autres dans un graphe avec des poids positifs. Fonctionnement : initialiser les distances à l'infini sauf la source (0). Utiliser une priority queue (min-heap). A chaque étape, extraire le nœud avec la distance minimale, relaxer ses voisins (si distance actuelle + poids arete < distance enregistree, mettre à jour). Complexité : O((V+E) log V) avec un min-heap binaire. Ne fonctionne pas avec des poids négatifs (utiliser Bellman-Ford dans ce cas). Variante A* : ajoute une heuristique pour guider la recherche vers la destination (plus rapide pour un chemin spécifique). Utilisation : GPS, routage réseau, jeux vidéo.
8. Expliquez les structures de données de type pile, file et deque.
Pile (Stack) : LIFO (Last In, First Out). Opérations O(1) : push (empiler), pop (depiler), peek (sommet). Utilisation : évaluation d'expressions, vérification de parenthèses, backtracking, DFS, undo. Implémentation : array ou liste chaînée. File (Queue) : FIFO (First In, First Out). Opérations O(1) : enqueue (enfiler), dequeue (defiler). Utilisation : BFS, planification de tâches, buffers. Implémentation : array circulaire ou liste chaînée doublement chaînée. Priority Queue : dequeue retourne l'élément de plus haute priorité. Implémentation par heap (binary heap). Deque : double-ended queue, insertion et suppression aux deux extremites en O(1). Utile pour les sliding windows.
9. Qu'est-ce que le backtracking et quand l'utiliser ?
Le backtracking explore systématiquement toutes les solutions possibles en construisant incrementalement et en abandonnant (pruning) dès que la solution partielle ne peut pas mener à une solution valide. Schéma : choisir une option, récursion, annuler le choix (backtrack). Plus efficace que la force brute grace au pruning qui elimine des branches entières. Exemples classiques : N-Queens (placer N reines sans conflit), Sudoku (remplir la grille), permutations/combinaisons, subset sum, coloring de graphe. Complexité : exponentielle dans le pire cas, mais le pruning réduit considerablement l'espace de recherche en pratique. Implémentation : récursion avec un état mutable (ajouter, recurser, retirer).
10. Comment résoudre les problèmes de sliding window et two pointers ?
Two Pointers : deux indices parcourent la structure (généralement triee). Patterns : un pointeur à chaque extremite se rapprochant (pair sum, container with most water), deux pointeurs avancant (merge de listes triees, remove duplicates). Réduit O(n2) à O(n). Sliding Window : sous-tableau contigu de taille fixe ou variable. Taille fixe : fenetre de taille k glisse, on ajoute un élément et retire un élément à chaque pas (max sum subarray de taille k). Taille variable : agrandir la fenetre (right++) tant que la condition est valide, retrecir (left++) quand elle ne l'est plus (longest substring without repeating, minimum window substring). Toujours se demander : peut-on maintenir la réponse en ajoutant/retirant un élément efficacement ?