Kit d'entretien : Tableaux - Fenêtre coulissante.

Tout est question de modèles !

Une fois que vous avez appris les modèles, tout commence à paraître un peu plus facile ! Si vous êtes comme moi, vous n'aimez probablement pas les entretiens techniques, et je ne vous en veux pas, ils peuvent être difficiles.

Les problèmes liés aux tableaux sont parmi les plus courants que vous rencontrerez lors des entretiens. Ces problèmes impliquent souvent de travailler avec des tableaux naturels :

const arr = [1, 2, 3, 4, 5];

Et les problèmes de chaînes, qui sont essentiellement des tableaux de caractères :

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']

L'un des modèles les plus courants pour résoudre les problèmes de tableau est la fenêtre coulissante.

Modèle de fenêtre coulissante

Le modèle de fenêtre coulissante implique deux pointeurs qui se déplacent dans la même direction, comme une fenêtre glissant sur le tableau.

Quand l'utiliser

Utilisez le modèle de fenêtre coulissante lorsque vous avez besoin de trouver un sous-tableau ou une sous-chaîne qui satisfait à une certaine condition, comme être le minimum, le maximum, le plus long ou le plus court.

Règle 1 : Si vous avez besoin de trouver un sous-tableau ou une sous-chaîne et que la structure des données est un tableau ou une chaîne, envisagez d'utiliser le modèle de fenêtre coulissante.

Exemple simple

Voici un exemple basique pour introduire le concept de pointeurs dans une fenêtre coulissante :

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l + 1;  // Right pointer

    while (r < arr.length) {
        console.log("left", arr[l]);
        console.log("right", arr[r]);
        l++;
        r++;
    }
}

SlidingWindow([1, 2, 3, 4, 5, 6, 7, 8]);

Notez que les pointeurs gauche (L) et droit (R) ne doivent pas nécessairement se déplacer en même temps, mais ils doivent se déplacer dans la même direction.

Le pointeur droit ne sera jamais plus bas que le pointeur gauche.

Explorons ce concept avec un vrai problème d'entretien.

Problème du monde réel : sous-chaîne la plus longue sans caractères répétitifs

Problème : Étant donné une chaîne s, trouver la longueur de la sous-chaîne la plus longue sans répéter de caractères.

Mots clés : sous-chaîne, la plus longue (maximum)

function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right < str.length; right++) {
        if (hash[str[right]] !== undefined && hash[str[right]] >= left) {
            left = hash[str[right]] + 1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left + 1);
    }

    return longest;
}

Ne vous inquiétez pas si cela semble compliqué, nous le verrons petit à petit.

let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5

Le cœur de ce problème est de trouver la sous-chaîne la plus longue sans répéter les caractères.

Fenêtre initiale : taille 0

Au départ, les pointeurs gauche (L) et droit (R) sont au même endroit :

let left = 0;

for (let right = 0; right < str.length; right++) {  // RIGHT POINTER

h e l l o w o r l d 
^
^
L
R

Et nous avons un hachage (objet) vide :

let hash = {};

Qu’est-ce qu’il y a de génial dans les objets ? Ils stockent des clés uniques, ce qui est exactement ce dont nous avons besoin pour résoudre ce problème. Nous utiliserons le hachage pour suivre tous les personnages que nous avons visités et vérifier si nous avons déjà vu le caractère actuel (pour détecter les doublons).

En regardant la chaîne, nous pouvons dire visuellement que world est la sous-chaîne la plus longue sans répéter de caractères :

h e l l o w o r l d 
          ^        ^   
          L        R

Ceci a une longueur de 5. Alors, comment y arriver ?

Décomposons-le étape par étape :

État initial

hash = {}

h e l l o w o r l d 
^
^
L
R

Itération 1 :

À chaque itération, nous ajoutons le caractère sous le pointeur R à la carte de hachage et incrémentons :

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);

Actuellement, il n'y a pas de caractères répétitifs dans notre fenêtre (h et e) :

hash = {h: 0}
h e l l o w o r l d 
^ ^
L R

Itération 2 :

hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R

Maintenant, nous avons une nouvelle fenêtre : hel.

Itération 3 :

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R

Voici où cela devient intéressant : nous avons déjà l dans notre hachage, et R pointe vers un autre l dans la chaîne. C'est là qu'intervient notre déclaration if :

if (hash[str[right]] !== undefined)

Si notre hachage contient la lettre R vers laquelle pointe, nous avons trouvé un doublon ! La fenêtre précédente (hel) est la plus longue jusqu'à présent.

Alors, on fait quoi ensuite ? Nous réduisons la fenêtre de gauche en déplaçant le pointeur L vers le haut puisque nous avons déjà traité la sous-chaîne de gauche. Mais jusqu'où peut-on déplacer L ?

left = hash[str[right]] + 1;

On déplace L juste après le doublon :

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R

Nous ajoutons toujours notre double au hachage, donc L aura désormais un index de 3.

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);

Nouvel état : itération 4

hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R

Itérations 4 à 6

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R

Quand R pointe vers un autre doublon (o), on déplace L juste après le premier o :

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R

Nous continuons jusqu'à ce que nous rencontrions un autre doublon l :

hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R

Mais remarquez que c'est en dehors de la fenêtre actuelle ! à partir de w,

Règle 3 : Ignorer le sous-x traité

Tout ce qui se trouve en dehors de la fenêtre actuelle n'est pas pertinent : nous l'avons déjà traité. Le code clé pour gérer cela est :

if (hash[str[right]] !== undefined && hash[str[right]] >= left)

Cette condition garantit que nous ne nous soucions que des caractères dans la fenêtre actuelle, en filtrant tout bruit.

hash[str[right]] >= left

Nous nous concentrons sur tout ce qui est plus grand ou égal au pointeur gauche

Itération finale :

hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R

Je sais que cela a été détaillé, mais décomposer les problèmes en modèles ou règles plus petits est le moyen le plus simple de les maîtriser.

In Summary:

• Rule 1: Keywords in the problem (e.g., maximum, minimum) are clues. This problem is about finding the longest sub-string without repeating characters.
• Rule 2: If you need to find unique or non-repeating elements, think hash maps.
• Rule 3: Focus on the current window—anything outside of it is irrelevant.

Bonus Tips:

• Break down the problem and make it verbose using a small subset.
• When maximizing the current window, think about how to make it as long as possible. Conversely, when minimizing, think about how to make it as small as possible.

To wrap things up, here's a little challenge for you to try out! I’ll post my solution in the comments—it’s a great way to practice.

Problem 2: Sum Greater Than or Equal to Target

Given an array, find the smallest subarray with a sum equal to or greater than the target(my solution will be the first comment).

/**
 * 
 * @param {Array<number>} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

Remember, like anything in programming, repetition is key! Sliding window problems pop up all the time, so don’t hesitate to Google more examples and keep practicing.

I’m keeping this one short, but stay tuned—the next article will dive into the two-pointer pattern and recursion (prepping for tree problems). It’s going to be a bit more challenging!

If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!

Resources:

Tech interview Handbook

leet code arrays 101

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!