Planteamiento y contexto
Implementa una pila con push, pop, top y getMin. Cada operación debe ser O(1) y el comportamiento para una pila vacía debe ser explícito. La pregunta es adecuada para roles de programación, backend y bibliotecas. La clave es mantener el mínimo para cada profundidad de la pila, no memorizar una API.
Qué evalúa el entrevistador
El invariante
La estructura auxiliar en la profundidad d almacena el mínimo de los primeros d valores. Las pilas principal y auxiliar conservan la misma longitud.
Mínimos duplicados
Cuando un nuevo valor es igual al mínimo actual, aún debe registrarse. De lo contrario, desapilar una copia pierde el mínimo correcto.
Errores y casos límite
pop, top y getMin en una pila vacía necesitan un contrato coherente: excepción, opción o código de error. Un valor centinela silencioso no es seguro.
Complejidad
Cada operación solo interactúa con el tope, por lo que el tiempo es O(1) y el espacio adicional es O(n). Un escaneo durante getMin no satisface el requisito.
Preguntas para aclarar primero
- ¿Qué debe devolver una operación en una pila vacía: una excepción, una opción o un código de error?
- ¿Los valores pueden ser negativos, repetidos o cercanos a los límites de enteros?
- ¿Se requiere un comparador genérico o únicamente enteros?
- ¿La API debe devolver el índice del mínimo o el recuento de apariciones?
- ¿Se requiere seguridad en hilos (thread safety) o una implementación sin bloqueos (lock-free)?
- ¿Las pruebas deben cubrir llamadas individuales o secuencias de operaciones aleatorias?
Una respuesta de 30 segundos
“Mantendría dos pilas de igual longitud: values y mins. El tope de mins almacena el mínimo de todos los valores presentes actualmente. En push, inserto min(x, mínimo actual); en pop, retiro de ambas; top y getMin leen el tope correspondiente. Cada operación es O(1), con O(n) de espacio adicional. Registro los mínimos duplicados, defino un contrato de error para pila vacía y verifico secuencias aleatorias contra una lista de referencia más lenta.”
Respuesta detallada paso a paso
Paso 1: Establecer el invariante
Sean S la pila de valores y M la pila auxiliar. Para cada profundidad d, M[d] es igual al mínimo de S[0..d]. Sus longitudes son siempre iguales.
Paso 2: Diseñar push
Si M no está vacía, inserta min(x, M.top()) en M; de lo contrario, inserta x. Luego inserta x en S. El nuevo tope auxiliar es el mínimo del prefijo.
Paso 3: Diseñar pop y consultas
Pop elimina un elemento de ambas pilas. top lee S.top(), y getMin lee M.top(). No se necesita ningún escaneo.
Paso 4: Conservar duplicados
Tras insertar 2, 1, 1, M es 2, 1, 1. Desapilar una vez aún debe devolver 1. Registrar únicamente valores estrictamente menores rompe el invariante.
Paso 5: Definir errores y tipos
Una pila vacía puede lanzar EmptyStackError o devolver un Result tipado. Una implementación genérica debería aceptar un comparador de orden total y definir la igualdad de forma coherente.
Paso 6: Demostrar y probar la complejidad
Las cuatro operaciones son O(1), con O(n) de espacio auxiliar. Una prueba aleatoria puede mantener una lista normal como oráculo y comparar top, mínimo, tamaño y errores después de cada operación.
~~~python class MinStack: def push(self, value): ... def pop(self): ... def top(self): ... def get_min(self): ... ~~~
Respuesta modelo
“Mantendría values y mins. mins[i] es el mínimo de values[0..i], por lo que las pilas tienen la misma longitud. push almacena el valor y su nuevo mínimo de prefijo; una pila mins vacía almacena el valor directamente. pop elimina de ambas, mientras que top y getMin leen el tope correspondiente.
Los mínimos duplicados deben almacenarse. Para 2, 1, 1, mins es 2, 1, 1; de lo contrario, un pop devolvería incorrectamente 2. Las operaciones vacías usan un contrato de error explícito. El tiempo es O(1) por operación y el espacio adicional es O(n). Probaría secuencias vacías, negativas, duplicadas, alternadas y aleatorias contra un oráculo basado en listas.”
Errores comunes
- Escanear la pila de valores durante getMin, haciéndolo O(n).
- Registrar únicamente valores estrictamente menores y perder mínimos duplicados.
- Desapilar solo la pila principal y desincronizar las estructuras.
- Mantener un único mínimo global que no se puede restaurar tras pop.
- Devolver cero para una pila vacía y confundirlo con una entrada válida.
- Ignorar valores negativos o límites de enteros.
- Calificar un límite amortizado como O(1) estricto sin justificación.
- Afirmar compatibilidad con objetos genéricos sin definir un comparador.
Preguntas de seguimiento
Pregunta de seguimiento 1: ¿Puedes usar una sola pila?
Sí. Almacena un par de valor y mínimo de prefijo en cada entrada. El invariante no cambia y el espacio sigue siendo O(n).
Pregunta de seguimiento 2: ¿Cómo agregarías getMax?
Mantén también una pila de máximos por prefijo, o almacena el valor, min y max en cada entrada. El tiempo sigue siendo O(1) por operación y el espacio total O(n).
Pregunta de seguimiento 3: ¿Cómo devolverías la cantidad de mínimos?
Almacena min y count en cada entrada auxiliar. Los valores iguales incrementan count, y pop restaura la entrada anterior. Define explícitamente la semántica de duplicados y reversión (rollback).
Pregunta de seguimiento 4: ¿Cómo la harías segura para hilos (thread-safe)?
Protege ambas pilas con un único mutex alrededor de cada operación lógica. Usar bloqueos separados podría exponer un estado intermedio inconsistente. Los diseños sin bloqueos (lock-free) requieren un estado compuesto atómico y una discusión sobre la recuperación de memoria.
Pregunta de seguimiento 5: ¿Cómo demuestras su corrección?
Usa inducción. La pila vacía cumple el invariante; push calcula el nuevo mínimo de prefijo; pop restaura el registro anterior. Por lo tanto, getMin siempre devuelve el mínimo de la pila de valores actual.