Entrevista de código: ¿Cómo diseñar un Max Stack con popMax?

Problema y contexto

Implementa MaxStack: push(x) agrega un elemento, pop() elimina y devuelve el tope, top() lee el tope, peekMax() lee el máximo y popMax() elimina y devuelve el máximo más cercano al tope. Los máximos repetidos usan un desempate de tipo último en entrar, primero en salir; el comportamiento con la pila vacía debe ser un error explícito o un resultado vacío.

El problema público de LeetCode y los registros recientes de preguntas de entrevistas utilizan esta interfaz. Difiere de una pila de mínimo por prefijo: popMax debe ubicar un nodo interior y restaurar el orden restante de la pila.

Qué está evaluando el entrevistador

• Si defines primero el desempate de máximos duplicados y el contrato para la pila vacía.
• Si puedes explicar por qué una sola variable currentMax no puede restaurar el siguiente máximo tras una eliminación.
• Si separas el orden de la pila del orden por valor y eliminas el mismo nodo de ambos índices.
• Si distingues un diseño de pila auxiliar con costo amortizado O(1) de un diseño de índice ordenado O(log n).

Aclaraciones previas a la codificación

1. ¿Debe ser popMax de orden O(1), amortizado O(1) o puede ser O(log n)? Esto determina la estructura de datos.
2. Para máximos duplicados, ¿debe eliminarse el elemento más cercano al tope o se acepta cualquier máximo? La regla cambia la búsqueda en el índice.
3. ¿Se requieren iteradores estables, llamadas concurrentes o persistencia? Esto modifica el ciclo de vida del nodo y el bloqueo.
4. ¿Los valores son objetos comparables o enteros acotados? Los enteros acotados permiten cubos (buckets); los objetos genéricos normalmente necesitan un índice de comparación.

Respuesta de 30 segundos

“Envuelvo cada valor en un nodo con un número de secuencia monótonamente creciente. Una lista doblemente enlazada preserva el orden de la pila; un índice ordenado clasifica por (value, sequence), de modo que su última entrada es el máximo más cercano al tope. top lee la cola de la lista, peekMax lee la cola del índice y popMax toma ese nodo y lo desenlaza a través de sus punteros de lista. Con un índice de árbol balanceado, push, pop, peekMax y popMax son O(log n), mientras que top es O(1). Si solo las operaciones del tope y peekMax necesitan tiempo constante, una pila auxiliar de máximos es más simple, pero popMax no puede mantenerse honestamente en O(1).”

Análisis detallado paso a paso

Paso 1: Separar el orden de la pila del orden clasificado.

Cada nodo almacena value, un sequence monótonamente creciente, prev y next. La cola de la lista es el tope de la pila. La clave ordenada es (value, sequence); para valores iguales, la secuencia mayor se ordena después, haciendo que la cola del índice sea el máximo más cercano al tope.

Paso 2: Elegir un índice ordenado eliminable.

Utiliza un árbol balanceado consciente de duplicados, un TreeMap junto con un conjunto ordenado de nodos, o un índice de dos niveles de valor a IDs de secuencia ordenados. Un currentMax solitario es insuficiente: tras eliminarlo, se debe encontrar el siguiente máximo y su nodo correspondiente.

Paso 3: Mantener las cinco operaciones sincronizadas.

• push: crea un nodo, agrégalo al final de la lista e insértalo en el índice ordenado.
• pop: toma la cola de la lista, elimina ese nodo del índice ordenado y luego desenlázalo.
• top: devuelve el valor de la cola de la lista.
• peekMax: devuelve el valor de la cola del índice ordenado.
• popMax: toma la cola del índice ordenado, desenlázala mediante sus punteros de lista y luego elimínala del índice.

El pseudocódigo muestra el invariante clave; la API concreta del árbol depende del lenguaje:

node = orderedByValueAndSequence.last()
orderedByValueAndSequence.erase(node.key)
unlink(node.prev, node, node.next)
return node.value

Paso 4: Complejidad y la alternativa más simple.

Con un árbol balanceado, top es O(1) y las demás operaciones de índice son O(log n); el espacio es O(n). Si un popMax amortizado O(n) es aceptable, una pila principal más una pila de máximos por prefijo registra el máximo en cada profundidad. Eso es más fácil, pero no se adapta a la eliminación frecuente en posiciones arbitrarias.

Paso 5: Duplicados, estado vacío e identidad de los nodos.

La secuencia resuelve tanto el orden de los duplicados como el desempate de popMax. Las operaciones en estado vacío devuelven un error consistente. Cada nodo aparece exactamente una vez en la lista y una vez en el índice; elimina el mismo nodo de ambas estructuras en lugar de reconstruirlo solo a partir de su valor.

Paso 6: Probar el orden y los índices.

Usa un arreglo lento como modelo de referencia. Prueba [5,1,5] con dos llamadas a popMax; debería eliminar el 5 superior y luego el 5 inferior. Cubre valores negativos, todos los valores iguales, estado vacío, push/pop alternados, un máximo interior, eliminaciones repetidas y secuencias aleatorias largas. Después de cada operación, verifica el orden de la lista, el tamaño del índice y peekMax.

Respuesta de muestra de alta calidad

“Utilizaría una lista doblemente enlazada para el orden de la pila y un índice ordenado balanceado con clave (value, sequence) para la búsqueda del máximo. La secuencia es creciente, por lo que la secuencia más grande entre máximos iguales es la más cercana al tope. Cada nodo lleva tanto los punteros de la lista como su clave de índice: pop toma la cola de la lista, popMax toma la cola del índice, y ambos eliminan ese mismo nodo de la otra estructura. Top es O(1), las operaciones restantes son O(log n) y el espacio es O(n). Si el entrevistador solo necesita peekMax, usaría una pila auxiliar de máximos para reducir la complejidad de implementación.”

Errores comunes

• Mantener solo un máximo actual → el siguiente máximo se desconoce tras la eliminación → mantén un índice ordenado que permita búsquedas.
• Tratar popMax como pop → se elimina la posición incorrecta y cambia el orden de la pila → encuentra el nodo por el índice de valores y luego desenlázalo mediante el puntero de lista.
• Dejar duplicados sin una secuencia → no se puede demostrar cuál es el máximo más cercano al tope → indexa por (value, sequence).
• Eliminar del índice pero no de la lista → top puede devolver un nodo eliminado → comparte la identidad del nodo y actualiza ambas estructuras de forma atómica.
• Afirmar que popMax es O(1) para el diseño de pila auxiliar → la eliminación arbitraria usualmente mueve elementos o reconstruye el estado → establece los límites amortizados y en el peor caso con precisión.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Puede cada operación ser O(1)?

Para enteros de ancho fijo, son posibles estructuras de cubos o estructuras especializadas de prioridad para enteros, pero el límite depende del ancho de la clave, la memoria y el modelo computacional. Para objetos comparables arbitrarios, proporciona la solución honesta de índice O(log n) en lugar de mezclar afirmaciones amortizadas, esperadas y de peor caso.

Pregunta de seguimiento 2: ¿Cómo lo harías seguro para subprocesos (thread-safe)?

El contrato más simple protege cada operación compuesta con un único cerrojo (lock) para que la lista y el índice ordenado no diverjan temporalmente. Una mayor concurrencia puede usar sharding o instantáneas inmutables, pero popMax elimina de dos estructuras de forma atómica y no se puede garantizar la consistencia asumiendo que adquirir cerrojos por separado es suficiente.

Pregunta de seguimiento 3: ¿Qué pasa si solo se requiere peekMax y no popMax?

Usa una pila principal y una pila de máximos por prefijo de igual longitud. Push registra el nuevo máximo en ambas pilas; pop elimina de ambas; top y peekMax leen sus respectivos topes. Cada operación es O(1), y los máximos duplicados deben registrarse repetidamente.