La technique de la fenêtre glissante : un pattern d'entretien technique

J'ai été des deux côtés de la table d'entretien technique, surtout du côté candidat. La technique de la fenêtre glissante apparaît constamment, et elle sépare les candidats qui ont intériorisé un pattern de ceux qui essaient de dériver la solution à partir de zéro sous pression. Les premiers finissent en avance et expliquent leur raisonnement. Les seconds manquent de temps. Voici comment arriver dans la première catégorie.

Ce qu'est réellement le pattern

La fenêtre glissante est une optimisation pour les problèmes impliquant des séquences contiguës : sous-tableaux ou sous-chaînes. L'approche naïve pour la plupart de ces problèmes est une boucle imbriquée qui réexamine les éléments qui se chevauchent à chaque itération, donnant un temps O(n au carré). La fenêtre glissante évite cela en maintenant une plage avec deux pointeurs et en mettant à jour l'état de manière incrémentale à mesure que la plage se déplace. La plupart des problèmes passent à O(n).

Il existe deux variantes. Les fenêtres de taille fixe : la longueur de la fenêtre vous est donnée. Les fenêtres dynamiques : vous agrandissez et réduisez en fonction d'une contrainte. Identifier la variante à laquelle vous avez affaire est la première décision dans tout problème d'entretien qui correspond à ce pattern.

Quand utiliser ce pattern

• Le problème implique un sous-tableau ou une sous-chaîne contiguë
• On vous demande de trouver un maximum, un minimum ou un agrégat sur toutes les fenêtres d'une taille donnée
• Vous cherchez la sous-chaîne la plus longue ou la plus courte satisfaisant une contrainte
• La solution par force brute comporte des boucles imbriquées itérant sur le même tableau ou la même chaîne
• Le problème mentionne une 'fenêtre', une 'plage' ou des éléments 'consécutifs'

Fenêtre fixe : somme maximale d'un sous-tableau de taille K

C'est le point d'entrée du pattern. Étant donné un tableau d'entiers et un nombre k, trouvez la somme maximale de tout sous-tableau contigu de longueur k. L'approche naïve additionne k éléments pour chaque position de départ : O(n fois k). La fenêtre glissante ajoute l'élément entrant et retire l'élément sortant, en maintenant une somme courante : O(n).

function maxSumSubarray(nums: number[], k: number): number {
  if (nums.length < k) return 0;

  // Build the first window
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  let maxSum = windowSum;

  // Slide the window: add incoming, subtract outgoing
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (indices 2-4: 5+1+3)
console.log(maxSumSubarray([2, 3, 4, 1, 5], 2));    // 7 (3+4)

L'opération clé est windowSum += nums[i] - nums[i - k]. Vous ne recalculez pas à partir de zéro. Vous faites glisser : ajoutez le nouvel élément à droite, retirez l'ancien élément à gauche. Cette seule ligne contient toute l'idée de la fenêtre fixe.

Une ligne de ce code est une décision, pas un détail. Retourner 0 quand le tableau est plus court que k renvoie une valeur qu'une vraie fenêtre pourrait aussi produire, donc l'appelant ne peut pas distinguer 'aucune fenêtre valide' de 'la meilleure fenêtre vaut zéro'. Je retourne 0 ici pour garder l'exemple court. En entretien, dites-le à voix haute et choisissez délibérément : lever une erreur sur une entrée invalide, retourner null, ou demander à l'intervieweur quel devrait être le contrat. Remarquer qu'une valeur sentinelle entre en collision avec une réponse légitime, c'est exactement le genre de chose qu'ils écoutent.

Fenêtre dynamique : plus longue sous-chaîne sans caractères répétés

Les fenêtres dynamiques nécessitent de décider quand réduire. Dans ce problème, la contrainte est l'unicité : chaque caractère dans la fenêtre doit apparaître une seule fois. Étendez le pointeur droit librement. Quand un doublon entre dans la fenêtre, avancez le pointeur gauche jusqu'à ce que le doublon soit parti.

function lengthOfLongestUniqueSubstring(s: string): number {
  const lastSeen = new Map<string, number>();
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    // If we've seen this char and it's inside the current window, jump left past it
    if (lastSeen.has(char) && lastSeen.get(char)! >= left) {
      left = lastSeen.get(char)! + 1;
    }

    lastSeen.set(char, right);
    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

console.log(lengthOfLongestUniqueSubstring('abcabcbb')); // 3 (abc)
console.log(lengthOfLongestUniqueSubstring('pwwkew'));   // 3 (wke)

Stocker le dernier index vu plutôt que de supprimer des entrées de la map permet à left de sauter directement à la bonne position au lieu d'avancer caractère par caractère. Soyez précis sur ce que ça vous apporte, parce qu'un intervieweur va vérifier. Les deux versions sont en O(n). Dans la version qui avance d'un caractère à la fois, le pointeur left se déplace au plus n fois sur l'ensemble de la boucle, donc le travail total est linéaire dans les deux cas. Le saut économise des opérations sur la map et un facteur constant, pas une classe de complexité.

Le modèle reutilisable

La plupart des problèmes de fenêtre dynamique suivent la même structure. Intérioriser ce modèle signifie que vous passez le temps de l'entretien sur la logique spécifique au problème, pas sur l'échafaudage que vous avez déjà résolu.

function dynamicWindowTemplate(input: string | number[]): number {
  let left = 0;
  let result = 0;
  const windowState = new Map<string | number, number>();

  for (let right = 0; right < input.length; right++) {
    const incoming = input[right];

    // 1. Add incoming element to window state
    windowState.set(incoming, (windowState.get(incoming) ?? 0) + 1);

    // 2. Shrink window while constraint is violated
    while (/* window constraint violated */ false) {
      const outgoing = input[left];
      const count = windowState.get(outgoing)! - 1;
      if (count === 0) {
        windowState.delete(outgoing);
      } else {
        windowState.set(outgoing, count);
      }
      left++;
    }

    // 3. Update result with current valid window
    result = Math.max(result, right - left + 1);
  }

  return result;
}

Reconnaître le pattern en entretien

• Le problème dit-il 'sous-tableau', 'sous-chaîne' ou 'contigu' ? La fenêtre glissante est le pattern candidat.
• k est-il donné ? Fenêtre fixe. Y a-t-il une contrainte à satisfaire ? Fenêtre dynamique.
• La solution par force brute nécessite-t-elle des boucles imbriquées sur les mêmes données ? Vous regardez du O(n au carré) et la fenêtre glissante le corrigera.
• Pouvez-vous décrire le problème comme : trouver la plage optimale satisfaisant une condition ? C'est un problème de fenêtre glissante.

En entretien technique au tableau blanc, nommer le pattern à voix haute avant d'écrire du code signale la reconnaissance de patterns. C'est l'un des signaux les plus valorisés qu'un examinateur recherche.

Pratiquez le problème de somme maximale en fenêtre fixe et celui de la plus longue sous-chaîne unique en fenêtre dynamique jusqu'à ce qu'ils deviennent mécaniques. Ces deux-là couvrent les deux variantes structurelles. Chaque autre problème de fenêtre glissante que vous rencontrerez en entretien est une variation de l'un d'eux. Une fois le modèle intériorisé, le temps d'entretien est consacré à la logique spécifique à la contrainte, qui est la partie qui teste réellement la capacité de résolution de problèmes.

Références

• LeetCode. Problèmes de fenêtre glissante. https://leetcode.com/tag/sliding-window/
• GeeksforGeeks. Technique de la fenêtre glissante. https://www.geeksforgeeks.org/window-sliding-technique/
• MDN Web Docs. JavaScript Array. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array