Capítulo 3: Algoritmos & Estruturas de Dados
Estes exercícios cobrem as questões clássicas de algoritmos feitas em entrevistas Java. Cada solução inclui a complexidade de tempo/espaço e uma frase-chave para dizer na entrevista.
Exercício 1 — Contador de frequência de palavras (HashMap)
"Conte a frequência de cada palavra em uma string."
Solução imperativa
public Map<String, Integer> wordCount(String text) {
Map<String, Integer> freq = new HashMap<>();
for (String word : text.toLowerCase().split("\\s+")) {
freq.merge(word, 1, Integer::sum);
}
return freq;
}
Solução com Streams
public Map<String, Long> wordCountStream(String text) {
return Arrays.stream(text.toLowerCase().split("\\s+"))
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}
Teste: "hello world hello java" → {hello=2, world=1, java=1}
"Usei merge() na abordagem imperativa e groupingBy na abordagem com stream. Ambas são O(n)."
Exercício 2 — Verificação de parênteses válidos (Stack)
"Verifique se uma string de parênteses é válida: (), [], "
Solução
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) {
stack.push(c);
} else if (pairs.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
}
}
return stack.isEmpty();
}
Testes:
"({[]})" → true
"({[}])" → false
"(((" → false
"" → true
Complexidade: O(n) tempo, O(n) espaço.
"Problema clássico de stack. O(n) tempo, O(n) espaço. Usei ArrayDeque em vez da classe legada Stack porque é mais rápido e recomendado pela documentação do Java."
Exercício 3 — Inverter uma lista ligada
"Inverta uma lista ligada simples (singly linked list)."
Solução
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // salvar o próximo
curr.next = prev; // inverter o ponteiro
prev = curr; // avançar prev
curr = next; // avançar curr
}
return prev;
}
Visualização:
Antes: 1 → 2 → 3 → null
Depois: 3 → 2 → 1 → null
Complexidade: O(n) tempo, O(1) espaço.
"Três ponteiros: prev, curr, next. O(n) tempo, O(1) espaço. Esse é um clássico que testa manipulação de ponteiros."
Exercício 4 — Busca binária (Binary Search)
"Implemente uma busca binária em um array ordenado."
Solução
public int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // evita overflow de inteiro
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // não encontrado
}
Teste: [1, 3, 5, 7, 9, 11], target = 7 → retorna 3 (índice)
Complexidade: O(log n) tempo, O(1) espaço.
Por que lo + (hi - lo) / 2 em vez de (lo + hi) / 2?
Porque lo + hi pode ultrapassar Integer.MAX_VALUE se ambos os valores forem grandes. Esse é um detalhe que entrevistadores adoram.
"Uso lo + (hi - lo) / 2 em vez de (lo + hi) / 2 para evitar overflow de inteiro. Busca clássica O(log n) em dados ordenados."
Exercício 5 — Two Sum (Dois números que somam um alvo)
"Encontre dois números em um array cuja soma seja igual a um alvo."
Solução O(n) com HashMap
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
return new int[] { seen.get(complement), i };
}
seen.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
Teste: [2, 7, 11, 15], target = 9 → retorna [0, 1] (pois 2 + 7 = 9)
Complexidade: O(n) tempo, O(n) espaço.
A ideia
Para cada número x, verificamos se target - x já foi visto. O HashMap permite fazer essa busca em O(1).
"Solução HashMap de passagem única. Para cada número, verifico se o complemento existe no mapa. O(n) tempo em vez do brute-force O(n²)."
Exercício 6 — FizzBuzz (o clássico)
"Imprima os números de 1 a n. Para múltiplos de 3: 'Fizz'. Para múltiplos de 5: 'Buzz'. Para ambos: 'FizzBuzz'."
Solução limpa
public List<String> fizzBuzz(int n) {
List<String> result = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) result.add("FizzBuzz");
else if (i % 3 == 0) result.add("Fizz");
else if (i % 5 == 0) result.add("Buzz");
else result.add(String.valueOf(i));
}
return result;
}
Solução extensível (se o entrevistador pedir mais regras)
public List<String> fizzBuzz(int n) {
record Rule(int divisor, String word) {}
List<Rule> rules = List.of(
new Rule(3, "Fizz"),
new Rule(5, "Buzz"),
new Rule(7, "Jazz") // fácil de adicionar!
);
List<String> result = new ArrayList<>();
for (int i = 1; i <= n; i++) {
final int num = i;
String s = rules.stream()
.filter(r -> num % r.divisor() == 0)
.map(Rule::word)
.collect(Collectors.joining());
result.add(s.isEmpty() ? String.valueOf(i) : s);
}
return result;
}
"Começo com a versão simples, mas se o entrevistador pedir extensibilidade, mudo para uma abordagem baseada em regras. Adicionar uma nova regra é só uma linha."
Exercício 7 — Encontrar o primeiro duplicado
"Encontre o primeiro elemento duplicado em um array."
Solução
public int firstDuplicate(int[] arr) {
Set<Integer> seen = new HashSet<>();
for (int num : arr) {
if (!seen.add(num)) return num;
}
return -1; // sem duplicado
}
Dica: Set.add() retorna false se o elemento já existe — não precisa de contains() separado.
Teste: [2, 1, 3, 5, 3, 2] → retorna 3 (primeiro duplicado encontrado)
Complexidade: O(n) tempo, O(n) espaço.
Exercício 8 — Verificar se duas strings são anagramas
"Verifique se duas strings são anagramas."
Solução
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}
Teste: "listen", "silent" → true
Complexidade: O(n) tempo, O(1) espaço (array fixo de 26).
"Uso um array contador de frequência em vez de ordenar (O(n log n)). Passagem única, O(n) tempo, O(1) espaço já que o alfabeto é fixo."
Resumo das complexidades
| Exercício | Tempo | Espaço | Estrutura chave |
|---|---|---|---|
| Frequência de palavras | O(n) | O(n) | HashMap |
| Parênteses válidos | O(n) | O(n) | Stack (ArrayDeque) |
| Inverter linked list | O(n) | O(1) | 3 ponteiros |
| Binary Search | O(log n) | O(1) | Divisão por 2 |
| Two Sum | O(n) | O(n) | HashMap (complemento) |
| FizzBuzz | O(n) | O(n) | Módulo |
| Primeiro duplicado | O(n) | O(n) | HashSet |
| Anagrama | O(n) | O(1) | Array de frequências |
⬅️ Capítulo 2: Refatoração | Capítulo 4: Design REST & Patterns →