Dans cette deuxième partie de notre série, nous plongeons dans l'un des modèles les plus polyvalents pour résoudre les questions d'interview de codage: la fenêtre coulissante. Cette technique est incroyablement utile pour optimiser les problèmes impliquant des sous-réseaux ou des sous-chaînes d'éléments contiguës, tels que la maximisation des sommes, la recherche de conditions spécifiques dans une séquence ou le travail avec des sous-chaînes en chaînes.

Avant de commencer, si vous cherchez un guide complet pour vous préparer au codage des interviews, envisagez de consulter le craquage de l'interview de codage, un livre incontournable pour toute personne sérieuse sur l'atterrissage d'un emploi dans les meilleures entreprises technologiques.

Aperçu du motif de fenêtre coulissante

Le modèle de fenêtre coulissante est une technique qui vous permet de résoudre efficacement des problèmes où vous devez considérer un sous-ensemble de données à partir d'un ensemble de données plus large (comme un sous-réseau d'un tableau ou une sous-chaîne d'une chaîne). Au lieu de recalculer le sous-ensemble chaque fois que vous déplacez la fenêtre, cette technique maintient un total ou une condition en cours, glissant sur les données pour minimiser le travail inutile.

Quand utiliser la fenêtre coulissante:

• Le problème implique des sous-réseaux ou des sous-chaînes contiguës.
• Vous devez trouver la somme, le nombre ou les autres conditions maximales ou minimales dans une plage coulissante de l'ensemble de données.
• il implique une taille de fenêtre fixe ou nécessite une fenêtre dynamique qui se développe ou rétrécit.

Types d'approches de fenêtres coulissantes

1. Fenêtre de glissement de taille fixe

• ce que c'est : une fenêtre d'une taille fixe qui glisse sur le tableau ou la chaîne tout en maintenant une condition de course comme la somme ou le produit.
• Exemple : Trouvez la somme maximale d'une sous-réseau de taille k.

Exemple de problème : Étant donné un tableau d'entiers et un nombre k, trouvez la somme maximale de toute sous-réseau de taille k.

def max_sum_subarray(arr, k):
    # Initialize variables to store the maximum sum and the current window sum.
    max_sum = 0
    window_sum = 0

    # First, calculate the sum of the initial window (first 'k' elements).
    for i in range(k):
        window_sum  = arr[i]

    # Set the max_sum to the initial window's sum.
    max_sum = window_sum

    # Now, slide the window across the array. 
    # Start from the kth element and move until the end of the array.
    for i in range(k, len(arr)):
        # Slide the window by subtracting the element that is no longer in the window 
        # (arr[i - k]) and adding the new element (arr[i]).
        window_sum  = arr[i] - arr[i - k]

        # Update max_sum if the current window sum is greater than the previous max_sum.
        max_sum = max(max_sum, window_sum)

    # Return the maximum sum found.
    return max_sum

Explication:

• Une fenêtre de taille k est initialisée.
• Au fur et à mesure que la fenêtre se déplace sur le tableau, l'effet de glissement est réalisé en soustrayant l'élément qui n'est plus dans la fenêtre et en ajoutant le nouvel élément qui entre dans la fenêtre.
• Cela optimise le problème d'une approche de force brute de o (n * k) à o (n), car nous n'avons plus besoin de résumer la fenêtre entière pour chaque itération.

2. fenêtre de glissement dynamique

• ce que c'est : Ceci est utilisé lorsque la taille de la fenêtre n'est pas fixe. La fenêtre se développe ou les contrats en fonction des exigences du problème (comme satisfaire une somme ou une condition).
• Exemple : Trouvez le plus petit sous-réseau avec une somme supérieure ou égale à s.

Exemple de problème : Étant donné un tableau d'entiers et d'un nombre, trouvez le plus petit sous-réseau contigu dont la somme est supérieure ou égale à s.

  def smallest_subarray_with_sum(arr, S):
    # Initialize variables:
    # window_sum: to store the sum of the current window.
    # min_length: to store the length of the smallest subarray found.
    # window_start: the starting index of the sliding window.
    window_sum = 0
    min_length = float('inf')  # Start with a large number to compare minimum lengths.
    window_start = 0

    # Iterate over the array with window_end being the right boundary of the window.
    for window_end in range(len(arr)):
        # Add the current element to the window_sum.
        window_sum  = arr[window_end]

        # While the current window's sum is greater than or equal to S:
        while window_sum >= S:
            # Calculate the current window size and update min_length if smaller.
            min_length = min(min_length, window_end - window_start   1)

            # Shrink the window from the left by removing the element at window_start.
            window_sum -= arr[window_start]

            # Move the start of the window to the right.
            window_start  = 1

    # If min_length was updated, return it; otherwise, return 0 (meaning no valid subarray was found).
    return min_length if min_length != float('inf') else 0

Explication:

• La fenêtre se développe en augmentant la fenêtre_end jusqu'à ce que la somme dépasse ou égale s.
• Une fois la condition satisfaite, la fenêtre commence à se contracter à partir de la gauche (Window_start) pour trouver la taille minimale de la sous-bande.
• Cette approche est efficace car elle réduit le problème de o (n ^ 2) à o (n), en évitant les récomputations.

Étapes pour implémenter des solutions de fenêtres coulissantes

1. Définissez les limites de la fenêtre : vous devez définir le début et la fin de la fenêtre.

2. Définissez une condition initiale : Pour les fenêtres fixe, initialisez la somme / produit / condition pour la première fenêtre. Pour les fenêtres dynamiques, la condition initiale dépend de l'objectif du problème.

3. glisse la fenêtre :

   • pour la taille de la fenêtre fixe: décaliez la fenêtre en ajoutant l'élément suivant et en supprimant l'élément qui n'est plus dans la fenêtre.
   • pour les fenêtres dynamiques: développez ou contractez la fenêtre en fonction de la condition que vous essayez de satisfaire.

4. Vérifiez et mettez à jour les résultats : après chaque mouvement de fenêtre, mettez à jour le résultat (tel que la somme maximale, la longueur minimale, etc.) si nécessaire.

Questions d'entrevue courantes en utilisant la fenêtre coulissante

1. Sous-chaîne la plus longue sans répéter les caractères

   • Problème : Étant donné une chaîne s, trouvez la longueur de la sous-chaîne la plus longue sans répéter les caractères.
   • modèle : utilisez une fenêtre de glissement dynamique pour se développer jusqu'à ce qu'un caractère en double soit trouvé, puis contractez la fenêtre jusqu'à ce que la condition soit satisfaite.

2. Subanray maximum de taille de taille k

   • Problème : Étant donné un tableau d'entiers et un entier k, trouvez la somme maximale de toute sous-réseau de taille k.
   • motif : utilisez une fenêtre de glissement de taille fixe pour maintenir la somme des éléments k et mettre à jour la somme maximale lorsque vous faites glisser la fenêtre à travers le tableau.

3. le plus petit sous-réseau avec une somme donnée

   • Problème : Compte tenu d'un tableau d'entiers positifs et d'un nombre s, trouvez la longueur du plus petit sous-réseau contigu dont la somme est supérieure ou égale à s.
   • modèle : utilisez une fenêtre de glissement dynamique qui se développe pour trouver un sous-réseau valide et contracte pour minimiser sa longueur.

Hacks de fenêtres coulissantes pour des interviews

1. Pensez en termes de limites de la fenêtre : commencez par réfléchir à l'endroit où la fenêtre doit démarrer et se terminer. Cela vous aide à identifier la plage exacte avec laquelle vous travaillez.

2. Utilisez un hashmap ou un jeu pour les fenêtres dynamiques : Lorsque vous traitez des sous-chaînes ou des éléments uniques, utilisez un ensemble pour suivre les éléments de la fenêtre.

3. Commencez par Brute-Force, puis optimisez : dans certains problèmes, commencer par une approche de force brute (comme la vérification de chaque sous-réseau possible) peut vous aider à visualiser comment une fenêtre coulissante réduirait un travail inutile.

4. Recherchez des conditions optimales : Si le problème a un composant d'optimisation (comme minimiser ou maximiser une somme ou une longueur), la fenêtre coulissante peut être un bon ajustement.

Conclusion

Le modèle de fenêtre coulissante est un outil puissant pour résoudre de nombreux problèmes d'entrevue de codage, en particulier ceux impliquant des séquences telles que des tableaux ou des chaînes. En maîtrisant les fenêtres glissantes de taille fixe et dynamiques, vous pouvez résoudre un large éventail de problèmes plus efficacement.

Dans le prochain article, nous explorerons la technique deux pointeurs , une autre stratégie très efficace qui complète souvent l'approche de la fenêtre coulissante dans des problèmes qui impliquent des paires ou des comparaisons entre les éléments.

Restez à l'écoute pour la partie 3!