Modèles de codage : une approche plus intelligente de la préparation aux entretiens de codage

Se préparer aux entretiens de codage peut être un véritable défi, les développeurs passant souvent plusieurs semaines à réviser et à apprendre de nouveaux éléments.

La vérité est que la plupart des développeurs ne se sentent jamais pleinement préparés pour leurs entretiens de codage. Il n'est pas rare que les développeurs passent des semaines à résoudre des problèmes sur LeetCode et ne se sentent toujours pas préparés. De toute évidence, cette approche pose des problèmes.

Examinons de plus près certains problèmes associés à la préparation traditionnelle aux entretiens de codage.

Les pièges de la préparation traditionnelle aux entretiens

L’un des pièges les plus courants dans la préparation traditionnelle aux entretiens est la pratique du « broyage ». Cette approche implique de résoudre autant de problèmes LeetCode que possible sans plan ou stratégie clair. Même si cette stratégie peut sembler productive, elle présente plusieurs inconvénients.

Lorsque vous résolvez des problèmes sans approche structurée, vous risquez de ne pas reconnaître vos faiblesses. Il n'y a pas de plan délibéré pour votre étude ; le but est simplement de résoudre autant de problèmes que possible. En conséquence, vous pouvez avoir l’impression d’avoir beaucoup appris, mais il peut y avoir des lacunes importantes dans vos connaissances.

De plus, le problème est qu’il s’agit essentiellement de mémoriser des solutions à une multitude de problèmes. Tenter de mémoriser les solutions à une centaine de problèmes de codage différents s'avère inefficace lorsque les enquêteurs présentent des questions qui s'écartent même légèrement de ce que vous avez rencontré auparavant. Cela peut vous donner le sentiment de ne pas être préparé à gérer les variations du problème.

Mon dernier problème avec cette stratégie est qu’à long terme, elle crée davantage de stress et de maux de tête. Si vous devez subir la même séance de bachotage de plusieurs semaines à chaque fois que vous souhaitez changer d'emploi, vous aurez du mal à chaque fois. Vous passerez des semaines à réapprendre des choses et à résoudre les mêmes problèmes qu'avant.

Compte tenu de ces défis, il doit y avoir une meilleure solution.

Une meilleure façon : adopter des modèles de codage

Alors, existe-t-il une approche plus efficace et plus durable pour coder la préparation aux entretiens ? La réponse réside dans la compréhension et l’utilisation des modèles de codage.

Lorsque je me prépare aux entretiens de codage, je donne la priorité à la compréhension des schémas sous-jacents des problèmes. Ces modèles, qui incluent des techniques telles que Two-Pointers , Sliding Window , Modified Binary Search , Topological Sort et bien d'autres, fournissent un cadre polyvalent et puissant pour résoudre un large éventail de problèmes de codage. L'accent passe de la mémorisation des solutions aux techniques éprouvées de résolution de problèmes.

En vous concentrant sur les modèles de codage, vous pouvez rationaliser considérablement la préparation de votre entretien, la rendant ainsi plus efficace.

N'oubliez pas : préparez-vous plus intelligemment, pas plus dur.

À quoi s'attendre?

Dans cet article, j'ai compilé les Top 15 des modèles de codage que vous devez savoir pour répondre à toute question de codage. Je vais expliquer ce qu'est chaque modèle et comment il fonctionne. Partagez des indicateurs clés pour vous aider à identifier le modèle et proposez enfin des graphiques détaillés avec un code de modèle pour vous aider à consolider votre compréhension.

Bien que j'aborde beaucoup de choses dans cet article, si vous souhaitez une formation plus approfondie, des explications et des pratiques de codage, vous pouvez consulter notre cours complet de préparation aux entretiens de codage sur Techinterviews.io. Nous abordons également des sujets cruciaux tels que les structures de données , les entretiens comportementaux et même la négociation salariale .

Passons maintenant à ces modèles de codage.

1. Inversion de liste liée

L'inversion de liste chaînée consiste à changer la direction des pointeurs dans une liste chaînée pour inverser l'ordre des éléments. Il s'agit d'une opération fondamentale dans les structures de données et elle nécessite souvent une manipulation minutieuse des références de nœuds.

Ceci est utile lorsqu'il s'agit d'une liste chaînée et la contrainte est de l'inverser sur place.

Le processus pour inverser une liste chaînée en place est le suivant :

1. Commencez par définir trois variables : current , previous et next . Définissez current comme tête de la liste chaînée et initialisez previous et next sur None.

2. Bien que la variable actuelle ne soit pas None , procédez comme suit :

   1. Stockez le nœud suivant dans une variable temporaire.
   2. Inversez le pointeur du nœud actuel pour pointer vers le nœud précédent .
   3. Mettez à jour previous pour être le nœud actuel et current pour être le nœud suivant .

3. Enfin, définissez la tête de la liste inversée sur le dernier nœud atteint, qui est stocké dans la variable précédente .

Indicateurs clef:

• Vous devez inverser l'ordre des éléments dans une liste chaînée.
• Les problèmes impliquent la vérification des palindromes dans les listes chaînées.
• Vous souhaitez inverser l'ordre des éléments dans une sous-liste spécifique au sein de la liste.

Code du modèle :

Python

 def reverse_linked_list(head): curr = head prev = None while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev

JS

 function reverseLinkedList(head) { let curr = head; let prev = null; while (curr) { const nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

Java

 public ListNode reverseLinkedList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

2. Recherche binaire modifiée

La recherche binaire modifiée adapte l'algorithme de recherche binaire classique pour résoudre divers problèmes. Les variantes incluent la recherche de la première/dernière occurrence d'un élément ou la recherche dans des tableaux pivotés. Cela nécessite une gestion minutieuse des points médians et des conditions.

Si jamais vous recevez un tableau trié, une liste chaînée ou une matrice, envisagez d'utiliser une recherche binaire modifiée .

Voici un aperçu de la façon d'appliquer ce modèle à une structure de données triée :

1. Commencez par identifier le point médian entre les positions de début et de fin . Pour éviter un éventuel débordement d'entier, il est plus sûr de calculer le milieu comme suit : middle = start + (end - start) / 2 .
2. Vérifiez si la clé correspond à l'élément à l'index du milieu . Si tel est le cas, renvoyez l’index du milieu comme résultat.
3. Si la clé ne correspond pas à l'élément de l'index du milieu , passez aux étapes suivantes.
4. Évaluez si la clé est inférieure à l'élément au milieu de l'index. Si tel est le cas, affinez votre plage de recherche en mettant à jour la fin vers le milieu - 1 .
5. À l'inverse, si la clé est supérieure à l'élément de l'index middle , ajustez votre plage de recherche en mettant à jour start vers middle + 1 .

Indicateurs clef:

• Vous travaillez avec une structure de données triée.
• Vous devez trouver efficacement des éléments, des limites ou des points pivots spécifiques.
• Les problèmes impliquent la recherche dans des tableaux triés en rotation.

Code du modèle :

Python

 def binary_search(arr: List[int], target: int) -> int: left, right = 0, len(arr) - 1 first_true_index = -1 # Perform binary search until left and right pointers meet while left <= right: mid = (left + right) // 2 if feasible(mid): # If the condition is true at mid index, update first_true_index first_true_index = mid right = mid - 1 else: # If the condition is false at mid index, narrow down the search space left = mid + 1 return first_true_index

JS

 function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; let firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { const mid = Math.floor((left + right) / 2); if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

Java

 public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; int firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { int mid = left + (right - left) / 2; if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

3. Deux indicateurs

La technique des deux pointeurs consiste à maintenir deux pointeurs qui traversent une structure de données, généralement des tableaux ou des listes chaînées, souvent utilisées pour des problèmes impliquant des paires ou des sous-tableaux. Il optimise les problèmes qui nécessitent une comparaison entre des éléments situés à différentes positions.

L'avantage de cette technique réside dans sa simplicité et son efficacité, en particulier lorsqu'il s'agit de structures de données linéaires telles que des tableaux ou des chaînes pour lesquelles vous pourriez initialement utiliser un seul pointeur. En utilisant deux pointeurs, vous pouvez éviter les opérations redondantes et améliorer considérablement l'efficacité de l'exécution, la réduisant potentiellement de O(n^2) à O(n) .

Le modèle « Two Pointers » englobe plusieurs variantes, chacune adaptée à des scénarios spécifiques. Ces variations incluent la même direction , la direction opposée et une méthode unique connue sous le nom de « rapide et lente », souvent appelée technique « tortue et lièvre » , qui implique deux pointeurs se déplaçant à des vitesses différentes à travers une structure de données, particulièrement utile pour détecter cycles.

Si vous utilisez plusieurs pointeurs pour parcourir une structure de données, vous pouvez classer votre approche comme suivant le modèle « Deux pointeurs » .

Indicateurs clef:

• Vous devez comparer ou opérer sur des éléments situés à différentes positions.
• Les problèmes nécessitent la recherche de paires d'éléments dans un tableau trié.
• Vous souhaitez supprimer efficacement les doublons d’un tableau trié.
• Lorsque vous traitez des structures de données linéaires (tableaux, chaînes ou listes chaînées) et que vous faites face à une complexité temporelle quadratique (solution de force brute O(n^2 ), envisagez d'utiliser deux pointeurs.

Code du modèle :

Modèle pour variation « direction opposée »

Python

 def two_pointers_opposite(arr): left = 0 right = len(arr) - 1 ans = 0 while left < right: # Perform logic using the left and right pointers if CONDITION: left += 1 else: right -= 1 return ans

JS

 function twoPointersOpposite(arr) { let left = 0; let right = arr.length - 1; let ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

Java

 public int twoPointersOpposite(int[] arr) { int left = 0; int right = arr.length - 1; int ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

4. Fenêtre coulissante

La technique de la fenêtre coulissante consiste à maintenir une fenêtre dynamique sur une structure de données linéaire, telle que des tableaux, des chaînes ou des listes chaînées. La taille de la fenêtre peut varier en fonction de l'implémentation spécifique et elle peut également être définie comme une valeur fixe. L'objectif principal de cette fenêtre est de surveiller et de capturer en permanence les données qui satisfont à des critères spécifiques, ce qui la rend particulièrement utile pour résoudre efficacement les problèmes de sous-réseaux ou de sous-chaînes.

Ce modèle utilise souvent une carte de hachage pour faciliter le suivi des données individuelles dans la fenêtre. Cependant, il est important de noter que cette approche peut entraîner une complexité spatio-temporelle de O(n) .

Indicateurs clef:

• Vous devez analyser des sous-tableaux ou des sous-chaînes contigus ou non contigus.
• Les problèmes impliquent le suivi de séquences de longueur variable au sein d’un ensemble de données plus vaste.
• Vous souhaitez trouver le sous-tableau de somme maximale de longueur fixe.
• L'entrée du problème est une structure de données linéaire telle qu'un tableau, une liste chaînée ou une chaîne.

Code du modèle :

Python

 def slidingWindow(nums): # Initialize necessary variables left = 0 window = [] # Initialize the window ans = 0 # Initialize the answer variable for right in range(len(nums)): window.append(nums[right]) # Expand the window to the right while invalid(window): # Condition to shrink the window from the left until it is valid again window.pop(0) # Remove the left element from the window left += 1 ans = max(ans, len(window)) # Update the answer, can vary on your implementation return ans

JS

 function slidingWindow(nums) { let left = 0; const window = []; // Initialize the window let ans = 0; // Initialize the answer variable for (let right = 0; right < nums.length; right++) { window.push(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.shift(); // Remove the left element from the window left++; } ans = Math.max(ans, window.length); // Update the answer , can vary on your implementation } return ans; }

Java

 public static int slidingWindow(int[] nums) { int left = 0; List<Integer> window = new ArrayList<>(); // Initialize the window int ans = 0; // Initialize the answer variable for (int right = 0; right < nums.length; right++) { window.add(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.remove(0); // Remove the left element from the window left++; } ans = Math.max(ans, window.size()); // Update the answer , can vary on your implementation } return ans; }

5. Principaux éléments K

Ce modèle implique de rechercher les K éléments les plus grands ou les plus petits d'une collection, souvent implémentés à l'aide de structures de données telles que des tas ou des files d'attente prioritaires. C'est utile pour sélectionner un sous-ensemble d'éléments en fonction de leur valeur ou de leur fréquence.

Chaque fois qu'on nous demande de trouver les éléments « K » les plus fréquents, les plus petits ou les plus importants dans un ensemble de données donné, nous pouvons envisager d'utiliser ce modèle.

La façon dont cela fonctionne est simple :

1. Nous insérons des éléments 'K' dans notre tas min ou max (cela dépend de l'implémentation).
2. Chaque fois que nous ajoutons à notre tas, nous devons nous ajuster de manière à ce qu'à tout moment les éléments « K » fréquents/les plus petits/les plus élevés soient conservés.

La beauté de cette approche réside dans son efficacité ; vous n'avez pas besoin de recourir à des algorithmes de tri, car le tas lui-même maintient naturellement l'ordre requis pour vous.

Indicateurs clef:

• Vous devez identifier les K éléments les plus grands ou les plus petits d’une collection.
• Les problèmes nécessitent de classer les éléments en fonction de certains critères.
• Vous souhaitez trouver les K principaux éléments fréquents dans un ensemble de données.

Code du modèle :

Python

 import heapq def top_k_elements(arr, k): heap = [] for num in arr: # Define your own criteria and logic to push elements onto the heap # For example, if you want to find the top k largest elements, push (-num, num) onto the heap heapq.heappush(heap, (-CRITERIA, num)) if len(heap) > k: heapq.heappop(heap) return [num for _, num in heap]

JS

 function topKElements(arr, k) { const minHeap = []; for (const num of arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k smallest elements, push num onto the heap minHeap.push(CRITERIA); if (minHeap.length > k) { minHeap.sort((a, b) => a - b).shift(); } } return minHeap.sort((a, b) => a - b); }

Java

 import java.util.*; public List<Integer> topKElements(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(a -> -CRITERIA)); for (int num : arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k largest elements, push -num onto the heap heap.offer(-CRITERIA); if (heap.size() > k) { heap.poll(); } } List<Integer> topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; }

6. Deux tas

Two Heaps utilise deux tas (un tas maximum et un tas min) pour optimiser certains problèmes, comme trouver des valeurs médianes dans un ensemble de données. Ce modèle est particulièrement utile pour maintenir une structure équilibrée.

Voici comment cela fonctionne:

1. Utilisez deux tas : un tas maximum pour identifier le plus grand élément et un tas min pour localiser le plus petit.
2. Remplissez le Max Heap avec la première moitié des nombres, dans le but de trouver le plus grand d'entre eux.
3. Remplissez le Min Heap avec la seconde moitié des nombres pour identifier le plus petit de cette partie.
4. La médiane de l'ensemble de nombres actuel peut être calculée à tout moment en examinant les éléments supérieurs des deux tas.

Indicateurs clef:

• Vous devez maintenir une structure équilibrée pour une recherche médiane efficace.
• Les problèmes impliquent la gestion des problèmes de fenêtre glissante avec des médianes dynamiques.
• Vous souhaitez hiérarchiser les éléments d'une collection en fonction de leurs valeurs.

Code du modèle :

Python

 import heapq class TwoHeaps: def __init__(self): self.min_heap = [] # Right heap to store larger half self.max_heap = [] # Left heap to store smaller half def add_num(self, num): if not self.max_heap or num <= -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) # Balance the heaps if necessary if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def find_median(self): if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return -self.max_heap[0] # Usage: two_heaps = TwoHeaps() two_heaps.add_num(1) two_heaps.add_num(2) median = two_heaps.find_median() print("Median:", median)

JS

 class TwoHeaps { constructor() { this.minHeap = []; // Right heap to store larger half this.maxHeap = []; // Left heap to store smaller half } addNumber(num) { if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) { this.maxHeap.push(-num); } else { this.minHeap.push(num); } // Balance the heaps if necessary if (this.maxHeap.length > this.minHeap.length + 1) { this.minHeap.push(-this.maxHeap.shift()); } else if (this.minHeap.length > this.maxHeap.length) { this.maxHeap.push(-this.minHeap.shift()); } } findMedian() { if (this.maxHeap.length === this.minHeap.length) { return (-this.maxHeap[0] + this.minHeap[0]) / 2; } else { return -this.maxHeap[0]; } } } // Usage: const twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); const median = twoHeaps.findMedian(); console.log("Median:", median);

Java

 import java.util.*; class TwoHeaps { private PriorityQueue<Integer> minHeap; // Right heap to store larger half private PriorityQueue<Integer> maxHeap; // Left heap to store smaller half public TwoHeaps() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Collections.reverseOrder()); } public void addNumber(int num) { if (maxHeap.isEmpty() || num <= -maxHeap.peek()) { maxHeap.offer(-num); } else { minHeap.offer(num); } // Balance the heaps if necessary if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(-maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(-minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (-maxHeap.peek() + minHeap.peek()) / 2.0; } else { return -maxHeap.peek(); } } } // Usage: TwoHeaps twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); double median = twoHeaps.findMedian(); System.out.println("Median: " + median);

7. Pile monotone

Monotonique - (d'une fonction ou d'une quantité) variant de telle manière qu'elle ne diminue jamais ou n'augmente jamais.

La pile monotonique maintient une pile d'éléments dans un ordre non croissant ou non décroissant, souvent utilisée pour trouver les éléments plus petits/plus proches les plus proches dans un tableau. C'est un outil puissant pour optimiser certains problèmes.

L'ordre est strict, chaque fois que nous rencontrons un élément qui est plus petit (ou plus grand) que ce qui se trouve en haut de la pile, nous devons alors sortir de la pile monotone jusqu'à ce que l'élément que nous cherchons à ajouter soit le plus petit (ou le plus grand) des eux.

Indicateurs clef:

• Vous devez conserver les éléments dans un ordre non croissant ou non décroissant.
• Les problèmes consistent à trouver l’élément le plus petit ou le plus grand le plus proche.
• Vous souhaitez optimiser les opérations basées sur la pile tout en préservant l'ordre.

Code du modèle :

Python

 def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] <= item: stack.pop() # Do something with the popped item here stack.append(item)

JS

 function monotonicStack(items) { const stack = []; for (const item of items) { // Adjust the condition for comparisons to suit your needs while (stack.length > 0 && stack[stack.length - 1] <= item) { stack.pop(); // Do something with the popped item here } stack.push(item); } return stack; }

Java

 import java.util.*; public static int[] monotonicStack(int[] items) { Deque<Integer> stack = new ArrayDeque<>(); for (int item : items) { // Adjust the condition for comparisons to suit your needs while (!stack.isEmpty() && stack.peekLast() <= item) { stack.pollLast(); // Do something with the popped item here } stack.offerLast(item); } int[] result = new int[stack.size()]; int i = stack.size() - 1; while (!stack.isEmpty()) { result[i--] = stack.pollLast(); } return result; }

8. Recherche en profondeur d'abord

DFS , ou Depth-First Search , est une méthode de traversée dans laquelle vous explorez aussi profondément que possible le long d'une branche avant de revenir en arrière ; il est largement appliqué aux problèmes impliquant des arbres et des graphiques, en particulier pour les opérations de parcours et de recherche.

Pour exécuter DFS sur une arborescence, vous devez commencer à la racine. Suivez ensuite les étapes ci-dessous :

1. Explorez le nœud actuel en visitant ses nœuds enfants, généralement de gauche à droite .
2. Appliquez de manière récursive le processus DFS à chaque nœud enfant, en approfondissant l'arborescence.
3. Une fois que tous les nœuds enfants ont été visités, revenez au nœud parent.
4. Répétez les étapes 1 à 3 pour chaque enfant non visité du nœud actuel jusqu'à ce que tous les nœuds de l'arborescence aient été visités.

Différence avec DFS sur un graphique : La principale différence entre DFS arborescent et DFS graphique réside dans la présence de cycles. Dans un arbre, il n'y a pas de cycles par définition, donc l'arbre DFS garantit que chaque nœud est visité exactement une fois, et il se termine naturellement lorsque l'arbre entier est parcouru. En revanche, le graphique DFS doit intégrer des mesures supplémentaires pour gérer les structures cycliques au sein d'un graphique. Pour éviter de revisiter indéfiniment les nœuds d'un cycle, le graphe DFS nécessite des mécanismes tels que le marquage des nœuds visités et la gestion appropriée du retour en arrière . Cette distinction rend le DFS graphique plus complexe que le DFS arborescent en raison du potentiel de boucles infinies en présence de cycles.

Indicateurs clef:

• Vous avez affaire à des structures arborescentes et devez explorer des ordres de parcours spécifiques.
• Les problèmes impliquent de trouver des chemins, de calculer la profondeur ou d'effectuer un parcours en pré-ordre/dans l'ordre/après-ordre.
• Vous souhaitez vérifier si un chemin existe entre deux nœuds.

Code du modèle :

Python

 def dfs(root, target): if root is None: # Base case: Check if the current node is None return None if root.val == target: # Base case: Check if the current node value matches the target return root left = dfs(root.left, target) # Recursively search the left subtree if left is not None: # If the target is found in the left subtree, return the result return left return dfs(root.right, target) # Recursively search the right subtree

JS

 function dfs(root, target) { if (root === null) { // Base case: Check if the current node is null return null; } if (root.val === target) { // Base case: Check if the current node value matches the target return root; } let left = dfs(root.left, target); // Recursively search the left subtree if (left !== null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

Java

 public TreeNode dfs(TreeNode root, int target) { if (root == null) { // Base case: Check if the current node is null return null; } if (root.val == target) { // Base case: Check if the current node value matches the target return root; } TreeNode left = dfs(root.left, target); // Recursively search the left subtree if (left != null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

9. Recherche en largeur

BFS est une technique de parcours pour les arbres et les graphiques qui explore tous les nœuds à la profondeur actuelle avant de passer au niveau suivant.

Pour exécuter BFS sur une arborescence, vous devez commencer à la racine. Suivez ensuite les étapes ci-dessous :

1. Initialisez une structure de données de file d'attente vide pour garder une trace des nœuds à visiter.

2. Mettez le nœud racine dans la file d'attente.

3. Entrez une boucle jusqu'à ce que la file d'attente soit vide :

   1. Retirez le nœud en tête de la file d'attente.
   2. Traitez le nœud retiré de la file d'attente (par exemple, visitez-le ou effectuez une opération dessus).
   3. Mettez en file d'attente tous les enfants du nœud (le cas échéant) dans la file d'attente.

4. Répétez les étapes 3a à 3c jusqu'à ce que la file d'attente soit vide.

5. Le parcours BFS est terminé lorsque tous les nœuds de l'arborescence ont été visités par niveau, de gauche à droite.

Essentiellement, BFS sur un arbre explore les nœuds niveau par niveau , en commençant par la racine et en passant aux enfants avant de passer au niveau suivant. Cela garantit que les nœuds de chaque niveau sont visités avant de passer au niveau suivant, ce qui le rend particulièrement utile pour des tâches telles que la recherche du chemin le plus court dans un arbre non pondéré ou l'exploration d'un arbre niveau par niveau.

Différence avec BFS sur un graphique : Semblable à DFS, Graph BFS s'adapte à la présence de cycles et de chemins multiples entre les nœuds. Il utilise des mécanismes tels que le marquage des nœuds visités et des conditions de terminaison spécialisées pour naviguer efficacement dans le réseau complexe de relations au sein des graphiques.

Indicateurs clef:

• Vous devez parcourir un arbre niveau par niveau.
• Les problèmes consistent à trouver le chemin le plus court dans des graphiques non pondérés.
• Vous souhaitez explorer un arbre ou un graphique en profondeur.

Code du modèle :

Python

 from collections import deque def bfs(root): # Create a queue and initialize it with the root node queue = deque([root]) # Perform breadth-first search until the queue is empty while len(queue) > 0: # Dequeue the front node from the queue node = queue.popleft() # Process the current node for child in node.children: if is_goal(child): # If the goal condition is satisfied, return the child node return FOUND(child) # Enqueue the child node to explore it in the next iterations queue.append(child) # Return NOT_FOUND if the goal is not reached return NOT_FOUND

JS

 function bfs(root) { const queue = []; // Create a queue and initialize it with the root node queue.push(root); while (queue.length > 0) { // Perform breadth-first search until the queue is empty const node = queue.shift(); // Dequeue the front node from the queue for (const child of node.children) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return `FOUND ${child}`; } queue.push(child); // Enqueue the child node to explore it in the next iterations } } return 'NOT_FOUND'; // Return NOT_FOUND if the goal is not reached }

Java

 import java.util.LinkedList; import java.util.Queue; public String bfs(Node root) { Queue<Node> queue = new LinkedList<>(); // Create a queue and initialize it with the root node queue.offer(root); while (!queue.isEmpty()) { // Perform breadth-first search until the queue is empty Node node = queue.poll(); // Dequeue the front node from the queue for (Node child : node.getChildren()) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return "FOUND(child)"; } queue.offer(child); // Enqueue the child node to explore it in the next iterations } } return "NOT_FOUND"; // Return NOT_FOUND if the goal is not reached }

10. Recherche d'union (Union à ensemble disjoint)

La structure de données Union-Find , également connue sous le nom de Disjoint Set Union (DSU) , est utilisée pour gérer et résoudre efficacement des problèmes impliquant des ensembles disjoints ou des composants connectés. Il fournit des opérations pour fusionner des ensembles (union) et déterminer l'ensemble auquel appartient un élément (trouver). Union-Find est couramment utilisé dans des algorithmes tels que l'arbre couvrant minimum de Kruskal et la détection de cycles dans les graphiques.

Union Find est implémenté comme suit :

1. Initialisation : commencez par une collection d'éléments, chacun étant considéré comme un ensemble disjoint distinct. Attribuez un représentant unique (souvent l'élément lui-même) à chaque ensemble.
2. Opération d'union : pour fusionner deux ensembles, effectuez l'opération d'union. Choisissez le représentant d'un ensemble (souvent en fonction de certains critères, comme le rang ou la taille) et faites-en le parent du représentant de l'autre ensemble. Cela relie efficacement les deux ensembles.
3. Opération de recherche : lorsque vous devez déterminer l’ensemble auquel appartient un élément, utilisez l’opération de recherche. En commençant par l'élément en question, parcourez l'arbre vers le haut pour trouver le nœud racine (représentatif) de son ensemble. La technique de compression de chemin peut être appliquée ici pour optimiser les futures opérations de recherche en faisant en sorte que les éléments le long du chemin pointent directement vers la racine.
4. Détection de cycles : Union-Find est souvent utilisé pour détecter des cycles dans les graphiques. Lors de l'opération d'union, si les deux éléments appartiennent au même ensemble (c'est-à-dire qu'ils ont le même représentant), cela indique que l'ajout d'une arête entre les nœuds créerait un cycle dans le graphique.
5. Optimisation : diverses techniques d'optimisation peuvent être appliquées pour améliorer l'efficacité des opérations Union-Find, telles que l'union par rang et la compression de chemin.

Code du modèle :

Python

 class UnionFind: def __init__(self): self.id = {} def find(self, x): y = self.id.get(x, x) if y != x: self.id[x] = y = self.find(y) return y def union(self, x, y): self.id[self.find(x)] = self.find(y)

JS

 class UnionFind { constructor() { this.id = {}; } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @returns The root parent of the element. */ find(x) { let y = this.id[x] || x; if (y !== x) { this.id[x] = y = this.find(y); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ union(x, y) { this.id[this.find(x)] = this.find(y); } }

Java

 import java.util.*; class UnionFind { private Map<String, String> id; public UnionFind() { id = new HashMap<>(); } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @return The root parent of the element. */ public String find(String x) { String y = id.getOrDefault(x, x); if (!y.equals(x)) { id.put(x, find(y)); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ public void union(String x, String y) { id.put(find(x), find(y)); } }

11. Tri topologique

Un graphe acyclique orienté (DAG) est un graphe orienté sans cycles orientés.

Le tri topologique est un algorithme permettant d'organiser les nœuds d'un graphe acyclique orienté ( DAG ) dans un ordre linéaire, où chaque nœud apparaît avant ses successeurs. Il est crucial pour des tâches telles que la planification des dépendances, la compilation du code et l'analyse de la priorité des tâches dans diverses applications.

Voici une présentation étape par étape du tri topologique :

1. Initialisation : commencez par un graphe acyclique dirigé ( DAG ) qui représente des tâches ou des nœuds avec des dépendances. Initialisez une file d'attente pour contenir les nœuds triés.

2. Calcul en degré : calculez le degré en degré (le nombre d'arêtes entrantes) pour chaque nœud du graphique. Les nœuds avec un degré d'entrée de 0 n'ont aucune dépendance et peuvent être le point de départ du tri topologique.

3. Remplissage initial de la file d'attente : mettez en file d'attente tous les nœuds avec un degré d'entrée de 0 dans la file d'attente. Ces nœuds peuvent être traités en premier.

4. Boucle de tri topologique : tant que la file d'attente n'est pas vide, effectuez les étapes suivantes :

   1. Retirez un nœud de la file d'attente du début de la file d'attente.
   2. Traitez le nœud (par exemple, ajoutez-le à la liste triée).
   3. Pour chacun des voisins du nœud (nœuds vers lesquels il pointe), décrémentez leur degré d'entrée de 1.
   4. Si le degré d'entrée d'un voisin devient 0 à la suite de la décrémentation, mettez-le dans la file d'attente.

5. Achèvement : une fois la boucle de tri topologique terminée, la file d'attente sera vide et la liste triée contiendra tous les nœuds dans un ordre topologique valide.

6. Détection de cycle : si à un moment donné du processus de tri topologique, il n'y a plus de nœuds avec un degré entrant de 0 dans la file d'attente, cela indique la présence de cycles dans le graphique, rendant le tri topologique impossible.

Le résultat du tri topologique est un ordre linéaire des nœuds qui respecte leurs dépendances, ce qui le rend adapté à la planification de tâches ou à l'analyse de l'ordre d'exécution dans diverses applications.

Indicateurs clef:

• Le problème implique la planification ou l’ordonnancement de tâches avec des dépendances.
• Vous travaillez avec un graphe acyclique orienté (DAG).
• Les tâches doivent être exécutées dans un ordre spécifique tout en respectant leurs dépendances.

Code du modèle :

Python

 from collections import deque def find_indegree(graph): # Calculate the indegree of each node in the graph indegree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 return indegree def topological_sort(graph): result = [] queue = deque() indegree = find_indegree(graph) # Add nodes with 0 indegree to the queue for node in indegree: if indegree[node] == 0: queue.append(node) while queue: node = queue.popleft() result.append(node) # Update the indegree of neighboring nodes for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # If all nodes are visited, return the result if len(graph) == len(result): return result else: return None

JS

 /** * Finds the indegree of each node in the graph. * @param {object} graph - The input graph. * @returns {object} - The indegree of each node. */ function findIndegree(graph) { const indegree = {}; for (const node in graph) { indegree[node] = 0; } for (const node in graph) { for (const neighbor of graph[node]) { indegree[neighbor]++; } } return indegree; } /** * Performs topological sorting on the given graph. * @param {object} graph - The input graph. * @returns {array|null} - The sorted nodes in topological order or null if a cycle is detected. */ function topologicalSort(graph) { const result = []; const queue = []; const indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (const node in indegree) { if (indegree[node] === 0) { queue.push(node); } } while (queue.length > 0) { const node = queue.shift(); result.push(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (const neighbor of graph[node]) { indegree[neighbor]--; if (indegree[neighbor] === 0) { queue.push(neighbor); } } } // Check if all nodes have been visited (no cycles) if (Object.keys(graph).length === result.length) { return result; } else { return null; } }

Java

 import java.util.*; /** * Finds the indegree of each node in the graph. * @param graph - The input graph. * @return The indegree of each node. */ public Map<String, Integer> findIndegree(Map<String, List<String>> graph) { Map<String, Integer> indegree = new HashMap<>(); for (String node : graph.keySet()) { indegree.put(node, 0); } for (String node : graph.keySet()) { for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1); } } return indegree; } /** * Performs topological sorting on the given graph. * @param graph - The input graph. * @return The sorted nodes in topological order or null if a cycle is detected. */ public List<String> topologicalSort(Map<String, List<String>> graph) { List<String> result = new ArrayList<>(); Queue<String> queue = new LinkedList<>(); Map<String, Integer> indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (String node : indegree.keySet()) { if (indegree.get(node) == 0) { queue.offer(node); } } while (!queue.isEmpty()) { String node = queue.poll(); result.add(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); } } } // Check if all nodes have been visited (no cycles) if (graph.size() == result.size()) { return result; } else { return null; } }

12. Essais (Préfixe-Arbre)

Un Trie est une structure de données arborescente utilisée pour une correspondance efficace des chaînes et le stockage des mots. Il excelle dans les problèmes où vous devez stocker et rechercher des chaînes avec des préfixes communs.

Voici comment implémenter un Trie :

1. Initialisation : commencez par un Trie vide, qui consiste généralement en un nœud racine sans caractère associé.

2. Insertion : pour insérer un mot dans le Trie, commencez par le nœud racine et parcourez l'arborescence, un caractère à la fois. Pour chaque caractère du mot :

   1. Vérifiez si un nœud enfant avec ce caractère existe sous le nœud actuel.
   2. Si tel est le cas, passez au nœud enfant.
   3. Sinon, créez un nouveau nœud enfant avec le personnage et déplacez-vous vers celui-ci.

3. Achèvement de mots : pour vérifier si un mot existe dans le Trie, parcourez-le d'une manière similaire à l'insertion. Assurez-vous que chaque caractère du mot correspond à un nœud enfant du nœud actuel. Si le parcours atteint la fin du mot et qu'il existe un marqueur de fin valide (par exemple, un indicateur booléen) au dernier nœud de caractère, le mot existe dans le Trie.

4. Recherche de préfixe : Trie excelle dans la recherche de préfixe. Pour trouver tous les mots avec un préfixe donné, démarrez le parcours au nœud racine et descendez dans l'arborescence en suivant les caractères du préfixe. Une fois que vous avez atteint le dernier caractère du préfixe, vous pouvez effectuer une recherche en profondeur (DFS) à partir de ce nœud pour trouver tous les mots partageant le même préfixe.

5. Suppression : Pour supprimer un mot du Trie, effectuez une recherche du mot. Lorsque vous atteignez la fin du mot, supprimez le marqueur de fin (s'il existe). Si le nœud n'a pas d'autres enfants, vous pouvez supprimer en toute sécurité la branche entière du Trie, qui représente le mot.

Les essais peuvent être gourmands en mémoire, en particulier pour les vocabulaires volumineux. Pour optimiser la mémoire, des techniques telles que la compression (par exemple, utiliser une carte au lieu d'un tableau de caractères dans chaque nœud) et l'élagage (supprimer les nœuds sans descendants) peuvent être appliquées.

Les essais sont particulièrement utiles pour une correspondance efficace des chaînes, des suggestions de saisie semi-automatique, des correcteurs orthographiques et des mots d'indexation avec des préfixes communs. Ils offrent un moyen rapide et peu encombrant de stocker et de rechercher des mots ou des chaînes avec des préfixes partagés dans une structure arborescente.

Indicateurs clef:

• Vous avez affaire à des chaînes et avez besoin d'une correspondance de chaînes efficace.
• Les problèmes impliquent des suggestions de saisie semi-automatique, des correcteurs orthographiques ou la recherche de mots avec des préfixes communs.
• Vous souhaitez stocker et rechercher des mots efficacement.

Code du modèle :

Python

 class TrieNode: def __init__(self, value): self.value = value self.children = {} def insert(self, s, idx): # idx: index of the current character in s if idx != len(s): self.children.setdefault(s[idx], TrieNode(s[idx])) self.children.get(s[idx]).insert(s, idx + 1)

JS

 class TrieNode { constructor(value) { this.value = value; this.children = {}; } insert(s, idx) { // idx: index of the current character in s if (idx !== s.length) { if (!this.children[s[idx]]) { this.children[s[idx]] = new TrieNode(s[idx]); } this.children[s[idx]].insert(s, idx + 1); } } }

Java

 import java.util.*; class TrieNode { char value; Map<Character, TrieNode> children; TrieNode(char value) { this.value = value; this.children = new HashMap<>(); } void insert(String s, int idx) { // idx: index of the current character in s if (idx != s.length()) { char c = s.charAt(idx); if (!children.containsKey(c)) { children.put(c, new TrieNode(c)); } children.get(c).insert(s, idx + 1); } } }

13. Programmation dynamique

La programmation dynamique est une technique puissante de résolution de problèmes utilisée en informatique et en mathématiques pour résoudre efficacement un large éventail de problèmes complexes. Cela est particulièrement utile lorsqu’un problème peut être décomposé en sous-problèmes plus simples et que les solutions à ces sous-problèmes peuvent être combinées pour résoudre le problème global.

Voici ses principales caractéristiques et son fonctionnement :

Sous-structure optimale :

• Cette caractéristique fait référence à la propriété selon laquelle une solution optimale à un problème plus vaste peut être construite à partir de solutions optimales à ses sous-problèmes plus petits.
• En d’autres termes, les problèmes DP présentent une structure récursive, dans laquelle la solution optimale d’un problème repose sur les solutions optimales de ses sous-problèmes.
• Par exemple, pour trouver le chemin le plus court entre deux points dans un graphique, le chemin le plus court entre deux points intermédiaires doit également être optimal.

Sous-problèmes qui se chevauchent :

• Des sous-problèmes qui se chevauchent se produisent lorsque les mêmes sous-problèmes sont résolus plusieurs fois au cours du calcul, conduisant à un travail redondant.
• La Programmation Dynamique vise à résoudre ce problème en stockant les solutions aux sous-problèmes dans une structure de données (souvent une table ou un tableau de mémorisation) pour éviter de les recalculer.
• Ce stockage et cette réutilisation des solutions de sous-problèmes réduisent considérablement la complexité temporelle de l'algorithme.

Comment fonctionne la programmation dynamique :

1. Identifier les sous-problèmes : la première étape pour résoudre un problème à l'aide de DP consiste à identifier les sous-problèmes. Décomposez le problème en sous-problèmes plus petits et gérables qui, une fois résolus, contribuent à résoudre le problème principal.
2. Solution récursive : développer une solution récursive qui exprime la solution d'un problème plus vaste en termes de solutions à des sous-problèmes plus petits. Cette formulation récursive capture la sous-structure optimale.
3. Mémorisation ou tabulation : pour résoudre des sous-problèmes qui se chevauchent, vous pouvez choisir entre deux techniques courantes :
   • Mémorisation : stockez les résultats des sous-problèmes dans une structure de données (généralement un tableau ou une table de hachage) au fur et à mesure de leur calcul. Lorsqu'un sous-problème se reproduit, récupérez sa solution dans le stockage au lieu de la recalculer. C’est ce qu’on appelle également l’approche descendante .
   • Tabulation : créez un tableau (souvent un tableau 2D) pour stocker les solutions aux sous -problèmes de manière ascendante . Commencez par résoudre les plus petits sous-problèmes et progressez progressivement jusqu'au problème principal.
4. Solution optimale : Une fois tous les sous-problèmes résolus, la solution du problème principal peut être obtenue en combinant les solutions de ses sous-problèmes selon la structure récursive du problème.

La programmation dynamique est appliquée à un large éventail de problèmes, notamment la recherche des chemins les plus courts dans les graphiques, l'optimisation de l'allocation des ressources, le comptage des combinaisons, la résolution de problèmes de sac à dos et bien plus encore. Sa capacité à optimiser des solutions en décomposant des problèmes complexes en parties plus simples et en évitant les calculs redondants en fait une technique fondamentale dans la conception et l’optimisation d’algorithmes.

Concepts importants : approche ascendante, descendante, mémorisation, tabulation

Indicateurs clef:

• Le problème peut être décomposé en sous-problèmes plus petits qui se chevauchent.
• Il est nécessaire d'optimiser en stockant et en réutilisant les solutions aux sous-problèmes.
• Vous souhaitez résoudre des problèmes d’optimisation ou de comptage.

Code du modèle :

Le modèle de mémorisation descendante est l’une des nombreuses façons de mettre en œuvre une programmation dynamique.

Python

 def top_down_memo(arr): def dp(state): # Base case(s): Define your own base case(s) for the problem if base_case: return 0 # Check if the state has already been memoized if state in memo: return memo[state] # Calculate the result using recurrence relation and memoize it result = recurrence_relation(state) memo[state] = result return result memo = {} # Memoization table to store calculated results return dp(initial_state)

JS

 function topDownMemo(arr) { function dp(state) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.has(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it const result = recurrenceRelation(state); memo.set(state, result); return result; } const memo = new Map(); // Memoization map to store calculated results return dp(initialState); }

Java

 import java.util.HashMap; import java.util.Map; public int topDownMemo(int[] arr) { Map<StateType, Integer> memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map<StateType, Integer> memo) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.containsKey(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it int result = recurrenceRelation(state); memo.put(state, result); return result; }

14. Retour en arrière

Le backtracking est une technique algorithmique générale permettant de résoudre des problèmes de manière incrémentale en essayant différentes possibilités et en les annulant si elles ne conduisent pas à une solution. Il est utilisé lorsqu'une recherche exhaustive est requise.

Voici un aperçu détaillé du fonctionnement du backtracking :

1. Exploration de l'espace du problème : le retour en arrière explore l'espace du problème en construisant progressivement une solution, une pièce à la fois. A chaque étape, il prend une décision et avance.
2. Structure récursive : le retour en arrière implique souvent une récursion. Il commence par une solution partielle initiale et explore toutes les manières possibles de l’étendre. Ce processus se poursuit de manière récursive jusqu'à ce qu'une solution complète soit trouvée ou qu'il devienne évident qu'aucune solution valide n'existe.
3. Points de décision : à chaque étape, il existe des points de décision où l'algorithme doit choisir parmi les options disponibles. Ces choix conduisent à des ramifications dans le processus d’exploration.
4. Validation de la solution : après avoir fait un choix, l'algorithme vérifie si la solution partielle actuelle est valide. S'il est valide, l'algorithme passe à l'étape suivante. Dans le cas contraire, il revient en arrière, annulant le choix précédent et explorant d'autres options.
5. Conditions de résiliation : le retour en arrière se poursuit jusqu'à ce que l'une des deux conditions suivantes soit remplie :
   • Une solution valide est trouvée, auquel cas l'algorithme s'arrête et renvoie la solution.
   • Il est déterminé qu’aucune solution valide n’existe, auquel cas l’algorithme revient à un point de décision précédent et explore différentes options.
6. Élagage : pour optimiser la recherche, le retour en arrière inclut souvent des stratégies d'élagage. L'élagage consiste à éviter l'exploration de chemins qui mèneront à coup sûr à des solutions invalides, réduisant ainsi considérablement l'espace de recherche.

Applications du retour en arrière :

Le backtracking est utilisé dans divers domaines problématiques, notamment :

• Résoudre des énigmes comme Sudoku et N-Queens.
• Générer des permutations et des combinaisons.
• Recherche de chemins dans des graphiques et des arbres.
• Problèmes de satisfaction de contraintes (par exemple, le problème du voyageur de commerce).
• Algorithmes de jeu (par exemple, l'IA des échecs).

Indicateurs clef:

• Le problème consiste à explorer progressivement plusieurs possibilités.
• Il existe des points de décision ou des contraintes qui nécessitent d’essayer différentes options.
• Il vous faut trouver toutes les solutions possibles ou satisfaire des conditions précises grâce à une recherche exhaustive.

Code du modèle :

Python

 def backtrack(curr, OTHER_ARGUMENTS...): if BASE_CASE: # Modify the answer according to the problem's requirements return ans = 0 for ITERATE_OVER_INPUT: # Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS...) # Undo the modification of the current state (backtrack) return ans

JS

 function backtrack(curr, ...OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } let ans = 0; for (let i = 0; i < ITERATE_OVER_INPUT.length; i++) { const item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, ...OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

Java

 public int backtrack(StateType curr, OtherArgumentType... OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } int ans = 0; for (int i = 0; i < ITERATE_OVER_INPUT.length; i++) { ItemType item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

15. Fusionner les intervalles

La fusion d'intervalles consiste à combiner des intervalles qui se chevauchent ou adjacents dans un ensemble consolidé, souvent utilisé dans les problèmes impliquant des intervalles de temps ou une planification. Il simplifie les opérations basées sur des intervalles.

Voici un aperçu plus détaillé du fonctionnement de la fusion des intervalles :

1. Représentation des intervalles : les intervalles sont généralement représentés sous forme de paires de points de début et de fin (par exemple, [start, end] ).
2. Tri : pour fusionner efficacement les intervalles, commencez par les trier en fonction de leurs points de départ. Cela garantit que les intervalles superposés ou adjacents sont adjacents dans la liste triée.
3. Processus de fusion : initialisez une liste vide pour contenir les intervalles fusionnés. Ensuite, parcourez les intervalles triés un par un :
   • Si l'intervalle actuel ne chevauche pas le précédent, ajoutez-le à la liste des intervalles fusionnés.
   • S'il y a un chevauchement, mettez à jour le point de terminaison de l'intervalle fusionné précédent pour englober à la fois les intervalles actuels et précédents, en les fusionnant efficacement.
4. Achèvement : après avoir traité tous les intervalles, la liste des intervalles fusionnés contiendra des intervalles non chevauchants et consolidés.

Applications des intervalles de fusion :

Les intervalles de fusion sont couramment utilisés dans :

• Applications de planification et de gestion du temps.
• Détection d'événements qui se chevauchent dans les systèmes de calendrier.
• Analyse de données basée sur des intervalles, comme dans les requêtes de base de données.
• Résoudre les problèmes liés à l'allocation des ressources et à la planification des réunions.

En fusionnant des intervalles qui se chevauchent, cette technique simplifie les opérations basées sur des intervalles et améliore l'efficacité dans diverses applications.

Indicateurs clef:

• Vous avez affaire à des intervalles ou à des données temporelles.
• Les problèmes impliquent la fusion d’intervalles superposés ou adjacents.
• Vous souhaitez simplifier les opérations basées sur des intervalles ou optimiser la planification d'événements.

Code du modèle :

Python

 def merge_intervals(intervals): # 1. Sort the intervals based on their start values. intervals.sort(key=lambda x: x[0]) # 2. Initialize an empty list to store merged intervals. merged_intervals = [] # 3. Iterate through the sorted intervals. for interval in intervals: # 4. If the merged_intervals list is empty or the current interval does not overlap with the last merged interval: if not merged_intervals or interval[0] > merged_intervals[-1][1]: merged_intervals.append(interval) else: # 5. If the current interval overlaps with the last merged interval, merge them. merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1]) # 6. Return the merged_intervals list. return merged_intervals

JS

 function mergeIntervals(intervals) { // 1. Sort the intervals based on their start values. intervals.sort((a, b) => a[0] - b[0]); // 2. Initialize an empty array to store merged intervals. const mergedIntervals = []; // 3. Iterate through the sorted intervals. for (const interval of intervals) { // 4. If the mergedIntervals array is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.length === 0 || interval[0] > mergedIntervals[mergedIntervals.length - 1][1]) { mergedIntervals.push(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]); } } // 6. Return the mergedIntervals array. return mergedIntervals; }

Java

 public class MergeIntervals { public int[][] merge(int[][] intervals) { // 1. Sort the intervals based on their start values. Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. Create a list to store merged intervals. List<int[]> mergedIntervals = new ArrayList<>(); // 3. Iterate through the sorted intervals. for (int[] interval : intervals) { // 4. If the mergedIntervals list is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.isEmpty() || interval[0] > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]); } } // 6. Convert the list to an array and return it. return mergedIntervals.toArray(new int[mergedIntervals.size()][]); } }

Vous voulez en savoir plus ?

Si vous souhaitez en savoir plus sur ces modèles et comment les mettre en œuvre plus efficacement lors de votre prochain entretien de codage, consultez techinterviews.io dès aujourd'hui ! Nous proposons un programme complet pour vous préparer à votre prochain entretien de codage, couvrant des sujets tels que les structures de données , les algorithmes , les entretiens comportementaux et même la négociation salariale . Nous disposons même d’un espace de travail de codage intégré pour que vous puissiez vous entraîner.

Boostez votre préparation à un entretien de codage dès aujourd'hui avec notre code promotionnel TECH30 pour 30 $ de réduction !