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 Esta abordagem envolve resolver tantos problemas quanto possível sem um plano ou estratégia clara. Embora possa parecer uma estratégia produtiva, tem várias desvantagens. "triturar". LeetCode 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 , , , 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. Two-Pointers Sliding Window Modified Binary Search Topological Sort 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 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. Os 15 principais padrões de codificaçã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 em Também cobrimos tópicos cruciais como , e até . Curso Preparatório para Entrevista de Codificação Abrangente Techinterviews.io. estruturas de dados entrevistas comportamentais 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: Comece definindo três variáveis: , e . Defina atual como o topo da lista vinculada e inicialize anterior e próximo como Nenhum. current previous next Embora a variável atual não seja , proceda da seguinte forma: None Armazene o nó em uma variável temporária. próximo Inverta o ponteiro do nó para apontar para o nó . atual anterior Atualize para ser o nó atual e para ser o nó. anterior atual próximo Por fim, defina o da lista invertida para o último nó alcançado, que está armazenado na variável . cabeçalho 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 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. A Pesquisa Binária Modificada 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: Comece identificando o ponto médio entre as posições e . Para evitar um potencial estouro de número inteiro, é mais seguro calcular o meio da seguinte forma: . inicial final middle = start + (end - start) / 2 Verifique se a chave corresponde ao elemento no índice . Se isso acontecer, retorne o índice como resultado. intermediário do meio Se a chave não corresponder ao elemento no índice , prossiga para as próximas etapas. intermediário Avalie se a chave é menor que o elemento no do índice. Se for, restrinja seu intervalo de pesquisa atualizando to . meio end middle - 1 Por outro lado, se a chave for maior que o elemento no índice , ajuste seu intervalo de pesquisa atualizando para . middle start 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 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. técnica de Dois Ponteiros 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 para . O(n^2) O(n) O padrão abrange diversas variações, cada uma adaptada a cenários específicos. Essas variações incluem , e um método exclusivo conhecido como muitas vezes referido como a técnica , que envolve dois ponteiros movendo-se em velocidades diferentes através de uma estrutura de dados, particularmente útil para detectar ciclos. "Dois Ponteiros" a mesma direção a direção oposta "rápido e lento", "tartaruga e lebre" 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 ), considere empregar dois ponteiros. O (n ^ 2) 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 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. técnica da janela deslizante 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: Inserimos elementos 'K' em nosso heap mínimo ou máximo (isso depende da implementação). 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: um Max Heap para identificar o maior elemento e um Min Heap para localizar o menor. Utilize dois heaps: Preencha o Max Heap com a primeira metade dos números, visando encontrar o maior entre eles. Preencha o Min Heap com a segunda metade dos números para identificar o menor nesta parte. 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 , ou , é 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. DFS Depth-First Search Para executar DFS em uma árvore, você precisa começar na raiz. Em seguida, siga as etapas abaixo: Explore o nó atual visitando seus nós filhos, normalmente da para . esquerda a direita a cada nó filho, aprofundando-se na árvore. Aplique recursivamente o processo DFS Depois que todos os nós filhos forem visitados, para o nó pai. volte para cada filho não visitado do nó atual até que todos os nós da árvore tenham sido visitados. Repita as etapas 1 a 3 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 e . 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. Diferença com DFS em um gráfico: marcação de nós visitados tratamento adequado do retrocesso 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: Inicialize uma estrutura de dados de fila vazia para controlar os nós a serem visitados. o nó raiz na fila. Enfileirar Insira um loop até que a fila esteja vazia: Retire da fila o nó no início da fila. Processe o nó retirado da fila (por exemplo, visite ou execute alguma operação nele). Enfileirar todos os filhos do nó (se houver) na fila. até que a fila fique vazia. Repita as etapas 3a-3c 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 , 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. nível por nível 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. Diferença com BFS em um gráfico: 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 , também conhecida como , é 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 Disjoint Set Union (DSU) Union Find é implementado da seguinte forma: 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. Inicializaçã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. Operação de união: 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. Operação Find: 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. Detecção de ciclo: 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. Otimização: 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. é um algoritmo para organizar os nós de um grafo acíclico direcionado ( ) 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. Topological Sort DAG Aqui está uma análise passo a passo da classificação topológica: comece com um gráfico acíclico direcionado ( ) que representa tarefas ou nós com dependências. Inicialize uma fila para armazenar os nós classificados. Inicialização: DAG 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. Cálculo em graus: enfileira todos os nós com grau de entrada 0 na fila. Esses nós podem ser processados primeiro. Preenchimento inicial da fila: enquanto a fila não estiver vazia, execute as seguintes etapas: Loop de classificação topológica: Retire um nó da frente da fila. Processe o nó (por exemplo, adicione-o à lista ordenada). Para cada um dos vizinhos do nó (nós para os quais ele aponta), diminua seu grau de entrada em 1. Se o grau de entrada de um vizinho se tornar 0 como resultado do decremento, coloque-o na fila. 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. Conclusão: 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. Detecção de Ciclo: 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 é 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. Trie Veja como implementar um Trie: comece com um Trie vazio, que normalmente consiste em um nó raiz sem nenhum caractere associado. Inicialização: Para inserir uma palavra no Trie, comece no nó raiz e percorra a árvore, um caractere por vez. Para cada caractere da palavra: Inserção: Verifique se existe um nó filho com esse caractere no nó atual. Se isso acontecer, vá para o nó filho. Caso contrário, crie um novo nó filho com o personagem e vá até ele. 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. Completação de palavra: 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. Pesquisa de prefixo: 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. Exclusão: 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 é 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. A Programação Dinâmica 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: 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. Identificar Subproblemas: 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. Solução Recursiva: Para resolver subproblemas sobrepostos, você pode escolher entre duas técnicas comuns: Memoização ou Tabulaçã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 . Memoização: de cima para baixo Crie uma tabela (geralmente uma matriz 2D) para armazenar soluções para subproblemas de . Comece resolvendo os menores subproblemas e vá avançando progressivamente até o problema principal. Tabulação: baixo para cima 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. Solução Ótima: 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. abordagem de baixo para cima, de cima para baixo, memorização, tabulação Conceitos importantes: 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 é 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. Backtracking Aqui está uma visão detalhada de como funciona o retrocesso: 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. Exploração do espaço do problema: 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. Estrutura Recursiva: 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. Pontos de Decisã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. Validação da Solução: O retrocesso continua até que uma das duas condições seja atendida: Condições de rescisão: 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. 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. Poda: 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: Os intervalos são normalmente representados como pares de pontos e (por exemplo, ). Representação de intervalo: inicial final [início, fim] 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. Classificação: Inicialize uma lista vazia para armazenar os intervalos mesclados. Em seguida, itere pelos intervalos classificados um por um: Processo de mesclagem: 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. Após processar todos os intervalos, a lista de intervalos mesclados conterá intervalos não sobrepostos e consolidados. Conclusão: 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 hoje mesmo! Oferecemos um currículo abrangente para prepará-lo para sua próxima entrevista de codificação, cobrindo tópicos como , , e até . Temos até um espaço de trabalho de codificação integrado para você praticar. techinterviews.io estruturas de dados algoritmos entrevistas comportamentais negociação salarial Incremente sua preparação para entrevista de codificação hoje mesmo com nosso código promocional com desconto de $ 30! TECH30 Imagem em destaque por @Limarc “um desenvolvedor escrevendo código” Gráficos feitos com Okso.app