Força Bruta

1class Solution {
2    public List<List<Integer>> threeSum(int[] nums) {
3        List<List<Integer>> threeSums = new ArrayList<>();
4        
5        for (int i = 0; i < nums.length; i++) {
6            for (int j = i+1; j < nums.length; j++) {
7                for (int k = j+1; k < nums.length; k++) {
8                    if (nums[i] + nums[j] + nums[k] == 0) {
9                        List<Integer> sortedAnswer = Arrays.asList(nums[i], nums[j], nums[k]);
10                        Collections.sort(sortedAnswer);
11                        if (!threeSums.contains(sortedAnswer)) {
12                            threeSums.add(sortedAnswer);
13                        }
14                    }
15                }
16            }
17        }
18        
19        return threeSums;
20    }
21}

Complexidade de Tempo/Espaço

• Complexidade de tempo:O(n³)
• Complexidade do espaço: O(len(answer))(a complexidade do espaço será dimensionada de acordo com o número de trigêmeos encontrados)

Hashmap de soma dupla

1class Solution {
2    public List<List<Integer>> threeSum(int[] nums) {
3        Arrays.sort(nums);
4        List<List<Integer>> threeSums = new ArrayList<>();
5        for (int i = 0; i < nums.length; i++) {
6            if (i > 0 && nums[i] == nums[i - 1]) {
7                continue;
8            }
9            int target = -nums[i];
10            int l = i + 1, r = nums.length - 1;
11            while (l < r) {
12                if (nums[l] + nums[r] == target) {
13                    threeSums.add(Arrays.asList(nums[i], nums[l], nums[r]));
14                    l++;
15                    while (l < r && nums[l] == nums[l - 1]) {
16                        l++;
17                    }
18                } else if (nums[l] + nums[r] < target) {
19                    l++;
20                } else {
21                    r--;
22                }
23            }
24        }
25        return threeSums;
26    }
27}

Complexidade de Tempo/Espaço

• Complexidade de tempo:O(n²)
• Complexidade do espaço: O(n)(ou O(1)se classificado no local)

Força Bruta

1import java.util.HashMap;
2
3 class Solution {
4  public static int[] twoSum(int[] nums, int target) {
5      // 1. Iterate over every possible number pair
6      for (int i = 0; i < nums.length; i++) {
7          // j is always ahead of i so that we don't re-evaluate already evaluated sums
8          for (int j = i + 1; j < nums.length; j++) {
9              // 2. Check if a given pair adds up to our target
10              if (nums[i] + nums[j] == target) {
11                  // Return the indices when a pair has been found
12                  return new int[]{i, j};
13              }
14          }
15      }
16      // Return an empty array if no pair is found
17      return new int[]{};
18  }
19 }

Análise de Complexidade Temporal/Espaço

• Complexidade de Tempo: O(n^2), onde né o tamanho do array. Para cada número, precisamos avaliar todos os outros números do array.

• Complexidade do espaço: O(1), desconsiderando a entrada, todas as outras variáveis ​​têm espaço constante.

Tabela de hash

1import java.util.HashMap;
2
3 class Solution {
4  public static int[] twoSum(int[] nums, int target) {
5        // Our hash table that stores at which index the number is at
6        HashMap<Integer, Integer> numToIndex = new HashMap<>();
7        
8        // 1. Iterate over every number in the array
9        for (int i = 0; i < nums.length; i++) {
10            // 2. Calculate the complement that would sum to our target
11            int complement = target - nums[i];
12            
13            // 3. Check if that complement is in our hash table
14            if (numToIndex.containsKey(complement)) {
15                return new int[]{numToIndex.get(complement), i};
16            }
17            
18            // 4. Add the current number to our hash table
19            numToIndex.put(nums[i], i);
20        }
21        
22        // If no solution found, return an empty array
23        return new int[]{};
24    }
25 }

Complexidade de Tempo/Espaço

• Complexidade de Tempo: O(n), onde né o tamanho do array. Iteramos sobre cada número no array e as operações de consulta/adição da tabela de hash levam um tempo constante.
• Complexidade do Espaço: O(n), onde né o tamanho do array. Nosso mapa de hash armazena todos os números no array de entrada.

HackerRank

LeetCode

Two Sum Reverse a Linked List Merge Intervals Longest Substring Without Repeating Characters Binary Tree Inorder Traversal Valid Parentheses Search in Rotated Sorted Array Merge Two Sorted Lists Maximum Subarray Word Break Coin Change Climbing Stairs Subtree of Another Tree Product of Array Except Self Valid Anagram Linked List Cycle Find Minimum in Rotated Sorted Array Combination Sum House Robber Longest Palindromic Substring Word Ladder Pow(x, n) Rotate Image Group Anagrams Maximum Depth of Binary Tree Insert Interval Subsets Palindromic Substrings Minimum Path Sum 3Sum Best Time to Buy and Sell Stock Course Schedule Linked List Random Node Min Stack Reverse Integer Integer to Roman Roman to Integer Palindrome Number Container With Most Water Longest Valid Parentheses Maximum Product Subarray Search Insert Position Unique Paths Decode Ways Jump Game Word Search Set Matrix Zeroes Trapping Rain Water Sudoku Solver Spiral Order Matrix Permutations LRU Cache Validate Binary Search Tree Recover Binary Search Tree Kth Largest Element Merge K Sorted Lists Flatten Nested List Iterator Binary Tree Zigzag Level Order Traversal Longest Consecutive Sequence Graph Valid Tree Course Schedule II Valid Palindrome Longest Common Prefix Find Peak Element Find the Duplicate Number First Missing Positive N-Queens Minimum Window Substring Rotate List Word Search II Basic Calculator First Unique Character in a String Serialize and Deserialize Binary Tree Sort Colors Find Median from Data Stream Isomorphic Strings Reverse Linked List II Maximal Square Largest Rectangle in Histogram Binary Tree Maximum Path Sum House Robber II N-Queens II Best Time to Buy and Sell Stock II Clone Graph Sliding Window Maximum Merge Sorted Array Find the Celebrities Regular Expression Matching Distinct Subsequences Longest Increasing Subsequence Palindrome Partitioning Different Ways to Add Parentheses Serialize and Deserialize BST Range Sum Query Jump Game II Copy List with Random Pointer Critical Connections in a Network Coin Change 2 Path Sum Number of Islands

Two Sum Add Two Numbers Longest Substring Without Repeating Characters Median of Two Sorted Arrays Longest Palindromic Substring Zigzag Conversion Reverse Integer String to Integer (atoi) Palindrome Number Regular Expression Matching Container With Most Water Integer to Roman Roman to Integer Longest Common Prefix 3Sum 3Sum Closest Letter Combinations of a Phone Number Valid Parentheses Merge Two Sorted Lists Remove Nth Node From End of List Generate Parentheses Merge k Sorted Lists Swap Nodes in Pairs Reverse Nodes in k-Group Remove Duplicates from Sorted Array Remove Element Implement strStr() Divide Two Integers Substring with Concatenation of All Words Next Permutation Longest Valid Parentheses Search in Rotated Sorted Array Find First and Last Position of Element in Sorted Array Search Insert Position Valid Sudoku Sudoku Solver Count and Say Combination Sum Combination Sum II First Missing Positive Trapping Rain Water Multiply Strings Jump Game Permutations Permutations II Rotate Image Group Anagrams Pow(x, n) N-Queens N-Queens II Maximum Subarray Spiral Matrix Jump Game II Merge Intervals Insert Interval Length of Last Word Spiral Matrix II Set Matrix Zeroes Search a 2D Matrix Sort Colors Minimum Window Substring Search in Rotated Sorted Array II Remove Duplicates from Sorted List Remove Duplicates from Sorted List II Subsets Word Search Climbing Stairs Set Matrix Zeroes Search a 2D Matrix II Sort Colors Minimum Path Sum Unique Paths Unique Paths II Subsets II Word Ladder Word Ladder II Longest Consecutive Sequence Palindrome Partitioning Restore IP Addresses Distinct Subsequences Largest Rectangle in Histogram Maximal Rectangle Scramble String Interleaving String Minimum Edit Distance Decode Ways Unique Binary Search Trees Unique Binary Search Trees II Validate Binary Search Tree Binary Tree Maximum Path Sum Flatten Binary Tree to Linked List Populating Next Right Pointers in Each Node Populating Next Right Pointers in Each Node II Binary Tree Inorder Traversal Binary Tree Preorder Traversal Binary Tree Postorder Traversal Symmetric Tree Binary Tree Level Order Traversal Binary Tree Zigzag Level Order Traversal Maximum Depth of Binary Tree

 

Exemplos de algoritmos e estruturas de dados frequentemente usados em entrevistas técnicas, com explicações e exemplos para ajudar na compreensão:

Two Sum

Dado um array de inteiros, encontre dois números que somam um valor alvo específico.

Abordagem: Use um hash map para armazenar cada número do array e seu índice. Para cada número, verifique se o complemento (target – número) existe no hash map.
Exemplo: nums = [2, 7, 11, 15], target = 9. A solução é [0, 1] (porque nums[0] + nums[1] == 9).
Considerações: Ideal para demonstrar conhecimento de hash tables e otimização de tempo de execução de O(n^2) para O(n).
Reverse a Linked List: Inverta a ordem dos nós em uma linked list.

Abordagem: Use três ponteiros: prev, current e next. Itere pela lista, invertendo a direção dos ponteiros.
Exemplo: 1 -> 2 -> 3 -> 4 -> 5 torna-se 5 -> 4 -> 3 -> 2 -> 1.
Considerações: Importante para entender manipulação de ponteiros e linked lists.

Merge Intervals:

Dado uma coleção de intervalos, combine todos os intervalos sobrepostos.

Abordagem: Ordene os intervalos pelo início e, em seguida, itere sobre eles, combinando os intervalos sobrepostos.
Exemplo: [[1,3],[2,6],[8,10],[15,18]] torna-se [[1,6],[8,10],[15,18]].
Considerações: Demonstra conhecimento de algoritmos de ordenação e manipulação de intervalos.

Longest Substring Without Repeating Characters:

Encontre o comprimento da maior substring sem caracteres repetidos.

Abordagem: Use a técnica de sliding window com um hash set para rastrear os caracteres no intervalo atual.
Exemplo: Para “abcabcbb”, a resposta é 3 (“abc”).
Considerações: Útil para demonstrar otimização de algoritmos com sliding window.

Binary Tree Inorder Traversal:

Percorra uma binary tree usando a ordem inorder (esquerda, raiz, direita).

Abordagem: Use recursão ou uma pilha para implementar a travessia inorder.
Exemplo: Para uma árvore com raiz 1, esquerda 2, direita 3, a travessia inorder é 2 -> 1 -> 3.
Considerações: Fundamental para entender algoritmos de travessia de árvores.

Valid Parentheses:

Determine se uma string contendo parênteses é válida (ou seja, cada parêntese de abertura tem um parêntese de fechamento correspondente).

Abordagem: Use uma pilha para rastrear os parênteses de abertura. Quando encontrar um parêntese de fechamento, verifique se corresponde ao parêntese de abertura no topo da pilha.
Exemplo: “()[]{}” é válido, “(]” não é.
Considerações: Demonstra conhecimento de estruturas de pilha e correspondência de caracteres.

Search in Rotated Sorted Array:

Pesquise um valor em um array ordenado que foi rotacionado.

Abordagem: Use uma variação da busca binária. Encontre o ponto de rotação e, em seguida, execute a busca binária na metade apropriada do array.
Exemplo: [4,5,6,7,0,1,2], target = 0. A resposta é 4 (índice de 0).
Considerações: Demonstra conhecimento de busca binária e manipulação de arrays rotacionados.

Merge Two Sorted Lists:

Combine duas sorted linked lists em uma única sorted linked list.

Abordagem: Use um ponteiro para rastrear a cabeça da nova lista e compare os nós das duas listas para determinar qual nó adicionar à nova lista.
Exemplo: 1->2->4, 1->3->4 torna-se 1->1->2->3->4->4.
Considerações: Importante para entender manipulação de linked lists e algoritmos de ordenação.

Maximum Subarray:

Encontre a soma máxima de um subarray contíguo.

Abordagem: Use o algoritmo de Kadane, que mantém a soma máxima atual e a soma máxima até o momento.
Exemplo: [-2,1,-3,4,-1,2,1,-5,4]. A resposta é 6 ([4,-1,2,1]).
Considerações: Demonstra conhecimento de programação dinâmica e otimização de algoritmos.

Word Break:

Determine se uma string pode ser segmentada em uma sequência de palavras do dicionário.

Abordagem: Use programação dinâmica para construir uma tabela booleana indicando se cada prefixo da string pode ser segmentado.
Exemplo: s = “leetcode”, wordDict = [“leet”, “code”]. A resposta é true.
Considerações: Demonstra conhecimento de programação dinâmica e manipulação de strings.

Coin Change:

Dado um conjunto de denominações de moedas e um valor alvo, encontre o número mínimo de moedas necessárias para atingir o valor alvo.

Abordagem: Use programação dinâmica para construir uma tabela que armazena o número mínimo de moedas necessárias para cada valor de 0 ao valor alvo.
Exemplo: coins = [1, 2, 5], amount = 11. A resposta é 3 (5 + 5 + 1).
Considerações: Demonstra conhecimento de programação dinâmica e problemas de otimização.

Climbing Stairs:

Calcule o número de maneiras distintas de subir até o topo de uma escada com n degraus, onde você pode subir 1 ou 2 degraus de cada vez.

Abordagem: Use programação dinâmica. O número de maneiras de subir até o degrau n é a soma do número de maneiras de subir até o degrau n-1 e o degrau n-2.
Exemplo: Para n = 3, a resposta é 3 (1+1+1, 1+2, 2+1).
Considerações: Demonstra conhecimento de programação dinâmica e sequências de Fibonacci.

Subtree of Another Tree:

Determine se uma árvore é uma subárvore de outra árvore.

Abordagem: Percorra a árvore maior e, para cada nó, verifique se a subárvore enraizada nesse nó é idêntica à árvore menor.
Considerações: Importante para entender algoritmos de travessia de árvores e recursão.

Product of Array Except Self:

Dado um array de inteiros, retorne um novo array onde cada elemento no índice i é o produto de todos os elementos no array original, exceto o elemento no índice i.

Abordagem: Calcule os produtos prefixados e sufixados do array e, em seguida, multiplique-os para obter o resultado.
Exemplo: [1,2,3,4] torna-se [24,12,8,6].
Considerações: Demonstra conhecimento de manipulação de arrays e otimização de algoritmos.

Valid Anagram:

Determine se duas strings são anagramas uma da outra (ou seja, contêm os mesmos caracteres na mesma quantidade, mas em uma ordem diferente).

Abordagem: Use um hash map para contar a frequência de cada caractere em ambas as strings. Se os hash maps forem iguais, as strings são anagramas.
Exemplo: “anagram” e “nagaram” são anagramas.
Considerações: Demonstra conhecimento de hash maps e manipulação de strings.

Linked List Cycle:

Determine se uma linked list contém um ciclo.

Abordagem: Use o algoritmo da lebre e da tartaruga (dois ponteiros, um movendo-se duas vezes mais rápido que o outro). Se houver um ciclo, os ponteiros se encontrarão.
Considerações: Importante para entender manipulação de linked lists e algoritmos de detecção de ciclos.

Find Minimum in Rotated Sorted Array:

Encontre o elemento mínimo em um array ordenado que foi rotacionado.

Abordagem: Use uma variação da busca binária. Compare o elemento do meio com o elemento mais à direita para determinar qual metade do array contém o mínimo.
Considerações: Demonstra conhecimento de busca binária e manipulação de arrays rotacionados.

Combination Sum:

Dado um conjunto de números candidatos e um valor alvo, encontre todas as combinações únicas dos números candidatos que somam o valor alvo.

Abordagem: Use backtracking para explorar todas as combinações possíveis dos números candidatos.
Considerações: Demonstra conhecimento de backtracking e algoritmos de busca.

House Robber:

Dado um array de inteiros representando os valores das casas ao longo de uma rua, determine o valor máximo que você pode roubar sem roubar duas casas adjacentes.

Abordagem: Use programação dinâmica para construir uma tabela que armazena o valor máximo que você pode roubar até cada casa.
Considerações: Demonstra conhecimento de programação dinâmica e problemas de otimização.

Longest Palindromic Substring:

Encontre a substring palindrômica mais longa em uma determinada string.

Abordagem: Use programação dinâmica ou expanda ao redor do centro para encontrar a substring palindrômica mais longa.
Considerações: Demonstra conhecimento de programação dinâmica e manipulação de strings.

Word Ladder:

Dado uma palavra inicial, uma palavra final e um dicionário de palavras, encontre o comprimento da sequência de transformação mais curta da palavra inicial para a palavra final, usando apenas palavras do dicionário e alterando apenas uma letra de cada vez.

Abordagem: Use a busca em largura (BFS) para explorar o espaço de busca de palavras possíveis.
Considerações: Demonstra conhecimento de algoritmos de busca em grafos e manipulação de strings.
Pow(x, n): Implemente a função para calcular x elevado à potência n.

Abordagem: Use recursão e divida e conquiste para calcular a potência de forma eficiente.
Considerações: Demonstra conhecimento de recursão e algoritmos de divisão e conquista.

Rotate Image:

Gire uma matriz quadrada (imagem) 90 graus no sentido horário.

Abordagem: Inverta a matriz ao longo da diagonal principal e, em seguida, inverta cada linha.
Considerações: Demonstra conhecimento de manipulação de matrizes e operações in-place.

Group Anagrams:

Dado um array de strings, agrupe os anagramas juntos.

Abordagem: Use um hash map para mapear cada string para sua versão ordenada. Todas as strings que são anagramas umas das outras terão a mesma versão ordenada.
Considerações: Demonstra conhecimento de hash maps e manipulação de strings.

Maximum Depth of Binary Tree:

Encontre a profundidade máxima de uma binary tree.

Abordagem: Use recursão para percorrer a árvore e calcular a profundidade de cada nó. A profundidade máxima é a profundidade máxima de qualquer nó na árvore.
Considerações: Fundamental para entender algoritmos de travessia de árvores e recursão.

Insert Interval:

Dado uma lista de intervalos não sobrepostos, insira um novo intervalo na lista.

Abordagem: Encontre a posição correta para inserir o novo intervalo e, em seguida, combine quaisquer intervalos sobrepostos.
Considerações: Demonstra conhecimento de manipulação de intervalos e algoritmos de ordenação.

Subsets:

Dado um conjunto de números distintos, retorne todos os subconjuntos possíveis.

Abordagem: Use backtracking para gerar todos os subconjuntos possíveis.
Considerações: Demonstra conhecimento de backtracking e algoritmos de busca.

Palindromic Substrings:

Dado uma string, conte o número de substrings palindrômicas.

Abordagem: Use programação dinâmica ou expanda ao redor do centro para encontrar todas as substrings palindrômicas.
Considerações: Demonstra conhecimento de programação dinâmica e manipulação de strings.

Minimum Path Sum:

Dado uma grade de números não negativos, encontre um caminho da parte superior esquerda para a parte inferior direita que minimize a soma de todos os números ao longo do caminho.

Abordagem: Use programação dinâmica para construir uma tabela que armazena a soma mínima do caminho até cada célula na grade.
Considerações: Demonstra conhecimento de programação dinâmica e problemas de otimização.

3Sum:

Dado um array de inteiros, encontre todos os triplos únicos que somam zero.

Abordagem: Ordene o array e, em seguida, itere sobre ele. Para cada elemento, use dois ponteiros para encontrar os dois outros elementos que somam zero.
Considerações: Demonstra conhecimento de algoritmos de ordenação e manipulação de arrays.

Find Peak Element:

Encontre um elemento de pico em um array. Um elemento de pico é um elemento que é maior que seus vizinhos.

Abordagem: Use busca binária para encontrar um elemento de pico.
Considerações: Demonstra conhecimento de busca binária e manipulação de arrays.

Serialize and Deserialize Binary Tree:

Serialize uma binary tree em uma string e, em seguida, desserialize a string de volta em uma binary tree.

Abordagem: Use uma travessia pré-ordem ou pós-ordem para serializar a árvore. Use a mesma travessia para desserializar a árvore.
Considerações: Importante para entender algoritmos de travessia de árvores e serialização/desserialização de dados.

Partition Equal Subset Sum:

Dado um array de inteiros, determine se o array pode ser particionado em dois subconjuntos com somas iguais.

Abordagem: Use programação dinâmica para construir uma tabela que armazena se cada soma possível pode ser alcançada usando um subconjunto dos números no array.
Considerações: Demonstra conhecimento de programação dinâmica e problemas de otimização.

Sort Colors:

Dado um array de cores (representadas por 0, 1 e 2), ordene as cores in-place.

Abordagem: Use o algoritmo de partição de três vias para ordenar as cores.
Considerações: Demonstra conhecimento de algoritmos de ordenação e operações in-place.

Letter Combinations of a Phone Number:

Dado um número de telefone, retorne todas as combinações de letras possíveis que o número pode representar.

Abordagem: Use backtracking para gerar todas as combinações possíveis de letras.
Considerações: Demonstra conhecimento de backtracking e algoritmos de busca.

Best Time to Buy and Sell Stock:

Dado um array de preços de ações, encontre o lucro máximo que você pode obter comprando e vendendo uma ação uma vez.

Abordagem: Mantenha o controle do preço mínimo e do lucro máximo. Itere sobre o array e atualize o preço mínimo e o lucro máximo conforme necessário.
Considerações: Demonstra conhecimento de problemas de otimização e manipulação de arrays.

Top K Frequent Elements:

Dado um array de inteiros, retorne os k elementos mais frequentes.

Abordagem: Use um hash map para contar a frequência de cada elemento. Em seguida, use uma fila de prioridade para armazenar os k elementos mais frequentes.
Considerações: Demonstra conhecimento de hash maps, filas de prioridade e algoritmos de ordenação.

Kth Largest Element in an Array:

Encontre o k-ésimo maior elemento em um array.

Abordagem: Use o algoritmo quickselect para encontrar o k-ésimo maior elemento.
Considerações: Demonstra conhecimento de algoritmos de seleção e manipulação de arrays.

Unique Paths:

Dado uma grade de m x n, encontre o número de caminhos únicos da parte superior esquerda para a parte inferior direita.

Abordagem: Use programação dinâmica para construir uma tabela que armazena o número de caminhos únicos até cada célula na grade.
Considerações: Demonstra conhecimento de programação dinâmica e problemas de otimização.

Longest Common Subsequence:

Encontre a subsequência comum mais longa de duas strings.

Abordagem: Use programação dinâmica para construir uma tabela que armazena o comprimento da subsequência comum mais longa de cada par de prefixos das duas strings.
Considerações: Demonstra conhecimento de programação dinâmica e manipulação de strings.

Implement Trie (Prefix Tree):

Implemente uma estrutura de dados trie (árvore de prefixos).

Abordagem: Use um nó para representar cada caractere em um prefixo. Cada nó tem um ponteiro para seus filhos e um sinalizador que indica se o nó representa o final de uma palavra.
Considerações: Importante para entender estruturas de dados de árvores e manipulação de strings.

Binary Search:

Implemente o algoritmo de busca binária.

Abordagem: Compare o valor alvo com o elemento do meio do array. Se o valor alvo for menor que o elemento do meio, pesquise na metade esquerda do array. Se o valor alvo for maior que o elemento do meio, pesquise na metade direita do array.
Considerações: Fundamental para entender algoritmos de busca e manipulação de arrays.

Flood Fill:

Dado uma imagem e uma coordenada inicial, preencha a região conectada da imagem com uma nova cor.

Abordagem: Use a busca em profundidade (DFS) ou a busca em largura (BFS) para percorrer a região conectada e preenchê-la com a nova cor.
Considerações: Demonstra conhecimento de algoritmos de busca em grafos e manipulação de matrizes.

Course Schedule:

Dado uma lista de cursos e seus pré-requisitos, determine se é possível concluir todos os cursos.

Abordagem: Use a detecção de ciclos em grafos. Construa um grafo onde cada nó representa um curso e cada aresta representa um pré-requisito. Se o grafo contiver um ciclo, não é possível concluir todos os cursos.
Considerações: Demonstra conhecimento de algoritmos de grafos e detecção de ciclos.

Lowest Common Ancestor of a Binary Search Tree:

Encontre o ancestral comum mais baixo de dois nós em uma binary search tree.

Abordagem: Percorra a árvore. Se ambos os nós estiverem na subárvore esquerda, o ancestral comum mais baixo está na subárvore esquerda. Se ambos os nós estiverem na subárvore direita, o ancestral comum mais baixo está na subárvore direita. Caso contrário, o nó atual é o ancestral comum mais baixo.
Considerações: Importante para entender algoritmos de travessia de árvores e propriedades de binary search trees.

Basic Calculator II:

Implemente uma calculadora básica para avaliar expressões de string.

Abordagem: Use uma pilha para armazenar os operandos e operadores. Itere sobre a string e execute as operações na ordem correta.
Considerações: Demonstra conhecimento de estruturas de pilha e manipulação de strings.

Jump Game:

Dado um array de inteiros, onde cada elemento representa o número máximo de degraus que você pode dar para frente, determine se você pode chegar ao último índice.

Abordagem: Mantenha o controle do índice mais distante que você pode alcançar. Itere sobre o array e atualize o índice mais distante conforme necessário. Se você puder alcançar o último índice, retorne true. Caso contrário, retorne false.
Considerações: Demonstra conhecimento de problemas de otimização e manipulação de arrays.

Zigzag Conversion:

Converta uma string em um padrão em zigue-zague com um determinado número de linhas.

Abordagem: Itere sobre a string e adicione cada caractere à linha apropriada. Em seguida, concatene as linhas para obter a string convertida.
Considerações: Demonstra conhecimento de manipulação de strings e padrões.

Set Matrix Zeroes:

Dado uma matriz, se um elemento for 0, defina toda a sua linha e coluna como 0.

Abordagem: Use o primeiro elemento de cada linha e coluna para rastrear se a linha ou coluna deve ser definida como 0.
Considerações: Demonstra conhecimento de manipulação de matrizes e operações in-place.

Permutations:

Dado um array de números distintos, retorne todas as permutações possíveis.

Abordagem: Use backtracking para gerar todas as permutações possíveis.
Considerações: Demonstra conhecimento de backtracking e algoritmos de busca.

LRU Cache:

Designe uma cache LRU (Least Recently Used).

Abordagem: Use uma combinação de um hash map e uma doubly linked list. O hash map armazena os pares chave-valor e a doubly linked list rastreia a ordem em que as chaves foram acessadas.
Considerações: Demonstra conhecimento de hash maps, linked lists e design de estruturas de dados.

N-Queens:

Resolva o problema das N-Rainhas. Coloque N rainhas em um tabuleiro de xadrez de N x N para que nenhuma rainha ataque outra.

Abordagem: Use backtracking para explorar todas as possíveis colocações das rainhas.
Considerações: Demonstra conhecimento de backtracking e algoritmos de busca.

Find Median from Data Stream:

Designe uma estrutura de dados que possa encontrar a mediana de um fluxo de dados.

Abordagem: Use duas filas de prioridade: uma fila máxima para armazenar a metade inferior dos dados e uma fila mínima para armazenar a metade superior dos dados.
Considerações: Demonstra conhecimento de filas de prioridade e design de estruturas de dados.

Maximum Product Subarray:

Encontre o produto máximo de um subarray contíguo.

Abordagem: Mantenha o controle do produto máximo atual, do produto mínimo atual e do produto máximo até o momento. Itere sobre o array e atualize os produtos conforme necessário.
Considerações: Demonstra conhecimento de problemas de otimização e manipulação de arrays.

Binary Tree Maximum Path Sum:

Encontre a soma máxima do caminho em uma binary tree.

Abordagem: Use recursão para percorrer a árvore e calcular a soma máxima do caminho para cada nó. A soma máxima do caminho é a soma máxima do caminho de qualquer nó na árvore.
Considerações: Importante para entender algoritmos de travessia de árvores e recursão.

Search a 2D Matrix:

Pesquise um valor em uma matriz 2D ordenada.

Abordagem: Use busca binária para encontrar a linha que pode conter o valor alvo. Em seguida, use busca binária novamente para encontrar o valor alvo na linha.
Considerações: Demonstra conhecimento de busca binária e manipulação de matrizes.

Valid Sudoku:

Determine se um tabuleiro de Sudoku é válido.

Abordagem: Verifique se cada linha, coluna e bloco 3×3 contém os dígitos de 1 a 9 sem repetição.
Considerações: Demonstra conhecimento de manipulação de matrizes e restrições.

Container with Most Water:

Dado um array de inteiros que representam as alturas das linhas verticais, encontre o contêiner que pode conter mais água.

Abordagem: Use dois ponteiros, um no início do array e outro no final do array. Mova o ponteiro com a menor altura em direção ao centro do array. Calcule a área do contêiner em cada etapa e atualize a área máxima conforme necessário.
Considerações: Demonstra conhecimento de problemas de otimização e manipulação de arrays.

Design Add and Search Words Data Structure:

Designe uma estrutura de dados que suporte adicionar novas palavras e pesquisar palavras que correspondam a um padrão.

Abordagem: Use uma trie (árvore de prefixos) para armazenar as palavras. Use a busca em profundidade (DFS) para pesquisar palavras que correspondam a um padrão.
Considerações: Demonstra conhecimento de estruturas de dados de árvores e algoritmos de busca.

Task Scheduler:

Dado um array de tarefas e um número inteiro n, encontre o número mínimo de unidades de tempo necessárias para concluir todas as tarefas.

Abordagem: Calcule a frequência de cada tarefa. O número mínimo de unidades de tempo é o número de vezes que a tarefa mais frequente precisa ser executada, mais o número de vezes que as outras tarefas precisam ser executadas.
Considerações: Demonstra conhecimento de problemas de otimização e manipulação de arrays.

Find the Duplicate Number:

Dado um array de inteiros contendo n + 1 inteiros onde cada inteiro está entre 1 e n (inclusive), prove que pelo menos um número duplicado deve existir. Suponha que haja apenas um número duplicado, encontre o número duplicado.

Abordagem: Use o algoritmo da lebre e da tartaruga (detecção de ciclo de Floyd).
Considerações: Demonstra conhecimento de algoritmos de detecção de ciclos e manipulação de arrays.

Maximum Width of Binary Tree:

Dado uma binary tree, escreva uma função para obter a largura máxima da árvore. A largura de uma linha é definida como o número de nós entre os dois nós não nulos mais distantes, que podem ser após o valor nulo.

Abordagem: Use a busca em largura (BFS) e atribua um índice a cada nó com base em sua posição.
Considerações: Demonstra conhecimento de algoritmos de travessia de árvores e manipulação de dados.

Evaluate Reverse Polish Notation:

Avalie o valor de uma expressão de Notação Polonesa Reversa (RPN), também conhecida como notação pós-fixada.

Abordagem: Use uma pilha para armazenar os operandos. Quando encontrar um operador, retire os dois operandos do topo da pilha, execute a operação e coloque o resultado de volta na pilha.
Considerações: Demonstra conhecimento de estruturas de pilha e manipulação de strings.

Spiral Matrix:

Dado uma matriz m x n, retorne todos os elementos da matriz em ordem espiral.

Abordagem: Mantenha o controle dos limites da matriz. Itere sobre a matriz em ordem espiral e atualize os limites conforme necessário.
Considerações: Demonstra conhecimento de manipulação de matrizes e padrões.

Surrounded Regions:

Dado uma matriz m x n de caracteres, capture todas as regiões ‘O’ que estão cercadas por ‘X’.

Abordagem: Percorra a borda da matriz. Para cada ‘O’ na borda, use a busca em profundidade (DFS) para marcar todas as regiões conectadas ‘O’ como ‘T’. Em seguida, itere sobre a matriz novamente. Converta todos os ‘O’ restantes em ‘X’ e todos os ‘T’ em ‘O’.
Considerações: Demonstra conhecimento de algoritmos de busca em grafos e manipulação de matrizes.

Valid Palindrome:

Dado uma string, determine se é um palíndromo, considerando apenas caracteres alfanuméricos e ignorando maiúsculas e minúsculas.

Abordagem: Use dois ponteiros, um no início da string e outro no final da string. Mova os ponteiros em direção ao centro da string, ignorando caracteres não alfanuméricos. Compare os caracteres em cada etapa. Se os caracteres forem diferentes, a string não é um palíndromo.
Considerações: Demonstra conhecimento de manipulação de strings e padrões.

Jump Game II:

Dado um array de inteiros, onde cada elemento representa o número máximo de degraus que você pode dar para frente, encontre o número mínimo de degraus necessários para chegar ao último índice.

Abordagem: Use uma abordagem gananciosa. Mantenha o controle do índice mais distante que você pode alcançar e o número de degraus que você deu. Itere sobre o array e atualize o índice mais distante e o número de degraus conforme necessário.
Considerações: Demonstra conhecimento de problemas de otimização e manipulação de arrays.

LRU Cache:

(Repetição do item 51, mantido para manter a sequência original) Designe uma cache LRU (Least Recently Used).

Abordagem: Use uma combinação de um hash map e uma doubly linked list. O hash map armazena os pares chave-valor e a doubly linked list rastreia a ordem em que as chaves foram acessadas.
Considerações: Demonstra conhecimento de hash maps, linked lists e design de estruturas de dados.

Longest Consecutive Sequence:

Dado um array de inteiros, encontre o comprimento da sequência consecutiva mais longa.

Abordagem: Use um hash set para armazenar todos os números no array. Itere sobre o array e, para cada número, verifique se é o início de uma sequência consecutiva. Se for, encontre o comprimento da sequência.
Considerações: Demonstra conhecimento de hash sets e manipulação de arrays.

Remove Nth Node From End of List:

Dado uma linked list, remova o n-ésimo nó do final da lista e retorne a cabeça da lista.

Abordagem: Use dois ponteiros. Mova o primeiro ponteiro n nós para frente. Em seguida, mova ambos os ponteiros até que o primeiro ponteiro chegue ao final da lista. Remova o nó apontado pelo segundo ponteiro.
Considerações: Importante para entender manipulação de linked lists.

Integer to Roman:

Converta um inteiro em um numeral romano.

Abordagem: Use um hash map para armazenar os valores dos numerais romanos. Itere sobre os numerais romanos em ordem decrescente e subtraia o valor do numeral romano do inteiro até que o inteiro seja 0.
Considerações: Demonstra conhecimento de hash maps e manipulação de números.

Roman to Integer:

Converta um numeral romano em um inteiro.

Abordagem: Use um hash map para armazenar os valores dos numerais romanos. Itere sobre o numeral romano e adicione o valor de cada numeral romano ao inteiro. Se o valor do numeral romano atual for menor que o valor do próximo numeral romano, subtraia o valor do numeral romano atual do inteiro.
Considerações: Demonstra conhecimento de hash maps e manipulação de números.

String to Integer (atoi):

Abordagem: Ignore espaços em branco, leia o sinal (se houver) e converta os caracteres numéricos subsequentes em um número inteiro.
Considerações: Lide com sobrecarga e valores fora do intervalo.

Zigzag Conversion:

Abordagem: Crie linhas que armazenem caracteres enquanto percorrem a string em zigue-zague, depois concatene os resultados.
Considerações: Evidencia manipulação de índices e padrões.

Multiply Strings:

Abordagem: Simule multiplicação manual, acumulando resultados parciais antes de somar.
Considerações: Desafio em otimizar manipulação de strings.

Median of Two Sorted Arrays:

Abordagem: Use busca binária para encontrar a mediana de forma eficiente.
Considerações: Demonstra habilidade em busca binária em contextos complexos.

Longest Increasing Subsequence:

Abordagem: Use programação dinâmica ou algoritmo de paciência para encontrar a sequência.
Considerações: Identificação de subsequências e otimização.

Reverse Nodes in k-Group:

Abordagem: Inverta nós de k em k numa lista ligada.
Considerações: Conhecimento aprofundado de manipulação de linked lists.

Word Search:

Abordagem: Use backtracking para verificar a presença de uma palavra em uma grade de caracteres.
Considerações: Algoritmos de busca em matrizes.

Edit Distance:

Abordagem: Use programação dinâmica para calcular a menor edição para transformar uma string em outra.
Considerações: Problemas de transformação e distâncias mínimas.

Minimum Window Substring:

Abordagem: Use a técnica de sliding window para encontrar o menor substrato que contém todos os caracteres.
Considerações: Manipulação de substrings e otimização.

Kth Largest Element in an Array:

Abordagem: Use heap ou Quickselect para eficiência.
Considerações: Algoritmos de ordenação e seleção.

Trapping Rain Water:

Abordagem: Use dois ponteiros para calcular a água retida entre colunas.
Considerações: Análise de problemas de espaço e volume.

Binary Search Tree Iterator:

Abordagem: Use uma pilha para implementar a travessia em ordem.
Considerações: Orthogonalidade em travessias de árvores.

Clone Graph:

Abordagem: Use busca em profundidade ou largura para clonar o gráfico.
Considerações: Estruturas de dados e clonagem.

Longest Common Subsequence:

Abordagem: Use programação dinâmica para encontrar a subsequência comum mais longa entre duas strings.
Considerações: Sequências e problemas de alinhamento.

Graph Valid Tree:

Abordagem: Verifique conectividade e aciclicidade usando BFS ou DFS.
Considerações: Estrutura de grafos e validez de árvores.

Game of Life:

Abordagem: Simule as transições de células vivas e mortas em uma matriz.
Considerações: Manipulação de matrizes e simulação.

Number of Islands:

Abordagem: Use BFS ou DFS para contar e marcar as ilhas em uma matriz.
Considerações: Conectividade em 2D.

Lowest Common Ancestor of a Binary Tree:

Abordagem: Use recursão para localizar o ancestral comum.
Considerações: Travessia de árvores e aninhamento.

Decode Ways:

Abordagem: Use programação dinâmica para calcular maneiras de decodificar uma string numérica em letras.
Considerações: Problemas de mapeamento e interpretação.

House Robber II:

Abordagem: Use programação dinâmica, considerando casas organizadas em um círculo.
Considerações: Otimização de problemas cíclicos.

Randomized Set:

Abordagem: Use uma combinação de array e hash map para permitir operações de tempo constante.
Considerações: Estruturas de dados de conjunto.

Sliding Window Maximum:

Abordagem: Use um deque para obter máximos em um intervalo deslizante.
Considerações: Algoritmos de janelas deslizantes.

Merge K Sorted Lists:

Abordagem: Use uma fila de prioridade para mesclar as listas eficientemente.
Considerações: Estruturas de dados de filas de prioridade.

Binary Tree Right Side View:

Abordagem: Use BFS para capturar a visão direita de uma árvore.
Considerações: Visualização e travessia de árvores.

Palindrome Partitioning:

Abordagem: Use backtracking para encontrar todas as partições palindrômicas possíveis.
Considerações: Particionamento e reconhecimento de padrões.

Vertical Order Traversal of a Binary Tree:

Abordagem: Use BFS com coordenadas para imprimir a ordem vertical.
Considerações: Visualização em árvores e coordenadas.

Peeking Iterator:

Abordagem: Adapte um iterador para permitir espiar o próximo elemento.
Considerações: Manipulação de iteradores.

Kth Smallest Element in a BST: –

Abordagem: Use in-order traversal para encontrar o k-ésimo elemento. – Considerações: Ordem de árvores binárias e travessia.

Python

# 3Sum
nums = [-1, 0, 1, 2, -1, -4]
result = []
nums.sort()
print(nums)
r=len(nums)-1
for i in range(len(nums)-2):
   l = i + 1 # we don't want l and i to be the same value.
   # for each value of i, l starts one greater
   # and increments from there.
   while (l < r):
      sum_ = nums[i] + nums[l] + nums[r]
      if (sum_ < 0):
         l = l + 1
      elif (sum_ > 0):
         r = r - 1
      else: # 0 is False in a boolean context
         result.append([nums[i],nums[l],nums[r]])
         l = l + 1 # increment l when we find a combination that works
print(result)

Java

class Solution {
2    public List<List<Integer>> threeSum(int[] nums) {
3        Arrays.sort(nums);
4        List<List<Integer>> threeSums = new ArrayList<>();
5        for (int i = 0; i < nums.length; i++) {
6            if (i > 0 && nums[i] == nums[i - 1]) {
7                continue;
8            }
9            int target = -nums[i];
10            int l = i + 1, r = nums.length - 1;
11            while (l < r) {
12                if (nums[l] + nums[r] == target) {
13                    threeSums.add(Arrays.asList(nums[i], nums[l], nums[r]));
14                    l++;
15                    while (l < r && nums[l] == nums[l - 1]) {
16                        l++;
17                    }
18                } else if (nums[l] + nums[r] < target) {
19                    l++;
20                } else {
21                    r--;
22                }
23            }
24        }
25        return threeSums;
26    }

Javascript

const threeSum = (nums) => {
2  const sortedNums = nums.sort((a, b) => a - b);
3  const threeSums = [];
4  for (let i = 0; i < nums.length; i++) {
5    // avoid duplicates
6    if (i > 0 && sortedNums[i] === sortedNums[i - 1]) {
7      continue;
8    }
9    const target = -sortedNums[i];
10    let [l, r] = [i + 1, sortedNums.length - 1];
11    while (l < r) {
12      if (sortedNums[l] + sortedNums[r] === target) {
13        threeSums.push([sortedNums[i], sortedNums[l], sortedNums[r]]);
14        l += 1;
15        // avoid duplicates again
16        while (l < r && sortedNums[l] === sortedNums[l - 1]) {
17          l += 1;
18        }
19      } else if (sortedNums[l] + sortedNums[r] < target) {
20        l += 1;
21      } else {
22        r -= 1;
23      }
24    }
25  }
26  return threeSums;
27};

 

Fontes:

https://interviewing.io/questions/three-sum