Fiche de Révision Entretiens Tech – Structures de Données & Algorithmes

Fiche complète pour entretiens techniques : arrays, listes, arbres, graphes et complexité.

algorithmique

Cette fiche de révision concentre les éléments essentiels pour réussir vos entretiens techniques. Basée sur une approche progressive et organisée, elle couvre les structures de données et algorithmes incontournables avec des exemples concrets en TypeScript.

🎯 Ordre d'apprentissage optimal :

  • Phase 1 : Structures de base (Arrays, Stacks, Queues, Linked Lists)
  • Phase 2 : Structures avancées (Trees, Hash Tables, Graphs)
  • Phase 3 : Algorithmes (Sorting, Search, Dynamic Programming)
  • Phase 4 : Patterns d'entretiens et simulation
Complexités Big O Comparées Taille des données (n) Temps O(1) O(log n) O(n) O(n log n) O(n²)

📊 Structures de Données Essentielles

🔢 Arrays (Tableaux)

Accès: O(1)
Recherche: O(n)
Insertion: O(n)
Structure Array 1 index 0 2 index 1 3 index 2 Accès O(1) 4 index 3 5 index 4
// Opérations essentielles
const arr: number[] = [1, 2, 3, 4, 5];

// Accès direct O(1)
const element = arr[2]; // 3

// Recherche O(n)
const index = arr.indexOf(4); // 3

// Insertion O(n) - décale les éléments
arr.splice(2, 0, 10); // [1,2,10,3,4,5]
                    

📚 Stacks (Piles)

Principe : LIFO (Last In, First Out)

Push: O(1)
Pop: O(1)
Stack (LIFO) Premier Deuxième Dernier ← Pop (sortie) ← Push (entrée)
class Stack<T> {
    private items: T[] = [];
    
    push(item: T): void {
        this.items.push(item);
    }
    
    pop(): T | undefined {
        return this.items.pop();
    }
    
    peek(): T | undefined {
        return this.items[this.items.length - 1];
    }
}
                    

🎯 Queues (Files)

Principe : FIFO (First In, First Out)

Enqueue: O(1)
Dequeue: O(1)*

*avec implémentation optimisée (voir code)

Queue (FIFO) 1er 2e 3e 4e Dequeue → ← Enqueue
// ⚠️ Version naïve : arr.shift() est O(n) en JavaScript !
// ✅ Version optimisée avec deux stacks
class Queue<T> {
    private inbox: T[] = [];
    private outbox: T[] = [];
    
    enqueue(item: T): void {
        this.inbox.push(item); // O(1)
    }
    
    dequeue(): T | undefined {
        if (!this.outbox.length) {
            while (this.inbox.length) {
                this.outbox.push(this.inbox.pop()!);
            }
        }
        return this.outbox.pop(); // O(1) amortized
    }
    
    front(): T | undefined {
        if (!this.outbox.length && this.inbox.length) {
            while (this.inbox.length) {
                this.outbox.push(this.inbox.pop()!);
            }
        }
        return this.outbox[this.outbox.length - 1];
    }
}
                    

🔗 Linked Lists

Accès: O(n)
Insertion: O(1)*

*si on a la référence du nœud

Linked List 1 → 2 → 3 → NULL data | next data | next data | next
class ListNode<T> {
    constructor(
        public data: T,
        public next: ListNode<T> | null = null
    ) {}
}

class LinkedList<T> {
    private head: ListNode<T> | null = null;
    
    prepend(data: T): void {
        const newNode = new ListNode(data);
        newNode.next = this.head;
        this.head = newNode;
    }
}
                    

🌳 Binary Search Trees

Recherche: O(log n)*
Insertion: O(log n)*
Suppression: O(log n)*

*arbre équilibré. Pire cas O(n) si déséquilibré

Binary Search Tree 8 3 10 1 6 14 Gauche < Parent Droite > Parent ⚠️ Pour garantir O(log n), utilisez AVL ou Red-Black Tree
class TreeNode<T> {
    constructor(
        public value: T,
        public left: TreeNode<T> | null = null,
        public right: TreeNode<T> | null = null
    ) {}
}

// Parcours inorder (gauche, racine, droite)
function inorderTraversal<T>(root: TreeNode<T> | null): T[] {
    if (!root) return [];
    
    return [
        ...inorderTraversal(root.left),
        root.value,
        ...inorderTraversal(root.right)
    ];
}

// Recherche dans BST
function searchBST(root: TreeNode<number> | null, target: number): TreeNode<number> | null {
    if (!root || root.value === target) return root;
    
    return target < root.value 
        ? searchBST(root.left, target)
        : searchBST(root.right, target);
}
                    

🗂️ Hash Tables

Recherche: O(1) moy
Insertion: O(1) moy
Suppression: O(1) moy
// En TypeScript, Map est une hash table optimisée
const cache = new Map<string, any>();

// Exemple : Fonction de mémorisation
const memoize = <T, R>(fn: (arg: T) => R) => {
    const cache = new Map<T, R>();
    
    return (arg: T): R => {
        if (cache.has(arg)) {
            return cache.get(arg)!;
        }
        
        const result = fn(arg);
        cache.set(arg, result);
        return result;
    };
};
                    

⚡ Algorithmes Fondamentaux

🔍 Recherche et Tri

Binary Search (Recherche Binaire)

Complexité: O(log n)
function binarySearch(arr: number[], target: number): number {
    let left = 0, right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1; // Non trouvé
}

Quick Sort

Moyenne: O(n log n)
Pire cas: O(n²)
function quickSort(arr: number[]): number[] {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter(x => x < pivot);
    const middle = arr.filter(x => x === pivot);
    const right = arr.filter(x => x > pivot);
    
    return [...quickSort(left), ...middle, ...quickSort(right)];
}

🔄 Parcours de Graphes

BFS & DFS

Complexité: O(V + E)
// BFS (Breadth-First Search) - Parcours en largeur
function bfs<T>(graph: Map<T, T[]>, start: T): T[] {
    const visited = new Set<T>();
    const queue: T[] = [start];
    const result: T[] = [];
    
    while (queue.length > 0) {
        const vertex = queue.shift()!;
        
        if (!visited.has(vertex)) {
            visited.add(vertex);
            result.push(vertex);
            
            const neighbors = graph.get(vertex) || [];
            queue.push(...neighbors.filter(n => !visited.has(n)));
        }
    }
    
    return result;
}

// DFS (Depth-First Search) - Parcours en profondeur
function dfs<T>(
    graph: Map<T, T[]>, 
    start: T, 
    visited = new Set<T>()
): T[] {
    visited.add(start);
    const result = [start];
    
    const neighbors = graph.get(start) || [];
    for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
            result.push(...dfs(graph, neighbor, visited));
        }
    }
    
    return result;
}

🎯 Dynamic Programming

Fibonacci avec Mémorisation

function fibonacci(n: number, memo: Map<number, number> = new Map()): number {
    if (n <= 1) return n;
    
    if (memo.has(n)) {
        return memo.get(n)!;
    }
    
    const result = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    memo.set(n, result);
    
    return result;
}

Problème du sac à dos (0/1 Knapsack) - Version Optimisée

// Version classique O(n * capacity) espace
function knapsack2D(weights: number[], values: number[], capacity: number): number {
    const n = weights.length;
    const dp: number[][] = Array(n + 1).fill(null)
        .map(() => Array(capacity + 1).fill(0));
    
    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    values[i - 1] + dp[i - 1][w - weights[i - 1]],
                    dp[i - 1][w]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][capacity];
}

// ✅ Version optimisée O(capacity) espace
function knapsackOptimized(weights: number[], values: number[], capacity: number): number {
    const dp = Array(capacity + 1).fill(0);
    
    for (let i = 0; i < weights.length; i++) {
        // Parcourir à l'envers pour éviter d'utiliser la même valeur deux fois
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
    
    return dp[capacity];
}

🚨 Erreurs classiques en Dynamic Programming :

  • Mauvais ordre de calcul : Calculer dp[i] avant dp[i-1] → Résultat incorrect
  • Mauvaise définition d'état : État qui ne capture pas toute l'information nécessaire
  • Redondance non évitée : Oublier la mémorisation → Complexité exponentielle
  • Cas de base oubliés : Ne pas initialiser dp[0] ou les conditions limites
  • Optimisation d'espace prématurée : Commencer par la version 2D puis optimiser

📝 Stratégies d'Entretien

🎯 Méthode UMPIRE

  • Understand - Comprendre le problème et les contraintes
  • Match - Identifier le pattern ou la structure de données appropriée
  • Plan - Planifier la solution étape par étape
  • Implement - Implémenter le code en pensant à voix haute
  • Review - Réviser le code et tester avec des exemples
  • Evaluate - Analyser la complexité temporelle et spatiale

📋 Patterns d'Algorithmes - Tableau de Référence

Pattern Quand l'utiliser Complexité Exemple classique
Two Pointers Array trié, recherche de paires O(n) Two Sum, Palindrome
Sliding Window Sous-array/substring continu O(n) Max Subarray Sum, Longest Substring
Fast & Slow Pointers Cycle detection, point milieu O(n) Linked List Cycle, Middle Element
Merge Intervals Intervalles qui se chevauchent O(n log n) Meeting Rooms, Overlapping Intervals
Binary Search Array trié, recherche optimisée O(log n) Search Insert Position, Peak Element
BFS Plus court chemin, niveau par niveau O(V + E) Level Order Traversal, Shortest Path
DFS Exploration complète, backtracking O(V + E) Path Finding, Islands Count
Dynamic Programming Optimisation, sous-problèmes Variable Fibonacci, Knapsack, Coin Change
Backtracking Toutes les solutions possibles Exponentielle N-Queens, Sudoku, Permutations

🎮 Exercices Recommandés par Niveau

🟢 Débutant (Easy)

  • Two Sum - Hash table pattern
  • Valid Parentheses - Stack usage
  • Reverse Linked List - Pointer manipulation
  • Maximum Subarray - Sliding window
  • Binary Tree Inorder - Tree traversal
  • Climbing Stairs - Simple DP

🟡 Intermédiaire (Medium)

  • Longest Substring Without Repeating - Advanced sliding window
  • Add Two Numbers - Linked list manipulation
  • 3Sum - Two pointers advanced
  • Binary Tree Level Order - BFS implementation
  • Coin Change - DP optimization
  • Number of Islands - DFS/BFS on matrix

🔴 Avancé (Hard)

  • Word Ladder - Complex BFS
  • Merge k Sorted Lists - Divide & conquer
  • Longest Increasing Subsequence - Advanced DP
  • Serialize Binary Tree - Tree design
  • Edit Distance - 2D DP
  • N-Queens - Backtracking

Two Pointers Pattern

// Exemple : Two Sum dans un array trié
function twoSumSorted(nums: number[], target: number): number[] {
    let left = 0, right = nums.length - 1;
    
    while (left < right) {
        const sum = nums[left] + nums[right];
        
        if (sum === target) return [left, right];
        else if (sum < target) left++;
        else right--;
    }
    
    return [];
}

Sliding Window Pattern

// Exemple : Somme maximale d'un sous-array de taille k
function maxSubarraySum(arr: number[], k: number): number {
    let maxSum = 0;
    let windowSum = 0;
    
    // Calculer la somme de la première fenêtre
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;
    
    // Faire glisser la fenêtre
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}

⚠️ Pièges Courants à Éviter

Erreur Conséquence Solution
Oublier les cas limites Array vide, valeurs nulles Toujours vérifier arr.length === 0
Condition de boucle incorrecte Boucle infinie ou index out of bounds Tester avec left <= right vs left < right
Oublier le cas de base en récursion Stack overflow Définir clairement les conditions d'arrêt
Mauvaise analyse de complexité Solution non-optimale acceptée Compter les boucles imbriquées et opérations

À Retenir

  • Complexités essentielles : O(1) > O(log n) > O(n) > O(n log n) > O(n²)
  • Structures de base : Maîtrisez Arrays, Stacks, Queues avant les structures avancées
  • Patterns récurrents : Two Pointers, Sliding Window, Fast & Slow Pointers
  • Algorithmes incontournables : Binary Search, BFS/DFS, Quick Sort, Dynamic Programming
  • Méthode UMPIRE : Structure systématique pour aborder tout problème
  • Implémentations optimisées : Queue avec deux stacks, BST équilibrés, Hash tables avec bon facteur de charge
  • Communication : Pensez à voix haute, expliquez votre raisonnement étape par étape
  • Tests : Toujours valider avec des exemples simples et cas limites
  • DP : Commencez par la version 2D, puis optimisez l'espace si nécessaire
  • Erreurs fréquentes : Cas limites oubliés, mauvaise condition de boucle, complexité mal analysée

L'essentiel est de comprendre les concepts fondamentaux et leurs implémentations optimisées plutôt que de mémoriser des solutions. Une approche méthodique avec la méthode UMPIRE vous donnera la confiance nécessaire pour réussir vos entretiens techniques.