Padrões de codificação: uma abordagem mais inteligente para preparação para entrevistas de codificação

A preparação para entrevistas de codificação pode ser um verdadeiro desafio, pois os desenvolvedores muitas vezes passam várias semanas revisando e aprendendo novos materiais.

A verdade é que a maioria dos desenvolvedores nunca se sente totalmente preparada para suas entrevistas de codificação. Não é incomum que os desenvolvedores passem semanas resolvendo problemas no LeetCode e ainda assim se sintam despreparados. Claramente, há problemas com esta abordagem.

Vamos examinar mais de perto alguns problemas associados à preparação tradicional para entrevistas de codificação.

As armadilhas da preparação tradicional para entrevistas

Uma das armadilhas mais comuns na preparação para entrevistas tradicionais é a prática de "triturar". Esta abordagem envolve resolver tantos problemas LeetCode quanto possível sem um plano ou estratégia clara. Embora possa parecer uma estratégia produtiva, tem várias desvantagens.

Ao resolver problemas sem uma abordagem estruturada, você pode não reconhecer seus pontos fracos. Não existe um plano deliberado para o seu estudo; o objetivo é simplesmente resolver o máximo de problemas possível. Como resultado, você pode sentir que aprendeu muito, mas pode haver lacunas significativas no seu conhecimento.

Além disso, o problema é que gira essencialmente em torno da memorização de soluções para uma infinidade de problemas. Tentar lembrar soluções para uma centena de problemas de codificação diferentes revela-se ineficaz quando os entrevistadores apresentam perguntas que se desviam, mesmo que ligeiramente, do que você encontrou antes. Isso pode fazer com que você se sinta despreparado para lidar com variações de problemas.

O meu último problema com esta estratégia é que, a longo prazo, ela cria mais stress e dores de cabeça. Se você tiver que passar pela mesma sessão de estudo de várias semanas toda vez que quiser mudar de emprego, terá dificuldades todas as vezes. Você passará semanas reaprendendo coisas e resolvendo os mesmos problemas de antes.

Dados esses desafios, deve haver uma maneira melhor.

Uma maneira melhor: adotando padrões de codificação

Então, existe uma abordagem mais eficaz e sustentável para codificar a preparação para entrevistas? A resposta está na compreensão e utilização de padrões de codificação.

Quando me preparo para entrevistas de codificação, priorizo a compreensão dos padrões subjacentes dos problemas. Esses padrões, que incluem técnicas como Two-Pointers , Sliding Window , Modified Binary Search , Topological Sort e muito mais, fornecem uma estrutura versátil e poderosa para lidar com uma ampla gama de problemas de codificação. A ênfase muda da memorização de soluções para técnicas comprovadas de resolução de problemas.

Ao focar nos padrões de codificação, você pode agilizar significativamente a preparação da entrevista, tornando-a mais eficiente.

Lembre-se, prepare-se de maneira mais inteligente, não mais difícil.

O que esperar?

Neste artigo, compilei o Os 15 principais padrões de codificação que você precisa saber para responder a qualquer questão de codificação. Vou detalhar o que é cada padrão e como funciona. Compartilhe indicadores-chave para ajudá-lo a identificar o padrão e, finalmente, ofereça gráficos detalhados com código de modelo para ajudá-lo a solidificar sua compreensão.

Embora eu aborde muito neste artigo, se você quiser treinamento mais aprofundado, explicações e prática de codificação, você pode conferir nosso Curso Preparatório para Entrevista de Codificação Abrangente em Techinterviews.io. Também cobrimos tópicos cruciais como estruturas de dados , entrevistas comportamentais e até negociação salarial .

Agora vamos mergulhar nesses padrões de codificação.

1. Reversão de lista vinculada

A reversão de lista vinculada envolve alterar a direção dos ponteiros em uma lista vinculada para inverter a ordem dos elementos. É uma operação fundamental em estruturas de dados e muitas vezes requer uma manipulação cuidadosa das referências dos nós.

Isso é útil ao lidar com uma lista vinculada e a restrição é revertê-la.

O processo para reverter uma lista vinculada é o seguinte:

1. Comece definindo três variáveis: current , previous e next . Defina atual como o topo da lista vinculada e inicialize anterior e próximo como Nenhum.

2. Embora a variável atual não seja None , proceda da seguinte forma:

   1. Armazene o próximo nó em uma variável temporária.
   2. Inverta o ponteiro do nó atual para apontar para o nó anterior .
   3. Atualize anterior para ser o nó atual e atual para ser o próximo nó.

3. Por fim, defina o cabeçalho da lista invertida para o último nó alcançado, que está armazenado na variável anterior .

Indicadores-chave:

• Você precisa inverter a ordem dos elementos em uma lista vinculada.
• Os problemas envolvem a verificação de palíndromos em listas vinculadas.
• Você deseja inverter a ordem dos elementos em uma sublista específica da lista.

Código do modelo:

Pitão

 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. Pesquisa binária modificada

A Pesquisa Binária Modificada adapta o algoritmo clássico de pesquisa binária para resolver vários problemas. As variações incluem encontrar a primeira/última ocorrência de um elemento ou pesquisar em matrizes giradas. Requer um manuseio cuidadoso dos pontos médios e das condições.

Se você receber uma matriz ordenada, uma lista vinculada ou uma matriz, considere usar uma pesquisa binária modificada .

Aqui está um resumo de como aplicar esse padrão a uma estrutura de dados classificada:

1. Comece identificando o ponto médio entre as posições inicial e final . Para evitar um potencial estouro de número inteiro, é mais seguro calcular o meio da seguinte forma: middle = start + (end - start) / 2 .
2. Verifique se a chave corresponde ao elemento no índice intermediário . Se isso acontecer, retorne o índice do meio como resultado.
3. Se a chave não corresponder ao elemento no índice intermediário , prossiga para as próximas etapas.
4. Avalie se a chave é menor que o elemento no meio do índice. Se for, restrinja seu intervalo de pesquisa atualizando end to middle - 1 .
5. Por outro lado, se a chave for maior que o elemento no índice middle , ajuste seu intervalo de pesquisa atualizando start para middle + 1 .

Indicadores-chave:

• Você está trabalhando com uma estrutura de dados classificada.
• Você precisa encontrar elementos, limites ou pontos de articulação específicos com eficiência.
• Os problemas envolvem a pesquisa em matrizes classificadas rotacionadas.

Código do modelo:

Pitão

 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. Duas dicas

A técnica de Dois Ponteiros envolve a manutenção de dois ponteiros que percorrem uma estrutura de dados, normalmente arrays ou listas vinculadas, frequentemente usados para problemas envolvendo pares ou submatrizes. Otimiza problemas que exigem comparação entre elementos em posições diferentes.

A vantagem desta técnica reside na sua simplicidade e eficiência, especialmente quando se trata de estruturas de dados lineares, como matrizes ou strings, onde inicialmente você pode usar apenas um ponteiro. Ao empregar dois ponteiros, você pode contornar operações redundantes e aumentar significativamente a eficiência do tempo de execução, reduzindo-o potencialmente de O(n^2) para O(n) .

O padrão "Dois Ponteiros" abrange diversas variações, cada uma adaptada a cenários específicos. Essas variações incluem a mesma direção , a direção oposta e um método exclusivo conhecido como "rápido e lento", muitas vezes referido como a técnica "tartaruga e lebre" , que envolve dois ponteiros movendo-se em velocidades diferentes através de uma estrutura de dados, particularmente útil para detectar ciclos.

Se você empregar vários ponteiros para percorrer uma estrutura de dados, poderá categorizar sua abordagem seguindo o padrão "Dois ponteiros" .

Indicadores-chave:

• Você precisa comparar ou operar elementos em posições diferentes.
• Os problemas exigem a busca por pares de elementos em uma matriz ordenada.
• Você deseja remover duplicatas de uma matriz classificada de forma eficiente.
• Ao lidar com estruturas de dados lineares (matrizes, strings ou listas vinculadas) e enfrentar uma complexidade de tempo quadrática (solução de força bruta O (n ^ 2) ), considere empregar dois ponteiros.

Código do modelo:

Modelo para variação de “direção oposta”

Pitão

 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. Janela deslizante

A técnica da janela deslizante envolve a manutenção de uma janela dinâmica sobre uma estrutura de dados linear, como matrizes, strings ou listas vinculadas. O tamanho da janela pode variar dependendo da implementação específica e também pode ser definido como um valor fixo. O objetivo principal desta janela é monitorar e capturar continuamente dados que satisfaçam critérios específicos, tornando-a particularmente valiosa para a resolução eficiente de problemas de submatrizes ou substrings.

Esse padrão geralmente utiliza um mapa hash para facilitar o rastreamento de dados individuais dentro da janela. No entanto, é importante notar que esta abordagem pode resultar em uma complexidade espaço-temporal de O(n) .

Indicadores-chave:

• Você precisa analisar submatrizes ou substrings contíguas ou não contíguas.
• Os problemas envolvem o rastreamento de sequências de comprimento variável em um conjunto de dados maior.
• Você deseja encontrar a submatriz de soma máxima de comprimento fixo.
• A entrada do problema é uma estrutura de dados linear, como uma matriz, lista vinculada ou string.

Código do modelo:

Pitão

 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. Principais K elementos

Esse padrão envolve encontrar os K maiores ou menores elementos em uma coleção, geralmente implementados usando estruturas de dados como heaps ou filas de prioridade. É útil para selecionar um subconjunto de elementos com base em seu valor ou frequência.

Sempre que somos solicitados a encontrar os elementos 'K' mais frequentes, menores ou principais em um determinado conjunto de dados, podemos considerar o uso desse padrão.

A maneira como isso funciona é simples:

1. Inserimos elementos 'K' em nosso heap mínimo ou máximo (isso depende da implementação).
2. Sempre que adicionamos ao nosso heap, devemos ajustar para que sempre os elementos 'K' frequentes/menores/superiores sejam mantidos.

A beleza desta abordagem reside na sua eficiência; você não precisa recorrer a nenhum algoritmo de classificação, pois o próprio heap mantém naturalmente a ordem necessária para você.

Indicadores-chave:

• Você precisa identificar os K maiores ou menores elementos de uma coleção.
• Os problemas exigem elementos de classificação com base em determinados critérios.
• Você deseja encontrar os K elementos mais frequentes em um conjunto de dados.

Código do modelo:

Pitão

 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. Dois montes

Dois heaps utilizam dois heaps (um heap máximo e um heap mínimo) para otimizar certos problemas, como encontrar valores medianos em um conjunto de dados. Este padrão é particularmente útil para manter uma estrutura equilibrada.

Veja como funciona:

1. Utilize dois heaps: um Max Heap para identificar o maior elemento e um Min Heap para localizar o menor.
2. Preencha o Max Heap com a primeira metade dos números, visando encontrar o maior entre eles.
3. Preencha o Min Heap com a segunda metade dos números para identificar o menor nesta parte.
4. A mediana do conjunto de números atual pode ser calculada a qualquer momento examinando os elementos superiores de ambos os heaps.

Indicadores-chave:

• Você precisa manter uma estrutura equilibrada para encontrar a mediana de maneira eficiente.
• Os problemas envolvem o tratamento de problemas de janelas deslizantes com medianas dinâmicas.
• Você deseja priorizar os elementos de uma coleção com base em seus valores.

Código do modelo:

Pitão

 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. Pilha Monotônica

Monotônico - (de uma função ou quantidade) variando de tal forma que nunca diminui ou nunca aumenta.

A pilha monotônica mantém uma pilha de elementos em ordem não crescente ou não decrescente, geralmente usada para encontrar os elementos menores/maiores mais próximos em uma matriz. É uma ferramenta poderosa para otimizar certos problemas.

A ordem é estrita, sempre que encontramos um elemento menor (ou maior) do que o que está no topo da pilha, devemos sair da pilha monotônica até que o elemento que pretendemos adicionar seja o menor (ou maior) de eles.

Indicadores-chave:

• Você precisa manter os elementos em ordem não crescente ou não decrescente.
• Os problemas envolvem encontrar o elemento menor ou maior mais próximo.
• Você deseja otimizar as operações baseadas em pilha enquanto preserva a ordem.

Código do modelo:

Pitão

 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. Pesquisa em profundidade

DFS , ou Depth-First Search , é um método de travessia onde você explora o mais profundamente possível ao longo de uma ramificação antes de voltar atrás; é amplamente aplicado em problemas envolvendo árvores e grafos, principalmente para operações de percurso e busca.

Para executar DFS em uma árvore, você precisa começar na raiz. Em seguida, siga as etapas abaixo:

1. Explore o nó atual visitando seus nós filhos, normalmente da esquerda para a direita .
2. Aplique recursivamente o processo DFS a cada nó filho, aprofundando-se na árvore.
3. Depois que todos os nós filhos forem visitados, volte para o nó pai.
4. Repita as etapas 1 a 3 para cada filho não visitado do nó atual até que todos os nós da árvore tenham sido visitados.

Diferença com DFS em um gráfico: A principal diferença entre DFS de árvore e DFS de gráfico está na presença de ciclos. Em uma árvore, não há ciclos por definição, então o DFS da árvore garante que cada nó seja visitado exatamente uma vez e termina naturalmente quando toda a árvore é atravessada. Em contraste, o DFS gráfico deve incorporar medidas adicionais para lidar com estruturas cíclicas dentro de um gráfico. Para evitar a revisitação de nós em um ciclo indefinidamente, o grafo DFS requer mecanismos como marcação de nós visitados e tratamento adequado do retrocesso . Esta distinção torna o DFS gráfico mais complexo do que o DFS em árvore devido ao potencial para loops infinitos na presença de ciclos.

Indicadores-chave:

• Você está lidando com estruturas em árvore e precisa explorar ordens de passagem específicas.
• Os problemas envolvem encontrar caminhos, calcular profundidade ou realizar travessia de pré-pedido/em-pedido/pós-pedido.
• Você deseja verificar se existe um caminho entre dois nós.

Código do modelo:

Pitão

 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. Pesquisa ampla

BFS é uma técnica de travessia para árvores e gráficos que explora todos os nós na profundidade atual antes de passar para o próximo nível.

Para executar o BFS em uma árvore, você precisa começar pela raiz. Em seguida, siga as etapas abaixo:

1. Inicialize uma estrutura de dados de fila vazia para controlar os nós a serem visitados.

2. Enfileirar o nó raiz na fila.

3. Insira um loop até que a fila esteja vazia:

   1. Retire da fila o nó no início da fila.
   2. Processe o nó retirado da fila (por exemplo, visite ou execute alguma operação nele).
   3. Enfileirar todos os filhos do nó (se houver) na fila.

4. Repita as etapas 3a-3c até que a fila fique vazia.

5. A travessia do BFS é concluída quando todos os nós da árvore foram visitados em níveis, da esquerda para a direita.

Em essência, o BFS em uma árvore explora nós nível por nível , começando pela raiz e passando para os filhos antes de prosseguir para o próximo nível. Isso garante que os nós de cada nível sejam visitados antes de passar para o próximo nível, tornando-o particularmente útil para tarefas como encontrar o caminho mais curto em uma árvore não ponderada ou explorar uma árvore nível por nível.

Diferença com BFS em um gráfico: semelhante ao DFS, o Graph BFS se adapta à presença de ciclos e múltiplos caminhos entre nós. Ele emprega mecanismos como marcação de nós visitados e condições de terminação especializadas para navegar com eficiência na intrincada rede de relacionamentos dentro dos gráficos.

Indicadores-chave:

• Você precisa percorrer uma árvore nível por nível.
• Os problemas envolvem encontrar o caminho mais curto em gráficos não ponderados.
• Você deseja explorar uma árvore ou gráfico de maneira ampla.

Código do modelo:

Pitão

 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. Union Find (União Disjoint-Set)

A estrutura de dados Union-Find , também conhecida como Disjoint Set Union (DSU) , é empregada para gerenciar e resolver com eficiência problemas envolvendo conjuntos disjuntos ou componentes conectados. Ele fornece operações para mesclar conjuntos (união) e determinar o conjunto ao qual um elemento pertence (encontrar). Union-Find é comumente usado em algoritmos como a árvore geradora mínima de Kruskal e detecção de ciclo em gráficos.

Union Find é implementado da seguinte forma:

1. Inicialização: comece com uma coleção de elementos, cada um considerado como um conjunto disjunto separado. Atribua um representante exclusivo (geralmente o próprio elemento) a cada conjunto.
2. Operação de união: Para mesclar dois conjuntos, execute a operação de união. Escolha o representante de um conjunto (geralmente com base em alguns critérios, como classificação ou tamanho) e torne-o pai do representante do outro conjunto. Isso conecta efetivamente os dois conjuntos.
3. Operação Find: Quando você precisar determinar o conjunto ao qual um elemento pertence, use a operação find. Começando pelo elemento em questão, percorra a árvore para cima para encontrar o nó raiz (representante) do seu conjunto. A técnica de compactação de caminho pode ser aplicada aqui para otimizar futuras operações de localização, fazendo com que os elementos ao longo do caminho apontem diretamente para a raiz.
4. Detecção de ciclo: Union-Find é frequentemente usado para detectar ciclos em gráficos. Ao realizar a operação de união, se ambos os elementos pertencem ao mesmo conjunto (ou seja, possuem o mesmo representante), indica que a adição de uma aresta entre os nós criaria um ciclo no grafo.
5. Otimização: Várias técnicas de otimização podem ser aplicadas para melhorar a eficiência das operações Union-Find, como união por classificação e compactação de caminho.

Código do modelo:

Pitão

 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. Classificação topológica

Um gráfico acíclico direcionado (DAG) é um gráfico direcionado sem ciclos direcionados.

Topological Sort é um algoritmo para organizar os nós de um grafo acíclico direcionado ( DAG ) em uma ordem linear, onde cada nó aparece antes de seus sucessores. É crucial para tarefas como agendamento de dependências, compilação de código e análise da precedência de tarefas em vários aplicativos.

Aqui está uma análise passo a passo da classificação topológica:

1. Inicialização: comece com um gráfico acíclico direcionado ( DAG ) que representa tarefas ou nós com dependências. Inicialize uma fila para armazenar os nós classificados.

2. Cálculo em graus: calcule o grau (o número de arestas de entrada) para cada nó no gráfico. Nós com grau de entrada 0 não têm dependências e são adequados para ser o ponto de partida da classificação topológica.

3. Preenchimento inicial da fila: enfileira todos os nós com grau de entrada 0 na fila. Esses nós podem ser processados primeiro.

4. Loop de classificação topológica: enquanto a fila não estiver vazia, execute as seguintes etapas:

   1. Retire um nó da frente da fila.
   2. Processe o nó (por exemplo, adicione-o à lista ordenada).
   3. Para cada um dos vizinhos do nó (nós para os quais ele aponta), diminua seu grau de entrada em 1.
   4. Se o grau de entrada de um vizinho se tornar 0 como resultado do decremento, coloque-o na fila.

5. Conclusão: Assim que o loop de classificação topológica for concluído, a fila estará vazia e a lista classificada conterá todos os nós em uma ordem topológica válida.

6. Detecção de Ciclo: Se em algum momento do processo de ordenação topológica não houver nós com grau de entrada 0 na fila, isso indica a presença de ciclos no gráfico, impossibilitando a ordenação topológica.

O resultado da Classificação Topológica é uma ordenação linear dos nós que respeita suas dependências, tornando-a adequada para escalonar tarefas ou analisar a ordem de execução em diversas aplicações.

Indicadores-chave:

• O problema envolve agendar ou ordenar tarefas com dependências.
• Você está trabalhando com um gráfico acíclico direcionado (DAG).
• As tarefas precisam ser executadas em uma ordem específica, respeitando suas dependências.

Código do modelo:

Pitão

 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. Tentativas (Árvore de Prefixo)

Um Trie é uma estrutura de dados semelhante a uma árvore usada para correspondência eficiente de strings e armazenamento de palavras. É excelente em problemas onde você precisa armazenar e pesquisar strings com prefixos comuns.

Veja como implementar um Trie:

1. Inicialização: comece com um Trie vazio, que normalmente consiste em um nó raiz sem nenhum caractere associado.

2. Inserção: Para inserir uma palavra no Trie, comece no nó raiz e percorra a árvore, um caractere por vez. Para cada caractere da palavra:

   1. Verifique se existe um nó filho com esse caractere no nó atual.
   2. Se isso acontecer, vá para o nó filho.
   3. Caso contrário, crie um novo nó filho com o personagem e vá até ele.

3. Completação de palavra: para verificar se existe uma palavra no Trie, percorra-a de maneira semelhante à inserção. Certifique-se de que cada caractere da palavra corresponda a um nó filho do nó atual. Se a travessia atingir o final da palavra e houver um marcador de final válido (por exemplo, um sinalizador booleano) no último nó de caractere, a palavra existirá no Trie.

4. Pesquisa de prefixo: Trie é excelente na pesquisa de prefixo. Para encontrar todas as palavras com um determinado prefixo, inicie o percurso no nó raiz e desça na árvore seguindo os caracteres do prefixo. Depois de atingir o último caractere do prefixo, você pode realizar uma pesquisa em profundidade (DFS) desse nó para encontrar todas as palavras que compartilham o mesmo prefixo.

5. Exclusão: Para excluir uma palavra do Trie, faça uma busca pela palavra. Ao chegar ao final da palavra, remova o marcador de final (se existir). Se o nó não tiver outros filhos, você poderá remover com segurança todo o ramo do Trie, que representa a palavra.

As tentativas podem consumir muita memória, especialmente para vocabulários grandes. Para otimizar a memória, técnicas como compressão (por exemplo, usar um mapa em vez de um array de caracteres em cada nó) e poda (remoção de nós sem descendentes) podem ser aplicadas.

As tentativas são particularmente úteis para correspondência eficiente de strings, sugestões de preenchimento automático, verificadores ortográficos e indexação de palavras com prefixos comuns. Eles fornecem uma maneira rápida e eficiente de armazenar e pesquisar palavras ou strings com prefixos compartilhados em uma estrutura semelhante a uma árvore.

Indicadores-chave:

• Você está lidando com strings e precisa de uma correspondência eficiente de strings.
• Os problemas envolvem sugestões de preenchimento automático, corretores ortográficos ou busca de palavras com prefixos comuns.
• Você deseja armazenar e pesquisar palavras com eficiência.

Código do modelo:

Pitão

 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. Programação Dinâmica

A Programação Dinâmica é uma técnica poderosa de resolução de problemas usada em ciência da computação e matemática para resolver uma ampla gama de problemas complexos de forma eficiente. É especialmente valioso quando um problema pode ser dividido em subproblemas mais simples e as soluções para esses subproblemas podem ser combinadas para resolver o problema geral.

Aqui estão suas principais características e como funciona:

Subestrutura ideal:

• Esta característica refere-se à propriedade de que uma solução ótima para um problema maior pode ser construída a partir de soluções ótimas para seus subproblemas menores.
• Em outras palavras, os problemas de DP exibem uma estrutura recursiva, onde a solução ótima para um problema depende das soluções ótimas de seus subproblemas.
• Por exemplo, ao encontrar o caminho mais curto entre dois pontos num gráfico, o caminho mais curto entre quaisquer dois pontos intermediários também deve ser ótimo.

Subproblemas sobrepostos:

• Subproblemas sobrepostos ocorrem quando os mesmos subproblemas são resolvidos várias vezes durante o cálculo, levando a trabalho redundante.
• A Programação Dinâmica visa resolver esse problema armazenando as soluções para subproblemas em uma estrutura de dados (geralmente uma tabela ou array de memoização) para evitar recalculá-los.
• Este armazenamento e reutilização de soluções de subproblemas reduzem significativamente a complexidade de tempo do algoritmo.

Como funciona a programação dinâmica:

1. Identificar Subproblemas: O primeiro passo para resolver um problema usando DP é identificar os subproblemas. Divida o problema em subproblemas menores e gerenciáveis que, quando resolvidos, contribuem para a resolução do problema principal.
2. Solução Recursiva: Desenvolva uma solução recursiva que expresse a solução de um problema maior em termos de soluções para subproblemas menores. Esta formulação recursiva captura a subestrutura ideal.
3. Memoização ou Tabulação: Para resolver subproblemas sobrepostos, você pode escolher entre duas técnicas comuns:
   • Memoização: Armazene os resultados de subproblemas em uma estrutura de dados (geralmente um array ou tabela hash) à medida que são computados. Quando um subproblema for encontrado novamente, recupere sua solução do armazenamento em vez de recalculá-la. Isso também é conhecido como abordagem de cima para baixo .
   • Tabulação: Crie uma tabela (geralmente uma matriz 2D) para armazenar soluções para subproblemas de baixo para cima . Comece resolvendo os menores subproblemas e vá avançando progressivamente até o problema principal.
4. Solução Ótima: Uma vez resolvidos todos os subproblemas, a solução do problema principal pode ser obtida combinando as soluções de seus subproblemas de acordo com a estrutura recursiva do problema.

A Programação Dinâmica é aplicada a uma ampla gama de problemas, incluindo encontrar os caminhos mais curtos em gráficos, otimizar a alocação de recursos, contar combinações, resolver problemas de mochila e muito mais. Sua capacidade de otimizar soluções, dividindo problemas complexos em partes mais simples e evitando cálculos redundantes, torna-a uma técnica fundamental no projeto e otimização de algoritmos.

Conceitos importantes: abordagem de baixo para cima, de cima para baixo, memorização, tabulação

Indicadores-chave:

• O problema pode ser dividido em subproblemas menores sobrepostos.
• É necessário otimizar armazenando e reutilizando soluções para subproblemas.
• Você deseja resolver problemas que envolvam otimização ou contagem.

Código do modelo:

O modelo para memoização de cima para baixo é uma das muitas maneiras de implementar programação dinâmica.

Pitão

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

Backtracking é uma técnica algorítmica geral para resolver problemas de forma incremental, experimentando diferentes possibilidades e desfazendo-as se não levarem a uma solução. É usado quando uma pesquisa exaustiva é necessária.

Aqui está uma visão detalhada de como funciona o retrocesso:

1. Exploração do espaço do problema: o retrocesso explora o espaço do problema construindo gradativamente uma solução, uma peça de cada vez. A cada passo, toma uma decisão e segue em frente.
2. Estrutura Recursiva: O retrocesso geralmente envolve recursão. Começa com uma solução parcial inicial e explora todas as formas possíveis de estendê-la. Este processo continua recursivamente até que uma solução completa seja encontrada ou se torne evidente que não existe nenhuma solução válida.
3. Pontos de Decisão: Em cada etapa, existem pontos de decisão onde o algoritmo deve escolher entre as opções disponíveis. Essas escolhas levam à ramificação do processo de exploração.
4. Validação da Solução: Após fazer uma escolha, o algoritmo verifica se a solução parcial atual é válida. Se for válido, o algoritmo prossegue para a próxima etapa. Caso contrário, recua, desfazendo a escolha anterior e explorando outras opções.
5. Condições de rescisão: O retrocesso continua até que uma das duas condições seja atendida:
   • Uma solução válida é encontrada e, nesse caso, o algoritmo para e retorna a solução.
   • É determinado que não existe nenhuma solução válida, momento em que o algoritmo volta a um ponto de decisão anterior e explora diferentes opções.
6. Poda: Para otimizar a pesquisa, o retrocesso geralmente inclui estratégias de poda. A poda envolve evitar a exploração de caminhos que certamente levarão a soluções inválidas, reduzindo significativamente o espaço de busca.

Aplicações de retrocesso:

O retrocesso é usado em vários domínios de problemas, incluindo:

• Resolvendo quebra-cabeças como Sudoku e N-Queens.
• Gerando permutações e combinações.
• Procurando caminhos em gráficos e árvores.
• Problemas de satisfação de restrições (por exemplo, o problema do caixeiro viajante).
• Algoritmos de jogo (por exemplo, IA de xadrez).

Indicadores-chave:

• O problema envolve explorar múltiplas possibilidades de forma incremental.
• Existem pontos de decisão ou restrições que exigem a experimentação de diferentes opções.
• Você precisa encontrar todas as soluções possíveis ou satisfazer condições específicas por meio de uma busca exaustiva.

Código do modelo:

Pitão

 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. Intervalos de mesclagem

A fusão de intervalos envolve a combinação de intervalos sobrepostos ou adjacentes em um conjunto consolidado, frequentemente usado em problemas que envolvem intervalos de tempo ou programação. Ele simplifica as operações baseadas em intervalos.

Aqui está uma visão mais detalhada de como funciona a mesclagem de intervalos:

1. Representação de intervalo: Os intervalos são normalmente representados como pares de pontos inicial e final (por exemplo, [início, fim] ).
2. Classificação: para mesclar intervalos com eficiência, comece classificando-os com base em seus pontos iniciais. Isso garante que os intervalos sobrepostos ou adjacentes sejam adjacentes na lista classificada.
3. Processo de mesclagem: Inicialize uma lista vazia para armazenar os intervalos mesclados. Em seguida, itere pelos intervalos classificados um por um:
   • Se o intervalo atual não se sobrepuser ao anterior, adicione-o à lista de intervalos mesclados.
   • Se houver uma sobreposição, atualize o ponto final do intervalo mesclado anterior para abranger os intervalos atual e anterior, mesclando-os efetivamente.
4. Conclusão: Após processar todos os intervalos, a lista de intervalos mesclados conterá intervalos não sobrepostos e consolidados.

Aplicações de intervalos de mesclagem:

Intervalos de mesclagem são comumente usados em:

• Aplicativos de agendamento e gerenciamento de tempo.
• Detecção de eventos sobrepostos em sistemas de calendário.
• Análise de dados baseada em intervalos, como em consultas de banco de dados.
• Resolução de problemas relacionados à alocação de recursos e agendamento de reuniões.

Ao mesclar intervalos sobrepostos, essa técnica simplifica as operações baseadas em intervalos e aumenta a eficiência em diversas aplicações.

Indicadores-chave:

• Você está lidando com intervalos ou dados baseados em tempo.
• Os problemas envolvem a fusão de intervalos sobrepostos ou adjacentes.
• Você deseja simplificar as operações baseadas em intervalos ou otimizar o agendamento de eventos.

Código do modelo:

Pitão

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

Quer saber mais?

Se você quiser saber mais sobre esses padrões e como implementá-los de forma mais eficaz durante sua próxima entrevista de codificação, confira techinterviews.io hoje mesmo! Oferecemos um currículo abrangente para prepará-lo para sua próxima entrevista de codificação, cobrindo tópicos como estruturas de dados , algoritmos , entrevistas comportamentais e até negociação salarial . Temos até um espaço de trabalho de codificação integrado para você praticar.

Incremente sua preparação para entrevista de codificação hoje mesmo com nosso código promocional TECH30 com desconto de $ 30!