Contient des Duplicatas II – Résolvez cette Question d’Entretien en Python
Introduction
La question « Contient des Duplicatas II » est un problème classique posé lors des entretiens techniques pour évaluer votre capacité à manipuler des structures de données et à concevoir des algorithmes efficaces. Cet article a pour objectif de vous guider à travers la compréhension, l’analyse et la résolution de ce problème. Vous découvrirez différentes approches, allant de la solution la plus intuitive à des méthodes plus optimisées, ce qui vous permettra d’être bien préparé lors de futurs entretiens.
Compréhension du Problème
Énoncé du problème
Le problème « Contient des Duplicatas II » peut être formulé de la manière suivante : « Étant donné un tableau nums
de nombres entiers et un entier k
, déterminer s’il existe deux indices i
et j
dans le tableau tels que nums[i] == nums[j]
et |i - j| <= k
."
Exemples Concrets :
- Entrée :
nums = [1, 2, 3, 1], k = 3
- Sortie :
True
(carnums[0] == nums[3]
et|0 - 3| <= 3
) - Entrée :
nums = [1, 0, 1, 1], k = 1
- Sortie :
True
(carnums[2] == nums[3]
et|2 - 3| <= 1
) - Entrée :
nums = [1, 2, 3, 4], k = 2
- Sortie :
False
(aucun duplicate dans la condition)
Conditions et contraintes
- Les valeurs des éléments dans
nums
peuvent être quelconques. k
est un entier positif.- La taille du tableau
nums
peut aller jusqu'à10^5
éléments, ce qui nécessite une solution performante en termes de complexité temporelle.
Approche Naïve
Explication de l'approche simple
La solution la plus directe est d'utiliser deux boucles imbriquées pour comparer chaque paire d'éléments du tableau nums
. Cette approche vérifie chaque combinaison possible d'indices pour satisfaire la condition donnée.
Implémentation en Python
def contains_nearby_duplicate_naive(nums, k):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j] and j - i <= k:
return True
return False
Analyse de la complexité
- Complexité temporelle : O(n²), car il y a deux boucles imbriquées parcourant les indices.
- Complexité spatiale : O(1), car nous n'utilisons pas de structure auxiliaire susceptible de croître avec la taille de l'entrée.
Approche Efficace avec HashMap (Dictionnaire)
Concepts de base de l'utilisation d'un HashMap
Le concept clé ici est de stocker l'index de chaque élément rencontré dans un dictionnaire. Cela permet de vérifier rapidement si nous avons déjà rencontré un élément identique dans un rayon de k
.
Implémentation de la solution
def contains_nearby_duplicate_hashmap(nums, k):
index_map = {}
for i, num in enumerate(nums):
if num in index_map and i - index_map[num] <= k:
return True
index_map[num] = i
return False
Analyse de la complexité
- Complexité temporelle : O(n), car chaque élément est traversé une seule fois.
- Complexité spatiale : O(n), car nous pourrions stocker potentiellement chaque élément du tableau dans le dictionnaire.
Approche Avancée avec Sliding Window (Fenêtre Glissante)
Introduction au concept de la fenêtre glissante
Une fenêtre glissante consiste à maintenir une "fenêtre" ou une sous-liste dynamique qui se déplace à travers le tableau, vérifiant la condition du problème.
Implémentation en Python
def contains_nearby_duplicate_sliding_window(nums, k):
window_set = set()
for i, num in enumerate(nums):
if num in window_set:
return True
window_set.add(num)
if len(window_set) > k:
window_set.remove(nums[i - k])
return False
Analyse de la complexité
- Complexité temporelle : O(n), chaque ajout ou suppression dans l'ensemble est en temps constant.
- Complexité spatiale : O(min(n, k)), en raison de la dimension de la fenêtre.
Comparaison des Approches
- Approche Naïve : Facile à comprendre mais inefficace pour de grands tableaux.
- HashMap : Très efficace en termes de temps, à utiliser lorsque la mémoire n'est pas une contrainte.
- Fenêtre Glissante : Offre une bonne balance entre efficacité temps et utilisation mémoire pour des
k
relativements petits.
Conseils d'Entretien
- Il est crucial de d'abord exposer la solution naïve avant de converger vers une approche optimisée.
- Expliquez clairement chaque étape de votre raisonnement et vos choix.
- Discutez des compromis entre complexité temporelle et spatiale.
Conclusion
Nous avons exploré différentes méthodes pour résoudre le problème "Contient des Duplicatas II", allant de l'approche naïve à des solutions plus sophistiquées utilisant des structures de données avancées. Comprendre et savoir appliquer ces stratégies est essentiel pour réussir lors d'entretiens techniques.
Ressources et Lectures Complémentaires
- Tutoriels Python : Documentation Officielle Python
- Plateformes de codage : LeetCode, HackerRank
- Livres recommandés : "Introduction to Algorithms" de Thomas H. Cormen.
Exercices Pratiques
- Essayez d'implémenter une solution en utilisant une pile ou une file pour des variations de ce problème.
- Résolvez d'autres problèmes similaires sur les permutations et les combinaisons d'indices dans un tableau pour affiner votre compréhension des structures de données et des algorithmes.