Dynamic programming Preguntas de entrevista

Lo que cubren las entrevistas de Dynamic programming

Ejemplos de preguntas de entrevista sobre Dynamic programming

• Explica la diferencia entre memoización y tabulación en PD.
  Lo que cubre una buena respuesta

  • Dirección del enfoque: memoización es top-down, tabulación es bottom-up.
  • Estructura de datos: memoización usa diccionario o arreglo para almacenar resultados; tabulación usa tabla.
  • Orden de cálculo: memoización resuelve recursivamente y almacena; tabulación itera desde subproblemas pequeños.
  • Rendimiento: memoización puede tener overhead de recursión; tabulación suele ser más eficiente en espacio si se optimiza.
  • Casos base: memoización los maneja al inicio de la función; tabulación los inicializa en la tabla.

  Ver respuesta de ejemplo

  La memoización y la tabulación son dos técnicas de programación dinámica para optimizar problemas con subproblemas superpuestos. La memoización sigue un enfoque top-down: se parte del problema original y se descompone recursivamente, almacenando los resultados de subproblemas ya resueltos en una estructura (usualmente un diccionario o arreglo) para evitar recálculos. En cambio, la tabulación es bottom-up: se construye una tabla iterativamente desde los casos base hasta el problema completo. La memoización tiene la ventaja de solo resolver los subproblemas necesarios, pero puede incurrir en overhead de recursión y desbordamiento de pila. La tabulación resuelve todos los subproblemas relevantes de manera iterativa, siendo a menudo más eficiente en tiempo y espacio, especialmente si se reduce la dimensionalidad de la tabla. La elección depende del problema: memoización es natural cuando la descomposición recursiva es clara; tabulación es preferible cuando se necesita un control fino sobre el orden de cálculo o cuando el espacio se puede optimizar (por ejemplo, usando solo dos filas). Un error común es no identificar correctamente los subproblemas o no inicializar bien los casos base en tabulación.

• Implementa los números de Fibonacci usando PD (tanto top-down como bottom-up).
  Lo que cubre una buena respuesta

  • Top-down: función recursiva con memoización (arreglo o diccionario).
  • Bottom-up: arreglo iterativo desde 0 hasta n.
  • Casos base: fib(0)=0, fib(1)=1.
  • Complejidad: O(n) tiempo, O(n) espacio en ambas, pero bottom-up puede reducirse a O(1) espacio.

  Ver respuesta de ejemplo

  Implementamos los números de Fibonacci usando PD en ambas variantes. El top-down define una función recursiva que verifica si el resultado ya está memoizado; si no, lo calcula y almacena. El bottom-up inicializa los dos primeros valores y luego itera llenando un arreglo o solo manteniendo los dos últimos valores para optimizar espacio. La complejidad temporal en ambos casos es O(n) porque cada subproblema se calcula una vez. El espacio del bottom-up puede ser O(1) si usamos variables en lugar de arreglo completo. Un error común es no incluir el caso base o usar recursión sin memoización, lo que lleva a O(2^n).

  # Fibonacci con programación dinámica
  # Top-down con memoización
  def fib_top_down(n, memo=None):
      if memo is None:
          memo = {}
      if n in memo:
          return memo[n]
      if n <= 1:
          return n
      memo[n] = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
      return memo[n]
  
  # Bottom-up con optimización de espacio
  def fib_bottom_up(n):
      if n <= 1:
          return n
      prev2, prev1 = 0, 1
      for _ in range(2, n+1):
          actual = prev1 + prev2
          prev2, prev1 = prev1, actual
      return prev1
  
  # Complejidad: O(n) tiempo, O(1) espacio (bottom-up), O(n) espacio (top-down por recursión)

• Dado un conjunto de elementos con pesos y valores, resuelve el problema de la mochila 0/1 para obtener el valor máximo.
  Lo que cubre una buena respuesta

  • Subproblema: valor máximo con primeros i elementos y capacidad w.
  • Ecuación de recurrencia: dp[i][w] = max(dp[i-1][w], dp[i-1][w-peso_i] + valor_i) si cabe.
  • Tabulación: matriz 2D de (n+1) x (capacidad+1).
  • Inicialización: primera fila y columna en 0.
  • Complejidad: O(n * capacidad) tiempo, O(n * capacidad) espacio (se puede optimizar a O(capacidad)).

  Ver respuesta de ejemplo

  El problema de la mochila 0/1 consiste en seleccionar un subconjunto de elementos con pesos y valores para maximizar el valor total sin exceder la capacidad. La solución PD define dp[i][w] como el valor máximo usando los primeros i elementos y capacidad w. La recurrencia es: si el peso del elemento i excede w, dp[i][w] = dp[i-1][w]; de lo contrario, dp[i][w] = max(dp[i-1][w], dp[i-1][w - peso_i] + valor_i). Se itera sobre i y w, llenando la matriz. La respuesta está en dp[n][capacidad]. Se puede optimizar el espacio a un arreglo 1D iterando la capacidad en orden inverso para evitar reutilizar elementos más de una vez. Un error común es no manejar correctamente el índice o no entender que la mochila 0/1 no permite repetición. El tiempo es O(n*C) y el espacio O(C) con optimización.

  # Problema de la mochila 0/1
  # pesos: lista de pesos, valores: lista de valores, capacidad: entero
  def knapsack_01(pesos, valores, capacidad):
      n = len(pesos)
      # Inicializar dp con ceros (optimizado a 1D)
      dp = [0] * (capacidad + 1)
      for i in range(n):
          # Recorrer capacidad de forma inversa para no reutilizar el mismo elemento
          for w in range(capacidad, pesos[i] - 1, -1):
              dp[w] = max(dp[w], dp[w - pesos[i]] + valores[i])
      return dp[capacidad]
  
  # Ejemplo:
  # pesos = [2,3,4,5]
  # valores = [3,4,5,6]
  # capacidad = 8
  # print(knapsack_01(pesos, valores, capacidad))  # Output: 10 (elementos 0 y 2)
  
  # Complejidad: O(n*C) tiempo, O(C) espacio

• Encuentra la longitud de la subsecuencia creciente más larga en un arreglo.
  Lo que cubre una buena respuesta

  • Subproblema: LIS hasta índice i, terminando en arr[i].
  • Ecuación: dp[i] = 1 + max(dp[j]) para j < i y arr[j] < arr[i], o 1 si no hay.
  • Tabulación: arreglo dp de tamaño n inicializado en 1.
  • Complejidad: O(n^2) tiempo, O(n) espacio.
  • Optimización: usar búsqueda binaria para O(n log n) con arreglo de colas.

  Ver respuesta de ejemplo

  La subsecuencia creciente más larga (LIS) busca la longitud máxima de una subsecuencia (no necesariamente contigua) que sea estrictamente creciente. La solución PD define dp[i] como la longitud del LIS que termina en el índice i. Se recorre el arreglo, para cada i se busca un j anterior con arr[j] < arr[i] y se toma el máximo dp[j] + 1. La respuesta es el máximo valor en dp. Este enfoque es O(n^2). Existe una optimización O(n log n) usando un arreglo que mantiene el menor valor posible para cada longitud, pero la versión O(n^2) es más directa para entender el concepto PD. Un error común es no considerar la subsecuencia que comienza en el mismo elemento (dp[i] = 1) o no iterar correctamente sobre los j.

  # Longitud de la subsecuencia creciente más larga (LIS) - O(n^2)
  def lis_longitud(arr):
      n = len(arr)
      if n == 0:
          return 0
      dp = [1] * n  # Inicializar en 1 (cada elemento es una subsecuencia de longitud 1)
      for i in range(1, n):
          for j in range(i):
              if arr[j] < arr[i]:
                  dp[i] = max(dp[i], dp[j] + 1)
      return max(dp)
  
  # Ejemplo:
  # arr = [10,9,2,5,3,7,101,18]
  # print(lis_longitud(arr))  # Output: 4 ([2,5,7,101] o [2,3,7,18])
  
  # Complejidad: O(n^2) tiempo, O(n) espacio

• Calcula la distancia de edición (distancia Levenshtein) entre dos cadenas.
  Lo que cubre una buena respuesta

  • Subproblema: distancia entre prefijos s1[0..i] y s2[0..j].
  • Ecuación: si caracteres iguales, dp[i][j]=dp[i-1][j-1]; si no, 1+min(insertar, eliminar, sustituir).
  • Tabulación: matriz (n+1)x(m+1), dp[0][j]=j, dp[i][0]=i.
  • Complejidad: O(n*m) tiempo y espacio.
  • Optimización: espacio O(min(n,m)) usando solo dos filas.

  Ver respuesta de ejemplo

  La distancia de Levenshtein mide el número mínimo de operaciones (insertar, eliminar, sustituir) para transformar una cadena en otra. La solución PD define dp[i][j] como la distancia entre los primeros i caracteres de s1 y j caracteres de s2. Se llena la matriz: si s1[i-1] == s2[j-1], entonces dp[i][j] = dp[i-1][j-1]; si no, dp[i][j] = 1 + min(dp[i-1][j] (eliminar), dp[i][j-1] (insertar), dp[i-1][j-1] (sustituir)). Se inicializa la primera fila y columna con los valores de i y j respectivamente. La respuesta está en dp[n][m]. Se puede optimizar espacio usando solo dos filas porque solo se necesita la fila anterior. Un error común es confundir los índices o no considerar correctamente el costo de sustitución.

  # Distancia de Levenshtein (edición) entre dos cadenas
  def distancia_edicion(s1, s2):
      n, m = len(s1), len(s2)
      # Inicializar matriz (n+1) x (m+1)
      dp = [[0] * (m + 1) for _ in range(n + 1)]
      # Casos base
      for i in range(n + 1):
          dp[i][0] = i
      for j in range(m + 1):
          dp[0][j] = j
      # Llenar matriz
      for i in range(1, n + 1):
          for j in range(1, m + 1):
              if s1[i-1] == s2[j-1]:
                  dp[i][j] = dp[i-1][j-1]
              else:
                  dp[i][j] = 1 + min(dp[i-1][j],    # eliminar
                                     dp[i][j-1],    # insertar
                                     dp[i-1][j-1])  # sustituir
      return dp[n][m]
  
  # Ejemplo:
  # print(distancia_edicion("kitten", "sitting"))  # Output: 3
  
  # Complejidad: O(n*m) tiempo, O(n*m) espacio (se puede optimizar a O(min(n,m)))

• Resuelve el problema de cambio de monedas: número mínimo de monedas para obtener una cantidad dada.
  Lo que cubre una buena respuesta

  • Subproblema: número mínimo de monedas para cantidad c, usando monedas disponibles.
  • Ecuación: dp[c] = min(dp[c - moneda] + 1) para cada moneda, con dp[0]=0.
  • Tabulación: arreglo de tamaño cantidad+1, inicializado con infinito.
  • Complejidad: O(cantidad * número de monedas) tiempo, O(cantidad) espacio.
  • Importante: las monedas se pueden reutilizar (problema de cambio sin límite).

  Ver respuesta de ejemplo

  El problema de cambio de monedas busca el número mínimo de monedas para una cantidad dada, asumiendo un suministro ilimitado de cada denominación. La solución PD define dp[c] como el número mínimo de monedas para la cantidad c. Se inicializa dp[0]=0 y los demás con un valor grande (infinito). Luego, para cada cantidad de 1 a cantidad, se recorre cada moneda; si la moneda es menor o igual a c, se actualiza dp[c] = min(dp[c], dp[c - moneda] + 1). La respuesta está en dp[cantidad] si es finito, o -1 si no es posible. Este es un problema de PD típico con orden O(cantidad * monedas). Un error común es no inicializar correctamente o confundir con el problema de contar formas (donde se suman en lugar de tomar mínimo). Aquí se minimiza, por lo que se usa min.

  # Cambio de monedas: número mínimo de monedas para una cantidad
  def cambio_minimo(monedas, cantidad):
      # Inicializar dp con infinito
      INF = float('inf')
      dp = [INF] * (cantidad + 1)
      dp[0] = 0
      for c in range(1, cantidad + 1):
          for moneda in monedas:
              if moneda <= c:
                  dp[c] = min(dp[c], dp[c - moneda] + 1)
      return dp[cantidad] if dp[cantidad] != INF else -1
  
  # Ejemplo:
  # monedas = [1,2,5]
  # cantidad = 11
  # print(cambio_minimo(monedas, cantidad))  # Output: 3 (5+5+1)
  
  # Complejidad: O(cantidad * len(monedas)) tiempo, O(cantidad) espacio

• Cuenta el número de formas de subir una escalera con 1 o 2 pasos a la vez.
  Lo que cubre una buena respuesta

  • Subproblema: formas de llegar al escalón i, dp[i] = dp[i-1] + dp[i-2].
  • Casos base: dp[0]=1, dp[1]=1.
  • Tabulación: arreglo de tamaño n+1, o variables para espacio O(1).
  • Complejidad: O(n) tiempo, O(1) espacio.
  • Interpretación: también es la serie de Fibonacci desplazada.

  Ver respuesta de ejemplo

  Contar las formas de subir una escalera de n escalones, pudiendo dar pasos de 1 o 2 escalones, es un problema clásico de PD. La recurrencia es dp[i] = dp[i-1] + dp[i-2], ya que para llegar al escalón i, se puede venir desde el i-1 (dando un paso de 1) o desde el i-2 (dando un paso de 2). Los casos base son dp[0]=1 (hay una forma de no subir) y dp[1]=1 (una forma). Esto genera la secuencia de Fibonacci. La solución se puede implementar con un arreglo o con dos variables para ahorrar espacio (O(1)). Un error común es empezar con dp[0]=0, lo cual es incorrecto porque hay exactamente una forma de estar en el suelo sin subir. La respuesta final es dp[n].

  # Número de formas de subir una escalera con pasos de 1 o 2
  def subir_escaleras(n):
      if n <= 1:
          return 1
      prev2, prev1 = 1, 1  # dp[0] y dp[1]
      for _ in range(2, n + 1):
          actual = prev1 + prev2
          prev2, prev1 = prev1, actual
      return prev1
  
  # Ejemplo:
  # n = 5
  # print(subir_escaleras(n))  # Output: 8 (secuencia Fibonacci: 1,1,2,3,5,8)
  
  # Complejidad: O(n) tiempo, O(1) espacio

• Describe el enfoque paso a paso para resolver cualquier problema de PD, desde identificar subproblemas hasta codificar la solución.
  Lo que cubre una buena respuesta

  • Identificar subproblemas: buscar la estructura óptima (decisiones que llevan a la solución).
  • Definir estado: variables que describen un subproblema (índices, capacidad, etc.).
  • Ecuación de recurrencia: relación entre estados (max, min, suma, etc.).
  • Casos base: valores iniciales para estados triviales.
  • Orden de cómputo: top-down (recursión+memo) o bottom-up (iteración).
  • Optimización de espacio: reducir dimensiones cuando sea posible.

  Ver respuesta de ejemplo

  Para resolver cualquier problema de PD, primero se debe identificar si el problema tiene subproblemas superpuestos y una subestructura óptima. El proceso paso a paso es: (1) Identificar la naturaleza del problema (maximización, minimización, conteo, etc.) y definir qué significa una solución óptima. (2) Definir el estado: elegir las variables que describen un subproblema único, típicamente índices, capacidades, o valores acumulados. (3) Encontrar la recurrencia: cómo se relaciona la solución de un estado con las soluciones de estados más pequeños. (4) Establecer los casos base: los estados más simples que se pueden resolver directamente. (5) Decidir el orden de cómputo: top-down con memoización (bueno si muchos estados no se usan) o bottom-up con tabulación (eficiente si todos los estados son necesarios). (6) Implementar usando estructuras de datos (arreglos, diccionarios) y luego optimizar espacio si es posible (por ejemplo, reduciendo matrices 2D a 1D). Un error común es no verificar que los subproblemas sean independientes o tener una recurrencia cíclica. También se debe validar que el orden de iteración sea el correcto en bottom-up para que los subproblemas ya estén resueltos. Finalmente, probar con casos pequeños para verificar la corrección.

Cómo prepararse

• Domina los patrones comunes de PD como la mochila, LCS y problemas de cuadrícula.
• Practica escribir relaciones de recurrencia desde cero antes de codificar.
• Comienza con recursión de fuerza bruta, luego agrega memoización, luego convierte a tabulación si es necesario.
• Usa técnicas de optimización de espacio (por ejemplo, reducir PD 2D a 1D) para mejorar la eficiencia.
• Resuelve al menos 3-4 problemas de cada patrón para desarrollar intuición para reconocer PD.

Preguntas frecuentes