Entrevista de código: ¿Cómo se implementa una mezcla uniforme de un arreglo in-place?

Problema y contexto

Implemente reset() para restaurar el orden original y shuffle() para devolver una permutación aleatoria uniforme. La pregunta evalúa algoritmos aleatorizados, intercambios in-place, límites de números aleatorios y capacidad de prueba; el mismo patrón aparece en muestreo, sorteos y fixtures de prueba.

Qué evalúa el entrevistador

• Elegir Fisher–Yates en lugar de intercambiar repetidamente posiciones aleatorias arbitrarias.
• Muestrear el índice i únicamente de la porción que no ha sido fijada.
• Distinguir entre APIs aleatorias inclusivas y semiabiertas para evitar sesgos o desbordamientos.
• Mantener una línea base inmutable para que reset() no se vea afectado por las mezclas.
• Explicar el tiempo O(n), el espacio adicional O(1) y la uniformidad.
• Discutir PRNGs con semilla, arreglos vacíos, valores duplicados y límites de pruebas estadísticas.

Preguntas aclaratorias para hacer

• ¿Debe shuffle() devolver un nuevo arreglo o mutar y devolver el arreglo de trabajo?
• ¿Debe reset() devolver una copia defensiva para que quienes llaman no puedan mutar el estado interno?
• ¿La fuente aleatoria es inyectable o se requiere una fuente criptográficamente segura?
• ¿Se permiten valores duplicados y los valores iguales en diferentes posiciones son permutaciones distintas?
• ¿Necesitamos seguridad para hilos (thread safety), semillas reproducibles o imprevisibilidad criptográfica?
• ¿La entrada requiere streaming o espacio auxiliar constante?

Marco de respuesta de 30 segundos

“Mantengo una instantánea original y un arreglo de trabajo. Para i desde el último índice hacia abajo hasta uno, tomo una muestra uniforme de j en [0, i] e intercambio a[i] con a[j]. Cada pasada fija una posición, por lo que el tiempo de ejecución es O(n) y el espacio auxiliar es O(1). reset() devuelve una copia de la instantánea; la fuente aleatoria se puede inyectar para reproducibilidad y pruebas estadísticas.”

Análisis paso a paso a fondo

Paso 1: Aislar el estado. Copie la entrada en original y working; reset() copia original nuevamente para que las referencias externas no puedan cambiar la línea base.

Paso 2: Definir el límite aleatorio. Deje que i disminuya de n - 1 a 1. Con una API semiabierta llame a randomInt(i + 1) para obtener 0..i; con una API inclusiva pase 0 y i explícitamente.

Paso 3: Intercambiar in-place. Intercambie working[i] y working[j]; la posición i ahora está fijada y no se crea un arreglo temporal del mismo tamaño.

Paso 4: Explicar la uniformidad. La primera posición fijada tiene n opciones igualmente probables, la siguiente tiene n-1, y así sucesivamente, produciendo n! rutas de elección igualmente probables. La fuente aleatoria debe ser uniforme sobre cada índice candidato.

Paso 5: Manejar duplicados. El algoritmo es uniforme sobre las posiciones de los elementos. Los valores repetidos pueden hacer que varias permutaciones de posiciones se muestren como la misma secuencia de valores; las secuencias visibles no son lo mismo que las permutaciones de posiciones.

Paso 6: Implementar reset. Devuelva una copia de original y reconstruya working; exponer el arreglo interno permitiría que quienes llaman creen alias y corrompan la línea base.

Paso 7: Verificar y declarar la complejidad. Utilice una semilla fija para la reproducibilidad, enumere las frecuencias de arreglos pequeños para una uniformidad aproximada y pruebe arreglos vacíos y de un solo elemento. Cada mezcla toma tiempo O(n) y espacio auxiliar O(1); la instantánea almacenada en sí utiliza un estado de O(n).

Respuesta modelo

“Mantengo los arreglos original y working. shuffle itera i = n-1..1, extrae un j ∈ [0,i] uniforme e intercambia las dos entradas; reset devuelve una copia de original y reconstruye working. Intercambiar repetidamente posiciones aleatorias arbitrarias puede reescribir posiciones anteriores y produce permutaciones sesgadas. Fisher–Yates muestrea solo el prefijo no fijado, por lo que cada permutación posicional es igualmente probable. Se ejecuta en tiempo O(n) y no necesita ningún arreglo adicional más allá de la instantánea de estado. Yo inyectaría la fuente aleatoria para pruebas con semilla y la reemplazaría con un CSPRNG cuando el resultado afecte la seguridad o la equidad.”

Errores comunes

• Muestrear [0,n-1] en cada ronda → las posiciones fijadas se modifican de nuevo → use [0,i].
• Calcular floor(random * i) → el índice i nunca se selecciona → use i + 1 como el límite semiabierto.
• Intercambiar pares aleatorios arbitrarios n veces → no se garantiza que las permutaciones sean uniformes → fije una posición por paso de Fisher–Yates.
• Devolver la misma referencia interna desde reset → quienes llaman pueden corromper la línea base → devuelva una copia defensiva.
• Tratar un PRNG como aleatoriedad segura → los resultados del sorteo pueden ser predecibles → elija un CSPRNG para el modelo de amenazas.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Por qué el bucle puede ejecutarse hacia adelante en su lugar?

La forma hacia adelante fija i muestreando de [i,n-1]; la demostración es simétrica. El invariante es que cada elección proviene únicamente de la región no fijada.

Pregunta de seguimiento 2: ¿Cómo se demuestra la uniformidad?

La posición n-1 tiene n opciones igualmente probables, la posición n-2 tiene n-1, y así sucesivamente. Por lo tanto, cada ruta de elección completa tiene una probabilidad de 1/n!.

Pregunta de seguimiento 3: ¿Cómo se prueba la aleatoriedad?

Ejecute muchas pruebas en un arreglo pequeño, compare las frecuencias de permutación con una tolerancia y use una semilla fija para verificar la reproducibilidad. Una muestra finita es evidencia, no una demostración.

Pregunta de seguimiento 4: ¿Cuándo es insuficiente la pseudoaleatoriedad ordinaria?

Utilice un CSPRNG del sistema cuando un sorteo, token o mezcla afecte la seguridad o los derechos de acceso. Los PRNGs con semilla son apropiados para simulaciones, juegos y pruebas.

Pregunta de seguimiento 5: ¿Qué pasa si la entrada es una lista enlazada?

Convertirla a un arreglo cuesta O(n) de espacio. Los intercambios de nodos pueden preservar el almacenamiento, pero el acceso aleatorio se vuelve costoso, por lo que las restricciones deben renegociarse.

Pregunta de seguimiento 6: ¿Cómo se manejan las llamadas concurrentes?

Otorgue a cada instancia un estado aislado y bloquee las mutaciones, o devuelva instantáneas inmutables. Un llamador no debe observar un intercambio parcial mientras otro hilo realiza un reinicio.

Pregunta de seguimiento 7: ¿La biblioteca estándar de Java utiliza esta idea?

Oracle documenta un recorrido hacia atrás que intercambia un elemento aleatorio en la posición actual; con una fuente justa, todas las permutaciones ocurren con igual probabilidad.