Estructuras de Datos y Algoritmos Preguntas de entrevista

Lo que cubren las entrevistas de Estructuras de Datos y Algoritmos

Ejemplos de preguntas de entrevista sobre Estructuras de Datos y Algoritmos

• Encuentra dos números en un arreglo que sumen un objetivo (y analiza la complejidad).
  Lo que cubre una buena respuesta

  • Uso de hash map para complementos
  • Complejidad O(n) tiempo y O(n) espacio
  • Manejo de arreglo no ordenado
  • Solución de una sola pasada

  Ver respuesta de ejemplo

  Para encontrar dos números que sumen un objetivo, usamos un hash map que almacena cada número como clave y su índice como valor. Iteramos sobre el arreglo; para cada elemento calculamos el complemento (objetivo - elemento). Si el complemento ya está en el hash map, hemos encontrado los dos números y devolvemos sus índices. Si no, agregamos el elemento actual al mapa. Esto nos da una complejidad temporal O(n) y espacial O(n) debido al mapa. Un error común es olvidar manejar el caso donde el complemento es el mismo elemento (ej. usar el mismo índice dos veces), que se evita verificando que el índice del complemento no sea el actual. Esta solución funciona para arreglos no ordenados y puede adaptarse fácilmente para devolver los números en lugar de los índices.

  def two_sum(nums, objetivo):
      mapa = {}  # diccionario para almacenar número:índice
      for i, num in enumerate(nums):
          complemento = objetivo - num
          if complemento in mapa:
              return [mapa[complemento], i]
          mapa[num] = i
      return []  # No se encontró solución
  
  # Complejidad: O(n) tiempo, O(n) espacio

• Detecta un ciclo en una lista enlazada.
  Lo que cubre una buena respuesta

  • Algoritmo de Floyd (tortuga y liebre)
  • Dos punteros con diferente velocidad
  • Complejidad O(n) tiempo y O(1) espacio
  • Detección de ciclo y punto de inicio

  Ver respuesta de ejemplo

  Para detectar un ciclo en una lista enlazada, utilizamos el algoritmo de Floyd, también conocido como 'tortuga y liebre'. Inicializamos dos punteros: lento (tortuga) avanza un nodo por paso, y rápido (liebre) avanza dos nodos por paso. Iteramos mientras el puntero rápido y su siguiente no sean nulos. Si en algún momento los punteros se encuentran, hay un ciclo. Si llegamos al final (rápido se vuelve None), no hay ciclo. La complejidad temporal es O(n) y espacial O(1). Una pregunta frecuente es encontrar el nodo donde comienza el ciclo: después del encuentro, reiniciamos el puntero lento al inicio y ambos avanzan a la misma velocidad hasta encontrarse de nuevo, ese punto es el inicio del ciclo.

  class ListNode:
      def __init__(self, x):
          self.val = x
          self.next = None
  
  def has_cycle(head):
      lento = head
      rapido = head
      while rapido and rapido.next:
          lento = lento.next
          rapido = rapido.next.next
          if lento == rapido:
              return True
      return False
  
  # Complejidad: O(n) tiempo, O(1) espacio

• Encuentra la subcadena más larga sin caracteres repetidos.
  Lo que cubre una buena respuesta

  • Ventana deslizante con dos punteros
  • Uso de conjunto o mapa para caracteres vistos
  • Complejidad O(n) tiempo, O(min(n, alfabeto)) espacio
  • Manejo de repeticiones moviendo el puntero izquierdo

  Ver respuesta de ejemplo

  Para encontrar la subcadena más larga sin caracteres repetidos, usamos una ventana deslizante con dos punteros (izquierdo y derecho) y un conjunto para llevar los caracteres actuales en la ventana. Movemos el puntero derecho para expandir la ventana; si el nuevo carácter ya está en el conjunto, movemos el puntero izquierdo eliminando caracteres hasta que el carácter repetido ya no esté, actualizando el conjunto. En cada paso actualizamos la longitud máxima de la subcadena. La complejidad temporal es O(n) porque cada carácter se añade y elimina a lo sumo una vez, y el espacio es O(min(n, tamaño del alfabeto)). Una mejora común es usar un diccionario que almacene el índice del último carácter, permitiendo saltar el puntero izquierdo directamente al siguiente del carácter repetido, sin borrar de uno en uno.

  def longitud_subcadena_sin_repetir(s):
      conjunto = set()
      izquierdo = 0
      max_len = 0
      for derecho in range(len(s)):
          while s[derecho] in conjunto:
              conjunto.remove(s[izquierdo])
              izquierdo += 1
          conjunto.add(s[derecho])
          max_len = max(max_len, derecho - izquierdo + 1)
      return max_len
  
  # Complejidad: O(n) tiempo, O(min(n, alfabeto)) espacio

• Realiza un recorrido por niveles (BFS) de un árbol binario.
  Lo que cubre una buena respuesta

  • Uso de cola para BFS
  • Recorrido nivel por nivel
  • Complejidad O(n) tiempo, O(n) espacio
  • Separación de niveles con contador

  Ver respuesta de ejemplo

  El recorrido por niveles (BFS) de un árbol binario se implementa con una cola. Iniciamos encolando la raíz. Luego, mientras la cola no esté vacía, procesamos todos los nodos del nivel actual: determinamos el tamaño actual de la cola, iteramos ese número de veces, desencolamos un nodo, lo visitamos (por ejemplo, agregamos su valor a la lista del nivel actual) y encolamos sus hijos izquierdo y derecho si existen. Al final de cada nivel, agregamos la lista del nivel al resultado. La complejidad temporal es O(n) porque visitamos cada nodo una vez, y la espacial es O(n) en el peor caso (cuando el árbol está balanceado, la cola puede contener hasta n/2 nodos en el nivel más ancho). Un error común es no separar los niveles y mezclar todos los nodos en una sola lista.

  from collections import deque
  
  def nivel_orden(raiz):
      if not raiz:
          return []
      resultado = []
      cola = deque([raiz])
      while cola:
          nivel = []
          for _ in range(len(cola)):
              nodo = cola.popleft()
              nivel.append(nodo.val)
              if nodo.left:
                  cola.append(nodo.left)
              if nodo.right:
                  cola.append(nodo.right)
          resultado.append(nivel)
      return resultado
  
  # Complejidad: O(n) tiempo, O(n) espacio

• Número de islas en una cuadrícula (BFS/DFS).
  Lo que cubre una buena respuesta

  • DFS o BFS para explorar islas
  • Marcar celdas visitadas para evitar repetición
  • Complejidad O(m*n) tiempo, O(m*n) espacio (recursión)
  • Iterar sobre toda la cuadrícula

  Ver respuesta de ejemplo

  Para contar el número de islas en una cuadrícula (matriz de '1's y '0's), aplicamos DFS (o BFS) desde cada celda con valor '1' no visitada. Al encontrar una, incrementamos el contador y realizamos una búsqueda en profundidad recursiva para marcar todas las celdas conectadas de la isla como visitadas (cambiando el valor a '0' o usando un array visitado). La búsqueda se mueve en las cuatro direcciones (arriba, abajo, izquierda, derecha) y verifica los límites. La complejidad temporal es O(m*n) porque cada celda se visita una vez, y la espacial es O(m*n) en el peor caso debido a la pila de recursión si la isla es grande. Una alternativa iterativa con BFS usando una cola reduce el riesgo de desbordamiento de pila en cuadrículas grandes.

  def num_islands(grid):
      if not grid:
          return 0
      filas = len(grid)
      cols = len(grid[0])
      contador = 0
  
      def dfs(f, c):
          if f < 0 or f >= filas or c < 0 or c >= cols or grid[f][c] == '0':
              return
          grid[f][c] = '0'  # marcar como visitado
          dfs(f+1, c)
          dfs(f-1, c)
          dfs(f, c+1)
          dfs(f, c-1)
  
      for i in range(filas):
          for j in range(cols):
              if grid[i][j] == '1':
                  contador += 1
                  dfs(i, j)
      return contador
  
  # Complejidad: O(m*n) tiempo, O(m*n) espacio en el peor caso (recursión)

• Subir escaleras / cambio de monedas (programación dinámica básica).
  Lo que cubre una buena respuesta

  • Programación dinámica con subproblemas óptimos
  • Ecuación de recurrencia f(n) = f(n-1) + f(n-2)
  • Optimización de espacio a O(1) usando variables
  • Casos base f(1)=1, f(2)=2

  Ver respuesta de ejemplo

  El problema de subir escaleras (n escalones, puedes subir 1 o 2 pasos) se resuelve con programación dinámica. Sea f(n) el número de formas de llegar al escalón n, se cumple f(n) = f(n-1) + f(n-2), porque para llegar al escalón n puedes venir del n-1 (dando un paso) o del n-2 (dando dos). Los casos base son f(1)=1 y f(2)=2. Podemos calcular iterativamente desde abajo hacia arriba usando solo dos variables para ahorrar espacio, obteniendo complejidad temporal O(n) y espacial O(1). Un error común es usar recursión sin memoización, lo que lleva a complejidad exponencial. Otra pregunta similar es el cambio de monedas, donde la recurrencia es diferente pero la idea de subproblemas óptimos es la misma.

  def subir_escaleras(n):
      if n == 1:
          return 1
      if n == 2:
          return 2
      prev2 = 1  # f(1)
      prev1 = 2  # f(2)
      for i in range(3, n+1):
          actual = prev1 + prev2
          prev2 = prev1
          prev1 = actual
      return prev1
  
  # Complejidad: O(n) tiempo, O(1) espacio

Cómo prepararse

• Aprende patrones, no problemas — la mayoría de las preguntas se asignan a un puñado de plantillas.
• Siempre indica la complejidad temporal y espacial, y busca un mejor enfoque si es fuerza bruta.
• Habla sobre tu plan antes de codificar y prueba con un pequeño ejemplo al final.
• Practica escribir código sin errores en una pizarra o editor simple sin autocompletado.

Preguntas frecuentes