1. Expliquez la notation Big O et les complexites les plus courantes.
La notation Big O decrit le comportement asymptotique d'un algorithme en fonction de la taille de l'entree (n). Complexites courantes (de la meilleure a la pire) : O(1) constant (acces array par index, hashmap lookup). O(log n) logarithmique (recherche binaire, operations sur arbre equilibre). O(n) lineaire (parcours de liste, recherche sequentielle). O(n log n) linearithmique (tri merge sort, quick sort en moyenne). O(n2) quadratique (tri par selection, deux boucles imbriquees). O(2^n) exponentiel (sous-ensembles, certains problemes de backtracking). O(n!) factoriel (permutations). En entretien, analyser le pire cas et le cas moyen. L'espace memoire (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 acces O(1) en moyenne. Fonctionnement : la fonction de hachage convertit la cle en un index du tableau interne. Les collisions (deux cles donnant le meme index) sont gerees par chainage (liste chainee a chaque index) ou adressage ouvert (probing lineaire, quadratique ou double hashing). Le facteur de charge (nombre d'elements / taille du tableau) determine quand redimensionner (generalement a 0.75). Le redimensionnement double la taille et re-hache toutes les entrees. Une bonne fonction de hachage distribue uniformement les cles. En Java, les cles doivent implementer hashCode() et equals() de maniere coherente.
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 supplementaire. Prefere quand la stabilite 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 complexite asymptotique.
4. Qu'est-ce qu'un arbre binaire de recherche (BST) et ses variantes ?
Un BST est un arbre ou pour chaque noeud : les descendants gauches sont inferieurs et les descendants droits sont superieurs. Operations : recherche, insertion, suppression en O(h) ou h est la hauteur. Probleme : un BST desequilibre degenere en liste chainee (O(n)). Solutions : AVL (strictement equilibre, hauteur max log n, rotations apres chaque insertion/suppression). Red-Black Tree (moins strictement equilibre que AVL, rotations et recoloration, utilise par Java TreeMap). B-Tree : arbre n-aire equilibre, optimise pour les acces disque, utilise par les bases de donnees et systemes de fichiers. Trie : arbre prefixe pour les chaines, 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. Complexite : O(V+E). Utilisation : plus court chemin, composantes connexes, detection de bipartite. DFS (Depth-First Search) : explore en profondeur avec une pile (stack ou recursion). Complexite : O(V+E). Utilisation : detection de cycles, tri topologique, composantes fortement connexes, backtracking. Le DFS a trois ordres de visite dans les arbres : pre-order (noeud, gauche, droite), in-order (gauche, noeud, droite), post-order (gauche, droite, noeud). BFS utilise plus de memoire 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 problemes 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 memes sous-problemes sont resolus plusieurs fois). Deux approches : top-down (memoization, recursion + cache) et bottom-up (tabulation, iteration). Etapes : identifier l'etat, definir la relation de recurrence, determiner le cas de base. Exemples classiques : Fibonacci, knapsack (sac a dos), longest common subsequence, edit distance, coin change. Astuce : souvent l'espace peut etre optimise (garder seulement la ligne precedente au lieu de la table complete).
7. Comment fonctionne l'algorithme de Dijkstra ?
L'algorithme de Dijkstra trouve le plus court chemin depuis un noeud source vers tous les autres dans un graphe avec des poids positifs. Fonctionnement : initialiser les distances a l'infini sauf la source (0). Utiliser une priority queue (min-heap). A chaque etape, extraire le noeud avec la distance minimale, relaxer ses voisins (si distance actuelle + poids arete < distance enregistree, mettre a jour). Complexite : O((V+E) log V) avec un min-heap binaire. Ne fonctionne pas avec des poids negatifs (utiliser Bellman-Ford dans ce cas). Variante A* : ajoute une heuristique pour guider la recherche vers la destination (plus rapide pour un chemin specifique). Utilisation : GPS, routage reseau, jeux video.
8. Expliquez les structures de donnees de type pile, file et deque.
Pile (Stack) : LIFO (Last In, First Out). Operations O(1) : push (empiler), pop (depiler), peek (sommet). Utilisation : evaluation d'expressions, verification de parentheses, backtracking, DFS, undo. Implementation : array ou liste chainee. File (Queue) : FIFO (First In, First Out). Operations O(1) : enqueue (enfiler), dequeue (defiler). Utilisation : BFS, planification de taches, buffers. Implementation : array circulaire ou liste chainee doublement chainee. Priority Queue : dequeue retourne l'element de plus haute priorite. Implementation 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 systematiquement toutes les solutions possibles en construisant incrementalement et en abandonnant (pruning) des que la solution partielle ne peut pas mener a une solution valide. Schema : choisir une option, recursion, annuler le choix (backtrack). Plus efficace que la force brute grace au pruning qui elimine des branches entieres. Exemples classiques : N-Queens (placer N reines sans conflit), Sudoku (remplir la grille), permutations/combinaisons, subset sum, coloring de graphe. Complexite : exponentielle dans le pire cas, mais le pruning reduit considerablement l'espace de recherche en pratique. Implementation : recursion avec un etat mutable (ajouter, recurser, retirer).
10. Comment resoudre les problemes de sliding window et two pointers ?
Two Pointers : deux indices parcourent la structure (generalement triee). Patterns : un pointeur a chaque extremite se rapprochant (pair sum, container with most water), deux pointeurs avancant (merge de listes triees, remove duplicates). Reduit O(n2) a O(n). Sliding Window : sous-tableau contigu de taille fixe ou variable. Taille fixe : fenetre de taille k glisse, on ajoute un element et retire un element a 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 reponse en ajoutant/retirant un element efficacement ?