Patrones de codificación: un enfoque más inteligente para la preparación de entrevistas de codificación

Prepararse para entrevistas de codificación puede ser un verdadero desafío, ya que los desarrolladores suelen pasar varias semanas revisando y aprendiendo material nuevo.

La verdad es que la mayoría de los desarrolladores nunca se sienten completamente preparados para sus entrevistas de codificación. No es raro que los desarrolladores pasen semanas resolviendo problemas en LeetCode y todavía no se sientan preparados. Claramente, hay problemas con este enfoque.

Echemos un vistazo más de cerca a algunos problemas asociados con la preparación tradicional de entrevistas de codificación.

Los peligros de la preparación tradicional para entrevistas

Uno de los errores más comunes en la preparación tradicional de una entrevista es la práctica de "pulir". Este enfoque implica resolver tantos problemas de LeetCode como sea posible sin un plan o estrategia claro. Si bien esto puede parecer una estrategia productiva, tiene varios inconvenientes.

Cuando resuelves problemas sin un enfoque estructurado, es posible que no reconozcas tus debilidades. No existe un plan deliberado para su estudio; el objetivo es simplemente resolver tantos problemas como puedas. Como resultado, es posible que sienta que ha aprendido mucho, pero podría haber lagunas importantes en su conocimiento.

Además, el problema con esto es que esencialmente gira en torno a memorizar soluciones a una multitud de problemas. Intentar recordar soluciones a cien problemas de codificación diferentes resulta ineficaz cuando los entrevistadores presentan preguntas que se desvían aunque sea ligeramente de lo que se ha encontrado antes. Esto puede hacer que usted se sienta no preparado para manejar las variaciones del problema.

Mi último problema con esta estrategia es que, a largo plazo, genera más estrés y dolores de cabeza. Si tienes que someterte a la misma sesión de estudio de varias semanas de duración cada vez que quieres cambiar de trabajo, siempre tendrás dificultades. Pasarás semanas reaprendiendo cosas y resolviendo los mismos problemas que antes.

Ante estos desafíos, tiene que haber una mejor manera.

Una mejor manera: adoptar patrones de codificación

Entonces, ¿existe un enfoque más eficaz y sostenible para codificar la preparación de entrevistas? La respuesta está en comprender y utilizar patrones de codificación.

Cuando me preparo para entrevistas de codificación, doy prioridad a comprender los patrones subyacentes de los problemas. Estos patrones, que incluyen técnicas como dos punteros , ventana deslizante , búsqueda binaria modificada , clasificación topológica y muchas más, proporcionan un marco versátil y potente para abordar una amplia gama de problemas de codificación. El énfasis pasa de memorizar soluciones a técnicas comprobadas de resolución de problemas.

Al centrarse en los patrones de codificación, puede optimizar significativamente la preparación de su entrevista, haciéndola más eficiente.

Recuerde, prepárese de manera más inteligente, no más difícil.

¿Que esperar?

En este artículo, he recopilado el Los 15 mejores patrones de codificación que necesita saber para responder cualquier pregunta de codificación. Explicaré qué es cada patrón y cómo funciona. Comparta indicadores clave para ayudarlo a identificar el patrón y, finalmente, ofrezca gráficos detallados con código de plantilla para ayudarlo a solidificar su comprensión.

Si bien cubro mucho en este artículo, si desea capacitación, explicaciones y práctica de codificación más detalladas, puede consultar nuestro curso integral de preparación para entrevistas de codificación en Techinterviews.io. También cubrimos temas cruciales como estructuras de datos , entrevistas de comportamiento e incluso negociación salarial .

Ahora profundicemos en estos patrones de codificación.

1. Inversión de lista enlazada

La inversión de lista vinculada implica cambiar la dirección de los punteros en una lista vinculada para invertir el orden de los elementos. Es una operación fundamental en las estructuras de datos y, a menudo, requiere una manipulación cuidadosa de las referencias de los nodos.

Esto es útil cuando se trata de una lista vinculada y la restricción es revertirla en su lugar.

El proceso para revertir una lista vinculada es el siguiente:

1. Comience definiendo tres variables: actual , anterior y siguiente . Establezca actual como encabezado de la lista vinculada e inicialice el anterior y el siguiente como Ninguno.

2. Mientras la variable actual no sea Ninguna , proceda de la siguiente manera:

   1. Almacene el siguiente nodo en una variable temporal.
   2. Invierta el puntero del nodo actual para que apunte al nodo anterior .
   3. Actualice el anterior para que sea el nodo actual y el actual para que sea el siguiente nodo.

3. Finalmente, establezca el encabezado de la lista invertida en el último nodo alcanzado, que se almacena en la variable anterior .

Indicadores clave:

• Debe invertir el orden de los elementos en una lista vinculada.
• Los problemas implican la búsqueda de palíndromos en listas enlazadas.
• Quiere invertir el orden de los elementos en una sublista específica dentro de la lista.

Código de plantilla:

Pitón

 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. Búsqueda binaria modificada

La búsqueda binaria modificada adapta el algoritmo de búsqueda binaria clásico para resolver varios problemas. Las variaciones incluyen encontrar la primera/última aparición de un elemento o buscar en matrices rotadas. Requiere un manejo cuidadoso de los puntos medios y las condiciones.

Si alguna vez recibe una matriz ordenada, una lista vinculada o una matriz, considere utilizar una búsqueda binaria modificada .

A continuación se muestra un desglose de cómo aplicar este patrón a una estructura de datos ordenada:

1. Comience identificando el punto medio entre las posiciones inicial y final . Para evitar un posible desbordamiento de enteros, es más seguro calcular el medio de la siguiente manera: middle = start + (end - start) / 2 .
2. Compruebe si la clave coincide con el elemento en el índice medio . Si es así, devuelve el índice medio como resultado.
3. Si la clave no coincide con el elemento en el índice medio , continúe con los siguientes pasos.
4. Evalúe si la clave es menor que el elemento en el índice medio . Si es así, limite su rango de búsqueda actualizando end to middle - 1 .
5. Por el contrario, si la clave es mayor que el elemento en el índice middle , ajuste su rango de búsqueda actualizando start a middle + 1 .

Indicadores clave:

• Estás trabajando con una estructura de datos ordenada.
• Necesita encontrar elementos, límites o puntos de pivote específicos de manera eficiente.
• Los problemas implican la búsqueda en matrices ordenadas rotadas.

Código de plantilla:

Pitón

 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. Dos consejos

La técnica de dos punteros implica mantener dos punteros que atraviesan una estructura de datos, generalmente matrices o listas vinculadas, que a menudo se utilizan para problemas que involucran pares o submatrices. Optimiza problemas que requieren comparación entre elementos en diferentes posiciones.

La ventaja de esta técnica radica en su simplicidad y eficiencia, especialmente cuando se trata de estructuras de datos lineales como matrices o cadenas en las que inicialmente se puede usar un solo puntero. Al emplear dos punteros, puede evitar operaciones redundantes y mejorar significativamente la eficiencia del tiempo de ejecución, reduciéndola potencialmente de O(n^2) a O(n) .

El patrón "Dos punteros" abarca varias variaciones, cada una adaptada a escenarios específicos. Estas variaciones incluyen la misma dirección , la dirección opuesta y un método único conocido como "rápido y lento", a menudo denominado técnica de "tortuga y liebre" , que involucra dos punteros que se mueven a diferentes velocidades a través de una estructura de datos, particularmente útil para detectar ciclos.

Si emplea varios punteros para recorrer una estructura de datos, puede categorizar su enfoque siguiendo el patrón "Dos punteros" .

Indicadores clave:

• Necesita comparar u operar elementos en diferentes posiciones.
• Los problemas requieren buscar pares de elementos en una matriz ordenada.
• Quiere eliminar duplicados de una matriz ordenada de manera eficiente.
• Cuando se trata de estructuras de datos lineales (matrices, cadenas o listas enlazadas) y se enfrenta a una complejidad de tiempo cuadrática (solución de fuerza bruta O(n^2) ,), considere emplear dos punteros.

Código de plantilla:

Plantilla para variación de “dirección opuesta”

Pitón

 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. Ventana corrediza

La técnica de ventana deslizante implica mantener una ventana dinámica sobre una estructura de datos lineal, como matrices, cadenas o listas vinculadas. El tamaño de la ventana puede variar según la implementación específica y también se puede establecer como un valor fijo. El objetivo principal de esta ventana es monitorear y capturar continuamente datos que satisfagan criterios específicos, lo que la hace particularmente valiosa para resolver eficientemente problemas de subarreglos o subcadenas.

Este patrón suele utilizar un mapa hash para facilitar el seguimiento de datos individuales dentro de la ventana. Sin embargo, es importante tener en cuenta que este enfoque puede dar como resultado una complejidad espacio-temporal de O(n) .

Indicadores clave:

• Necesita analizar subarreglos o subcadenas contiguos o no contiguos.
• Los problemas implican el seguimiento de secuencias de longitud variable dentro de un conjunto de datos más grande.
• Quiere encontrar el subarreglo de suma máxima de longitud fija.
• La entrada del problema es una estructura de datos lineal, como una matriz, una lista enlazada o una cadena.

Código de plantilla:

Pitón

 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. Elementos K principales

Este patrón implica encontrar los K elementos más grandes o más pequeños en una colección, a menudo implementado utilizando estructuras de datos como montones o colas de prioridad. Es útil para seleccionar un subconjunto de elementos en función de su valor o frecuencia.

Cada vez que se nos pide que encontremos los elementos 'K' más frecuentes, más pequeños o superiores dentro de un conjunto de datos determinado, podemos considerar usar este patrón.

La forma en que funciona es simple:

1. Insertamos elementos 'K' en nuestro montón mínimo o máximo (esto depende de la implementación).
2. Cada vez que agregamos a nuestro montón debemos ajustarlo para que en todo momento se mantengan los elementos 'K' frecuentes/más pequeños/superiores.

La belleza de este enfoque reside en su eficiencia; no necesita recurrir a ningún algoritmo de clasificación, ya que el montón mismo mantiene naturalmente el orden requerido por usted.

Indicadores clave:

• Debe identificar los K elementos más grandes o más pequeños de una colección.
• Los problemas requieren clasificar elementos según ciertos criterios.
• Quiere encontrar los K elementos más frecuentes en un conjunto de datos.

Código de plantilla:

Pitón

 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. Dos montones

Two Heaps utiliza dos montones (un montón máximo y un montón mínimo) para optimizar ciertos problemas, como encontrar valores medianos en un conjunto de datos. Este patrón es particularmente útil para mantener una estructura equilibrada.

Así es como funciona:

1. Utilice dos montones: un montón máximo para identificar el elemento más grande y un montón mínimo para localizar el más pequeño.
2. Complete el Max Heap con la primera mitad de los números, con el objetivo de encontrar el más grande entre ellos.
3. Llene el montón mínimo con la segunda mitad de los números para identificar el más pequeño en esta porción.
4. La mediana del conjunto de números actual se puede calcular en cualquier momento examinando los elementos superiores de ambos montones.

Indicadores clave:

• Es necesario mantener una estructura equilibrada para encontrar la mediana de manera eficiente.
• Los problemas implican el manejo de problemas de ventanas deslizantes con medianas dinámicas.
• Quiere priorizar elementos de una colección en función de sus valores.

Código de plantilla:

Pitón

 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. Pila monótona

Monótono - (de una función o cantidad) que varía de tal manera que nunca disminuye o nunca aumenta.

La pila monotónica mantiene una pila de elementos en orden no creciente ni decreciente, a menudo utilizada para encontrar los elementos más pequeños/mayores más cercanos en una matriz. Es una herramienta poderosa para optimizar ciertos problemas.

El orden es estricto, cada vez que encontramos un elemento que es más pequeño (o mayor) que el que está en la parte superior de la pila, debemos salir de la pila monótona hasta que el elemento que buscamos agregar sea el más pequeño (o mayor) de a ellos.

Indicadores clave:

• Debe mantener los elementos en orden no creciente ni decreciente.
• Los problemas implican encontrar el elemento mayor o menor más cercano.
• Quiere optimizar las operaciones basadas en pilas y al mismo tiempo preservar el orden.

Código de plantilla:

Pitón

 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. Búsqueda en profundidad

DFS , o búsqueda en profundidad primero , es un método transversal en el que se explora lo más profundamente posible a lo largo de una rama antes de retroceder; se aplica ampliamente en problemas que involucran árboles y gráficos, particularmente para operaciones de recorrido y búsqueda.

Para realizar DFS en un árbol, debe comenzar desde la raíz. Luego siga los pasos a continuación:

1. Explore el nodo actual visitando sus nodos secundarios, normalmente de izquierda a derecha .
2. Aplique recursivamente el proceso DFS a cada nodo secundario, profundizando en el árbol.
3. Una vez que se hayan visitado todos los nodos secundarios, retroceda hasta el nodo principal.
4. Repita los pasos 1 a 3 para cada hijo no visitado del nodo actual hasta que se hayan visitado todos los nodos del árbol.

Diferencia con DFS en un gráfico: la diferencia clave entre DFS de árbol y DFS de gráfico radica en la presencia de ciclos. En un árbol, no hay ciclos por definición, por lo que el árbol DFS garantiza que cada nodo se visite exactamente una vez y, naturalmente, termina cuando se recorre todo el árbol. Por el contrario, el gráfico DFS debe incorporar medidas adicionales para manejar estructuras cíclicas dentro de un gráfico. Para evitar volver a visitar los nodos en un ciclo indefinidamente, el gráfico DFS requiere mecanismos como marcar los nodos visitados y manejar el retroceso de manera adecuada . Esta distinción hace que el gráfico DFS sea más complejo que el árbol DFS debido a la posibilidad de que se formen bucles infinitos en presencia de ciclos.

Indicadores clave:

• Estás tratando con estructuras de árbol y necesitas explorar órdenes transversales específicas.
• Los problemas implican encontrar caminos, calcular la profundidad o realizar un recorrido de preorden/orden/postorden.
• Quiere comprobar si existe una ruta entre dos nodos.

Código de plantilla:

Pitón

 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. Búsqueda prioritaria en amplitud

BFS es una técnica transversal para árboles y gráficos que explora todos los nodos en la profundidad actual antes de pasar al siguiente nivel.

Para realizar BFS en un árbol, debe comenzar desde la raíz. Luego siga los pasos a continuación:

1. Inicialice una estructura de datos de cola vacía para realizar un seguimiento de los nodos que se visitarán.

2. Coloque el nodo raíz en la cola.

3. Ingrese un bucle hasta que la cola esté vacía:

   1. Retire el nodo al principio de la cola.
   2. Procesar el nodo fuera de cola (por ejemplo, visitarlo o realizar alguna operación en él).
   3. Coloque en cola a todos los hijos del nodo (si los hay).

4. Repita los pasos 3a-3c hasta que la cola quede vacía.

5. El recorrido BFS se completa cuando todos los nodos del árbol han sido visitados en forma nivelada, de izquierda a derecha.

En esencia, BFS en un árbol explora los nodos nivel por nivel , comenzando desde la raíz y pasando a los secundarios antes de pasar al siguiente nivel. Esto garantiza que se visiten los nodos de cada nivel antes de pasar al siguiente nivel, lo que lo hace particularmente útil para tareas como encontrar el camino más corto en un árbol no ponderado o explorar un árbol nivel por nivel.

Diferencia con BFS en un gráfico: similar a DFS, Graph BFS se adapta a la presencia de ciclos y múltiples rutas entre nodos. Emplea mecanismos como marcar nodos visitados y condiciones de terminación especializadas para navegar de manera eficiente por la intrincada red de relaciones dentro de los gráficos.

Indicadores clave:

• Necesitas atravesar un árbol nivel por nivel.
• Los problemas implican encontrar el camino más corto en gráficos no ponderados.
• Quiere explorar un árbol o un gráfico en términos de amplitud.

Código de plantilla:

Pitón

 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. Búsqueda de unión (unión de conjunto disjunto)

La estructura de datos Union-Find , también conocida como Unión de conjuntos disjuntos (DSU) , se emplea para gestionar y resolver de manera eficiente problemas que involucran conjuntos disjuntos o componentes conectados. Proporciona operaciones para fusionar conjuntos (unión) y determinar el conjunto al que pertenece un elemento (buscar). Union-Find se usa comúnmente en algoritmos como el árbol de expansión mínima de Kruskal y la detección de ciclos en gráficos.

Union Find se implementa de la siguiente manera:

1. Inicialización: comience con una colección de elementos, cada uno considerado como un conjunto separado y disjunto. Asigne un representante único (a menudo el propio elemento) a cada conjunto.
2. Operación de unión: para fusionar dos conjuntos, realice la operación de unión. Elija el representante de un conjunto (a menudo basándose en algunos criterios, como rango o tamaño) y conviértalo en el padre del representante del otro conjunto. Esto conecta efectivamente los dos conjuntos.
3. Operación de búsqueda: cuando necesite determinar el conjunto al que pertenece un elemento, utilice la operación de búsqueda. Comenzando con el elemento en cuestión, recorra el árbol hacia arriba para encontrar el nodo raíz (representante) de su conjunto. La técnica de compresión de ruta se puede aplicar aquí para optimizar futuras operaciones de búsqueda haciendo que los elementos a lo largo de la ruta apunten directamente a la raíz.
4. Detección de ciclos: Union-Find se utiliza a menudo para detectar ciclos en gráficos. Al realizar la operación de unión, si ambos elementos pertenecen al mismo conjunto (es decir, tienen el mismo representante), indica que la adición de una arista entre nodos crearía un ciclo en el gráfico.
5. Optimización: se pueden aplicar varias técnicas de optimización para mejorar la eficiencia de las operaciones Union-Find, como la unión por rango y la compresión de ruta.

Código de plantilla:

Pitón

 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. Ordenación topológica

Un gráfico acíclico dirigido (DAG) es un gráfico dirigido sin ciclos dirigidos.

La clasificación topológica es un algoritmo para organizar los nodos de un gráfico acíclico dirigido ( DAG ) en un orden lineal, donde cada nodo aparece antes que sus sucesores. Es crucial para tareas como programar dependencias, compilar código y analizar la precedencia de tareas en diversas aplicaciones.

Aquí hay un desglose paso a paso de la clasificación topológica:

1. Inicialización: comience con un gráfico acíclico dirigido ( DAG ) que represente tareas o nodos con dependencias. Inicialice una cola para contener los nodos ordenados.

2. Cálculo en grados: Calcule el grado (el número de aristas entrantes) para cada nodo en el gráfico. Los nodos con un grado de entrada de 0 no tienen dependencias y son adecuados para ser el punto de partida de la clasificación topológica.

3. Llenado de cola inicial: ponga en cola todos los nodos con un grado de entrada de 0 en la cola. Estos nodos se pueden procesar primero.

4. Bucle de clasificación topológica: mientras la cola no esté vacía, realice los siguientes pasos:

   1. Retire un nodo del frente de la cola.
   2. Procese el nodo (por ejemplo, agréguelo a la lista ordenada).
   3. Para cada uno de los vecinos del nodo (nodos a los que apunta), disminuya su grado de entrada en 1.
   4. Si el grado de entrada de un vecino se vuelve 0 como resultado de la disminución, colóquelo en la cola.

5. Finalización: una vez que se completa el ciclo de clasificación topológica, la cola estará vacía y la lista ordenada contendrá todos los nodos en un orden topológico válido.

6. Detección de ciclos: si en algún momento durante el proceso de clasificación topológica no quedan nodos con un grado de entrada de 0 en la cola, indica la presencia de ciclos en el gráfico, lo que hace imposible la clasificación topológica.

El resultado del Topological Sort es un ordenamiento lineal de nodos que respeta sus dependencias, haciéndolo adecuado para programar tareas o analizar el orden de ejecución en diversas aplicaciones.

Indicadores clave:

• El problema implica programar u ordenar tareas con dependencias.
• Estás trabajando con un gráfico acíclico dirigido (DAG).
• Las tareas deben ejecutarse en un orden específico respetando sus dependencias.

Código de plantilla:

Pitón

 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. Intentos (árbol de prefijos)

Un Trie es una estructura de datos en forma de árbol que se utiliza para la comparación de cadenas y el almacenamiento de palabras de manera eficiente. Destaca en problemas en los que es necesario almacenar y buscar cadenas con prefijos comunes.

A continuación se explica cómo implementar un Trie:

1. Inicialización: comience con un Trie vacío, que normalmente consta de un nodo raíz sin ningún carácter asociado.

2. Inserción: para insertar una palabra en el Trie, comience en el nodo raíz y recorra el árbol, un carácter a la vez. Para cada carácter de la palabra:

   1. Compruebe si existe un nodo secundario con ese carácter en el nodo actual.
   2. Si es así, muévase al nodo secundario.
   3. De lo contrario, cree un nuevo nodo secundario con el personaje y muévase hacia él.

3. Finalización de palabras: para comprobar si una palabra existe en Trie, recorrala de forma similar a la inserción. Asegúrese de que cada carácter de la palabra corresponda a un nodo secundario del nodo actual. Si el recorrido llega al final de la palabra y hay un marcador de final válido (por ejemplo, una bandera booleana) en el último nodo de carácter, la palabra existe en el Trie.

4. Búsqueda de prefijos: Trie sobresale en la búsqueda de prefijos. Para encontrar todas las palabras con un prefijo determinado, comience el recorrido en el nodo raíz y baje en el árbol siguiendo los caracteres del prefijo. Una vez que llegue al último carácter del prefijo, puede realizar una búsqueda en profundidad (DFS) desde ese nodo para encontrar todas las palabras que comparten el mismo prefijo.

5. Eliminación: para eliminar una palabra del Trie, realice una búsqueda de la palabra. Cuando llegue al final de la palabra, elimine el marcador de final (si existe). Si el nodo no tiene otros hijos, puede eliminar de forma segura toda la rama del Trie, que representa la palabra.

Los intentos pueden consumir mucha memoria, especialmente para vocabularios extensos. Para optimizar la memoria, se pueden aplicar técnicas como la compresión (por ejemplo, usar un mapa en lugar de una matriz de caracteres en cada nodo) y la poda (eliminar nodos sin descendientes).

Los intentos son particularmente útiles para una coincidencia eficiente de cadenas, sugerencias de autocompletar, correctores ortográficos e indexación de palabras con prefijos comunes. Proporcionan una forma rápida y que ahorra espacio para almacenar y buscar palabras o cadenas con prefijos compartidos en una estructura similar a un árbol.

Indicadores clave:

• Estás tratando con cadenas y necesitas una coincidencia de cadenas eficiente.
• Los problemas implican sugerencias de autocompletar, correctores ortográficos o búsqueda de palabras con prefijos comunes.
• Quiere almacenar y buscar palabras de manera eficiente.

Código de plantilla:

Pitón

 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. Programación dinámica

La programación dinámica es una poderosa técnica de resolución de problemas utilizada en informática y matemáticas para resolver una amplia gama de problemas complejos de manera eficiente. Es especialmente valioso cuando un problema se puede dividir en subproblemas más simples y las soluciones a estos subproblemas se pueden combinar para resolver el problema general.

Estas son sus características clave y cómo funciona:

Subestructura óptima:

• Esta característica se refiere a la propiedad de que se puede construir una solución óptima a un problema mayor a partir de soluciones óptimas a sus subproblemas más pequeños.
• En otras palabras, los problemas de DP exhiben una estructura recursiva, donde la solución óptima de un problema depende de las soluciones óptimas de sus subproblemas.
• Por ejemplo, al encontrar el camino más corto entre dos puntos en un gráfico, el camino más corto entre dos puntos intermedios cualesquiera también debería ser óptimo.

Subproblemas superpuestos:

• Los subproblemas superpuestos ocurren cuando los mismos subproblemas se resuelven varias veces durante el cálculo, lo que genera trabajo redundante.
• La programación dinámica tiene como objetivo abordar este problema almacenando las soluciones a los subproblemas en una estructura de datos (a menudo una tabla o matriz de memorización) para evitar volver a calcularlos.
• Este almacenamiento y reutilización de soluciones de subproblemas reduce significativamente la complejidad temporal del algoritmo.

Cómo funciona la programación dinámica:

1. Identificar subproblemas: el primer paso para resolver un problema utilizando DP es identificar los subproblemas. Divida el problema en subproblemas más pequeños y manejables que, una vez resueltos, contribuyan a resolver el problema principal.
2. Solución recursiva: desarrolle una solución recursiva que exprese la solución de un problema mayor en términos de soluciones a subproblemas más pequeños. Esta formulación recursiva captura la subestructura óptima.
3. Memorización o tabulación: para abordar subproblemas superpuestos, puede elegir entre dos técnicas comunes:
   • Memorización: almacene los resultados de los subproblemas en una estructura de datos (generalmente una matriz o tabla hash) a medida que se calculan. Cuando se vuelva a encontrar un subproblema, recupere su solución del almacenamiento en lugar de volver a calcularla. Esto también se conoce como enfoque de arriba hacia abajo .
   • Tabulación: cree una tabla (a menudo una matriz 2D) para almacenar soluciones a subproblemas de abajo hacia arriba . Comience resolviendo los subproblemas más pequeños y avance progresivamente hasta llegar al problema principal.
4. Solución óptima: una vez resueltos todos los subproblemas, la solución al problema principal se puede obtener combinando las soluciones de sus subproblemas de acuerdo con la estructura recursiva del problema.

La programación dinámica se aplica a una amplia gama de problemas, incluida la búsqueda de los caminos más cortos en gráficos, la optimización de la asignación de recursos, el conteo de combinaciones, la resolución de problemas de mochila y mucho más. Su capacidad para optimizar soluciones dividiendo problemas complejos en partes más simples y evitando cálculos redundantes la convierte en una técnica fundamental en el diseño y optimización de algoritmos.

Conceptos importantes: enfoque de abajo hacia arriba, de arriba hacia abajo, memorización, tabulación

Indicadores clave:

• El problema se puede dividir en subproblemas más pequeños superpuestos.
• Es necesario optimizar almacenando y reutilizando soluciones a subproblemas.
• Quiere resolver problemas que impliquen optimización o conteo.

Código de plantilla:

La plantilla para la memorización de arriba hacia abajo es una de las muchas formas de implementar la programación dinámica.

Pitón

 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. Retroceder

El retroceso es una técnica algorítmica general para resolver problemas de forma incremental probando diferentes posibilidades y deshaciéndolas si no conducen a una solución. Se utiliza cuando se requiere una búsqueda exhaustiva.

A continuación se ofrece un análisis en profundidad de cómo funciona el retroceso:

1. Exploración del espacio del problema: Backtracking explora el espacio del problema construyendo incrementalmente una solución pieza por pieza. En cada paso, toma una decisión y avanza.
2. Estructura recursiva: el retroceso a menudo implica recursividad. Comienza con una solución parcial inicial y explora todas las formas posibles de ampliarla. Este proceso continúa recursivamente hasta que se encuentra una solución completa o se hace evidente que no existe una solución válida.
3. Puntos de decisión: en cada paso, hay puntos de decisión donde el algoritmo debe elegir entre las opciones disponibles. Estas elecciones conducen a una ramificación en el proceso de exploración.
4. Validación de la solución: después de realizar una elección, el algoritmo verifica si la solución parcial actual es válida. Si es válido, el algoritmo continúa con el siguiente paso. Si no, retrocede, deshace la elección anterior y explora otras opciones.
5. Condiciones de terminación: el retroceso continúa hasta que se cumpla una de dos condiciones:
   • Se encuentra una solución válida, en cuyo caso el algoritmo se detiene y devuelve la solución.
   • Se determina que no existe una solución válida, momento en el que el algoritmo retrocede hasta un punto de decisión anterior y explora diferentes opciones.
6. Poda: Para optimizar la búsqueda, el retroceso suele incluir estrategias de poda. La poda implica evitar la exploración de caminos que seguramente conducirán a soluciones no válidas, reduciendo significativamente el espacio de búsqueda.

Aplicaciones del retroceso:

El retroceso se utiliza en varios dominios de problemas, que incluyen:

• Resolver acertijos como Sudoku y N-Queens.
• Generación de permutaciones y combinaciones.
• Búsqueda de caminos en gráficos y árboles.
• Problemas de satisfacción de restricciones (p. ej., el problema del viajante).
• Algoritmos de juego (por ejemplo, IA de ajedrez).

Indicadores clave:

• El problema implica explorar múltiples posibilidades de forma incremental.
• Hay puntos de decisión o limitaciones que requieren probar diferentes opciones.
• Es necesario encontrar todas las soluciones posibles o satisfacer condiciones específicas mediante una búsqueda exhaustiva.

Código de plantilla:

Pitón

 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. Fusionar intervalos

Fusionar intervalos implica combinar intervalos superpuestos o adyacentes en un conjunto consolidado, lo que a menudo se usa en problemas que involucran intervalos de tiempo o programación. Simplifica las operaciones basadas en intervalos.

He aquí un vistazo más de cerca a cómo funciona la combinación de intervalos:

1. Representación de intervalos: los intervalos normalmente se representan como pares de puntos de inicio y fin (p. ej., [inicio, fin] ).
2. Clasificación: para fusionar intervalos de manera eficiente, comience ordenándolos según sus puntos de inicio. Esto garantiza que los intervalos superpuestos o adyacentes sean adyacentes en la lista ordenada.
3. Proceso de fusión: inicialice una lista vacía para contener los intervalos fusionados. Luego, repita los intervalos ordenados uno por uno:
   • Si el intervalo actual no se superpone con el anterior, agréguelo a la lista de intervalos combinados.
   • Si hay una superposición, actualice el punto final del intervalo combinado anterior para abarcar tanto el intervalo actual como el anterior, fusionándolos de manera efectiva.
4. Finalización: después de procesar todos los intervalos, la lista de intervalos combinados contendrá intervalos consolidados y no superpuestos.

Aplicaciones de intervalos de fusión:

Los intervalos de fusión se utilizan comúnmente en:

• Aplicaciones de programación y gestión del tiempo.
• Detección de eventos superpuestos en sistemas de calendario.
• Análisis de datos basado en intervalos, como en consultas de bases de datos.
• Resolver problemas relacionados con la asignación de recursos y la programación de reuniones.

Al fusionar intervalos superpuestos, esta técnica simplifica las operaciones basadas en intervalos y mejora la eficiencia en diversas aplicaciones.

Indicadores clave:

• Se trata de intervalos o datos basados en el tiempo.
• Los problemas implican fusionar intervalos superpuestos o adyacentes.
• Quiere simplificar las operaciones basadas en intervalos u optimizar la programación de eventos.

Código de plantilla:

Pitón

 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()][]); } }

¿Querer aprender más?

Si desea obtener más información sobre estos patrones y cómo puede implementarlos de manera más efectiva durante su próxima entrevista de codificación, ¡visite techinterviews.io hoy! Ofrecemos un plan de estudios integral para prepararlo para su próxima entrevista de codificación, que cubre temas como estructuras de datos , algoritmos , entrevistas de comportamiento e incluso negociación salarial . Incluso tenemos un espacio de trabajo de codificación incorporado para que practiques.

¡Mejora tu preparación para la entrevista de codificación hoy con nuestro código de promoción TECH30 con un descuento de $30!