Entrevista técnica de código: Implementar muestreo de reservorio ponderado

1. Enunciado y contexto

Cada registro en un flujo tiene un peso positivo, pero no se conoce ni la cantidad de elementos ni el peso total. Implemente una muestra ponderada de tamaño k sin reemplazo: cada registro aparece a lo sumo una vez, su probabilidad de inclusión es proporcional a su peso y el flujo se recorre una sola vez. Explique la generación de claves, el mantenimiento de candidatos, los pesos extremos y las pruebas de distribución.

2. Qué está evaluando el entrevistador

• Si distingue entre muestreo con y sin reemplazo y comprende la probabilidad proporcional al peso.
• Si puede convertir el muestreo ponderado en mantener las k prioridades aleatorias o claves exponenciales superiores.
• Si elige un min-heap de tamaño k y proporciona una actualización de O(log k) por registro.
• Si maneja pesos cero, enormes o diminutos, límites aleatorios, IDs duplicados y una semilla reproducible.

3. Preguntas de clarificación antes de responder

1. ¿Los pesos son números positivos finitos, y los registros con peso cero deben descartarse o conservarse?
2. ¿La muestra es sin reemplazo o un registro puede aparecer más de una vez?
3. ¿Se requiere solo la muestra final o cada prefijo debe tener la distribución correcta?
4. ¿Se deben fusionar múltiples fragmentos, persistir el estado o reproducir los resultados con exactitud?

4. Estructura de respuesta en 30 segundos

Genere una clave aleatoria independiente para cada registro de peso w y conserve las k claves más grandes. Una forma estable extrae u uniformemente de (0, 1] y calcula key = log(u) / w; debido a que las claves son negativas, esto equivale a conservar las k claves más cercanas a cero. Almacene la muestra actual en un min-heap de tamaño k cuya raíz sea la clave más pequeña; reemplácela solo cuando una nueva clave sea mayor. Una sola pasada toma tiempo O(n log k) y espacio adicional O(k). Valide los pesos y haga que la fuente aleatoria sea inyectable.

5. Respuesta detallada paso a paso

Paso 1: Definir la distribución

El muestreo ponderado sin reemplazo no consiste en k extracciones independientes con probabilidad w / total, porque eso puede repetir un registro. El objetivo es un conjunto de tamaño k cuya distribución de estadísticos de orden sea equivalente a extraer repetidamente un elemento no seleccionado en proporción a su peso restante. El reservorio debe ser una muestra válida después de cada prefijo, no solo después de que termine el flujo.

Paso 2: Generar una clave numéricamente estable

La carrera exponencial proporciona una implementación conveniente: extraiga un valor uniforme u y calcule key = log(u) / w, luego conserve las claves más grandes. A medida que u se acerca a cero, log(u) se vuelve más negativo; un peso mayor hace que la clave esté más cerca de cero y, por lo tanto, sea más probable que entre en el top k. Evite u ** (1 / w), ya que puede sufrir subdesbordamiento (underflow) o perder separación con pesos extremos.

sample_key(weight):
    require finite(weight) and weight > 0
    u = uniform_random_open_interval()
    return log(u) / weight

Paso 3: Mantener el top-k con un min-heap

Almacene (key, sequence, item) en el montículo, utilizando la secuencia para desempatar claves exactas. Inserte elementos mientras el reservorio no esté lleno. Una vez lleno, compare la nueva clave con la raíz y reemplácela solo cuando sea mayor. Si k es cero, descarte todos los registros. Reordenar un arreglo después de cada registro haría que las actualizaciones fueran de O(k log k) en lugar de O(log k).

Paso 4: Manejar los límites de entrada y aleatoriedad

Rechace NaN, infinito y pesos negativos. Un registro con peso cero no puede ser seleccionado en una muestra con pesos positivos y se puede omitir. La fuente aleatoria no debe devolver cero, o de lo contrario log(0) se vuelve inutilizable; vuelva a generar el valor o ajústelo al valor flotante positivo más pequeño. Trate los IDs duplicados como registros independientes a menos que el problema solicite explícitamente la deduplicación de IDs. Inyecte una fuente pseudoaleatoria en las pruebas para que los fallos sean reproducibles.

Paso 5: Complejidad, validación y extensión distribuida

Para n registros, la implementación en una sola máquina toma tiempo O(n log k) y espacio adicional O(k). Utilice simulaciones de Monte Carlo con pesos fijos para comprobar que la inclusión marginal aumenta con el peso, y asegúrese mediante aserciones de que la muestra no contenga duplicados. En un flujo distribuido, cada fragmento puede generar claves con la misma regla y un coordinador puede fusionar los candidatos top-k de cada fragmento; el estado, las actualizaciones, las eliminaciones, las semillas y el costo de comunicación aún requieren un diseño explícito. El simple hecho de muestrear uniformemente a partir de los reservorios de los fragmentos pierde información sobre los registros descartados.

6. Ejemplo de una respuesta de alta calidad

Para cada registro de peso positivo, genero key = log(u) / w, donde u es uniforme en un intervalo abierto, y conservo las k claves más grandes. Las claves son negativas, por lo que los pesos más grandes tienden a estar más cerca de cero. Un min-heap de capacidad k almacena la muestra; cuando está lleno, una nueva clave reemplaza la raíz más pequeña solo si es mayor. Defino el comportamiento para pesos no válidos, valores aleatorios iguales a cero, k = 0 y registros duplicados. El escaneo toma tiempo O(n log k) y espacio O(k). Valido la distribución mediante simulaciones repetidas con pesos fijos y fusiono candidatos distribuidos siguiendo la misma regla global de claves top-k.

7. Errores comunes

• Muestrear de forma independiente con w / total → genera duplicados y no es muestreo sin reemplazo → utilice claves aleatorias y top-k.
• Calcular u ** (1 / w) directamente → subdesbordamiento (underflow) con pesos extremos → compare claves logarítmicas.
• Usar un max-heap para top-k → requiere buscar el valor más pequeño → use un min-heap para que el punto de reemplazo sea la raíz.
• Permitir u = 0 → log(0) se convierte en infinito negativo → use una fuente de intervalo abierto o vuelva a extraer.
• Probar solo una salida → pasa por alto sesgos a largo plazo → ejecute pruebas de Monte Carlo con pesos fijos y verifique que no haya duplicados.

8. Preguntas de seguimiento y respuestas

¿Por qué key = log(u) / w produce un muestreo ponderado?

Trate -log(u) como una variable exponencial con tasa uno. Dividir por w da un tiempo exponencial con tasa w. Es más probable que el tiempo exponencial más pequeño provenga de una tasa mayor; negarlo significa conservar las claves más grandes, lo que da como resultado un muestreo ponderado sin reemplazo.

¿Cómo hace que los resultados sean reproducibles?

Inyecte una fuente pseudoaleatoria con una semilla explícita y registre el identificador del elemento, la versión del peso y la versión del algoritmo en los metadatos del experimento. No dependa de la planificación de hilos ni del estado aleatorio global, o de lo contrario una misma entrada podría producir muestras diferentes.

¿Se pueden fusionar dos reservorios ya construidos?

Si ambos fragmentos generaron claves independientes bajo la misma regla, fusione sus claves candidatas y tome las k mejores globales. Tratar únicamente los dos reservorios finales como datos ordinarios y muestrear de nuevo pierde información sobre los registros descartados. Las claves persistidas y las actualizaciones o eliminaciones en los fragmentos también necesitan un comportamiento definido.

¿Qué sucede si los pesos cambian con el tiempo?

Cambiar un peso modifica la distribución objetivo, por lo que la clave anterior ya no representa el nuevo peso. Vuelva a generar claves para los registros afectados o reingrese un evento con la versión del peso en el flujo. Indique si se acepta una aproximación temporal breve y cómo se retiran las muestras antiguas.