Esta lección se tradujo automáticamente al español y aún no ha sido revisada por una persona. Si algo suena raro, la versión en inglés es la definitiva.
Aquí hay un secreto que los mejores entrenadores de entrevistas no le cobrarán $500 por aprender: aproximadamente el 90% de los problemas de codificación de las entrevistas giran en torno a solo siete estructuras de datos. Si comprendes profundamente cuándo y por qué recurrir a cada uno, ya habrás ganado la mitad de la batalla. La otra mitad es práctica, pero sin los modelos mentales adecuados, la práctica es sólo memorización. Esta lección le brinda el mapa para que cada problema que encuentre se sienta como un territorio familiar.
Cada entrevista técnica bebe del mismo pozo. Estas son las estructuras que encontrará, clasificadas por frecuencia:
| Estructura de datos | Frecuencia de la entrevista | Operaciones principales | Cuando lo esperan los entrevistadores | |---|---|---|---| | Matrices/cadenas | ★★★★★ | Acceder a O(1), Buscar O(n), Insertar O(n) | Casi todos los problemas comienzan aquí | | Mapas/conjuntos hash | ★★★★★ | Insertar O(1), Buscar O(1), Eliminar O(1) | "Optimice esto de O(n²) a O(n)" | | Listas enlazadas | ★★★★☆ | Insertar O(1), Eliminar O(1), Acceder a O(n) | Manipulación de punteros, detección de ciclos | | Pilas y colas | ★★★★☆ | Empujar/sacar O(1), poner en cola/quitar de cola O(1) | Análisis, BFS, deshacer operaciones | | Árboles (binario, BST) | ★★★★☆ | Buscar O(log n), Insertar O(log n) | Datos jerárquicos, operaciones ordenadas | | Gráficos | ★★★☆☆ | Depende de la representación | Relaciones, caminos, conectividad | | Montones | ★★★☆☆ | Insertar O (log n), Extraer-min O (log n) | "Encuentra el k mayor/menor" |
Las matrices son el punto de partida para casi todos los problemas de las entrevistas. La idea clave es que la mayoría de los problemas de matrices no tienen que ver realmente con matrices, sino con reconocer patrones como dos punteros, ventanas deslizantes o sumas de prefijos.
# Two Sum — the most classic interview problem
# "Given an array and target, find two numbers that add to target"
def two_sum(nums, target):
seen = {} # Hash map to store complement
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# Time: O(n), Space: O(n) — trading space for time
Observe cómo incluso este problema de "matriz" es en realidad un problema de mapa hash. Ese patrón se repite constantemente: la fuerza bruta utiliza bucles anidados sobre una matriz y la solución óptima introduce un mapa hash.
Inicia sesión para unirte al debate
Si está atrapado en algún problema y la fuerza bruta es O(n²), pregúntese: "¿Puede un mapa hash reducir esto a O(n)?" Sorprendentemente, la respuesta es sí.
Los mapas hash brillan cuando lo necesitas:
// Group Anagrams — a classic hash map problem
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
Los problemas de listas enlazadas ponen a prueba su capacidad para manipular punteros sin perder la pista de los nodos. Las tres técnicas que necesitas son:
# Detect a cycle in a linked list (Floyd's Algorithm)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Las pilas (LIFO) y las colas (FIFO) son estructuras más simples, pero desbloquean categorías enteras de problemas:
# Valid Parentheses — classic stack problem
def is_valid(s: str) -> bool:
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in matching:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
Los problemas de árbol suelen implicar recursividad y uno de tres órdenes transversales (en orden, preorden, postorden). El modelo mental a desarrollar es: "¿Qué necesito del subárbol izquierdo, del subárbol derecho y cómo los combino en el nodo actual?"
# Maximum depth of a binary tree — the template for tree recursion
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
Los problemas de BST (árbol de búsqueda binaria) añaden una propiedad crucial: el recorrido en orden produce elementos ordenados. Si ve "ordenado" y "árbol" en el mismo problema, piense en BST de inmediato.
Los problemas de gráficos parecen intimidantes, pero la mayoría se reducen a BFS o DFS una vez que se ha creado la lista de adyacencia. Las habilidades clave son:
# BFS shortest path in an unweighted graph
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == end:
return distance
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, distance + 1))
return -1 # Not reachable
Siempre que un problema dice "encontrar las K más grandes", "las K más cercanas" o "fusionar K listas ordenadas", es casi seguro que la respuesta sea un montón (cola de prioridad). En Python, heapq proporciona un montón mínimo; para un montón máximo, niegue los valores.
import heapq
# Find the K largest elements in an array
def k_largest(nums, k):
return heapq.nlargest(k, nums) # Uses a min-heap of size k internally
Necesita encontrar la mediana de un flujo de números en O (log n) por inserción. ¿Qué combinación de estructura de datos es la más apropiada?
| Estructura | Acceso | Buscar | Insertar | Eliminar | Espacio | |---|---|---|---|---|---| | Matriz | O(1) | O(n) | O(n) | O(n) | O(n) | | Mapa hash | — | O(1)* | O(1)* | O(1)* | O(n) | | Lista enlazada | O(n) | O(n) | O(1) | O(1) | O(n) | | Pila/Cola | O(n) | O(n) | O(1) | O(1) | O(n) | | BST (equilibrado) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | | Montón | — | O(n) | O(log n) | O(log n) | O(n) |
* Caso promedio; El peor de los casos es O(n) debido a colisiones de hash.
Desarrolle esta lista de verificación mental al leer un problema: