1 public class Solution {
2    public int maxSubArray(int[] nums) {
3        int maxSum = nums[0];
4        int currentSum = nums[0];
5
6        for (int i = 1; i < nums.length; i++) {
7            currentSum = Math.max(nums[i], currentSum + nums[i]);
8            maxSum = Math.max(maxSum, currentSum);
9        }
10
11        return maxSum;
12    }
13
14    public static void main(String[] args) {
15        Solution solution = new Solution();
16
17        int[] nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
18        int[] nums2 = {1};
19        int[] nums3 = {5, 4, -1, 7, 8};
20
21
22        System.out.println(solution.maxSubArray(nums1)); // Expected output: 6
23        System.out.println(solution.maxSubArray(nums2)); // Expected output: 1
24        System.out.println(solution.maxSubArray(nums3)); // Expected output: 23
25    }
26}

Fonte: https://interviewing.io/questions/maximum-subarray

Aqui vai um plano de estudo de 12 semanas, pensado para te preparar para as entrevistas de emprego usando os desafios do HackerRank. Esse cronograma é flexível e pode ser ajustado ao seu ritmo e às suas necessidades, mas ele abrange os tópicos e algoritmos que costumam ser mais solicitados em processos seletivos.

Semana 1: Preparação e Revisão da Lógica de Programação

• Objetivo: Garantir que você esteja confortável com a linguagem de programação que irá utilizar (Python, Java, C++, etc.) e com os fundamentos da lógica.
• Atividades:
  • Revisão dos Fundamentos: Variáveis, estruturas condicionais, loops e recursão.
  • Exercícios Básicos: Utilize problemas simples do HackerRank para se familiarizar com a plataforma e o ambiente de desenvolvimento.
• Dicas Importantes:
  • Certifique-se de entender bem a notação Big-O para poder analisar a complexidade dos algoritmos.
  • Mantenha um caderno ou documento com anotações dos principais “patterns” que você for encontrando.

Semana 2: Arrays e Strings

• Objetivo: Refletir sobre os padrões de manipulação de dados lineares.
• Atividades:
  • Estudo Teórico: Revisão de operações básicas em arrays (busca, iteração, divisão e conquista) e manipulação de strings (análise de padrões, substrings, palíndromos).
  • Prática: Resolva exercícios focados em arrays e strings, como encontrar subarrays com soma máxima, reversão de strings, anagramas e problemas de sliding window.
• Dicas Importantes:
  • Ao resolver cada exercício, tente identificar se há padrões que se repetem e como otimizar a solução.

Semana 3: Listas Ligadas e Estruturas Dinâmicas

• Objetivo: Compreender estruturas dinâmicas e a manipulação de ponteiros ou referências.
• Atividades:
  • Estudo Teórico: Conceitos de listas encadeadas (simples e duplamente ligadas).
  • Prática: Exercícios envolvendo inserção, remoção, reversão de listas e a detecção de ciclos.
• Dicas Importantes:
  • Visualize as estruturas desenhando diagramas simples à mão; isso ajuda na fixação dos conceitos.

Semana 4: Pilhas, Filas e Deque

• Objetivo: Dominar o uso dessas estruturas para resolver problemas que exigem controle de ordem.
• Atividades:
  • Estudo Teórico: Funcionamento e casos de uso para pilhas, filas e deques.
  • Prática: Exercícios sobre validação de expressões (como parênteses balanceados), avaliação de expressões e problemas que fazem uso de algoritmos de visitação.
• Dicas Importantes:
  • Refaça os exercícios de formas diferentes para ver como pequenas alterações podem impactar a performance.

Semana 5: Recursão e Técnicas de Backtracking

• Objetivo: Desenvolver a habilidade de pensar e implementar soluções recursivas.
• Atividades:
  • Estudo Teórico: Conceitos de recursão, pilha de execução e backtracking para resolução de problemas.
  • Prática: Resolva problemas envolvendo geração de permutações, combinação de dados e labirintos com backtracking.
• Dicas Importantes:
  • Escreva “tracebacks” manuais para entender a ordem de execução da sua recursão.

Semana 6: Busca e Ordenação

• Objetivo: Revisar algoritmos clássicos de ordenação e busca, fundamentais para otimização.
• Atividades:
  • Estudo Teórico: Bubble Sort, Merge Sort, Quick Sort e Binary Search.
  • Prática: Resolva desafios que combinem ordenação com busca, como problemas que exijam divisão e conquista.
• Dicas Importantes:
  • Sempre compare as diferentes abordagens para um mesmo problema e discuta sobre as vantagens e desvantagens de cada algoritmo.

Semana 7: Estruturas de Dados Avançadas – Árvores

• Objetivo: Entender a estrutura, travessias e operações em árvores.
• Atividades:
  • Estudo Teórico: Conceitos de árvores binárias e árvores de busca binária (BSTs); métodos de travessia (inorder, preorder, postorder).
  • Prática: Resolva problemas que envolvam a busca do menor ancestral comum (LCA), inserção e remoção em BSTs e a verificação de propriedades de árvores.
• Dicas Importantes:
  • Pratique desenhando árvores e mapeando as chamadas recursivas para visualizar as travessias.

Semana 8: Grafos

• Objetivo: Compreender as bases dos algoritmos de grafos, que aparecem com frequência em entrevistas.
• Atividades:
  • Estudo Teórico: Conceitos de grafos direcionados e não direcionados; profundidade de busca (DFS) e largura de busca (BFS); algoritmos para caminhos mínimos.
  • Prática: Resolva desafios que envolvam encontrar componentes conectados, ciclos, e caminhos mínimos (como Dijkstra ou BFS em grafos não ponderados).
• Dicas Importantes:
  • Use listas de adjacência para representar grafos e pratique implementações tanto recursivas quanto iterativas.

Semana 9: Programação Dinâmica (DP)

• Objetivo: Desenvolver uma mentalidade para identificar subproblemas que se repetem.
• Atividades:
  • Estudo Teórico: Conceitos de memoization versus tabulação, e como reconhecer problemas passíveis de DP.
  • Prática: Exercícios clássicos – Fibonacci, knapsack, longest common subsequence, e longest increasing subsequence.
• Dicas Importantes:
  • Crie tabelas ou diagramas para rastrear suas soluções. Isso é essencial para debugar e otimizar algoritmos dinâmicos.

Semana 10: Algoritmos Gulosos (Greedy) e Técnica de Divisão de Problemas

• Objetivo: Aprender a identificar e aplicar soluções “gulosas” quando aplicáveis.
• Atividades:
  • Estudo Teórico: Explorar o conceito de escolhas locais que levam à solução global, com exemplos práticos.
  • Prática: Resolva problemas como seleção de atividades, mudanças de moedas e interval scheduling, onde a abordagem greedy é eficiente.
• Dicas Importantes:
  • Sempre questione se a solução greedy garante a otimização total. Às vezes, ela funciona impecavelmente; em outras, pode ser um ponto de partida.

Semana 11: Simulações e Revisão Integrada

• Objetivo: Unir os conhecimentos adquiridos e aumentar a velocidade de resolução.
• Atividades:
  • Simulações de Entrevistas: Resolva problemas com limite de tempo para simular o ambiente de uma entrevista.
  • Revisão Cruzada: Identifique os tópicos em que você tem mais dificuldade e refaça exercícios para consolidar o aprendizado.
• Dicas Importantes:
  • Grave-se explicando suas soluções (mesmo que só para você) para melhorar a clareza na comunicação do raciocínio.

Semana 12: Revisão Final, Soft Skills e Estratégias de Entrevista

• Objetivo: Refinar sua abordagem e preparar sua “mindset” para a entrevista.
• Atividades:
  • Revisão Geral: Faça uma recapitulação rápida dos tópicos estudados, focando em exercícios errados ou que geraram dúvidas.
  • Comunicação do Raciocínio: Pratique “pensar em voz alta” enquanto resolve problemas, explicando passo a passo como chegar à solução.
  • Feedback e Reflexão: Se possível, participe de sessões de mock interviews ou grupos de estudo para trocar feedback.
• Dicas Importantes:
  • Além dos algoritmos, esteja preparado para perguntas comportamentais. A clareza na comunicação e a capacidade de justificar suas escolhas são tão importantes quanto a solução em si.

Considerações Adicionais

• Flexibilidade e Adaptabilidade: Se sentir que algum tópico precisa de mais tempo, ajuste o cronograma. A ideia é que você se sinta confortável e confiante em cada área antes de avançar.
• Registro de Progresso: Mantenha um diário de estudos, anotando os acertos, erros e insights. Isso irá ajudar a identificar padrões nos seus desafios e a medir a evolução.
• Diversificar Fontes: Além do HackerRank, explore outras plataformas (como LeetCode, CodeSignal ou GeeksforGeeks) e recursos teóricos (livros, vídeos, blogs) para ampliar sua visão sobre cada tópico.
• Saúde Mental e Descanso: Lembre-se de reservar tempo para pausas e reflexão. Algoritmos exigem tanto foco quanto criatividade, e um ritmo saudável de estudo é fundamental para manter a clareza mental.

Esse plano visa não só a prática intensa de resolução de problemas, mas também a internalização da lógica e a comunicação eficaz do seu raciocínio, que são pontos cruciais em entrevistas de emprego. Se você se aprofundar em cada tópico, registrando dúvidas e reforçando as áreas mais desafiadoras, estará preparado para enfrentar tanto as questões técnicas quanto as dinâmicas das entrevistas.

Caso queira expandir ainda mais sua preparação, podemos também explorar estratégias para designar revisões rápidas de complexidade ou até mesmo integrar estudos sobre design patterns e sistemas de arquitetura—tópicos que podem surgir em processos seletivos mais avançados.

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.