Stacks en entrevistas técnicas: 3 problemas resueltos paso a paso

Cuando empecé a resolver problemas de LeetCode cada uno se sentía como un mundo nuevo. Me costó un rato darme cuenta de que la mayoría se agrupan por estructura, y que si reconoces el patrón el problema se desarma solo. Hoy le toca a los stacks.

En el artículo anterior vimos cómo funcionan los stacks por debajo. Hoy usamos esa base para resolver tres problemas clásicos.

Lo que vas a encontrar:

• Tres problemas resueltos paso a paso: balanced parentheses, reverse string y simplify path
• Dónde aparecen los stacks fuera de las entrevistas

Recordatorio rápido

LIFO: el último que entra es el primero que sale. push agrega al tope, pop saca del tope. En JavaScript un array ya funciona como stack. Si necesitas el detalle completo, está en el artículo anterior.

Vamos a los problemas.

Problema 1: Balanced Parentheses

"Valid Parentheses" de LeetCode.

Problema: dado un string s con solo ()[]{}, determina si es válido. Cada apertura debe tener su cierre correspondiente y en el orden correcto.

Ejemplos

Input:  "()[]{}"   → true
Input:  "([)]"     → false
Input:  "{[]}"     → true

¿Cómo lo pensamos?

"El último que abrió es el primero que debe cerrarse." Justo eso es lo que un stack hace bien.

Recorremos el string. Cada apertura va al stack. Cada cierre debe coincidir con el tope. Si al final el stack queda vacío, todo cerró bien.

Solución

function validParentheses(s) {
  const stack = [];
  const pairs = { ")": "(", "}": "{", "]": "[" };

  for (const char of s) {
    if (char === "(" || char === "{" || char === "[") {
      stack.push(char);
    } else if (stack.pop() !== pairs[char]) {
      return false;
    }
  }

  return stack.length === 0;
}

Lo importante:

1. pairs mapea cada cierre con su apertura.
2. Aperturas van al stack. Cierres hacen pop y validan.
3. Si el stack está vacío al hacer pop, devuelve undefined y la comparación falla. Cómodo, así no necesitamos un chequeo extra.
4. Al final, el stack debe estar vacío.

Complejidad: O(n) tiempo y O(n) espacio.

Problema 2: Reverse String (easy)

Adaptación de "Reverse String" de LeetCode. Vamos a invertir una palabra usando stack.

Problema: dado un string s, devuelve el string invertido.

Ejemplos

Input:  "stack"   → "kcats"
Input:  "hello"   → "olleh"

¿Cómo lo pensamos?

"Invertir" es la pista. Metes los elementos en orden y los sacas en orden inverso. Eso es exactamente lo que hace un stack.

En la vida real usarías s.split("").reverse().join("") y listo. Aquí lo hacemos con stack para ver el patrón en acción.

Solución

var reverseString = function (s) {
  const stack = [...s]; // crea un stack con los caracteres
  let reversed = "";

  while (stack.length > 0) {
    reversed += stack.pop();
  }

  return reversed;
};

Metemos todos los caracteres al stack y los vamos sacando uno por uno. Como pop devuelve el último que entró, los caracteres salen al revés.

Complejidad: O(n) tiempo y O(n) espacio.

Problema 3: Simplify Path (medium)

"Simplify Path" de LeetCode.

Problema: dada una ruta absoluta de Unix, conviértela a su forma canónica.

Reglas:

• . es el directorio actual.
• .. sube un nivel.
• // se trata como /.
• El resultado no termina en /, salvo la raíz.

Ejemplos

Input:  "/home//foo/"       → "/home/foo"
Input:  "/../"              → "/"
Input:  "/a/./b/../../c/"   → "/c"

¿Cómo lo pensamos?

¿Qué hace ..? Nos regresa al directorio anterior. Ahí está la señal, necesitamos recordar por dónde pasamos y poder retroceder.

Partimos la ruta por / y recorremos cada componente:

• "" o ".", ignora.
• "..", saca el tope del stack.
• Cualquier otra cosa es un directorio y va al stack.

Al final, el stack contiene los directorios de la ruta simplificada.

Solución

var simplifyPath = function (path) {
  const stack = [];

  for (const part of path.split("/")) {
    if (part === "" || part === ".") continue;
    if (part === "..") stack.pop();
    else stack.push(part);
  }

  return "/" + stack.join("/");
};

Tip: en JavaScript, pop sobre un stack vacío no rompe nada, solo devuelve undefined. Así que si la ruta intenta subir más allá de la raíz, no hace falta validación extra.

Complejidad: O(n) tiempo y O(n) espacio.

El patrón detrás de los tres

Si los lees seguidos vas a notar lo mismo. Los tres resuelven el mismo problema de fondo, poder regresar a algo anterior.

• Balanced parentheses: recordar la última apertura para validar el cierre.
• Reverse string: regresar al orden opuesto.
• Simplify path: .. regresa un nivel.

Ese es el superpoder del stack. Cuando un problema te pide recordar lo último, deshacer algo o procesar de atrás hacia adelante, casi siempre la respuesta es stack.

Stacks más allá de las entrevistas

Los stacks no son trivia de entrevistas. El patrón de "regresar" aparece por todos lados:

• El botón de regresar del navegador es un stack.
• El undo/redo de tu editor también.
• Los call stacks de los lenguajes (por eso existen los stack overflow errors).
• Pipelines de datos que necesitan mantener contexto de lo último visto.

Para seguir practicando

Problemas de LeetCode ordenados por dificultad:

1. Min Stack, easy.
2. Baseball Game, easy.
3. Evaluate Reverse Polish Notation, medium.
4. Daily Temperatures, medium. Es la intro al patrón de monotonic stack.

¿Cuál te costó más? Déjamelo en los comentarios. A mí Simplify Path me hizo dar más vueltas para resolverlo.