Entrevista de Programación: Encontrar la Mediana desde un Flujo de Datos

Problema y Contexto Aplicable

Diseña MedianFinder con dos operaciones:

• addNum(num) agrega un entero al flujo.
• findMedian() devuelve la mediana de todos los valores vistos hasta el momento. Con un conteo impar, devuelve el valor del medio; con un conteo par, devuelve el promedio de los dos valores del medio.

Asume solo inserciones, sin eliminaciones, y que findMedian() se llama únicamente después de al menos una inserción. Las entradas pueden incluir números negativos, duplicados y enteros de 32 bits con signo, con un máximo de 50,000 operaciones. El objetivo es O(log n) por inserción, O(1) por consulta y espacio O(n).

Por ejemplo, después de insertar 5, 2, 10, 4, las medianas en ejecución son 5, 3.5, 5, 4.5. Ordenar en cada consulta es correcto pero cuesta O(n log n) por consulta. Mantener un arreglo completamente ordenado hace que la consulta sea O(1), pero insertar en el medio aún desplaza O(n) elementos.

El material público de preparación para entrevistas en 2026 continúa presentando este como un problema representativo de dos heaps. Se aplica a rondas de programación para software general, backend, datos e infraestructura. La señal útil no es recordar la frase "max-heap más min-heap". Es derivar la estructura a partir de la consulta, enunciar ambos invariantes y demostrar por qué una secuencia de transferencia fija preserva la partición.

Lo que el Entrevistador Está Evaluando

La primera señal es elegir una estructura a partir de la combinación de operaciones. Una mediana depende únicamente del centro del orden ordenado, por lo que mantener el orden completo es innecesario. Para responder en O(1), uno o dos candidatos del medio siempre deben estar expuestos en posiciones directamente legibles. Los topes de los heaps proporcionan exactamente ese acceso al límite.

La segunda señal es mantener tanto la partición como el balance:

1. Un max-heap lower almacena la mitad menor, un min-heap upper almacena la mitad mayor, y cada

valor en lower es como máximo cada valor en upper.

1. lower tiene el mismo tamaño que upper o exactamente un elemento extra.

Ninguna condición es suficiente por sí sola. Tamaños similares no impiden que los valores se coloquen en la mitad incorrecta. El orden correcto de partición no impide que un heap crezca mucho más, lo que haría que su tope dejara de representar el centro.

La tercera señal es un análisis de complejidad preciso. Una inserción realiza una cantidad constante de operaciones de heap, cada una O(log n). Una consulta lee uno o dos topes, por lo que es O(1). La estructura sigue almacenando cada entrada y por lo tanto usa espacio O(n). "Streaming" aquí significa actualizaciones en línea, no memoria constante.

Finalmente, el entrevistador busca validación más allá de la muestra. Una respuesta sólida prueba el primer elemento, conteos pares e impares, duplicados, valores todos negativos, secuencias crecientes y decrecientes, y extremos de enteros. También compara secuencias de operaciones aleatorias contra un modelo lento de lista ordenada que sea evidentemente correcto.

Preguntas de Aclaración Antes de Responder

• ¿Hay solo inserciones, o deben eliminarse valores antiguos? Dos heaps ordinarios son suficientes solo para inserciones. Una ventana deslizante necesita eliminación diferida o un multiconjunto ordenado.
• ¿Puede ejecutarse la consulta sobre un flujo vacío? Este enunciado dice que no. Una API de producción debería devolver un valor opcional o lanzar un error explícito en lugar de leer un tope vacío.
• ¿Las entradas son enteros o valores de punto flotante? Esta versión usa enteros. Si se permite NaN de punto flotante, los valores no forman un orden total normal, por lo que se deben definir semánticas de rechazo u ordenamiento.
• ¿Cómo se define la mediana para un conteo par? Este enunciado usa la media aritmética de los dos valores del medio, por lo que el tipo de retorno debe representar fracciones.
• ¿Debe el resultado ser exacto? Sí. Un flujo ilimitado con un presupuesto de memoria fijo requiere un contrato de cuantil aproximado en su lugar.
• ¿Puede el promedio causar desbordamiento? Los enteros de Python no se desbordan. Los lenguajes de ancho fijo deben promover ambos operandos antes de la suma y la división.
• ¿Cuál es la proporción de consultas a inserciones? Dos heaps son adecuados para consultas frecuentes. Si la mediana se solicita solo una vez después de que llega toda la entrada, recopilar y ordenar suele ser más sencillo.
• ¿Se requiere acceso concurrente? La implementación es de un solo hilo. Una versión concurrente debe hacer que las transferencias y las consultas observen un estado consistente de ambos heaps.

Marco de Respuesta en 30 Segundos

"Mantendré la mitad menor en un max-heap llamado lower y la mitad mayor en un min-heap llamado upper. Cada valor en lower debe ser como máximo cada valor en upper, y lower tiene el mismo tamaño o un elemento extra. En la inserción, primero empujo a lower, muevo su máximo a upper para restaurar el orden de partición, y muevo el mínimo de upper de vuelta si upper se volvió más grande. Para un conteo impar, la mediana es el tope de lower; para un conteo par, es el promedio de ambos topes. La inserción usa una cantidad constante de operaciones de heap O(log n), la consulta es O(1) y el espacio es O(n)."

Análisis Detallado Paso a Paso

Paso uno: comparar enfoques base y localizar el cuello de botella.

La búsqueda binaria encuentra un índice de inserción en un arreglo en O(log n), pero no elimina el costo de desplazamiento O(n). Un árbol balanceado regular preserva el orden, pero sin tamaños de subárboles no puede seleccionar directamente el k-ésimo elemento. Dos heaps retienen únicamente los dos límites necesarios para la mediana, convirtiéndolos en la estructura completa más pequeña para este contrato.

Paso dos: reescribir la mediana como uno o dos topes de heap.

Sea lower la mitad menor en un max-heap, exponiendo el valor más grande de esa mitad. Sea upper la mitad mayor en un min-heap, exponiendo el valor más pequeño de esa mitad. Permite que lower tenga un elemento extra:

Odd total:  lower has one extra, median = max(lower)
Even total: heaps have equal sizes, median = (max(lower) + min(upper)) / 2

La interfaz de Python heapq ampliamente disponible está basada en min-heaps. Para mantener la implementación portable entre versiones comunes de Python, almacena valores negados en lower. Un máximo lógico x se convierte en el valor negativo almacenado más pequeño -x, por lo que -lower[0] es el máximo de la mitad inferior.

Paso tres: usar una secuencia fija de empuje, transferencia y rebalanceo.

En lugar de ramificar en cada posible destino para el nuevo valor, siempre:

1. Empuja el num negado a lower.
2. Saca el máximo lógico de lower y empújalo a upper.
3. Si upper es ahora más grande, mueve su mínimo de vuelta a lower.

import heapq


class MedianFinder:
    def __init__(self) -> None:
        self.lower = []  # Negated max-heap containing the smaller half
        self.upper = []  # Min-heap containing the larger half

    def add_num(self, num: int) -> None:
        heapq.heappush(self.lower, -num)

        largest_lower = -heapq.heappop(self.lower)
        heapq.heappush(self.upper, largest_lower)

        if len(self.upper) > len(self.lower):
            smallest_upper = heapq.heappop(self.upper)
            heapq.heappush(self.lower, -smallest_upper)

    def find_median(self) -> float:
        if not self.lower:
            raise ValueError("median is undefined for an empty stream")

        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])

        return (-self.lower[0] + self.upper[0]) / 2.0

Esta secuencia realiza una transferencia aparentemente extra, pero elimina varios casos propensos a errores. Otra implementación válida compara num con -lower[0], elige un heap y luego rebalancea. Ambos tienen el mismo costo asintótico. En una entrevista, prefiere la versión cuyos invariantes puedas probar y revisar de manera confiable.

Paso cuatro: demostrar el invariante de orden.

Asume antes de la inserción que cada valor en lower es como máximo cada valor en upper. Después de que el nuevo valor se empuja temporalmente a lower, solo ese nuevo valor puede estar en la mitad incorrecta. Saca el máximo del lower ampliado:

• Cada valor restante en lower es como máximo el valor sacado.
• Cada valor antiguo de lower ya era como máximo cada valor antiguo de upper.
• Por lo tanto, después de agregar el máximo sacado a upper, cada nuevo valor de lower sigue siendo

como máximo cada nuevo valor de upper.

Después de esa transferencia, upper puede tener un elemento extra. Mover su mínimo de vuelta a lower preserva el orden: el valor movido es como máximo todo lo que queda en upper y no es menor que el límite inferior anterior. Los heaps entonces tienen tamaños iguales o lower tiene uno extra.

Ambos invariantes se cumplen para dos heaps vacíos. Cada inserción los preserva, por lo que por inducción los topes representan las posiciones del centro después de cualquier secuencia de operaciones.

Paso cinco: rastrear una secuencia que cruza la partición.

Insert 5:  lower = [5]       upper = []        median = 5
Insert 2:  lower = [2]       upper = [5]       median = 3.5
Insert 10: lower = [5, 2]    upper = [10]      median = 5
Insert 4:  lower = [4, 2]    upper = [5, 10]   median = 4.5

El arreglo de respaldo de un heap no está completamente ordenado. [4, 2] significa solo que 4 es el tope del max-heap. Las verificaciones de depuración deben verificar el orden del heap, los dos topes y el invariante entre heaps, en lugar de comparar los arreglos de respaldo como listas ordenadas.

Paso seis: calcular la complejidad e identificar cuándo un enfoque más simple gana.

add_num realiza como máximo cinco empujes o extracciones. Cada operación de heap es O(log n), por lo que una cantidad constante sigue siendo O(log n). find_median lee longitudes y topes de heap en O(1). Cada valor vive en exactamente un heap, produciendo espacio O(n).

Si un producto recopila un lote y pide una sola mediana al final, almacenar y ordenar el arreglo es más corto y puede tener mejor comportamiento de memoria contigua. Mantener una estructura en línea es innecesario. Si cada valor está en el rango fijo 0 a 100, un arreglo de 101 conteos da inserción O(1) y un escaneo de 101 cubetas fijas, también constante para ese dominio fijo.

Paso siete: cerrar el ciclo con casos deterministas y pruebas diferenciales aleatorizadas.

Como mínimo, prueba:

Para una prueba aleatorizada, agrega cada entero generado tanto a MedianFinder como a un arreglo de referencia. Ordena la referencia y calcula su centro después de cada inserción. Compara ambos resultados y verifica que len(lower) sea igual a len(upper) o sea uno mayor. El modelo lento no es adecuado para el rendimiento objetivo pero es excelente como oráculo de corrección.

Respuesta de Muestra de Alta Calidad

"Primero confirmaría que se trata de una mediana exacta con solo inserciones y que las consultas no ocurren sobre un flujo vacío. Si deben eliminarse elementos de ventana antiguos, los heaps ordinarios no pueden eliminar valores arbitrarios de manera eficiente, por lo que el diseño cambia.

Para consultas en tiempo constante, quiero que el centro del orden ordenado esté continuamente expuesto en los límites de la estructura. Usaré un max-heap lower para la mitad menor y un min-heap upper para la mitad mayor. Dos invariantes son importantes: cada valor en lower es como máximo cada valor en upper, y lower tiene el mismo tamaño o uno extra.

En la inserción uso una secuencia fija de tres pasos. Empujo el nuevo valor a lower, muevo el máximo de lower a upper para restaurar la partición, y muevo el mínimo de upper de vuelta si upper se volvió más grande. Ambos invariantes se cumplen de nuevo. Con un conteo impar, lower tiene el valor extra y su tope es la mediana. Con un conteo par, promedio ambos topes.

La inserción realiza una cantidad constante de operaciones de heap, por lo que es O(log n). La consulta lee topes en O(1), y retener cada valor cuesta espacio O(n). Probaría un elemento, conteos pares, duplicados, valores negativos, entrada monótona y extremos de enteros, y luego ejecutaría pruebas diferenciales aleatorizadas contra un modelo de ordenar en cada paso. Si los valores están limitados a 0 a 100, usaría 101 contadores; si hay solo una consulta final, simplemente ordenaría."

Errores Comunes

• Balancear solo los tamaños de los heaps → los valores pueden cruzar la partición y los topes no son los dos valores del centro → mantener ambos invariantes: de orden y de tamaño.
• Poner la mitad menor en un min-heap → su tope es el mínimo global, no el máximo de la mitad inferior → usar un max-heap para la mitad menor.
• Devolver un solo tope para un conteo par → la definición de mediana es incorrecta → promediar ambos topes cuando los tamaños son iguales.
• Sumar enteros de ancho fijo antes de la conversión → dos valores grandes pueden desbordarse primero → promover ambos operandos antes de sumar y dividir.
• Llamar O(log n) a la inserción en arreglo ordenado → encontrar el índice es rápido pero el desplazamiento sigue siendo O(n) → separar el costo de búsqueda del costo de mutación.
• Tratar el arreglo de heap de Python como completamente ordenado → las aserciones de depuración se vuelven inválidas → depender solo de la raíz y la propiedad de heap padre-hijo.
• Leer el índice cero de un heap vacío → el fallo ocurre en un límite poco claro → prohibir consultas vacías o devolver un valor opcional explícitamente.
• Afirmar que el algoritmo en línea usa espacio constante → ambos heaps retienen todas las entradas → declarar espacio O(n) para una mediana exacta.
• Reutilizar el mismo código para una ventana deslizante → los valores vencidos pueden permanecer en un tope y corromper el resultado → agregar eliminación diferida y tamaños válidos, o usar un multiconjunto ordenado.
• Probar solo la muestra → los errores de negación, duplicados y rebalanceo pueden no activarse → combinar casos límite con pruebas diferenciales aleatorizadas.

Preguntas de Seguimiento y Respuestas

Seguimiento 1: ¿Qué cambia si cada entero está entre 0 y 100?

Mantén un arreglo de 101 conteos y el conteo total de elementos. La inserción incrementa un cubo en O(1). Para consultar, escanea los cubos hasta alcanzar uno o dos rangos del centro. El escaneo y el espacio son constantes para este dominio fijo. Si el rango crece con la entrada, el escaneo es O(R) para un tamaño de rango R y ya no debe describirse como constante.

Seguimiento 2: ¿Qué pasa si el 99% de los valores están entre 0 y 100 pero el resto son arbitrarios?

Mantén los 101 contadores para valores dentro del rango y estructuras de estadística de orden para valores por debajo de 0 y por encima de 100. Sus conteos determinan si un rango objetivo cae en los valores atípicos inferiores, el rango fijo o los valores atípicos superiores; luego selecciona dentro de la estructura relevante. Los heaps ordinarios no admiten selección de rango arbitrario, por lo que la afirmación del 99% por sí sola no justifica consultas en tiempo constante. Un prefijo adversarial aún puede colocar el rango de la mediana entre los valores atípicos.

Seguimiento 3: ¿Cómo calcularías la mediana de los últimos k valores?

El movimiento de ventana requiere eliminar el valor saliente. Los heaps binarios no pueden localizar una entrada arbitraria de manera eficiente. Una solución común agrega un mapa de conteo de eliminación diferida y rastrea tamaños válidos para ambos heaps. Marca un valor saliente como lógicamente eliminado, y físicamente sácalo solo cuando llegue a un tope; poda ambos topes antes de leer la mediana. Las actualizaciones son amortizadas O(log k), mientras que la búsqueda del tope sigue siendo O(1). Un multiconjunto balanceado con soporte para duplicados es más simple cuando el lenguaje lo proporciona.

Seguimiento 4: ¿Puede un algoritmo de memoria fija devolver la mediana exacta de un flujo ilimitado?

En general, no para flujos de enteros arbitrarios. Un valor histórico descartado puede determinar posteriormente el rango del centro. El contrato debe cambiar a un cuantil aproximado, usando un boceto de cuantil con una garantía explícita de error de rango, requisito de confianza y comportamiento de fusión. Esa es una respuesta diferente a la estructura exacta de dos heaps.

Seguimiento 5: ¿Cómo admitirías inserciones y consultas concurrentes?

Los dos heaps forman un estado lógico único. La extensión correcta más simple protege las operaciones completas de add_num y find_median con el mismo mutex, evitando que una consulta observe el momento después de que un valor sale de lower pero antes de que entre a upper. Un servicio con muchas lecturas podría publicar instantáneas inmutables de la mediana, pero el intervalo de instantáneas introduce una compensación de frescura que pertenece al contrato de la API.

Seguimiento 6: ¿Pueden combinarse las medianas de varios fragmentos en una mediana global?

No. La mediana de un fragmento pierde el tamaño y la distribución de ese fragmento; incluso un promedio ponderado de medianas de fragmentos no es la mediana global. Un resultado exacto requiere una estructura que pueda responder al rango global, como agregar conteos sobre un dominio acotado y realizar selección distribuida. Un resultado aproximado puede usar resúmenes de cuantiles fusionables. Los requisitos de precisión y latencia deben elegirse antes de definir la estructura global.