Planteamiento y contexto
Heredas un MedianFinder con un max-heap para la mitad inferior y un min-heap para la mitad superior. Funciona para 1, 2, 3, pero falla en secuencias como 10, 1, 9, 2, entradas con muchos duplicados y enteros extremos. La tarea consiste en depurar una implementación existente, no en derivar la estructura de datos estándar desde cero.
Qué evalúa el entrevistador
- Si defines los invariantes antes de modificar el código.
- Si puedes reducir una secuencia que falla e identificar el primer estado inválido.
- Si la reparación maneja consultas vacías, duplicados y desbordamientos en longitudes pares.
- Si la demostración y la complejidad coinciden con el código.
Preguntas clarificadoras para hacer
- ¿Qué debería hacer
findMedian()antes de la primera inserción? - ¿Qué montículo puede contener el elemento adicional?
- ¿Qué ancho de enteros acepta la API y qué tipo devuelve la mediana?
- ¿Pueden aparecer duplicados y está el acceso concurrente dentro del alcance?
Asume que los duplicados son válidos, el montículo inferior puede tener un elemento adicional, la consulta devuelve un valor de punto flotante y la búsqueda en una estructura vacía genera un error documentado. La concurrencia queda fuera de esta tarea de programación.
Una respuesta en 30 segundos
«Instrumentaría ambos montículos después de cada inserción y afirmaría dos invariantes: sus tamaños difieren a lo sumo en uno, siendo el montículo inferior más grande, y cada valor inferior es menor o igual que cada valor superior, lo cual puede verificarse en las cimas de los montículos. Minimizaría la primera entrada que falla y luego repararía la inserción insertando en el montículo inferior, moviendo su máximo al montículo superior y devolviendo el mínimo superior solo cuando este último sea más grande. La consulta de la mediana utiliza la cima inferior para tamaños impares y un promedio seguro contra desbordamientos de ambas cimas para tamaños pares. Finalmente, ejecutaría un oráculo basado en un arreglo ordenado sobre secuencias cortas exhaustivas y extremos adversos».
Análisis detallado paso a paso
1. Hacer observable el fallo
Después de cada inserción, registra el prefijo de entrada, los tamaños de ambos montículos y ambas cimas. Deténte en el primer invariante roto. Aplica delta-debugging a la secuencia eliminando valores mientras el fallo persista. Un contraejemplo de cuatro valores es más útil que mil valores aleatorios.
2. Reparar con una única ruta de inserción determinista
Utiliza el montículo inferior como punto de entrada. Inserta x, mueve su máximo al montículo superior y luego devuelve el mínimo superior si el montículo superior quedó más grande. Esta secuencia restaura el orden antes que el tamaño. Con una biblioteca de lenguaje que solo proporciona un min-heap, almacena valores negados en el montículo inferior y mantén la conversión de signo en el límite.
3. Hacer que la consulta sea segura
Rechaza la consulta cuando ambos montículos estén vacíos. Para una cantidad impar, devuelve el máximo inferior. Para una cantidad par, convierte ambos extremos a un tipo más amplio o de punto flotante antes de sumarlos; (a + b) / 2 puede desbordarse en un tipo de entero de ancho fijo incluso cuando la mediana es representable.
4. Demostrar y probar la reparación
Mover el máximo inferior al lado superior garantiza que los valores inferiores restantes no superen el límite trasladado. Mover un mínimo superior de regreso restaura la regla de tamaño elegida sin romper el ordenamiento. Cada inserción realiza un número constante de operaciones de montículo, por lo que es O(log n); la consulta lee una o dos cimas en O(1) y el almacenamiento es O(n).
Utiliza un oráculo de lista ordenada después de cada prefijo. Cubre la consulta vacía, un solo valor, dos extremos, orden ascendente, descendente, alternancia bajo/alto, todo duplicados, valores negativos y muchas transiciones entre tamaños pares e impares.
Un ejemplo sólido de respuesta
«No parchearía la rama que casualmente falló. Primero afirmaría lower.size == upper.size o lower.size == upper.size + 1, más max(lower) <= min(upper) siempre que ambos existan. En cada add, inserto en el inferior, muevo su máximo al superior y luego muevo el mínimo superior de regreso solo si el superior es más grande. Eso hace que la restauración del orden sea independiente del patrón de entrada anterior.
findMedian rechaza una estructura vacía. Un flujo de tamaño impar devuelve la cima inferior; un flujo de tamaño par convierte ambas cimas antes de promediarlas para que los enteros extremos no se desborden. Compararía cada prefijo contra un oráculo de arreglo ordenado para secuencias cortas exhaustivas extraídas de valores negativos, cero, duplicados y extremos. La implementación central se mantiene en O(log n) por inserción, O(1) por consulta y espacio O(n)».
Errores comunes
- Equilibrar solo los tamaños → los montículos pueden contener valores cruzados → afirmar el orden de las cimas como un invariante separado.
- Elegir una rama solo a partir del valor entrante → el estado previo del montículo aún puede ser inválido → utilizar una secuencia determinista de movimiento entre montículos.
- Calcular el promedio en el tipo entero de entrada → los extremos pueden desbordarse → ampliar el tipo antes de la suma.
- Probar solo valores únicos ordenados → los duplicados y los extremos alternantes ocultan errores de bifurcación → utilizar oráculos de prefijo y secuencias adversas.
- Afirmar una inserción
O(1)→ las inserciones y extracciones de montículos son logarítmicas → contar las operaciones reales del montículo.
Preguntas de seguimiento y respuestas
¿Cómo encontrarías la entrada fallida más pequeña?
Continúa eliminando un elemento o un bloque contiguo y vuelve a ejecutar las verificaciones de invariantes. Conserva el prefijo más corto cuya inserción final viole primero el orden o el tamaño, y luego inspecciona únicamente esa transición.
¿Por qué los duplicados no necesitan un manejo especial?
El invariante utiliza <=, por lo que los valores iguales pueden residir en cualquiera de los lados. El tamaño del montículo determina qué copia igual contribuye a la mediana; la identidad no importa.
¿Cómo realizarías pruebas sin confiar en otra implementación de montículo?
Para entradas pequeñas, copia el prefijo, ordénalo y calcula la mediana matemática directamente. Agota todas las secuencias sobre un alfabeto pequeño y luego añade extremos de ancho fijo y casos aleatorios más grandes.
¿Soporta esto una ventana deslizante (sliding window)?
No. Eliminar un valor expirado arbitrario requiere una eliminación indexada o contadores de eliminación diferida (lazy deletion) en ambos montículos. Esa es una tarea diferente y no debe ocultarse dentro de esta reparación.