Patrons Two Pointers HashMap Stack pour les entretiens

Trois Patrons Essentiels pour les Algorithmes en Entretien de Code

Le patron Deux Pointeurs utilise deux pointeurs pour balayer les données en un seul passage. Il réduit la complexité de O(n²) à O(n) pour les palindromes, les paires d'éléments et les tâches de filtrage.

Deux variantes principales :

• Gauche-Droite (convergeant) : gauche commence à l'index 0, droite à s.length - 1. Les déplacer vers le centre pour vérifier la symétrie.
• Lent-Rapide : lent met à jour le résultat, rapide avance pour supprimer les doublons ou décaler les éléments.

Exemple : vérification d'un palindrome en ignorant les caractères non alphabétiques.

const isPalindrome = (s) => {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
};

console.log(isPalindrome("madam")); // true
console.log(isPalindrome("abc")); // false

HashMap : Recherches Rapides et Regroupement

HashMap (objet ou Map) stocke des paires clé-valeur pour un accès en O(1). Idéal pour les comptages de fréquences, vérifications d'unicité, anagrammes et mise en cache.

Algorithme : un passage pour construire, un second pour interroger. Évite complètement les boucles imbriquées.

Exemple : premier caractère unique dans une chaîne.

const firstUniqueChar = (s) => {
  const map = {};

  for (const char of s) {
    map[char] = (map[char] || 0) + 1;
  }

  for (const char of s) {
    if (map[char] === 1) {
      return char;
    }
  }

  return null;
};

console.log(firstUniqueChar("banana")); // 'b'
console.log(firstUniqueChar("aabbc")); // 'c'

Pile : Gestion des Structures LIFO

La pile suit le principe Dernier Entré - Premier Sorti. Un tableau avec push/pop excelle pour la validation de parenthèses, les piles sans récursion et le backtracking.

Exemple : validation de séquences de parenthèses.

const isValidBrackets = (s) => {
  const stack = [];
  const map = {
    ')': '(',
    ']': '[',
    '}': '{' 
  };

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else {
      const last = stack.pop();
      if (last !== map[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

console.log(isValidBrackets("{[()()]}")); // true
console.log(isValidBrackets("{[(])}")); // false

Quand Utiliser Chaque Patron

Avant de coder, repérez ces indices :

Deux Pointeurs :

• Tableau/chaîne avec symétrie (palindrome).
• Recherche de paires d'éléments.
• Tableau trié.
• Comparaison depuis les deux extrémités.

HashMap :

• Comptage de fréquences ou unicité.
• Anagrammes, regroupement.
• Vérification d'existence d'éléments.
• Données non triées nécessitant des recherches rapides.

Pile :

• Parentèses ou structures imbriquées.
• Logique LIFO (dernier ouvert se ferme en premier).
• Backtracking ou historique d'états.

Points Clés à Retenir

• Deux Pointeurs économise les passages de données, parfait pour les structures linéaires.
• HashMap offre un accès O(1), remplaçant les boucles imbriquées par deux passages.
• Pile garantit l'ordre d'imbrication correct sans récursion.
• Entraînez-vous : résolvez 10 problèmes par patron, puis mélangez-les.

Ces patrons résolvent la plupart des problèmes LeetCode/Codewars Facile/Moyen. Une pratique régulière forge l'intuition des entretiens seniors.

— Editorial Team