Entrevista técnica de código: ¿Cómo realizar un muestreo uniforme a partir de un flujo de longitud desconocida?

Planteamiento y casos de uso

Solo puede leer el flujo una vez; su longitud n es desconocida y necesita k elementos distintos con igual probabilidad. No puede almacenar el flujo ni esperar a un índice aleatorio final. El muestreo de reservorio mantiene un reservorio fijo de tamaño k: cuando llega el elemento i, entra con una probabilidad de k/i y reemplaza una posición del reservorio elegida uniformemente.

Este problema evalúa un algoritmo probabilístico para flujos continuos. El artículo de Vitter estudia el muestreo en una sola pasada cuando se desconoce el tamaño de la población, y las notas de cursos universitarios proporcionan la inducción de uniformidad. La categoría principal es coding: invariantes de probabilidad bajo un límite de memoria, no una implementación de plataforma de datos.

Lo que evalúa el entrevistador

• Si reconoce el patrón de reservorio para tamaño desconocido, una sola pasada y memoria fija.
• Si explica la regla de reemplazo k=1 1/i antes de generalizar a k.
• Si demuestra que después del elemento i, cada elemento tiene una probabilidad de k/i en la muestra.
• Si evita muestras duplicadas, la suposición falsa de que n es conocido y los enteros aleatorios sesgados.
• Si indica el tiempo O(n), el espacio O(k) y el límite del muestreo ponderado.

Aclaraciones antes de responder

• ¿Es k un entero positivo? ¿Qué debería suceder para k <= 0 o si hay menos de k elementos en el flujo?
• ¿"Distintos" significa registros distintos o deduplicación por valor?
• ¿Puede el flujo estar vacío, ser infinito o ser interrumpido? La salida y la recuperación difieren.
• ¿Es el reservorio final la única salida, o debe ser observable durante el escaneo?
• ¿La API de números aleatorios proporciona enteros no sesgados en el rango requerido?
• ¿El objetivo es uniforme o ponderado/estratificado? El muestreo ponderado necesita un invariante diferente.

Estructura de respuesta en 30 segundos

"Llene el reservorio con los primeros k elementos. Para el elemento i, comenzando en uno, genere un entero no sesgado j en [0, i-1]. Si j < k, reemplace reservoir[j]; de lo contrario, descarte el elemento. Después del elemento i, cada elemento tiene una probabilidad de k/i: el nuevo elemento entra con k/i, y un elemento antiguo sobrevive con k/(i-1) multiplicado por 1 - 1/i. El algoritmo es de una sola pasada, tiempo O(n) y espacio extra O(k)."

Respuesta detallada paso a paso

Paso 1: Comenzar con k=1.

Conserve el primer elemento. Para el elemento i, reemplace el candidato actual con una probabilidad de 1/i. Después de procesar i elementos, cada uno tiene una probabilidad de 1/i de ser retenido.

Paso 2: Generalizar a k.

Llene las primeras k posiciones. Para el elemento i, ingrese con una probabilidad de k/i; si entra, elija una de las k posiciones uniformemente. Un entero j en [0, i-1] implementa esto: j < k significa reemplazar la posición j.

Paso 3: Escribir el pseudocódigo.

reservoir = first k items
for i = k+1 .. n:
  j = uniformInteger(0, i-1)
  if j < k:
    reservoir[j] = item i
return reservoir

Si el flujo no se puede llenar previamente, agregue elementos mientras seen <= k, y luego use la misma rama. El generador de enteros debe cubrir el rango completo sin sesgo.

Paso 4: Demostrar la probabilidad del nuevo elemento.

En el elemento i, su probabilidad de inclusión es k/i. Una vez incluido, sobrevive a cada paso posterior con una probabilidad de ∏(1 - 1/t) = i/n, porque una posición en particular se reemplaza con una probabilidad de 1/t. Por lo tanto, su probabilidad final es k/i × i/n = k/n.

Paso 5: Demostrar la probabilidad del elemento antiguo.

Suponga que cada elemento antiguo tiene una probabilidad de k/(i-1) después del elemento i-1. En el paso i, se reemplaza con una probabilidad de k/i × 1/k = 1/i, por lo que sobrevive con 1 - 1/i. Su nueva probabilidad es k/(i-1) × (i-1)/i = k/i. Los elementos nuevos y antiguos satisfacen el mismo invariante.

Paso 6: Analizar la complejidad y la generación aleatoria.

Cada elemento se procesa una vez: tiempo O(n). El reservorio contiene k elementos: espacio adicional O(k). Para conteos que superen la precisión segura de enteros, use una API de enteros no sesgados que admita el rango requerido.

Paso 7: Manejar los límites de entrada.

Un flujo vacío devuelve una muestra vacía. k = 0 devuelve una muestra vacía o genera el error documentado. Si llegan menos de k elementos, devuelva los elementos reales o falle según el contrato. La deduplicación por valor requiere un estado adicional y puede violar O(k).

Paso 8: Explicar las extensiones ponderadas y distribuidas.

El muestreo ponderado cambia la distribución objetivo, por lo que el reemplazo con igual probabilidad no es válido; analice claves de reservorio ponderado como Efraimidis–Spirakis. Los reservorios distribuidos necesitan conteos y prioridades/pesos para fusionarse correctamente; concatenar muestras de fragmentos genera sesgo.

Respuesta de muestra de alta calidad

"Mantengo un reservorio de capacidad k. Lo lleno con los primeros k elementos. Desde el elemento i = k+1 en adelante, genero un entero no sesgado j en [0, i-1]; si j < k, reemplazo la posición j; de lo contrario, lo descarto. El nuevo elemento entra con una probabilidad de k/i. Un elemento antiguo específico se reemplaza con una probabilidad de 1/i, por lo que su probabilidad cambia de k/(i-1) a k/(i-1) × (1-1/i) = k/i. Por inducción, cada elemento tiene una probabilidad final de k/n. El algoritmo es de una sola pasada, tiempo O(n) y espacio O(k). Pruebo entradas vacías, k=1, k=0, registros repetidos, simulaciones repetidas y rederivo explícitamente el invariante para variantes ponderadas o distribuidas."

Errores comunes

• Almacenar todo el flujo primero → viola las restricciones de tamaño desconocido y memoria → actualice el reservorio en línea.
• Usar 1/k para cada nuevo elemento → las probabilidades no se adaptan a i → use k/i.
• Usar random() % i → el módulo puede estar sesgado → use un muestreo de enteros no sesgado.
• Elegir posiciones de reemplazo de forma no uniforme → algunas combinaciones se vuelven más probables → seleccione entre k posiciones de forma uniforme.
• Usar k/n durante el escaneo → n es desconocido y la probabilidad cambia en cada paso → use el conteo actual i.
• Ignorar la semántica de duplicados → los registros distintos y los valores distintos difieren → aclare primero la deduplicación.
• Concatenar reservorios de fragmentos → los tamaños de fragmentos desiguales sesgan el resultado → fusione con conteos y prioridades.
• Reutilizar el algoritmo uniforme para pesos → la distribución objetivo cambió → use muestreo de reservorio ponderado con una nueva demostración.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Por qué la probabilidad de reemplazo del nuevo elemento es k/i?

En el elemento i, el algoritmo elige una de i posiciones uniformemente. Las primeras k posiciones representan el reservorio, por lo que la probabilidad de acertar en una es k/i.

Pregunta de seguimiento 2: ¿Cómo demuestra la equidad para k=1?

El primer elemento se mantiene con probabilidad uno. El elemento i lo reemplaza con 1/i; cualquier elemento antiguo sobrevive con (1/(i-1)) × (1-1/i) = 1/i, lo que da lugar a la inducción.

Pregunta de seguimiento 3: ¿Cómo genera un entero no sesgado?

Use una API de enteros uniformes o muestreo por rechazo que descarte valores aleatorios fuera del rango divisible más grande. No asuma que el módulo simple siempre está libre de sesgo.

Pregunta de seguimiento 4: ¿Qué pasa si el flujo termina antes de k elementos?

Devuelva los elementos reales o genere el error documentado. Nunca invente entradas; defina el comportamiento antes de programar.

Pregunta de seguimiento 5: ¿Cómo realizaría el muestreo con pesos?

Defina la distribución objetivo ponderada y luego use claves aleatorias de reservorio ponderado o transformaciones exponenciales/logarítmicas. La demostración uniforme de k/i ya no se aplica directamente.

Pregunta de seguimiento 6: ¿Cómo fusionaría reservorios distribuidos?

Cada fragmento lleva su conteo de elementos y suficiente información de prioridad aleatoria o peso. Fusione según la regla de muestreo global; la concatenación directa o el truncamiento aleatorio favorecen a los fragmentos más pequeños.

Pregunta de seguimiento 7: ¿Cómo valida la uniformidad?

Ejecute muchas pruebas en un flujo corto fijo, compare la frecuencia de inclusión de cada elemento con k/n y pruebe casos límite y semillas reproducibles. Las estadísticas pueden revelar sesgos, pero no reemplazan la demostración de probabilidad.