Capítulo 3: Algoritmos y Estructuras de Datos
Estos ejercicios cubren las preguntas clásicas de algoritmos que se hacen en entrevistas de Java. Cada solución incluye la complejidad temporal/espacial y una frase clave para decir en la entrevista.
Ejercicio 1 — Contador de frecuencia de palabras (HashMap)
"Cuente la frecuencia de cada palabra en una cadena de caracteres."
Solución 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;
}
Solución con Streams
public Map<String, Long> wordCountStream(String text) {
return Arrays.stream(text.toLowerCase().split("\\s+"))
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}
Prueba: "hello world hello java" → {hello=2, world=1, java=1}
"Usé merge() para el enfoque imperativo y groupingBy para el enfoque con streams. Ambos son O(n)."
Ejercicio 2 — Verificación de paréntesis válidos (Stack)
"Verifique si una cadena de paréntesis es válida: (), [], "
Solución
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();
}
Pruebas:
"({[]})" → true
"({[}])" → false
"(((" → false
"" → true
Complejidad: O(n) tiempo, O(n) espacio.
"Problema clásico de stack. O(n) tiempo, O(n) espacio. Usé ArrayDeque en lugar de la clase Stack heredada porque es más rápido y recomendado por la documentación de Java."
Ejercicio 3 — Invertir una lista enlazada
"Invierta una lista enlazada simple (singly linked list)."
Solución
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; // sauvegarder le suivant
curr.next = prev; // inverser le pointeur
prev = curr; // avancer prev
curr = next; // avancer curr
}
return prev;
}
Visualización:
Antes : 1 → 2 → 3 → null
Después : 3 → 2 → 1 → null
Complejidad: O(n) tiempo, O(1) espacio.
"Tres punteros: prev, curr, next. O(n) tiempo, O(1) espacio. Es un clásico que prueba la manipulación de punteros."
Ejercicio 4 — Búsqueda binaria (Binary Search)
"Implemente una búsqueda binaria sobre un arreglo ordenado."
Solución
public int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // évite le dépassement d'entier
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // non trouvé
}
Prueba: [1, 3, 5, 7, 9, 11], target = 7 → retorna 3 (índice)
Complejidad: O(log n) tiempo, O(1) espacio.
¿Por qué lo + (hi - lo) / 2 en lugar de (lo + hi) / 2?
Porque lo + hi puede exceder Integer.MAX_VALUE si ambos valores son grandes. Es un detalle que a los entrevistadores les encanta.
"Uso lo + (hi - lo) / 2 en lugar de (lo + hi) / 2 para evitar el desbordamiento de enteros. Búsqueda clásica O(log n) en datos ordenados."
Ejercicio 5 — Two Sum (Dos números que suman un total)
"Encuentre dos números en un arreglo cuya suma sea igual a un objetivo."
Solución O(n) con 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");
}
Prueba: [2, 7, 11, 15], target = 9 → retorna [0, 1] (ya que 2 + 7 = 9)
Complejidad: O(n) tiempo, O(n) espacio.
La idea
Para cada número x, se busca si target - x ya ha sido visto. El HashMap permite hacer esta búsqueda en O(1).
"Solución de HashMap en una sola pasada. Para cada número, verifico si el complemento existe en el mapa. O(n) tiempo en vez del O(n²) de la fuerza bruta."
Ejercicio 6 — FizzBuzz (el clásico)
"Imprima los números del 1 al n. Para los múltiplos de 3: 'Fizz'. Para los múltiplos de 5: 'Buzz'. Para ambos: 'FizzBuzz'."
Solución limpia
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;
}
Solución extensible (si el entrevistador añade reglas)
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 agregar!
);
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;
}
"Comienzo con la versión simple, pero si el entrevistador pide extensibilidad, cambio a un enfoque basado en reglas. Agregar una nueva regla es solo una línea."
Ejercicio 7 — Encontrar el primer duplicado
"Encuentre el primer elemento duplicado en un arreglo."
Solución
public int firstDuplicate(int[] arr) {
Set<Integer> seen = new HashSet<>();
for (int num : arr) {
if (!seen.add(num)) return num;
}
return -1; // pas de doublon
}
Truco: Set.add() retorna false si el elemento ya existe — no es necesario un contains() separado.
Prueba: [2, 1, 3, 5, 3, 2] → retorna 3 (primer duplicado encontrado)
Complejidad: O(n) tiempo, O(n) espacio.
Ejercicio 8 — Verificar si dos cadenas son anagramas
"Verifique si dos cadenas son anagramas."
Solución
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;
}
Prueba: "listen", "silent" → true
Complejidad: O(n) tiempo, O(1) espacio (arreglo fijo de 26).
"Uso un arreglo contador de frecuencias en vez de ordenar (O(n log n)). Una sola pasada, O(n) tiempo, O(1) espacio ya que el alfabeto es fijo."
Resumen de complejidades
| Ejercicio | Tiempo | Espacio | Estructura clave |
|---|---|---|---|
| Frecuencia de palabras | O(n) | O(n) | HashMap |
| Paréntesis válidos | O(n) | O(n) | Stack (ArrayDeque) |
| Invertir linked list | O(n) | O(1) | 3 punteros |
| Binary Search | O(log n) | O(1) | División por 2 |
| Two Sum | O(n) | O(n) | HashMap (complemento) |
| FizzBuzz | O(n) | O(n) | Módulo |
| Primer duplicado | O(n) | O(n) | HashSet |
| Anagrama | O(n) | O(1) | Arreglo de frecuencias |
⬅️ Capítulo 2: Refactoring | Capítulo 4: Diseño REST & Patrones →