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.
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.
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.
Neste artigo, compilei 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.
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: current , previous e next . Defina atual como o topo da lista vinculada e inicialize anterior e próximo como Nenhum.
Embora a variável atual não seja None , proceda da seguinte forma:
Por fim, defina o cabeçalho da lista invertida para o último nó alcançado, que está armazenado na variável anterior .
Indicadores-chave:
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; }
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:
middle = start + (end - start) / 2
.
Indicadores-chave:
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; }
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:
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; }
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:
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; }
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:
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:
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; }
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:
Indicadores-chave:
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);
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:
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; }
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:
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:
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 }
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.
Enfileirar o nó raiz na fila.
Insira um loop até que a fila esteja vazia:
Repita as etapas 3a-3c até que a fila fique vazia.
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:
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 }
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:
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)); } }
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:
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.
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.
Preenchimento inicial da fila: enfileira todos os nós com grau de entrada 0 na fila. Esses nós podem ser processados primeiro.
Loop de classificação topológica: enquanto a fila não estiver vazia, execute as seguintes etapas:
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.
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:
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; } }
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:
Inicialização: comece com um Trie vazio, que normalmente consiste em um nó raiz sem nenhum caractere associado.
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:
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.
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.
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:
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); } } }
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:
Subproblemas sobrepostos:
Como funciona a programação dinâmica:
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:
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; }
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:
Aplicações de retrocesso:
O retrocesso é usado em vários domínios de problemas, incluindo:
Indicadores-chave:
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; }
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:
Aplicações de intervalos de mesclagem:
Intervalos de mesclagem são comumente usados em:
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:
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()][]); } }
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!
Imagem em destaque “um desenvolvedor escrevendo código” por @Limarc
Gráficos feitos com Okso.app