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
📊 Structures de Données Essentielles
🔢 Arrays (Tableaux)
// 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)
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)
*avec implémentation optimisée (voir code)
// ⚠️ 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
*si on a la référence du nœud
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
*arbre équilibré. Pire cas O(n) si déséquilibré
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
// 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)
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
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
// 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.