Prompt y contexto aplicable
El conjunto debe verificar la pertenencia, insertar, eliminar y devolver un elemento actual de manera uniformemente aleatoria. Un hash map proporciona búsqueda rápida mientras que un arreglo dinámico permite indexación aleatoria; eliminar un elemento intermedio es el conflicto.
Qué evalúa el entrevistador
- Combinar un hash map y un arreglo en lugar de forzar a una sola estructura a hacer todo.
- Mantener un mapa de valor a índice del arreglo y actualizarlo después de cada intercambio.
- Comprender el O(1) promedio y el crecimiento amortizado del arreglo.
- Definir la semántica de getRandom uniforme y de valores duplicados.
- Manejar conjuntos vacíos, eliminaciones inexistentes y límites de concurrencia.
Preguntas aclaratorias antes de responder
- ¿Los valores son únicos? Los duplicados requieren mapear un valor a un conjunto de índices.
- ¿getRandom debe ser uniforme o puede devolver cualquier miembro aleatorio? La prueba de aceptación cambia.
- ¿O(1) es promedio amortizado o el peor caso estricto? La política de colisiones de hash cambia la promesa.
- ¿La API devuelve valores o identificadores (handles)? Los objetos mutables necesitan reglas de igualdad y hashing.
- ¿Se requiere seguridad en hilos (thread safety), memoria fija o aleatoriedad reproducible?
Estructura de respuesta en 30 segundos
“Mantengo un arreglo items y un hash map indexOf. Insert agrega un nuevo valor al final y registra su índice; getRandom muestrea un índice uniforme del arreglo. Remove busca el índice objetivo, mueve el último elemento a esa posición, actualiza el índice del elemento movido, extrae el último elemento del arreglo (pop) y elimina el mapeo objetivo. Eso evita un desplazamiento O(n). Las operaciones de hash y el crecimiento del arreglo dinámico son en promedio O(1) amortizado; un conjunto vacío devuelve el error acordado, y los duplicados requieren un mapeo a un conjunto de índices.”
Análisis detallado paso a paso
Paso 1: Establecer el invariante. Para cada valor v, indexOf[v] apunta a su ubicación única en items; el arreglo no tiene huecos y cada índice está dentro del rango.
Paso 2: Implementar insert. Si el mapa ya contiene el valor, devuelve false según lo especificado. De lo contrario, agrégalo al final y almacena el nuevo índice en O(1) promedio.
Paso 3: Implementar remove. Lee el índice objetivo i y el último índice last. Si i !== last, escribe el último valor en items[i] y cambia su entrada en el mapa a i; luego extrae la última posición y elimina la entrada objetivo.
Paso 4: Implementar getRandom. Muestrea un índice uniforme de un arreglo no vacío. La documentación de choice de Python define la selección de secuencias con igual probabilidad; el orden de iteración de un hash no es una garantía de aleatoriedad.
Paso 5: Indicar la complejidad. La búsqueda en el hash, la inserción al final, el intercambio y el pop son O(1) promedio amortizado; el espacio del arreglo y del mapa es O(n). Las colisiones de hash en el peor caso o las pausas por redimensionamiento requieren una discusión de SLO por separado.
Paso 6: Manejar duplicados. Cambia indexOf[v] a un conjunto de índices. Al eliminar una instancia, remueve su índice y aplica el mismo intercambio con el final mientras actualizas ambos conjuntos de índices.
Paso 7: Verificar límites. Prueba un conjunto vacío, un solo elemento, eliminaciones repetidas, eliminar el elemento final, crecimiento repetido y una semilla fija. Ejecuta muchas llamadas a getRandom para verificar frecuencias, no solo la pertenencia.
Respuesta modelo
“Almaceno los valores actuales en un arreglo y el índice en el arreglo de cada valor en un hash map. Para eliminar un elemento intermedio, muevo el elemento final a su posición, actualizo el índice de ese elemento y extraigo el final, de modo que ningún elemento se desplace. getRandom lee un índice del arreglo seleccionado de forma uniforme, haciendo que cada valor único sea igualmente probable. La afirmación de O(1) es promedio amortizado para las operaciones de hash y el crecimiento del arreglo dinámico; si se permiten duplicados, reemplazo el índice único por un conjunto de índices y defino la eliminación como remover una instancia.”
Errores comunes
- Usar únicamente un hash map → getRandom escanea cada clave → agrega un arreglo compacto.
- Desplazar elementos tras la eliminación → delete se convierte en O(n) → intercambia con el extremo final.
- Olvidar el índice del valor movido → eliminaciones posteriores apuntan a la posición incorrecta → trata la actualización del mapa como parte del intercambio.
- Muestrear un iterador de hash → el orden de iteración no garantiza uniformidad → muestrea un índice del arreglo.
- Llamar al O(1) promedio como O(1) en el peor caso → se ignoran las colisiones y los costos de redimensionamiento → establece los supuestos de amortización.
Preguntas de seguimiento y respuestas
Pregunta de seguimiento 1: ¿Qué sucede al eliminar el último elemento del arreglo?
El índice objetivo es igual al índice final, por lo que se extrae y se elimina su entrada en el mapa sin necesidad de un intercambio.
Pregunta de seguimiento 2: ¿Cómo se admiten duplicados?
Mapea cada valor a un conjunto de índices. Después de mover el elemento final, elimina su índice anterior, agrega el nuevo índice y elimina un índice del conjunto objetivo.
Pregunta de seguimiento 3: ¿Cómo demuestras que getRandom es uniforme?
Cada instancia actual ocupa una posición en el arreglo, y el índice es uniforme sobre 0..n-1; por lo tanto, los valores únicos ocupan una posición igualmente probable cada uno.
Pregunta de seguimiento 4: ¿Pueden las colisiones de hash romper el O(1)?
La complejidad promedio depende del factor de carga y de la calidad del hash. Las garantías estrictas de peor caso requieren cubetas estructuradas en árboles (treeified buckets), hashing aleatorizado u otra estructura.
Pregunta de seguimiento 5: ¿Cómo manejas lecturas y eliminaciones concurrentes?
Protege las lecturas de índices aleatorios y los intercambios de eliminación con un solo bloqueo o una verificación de versión; de lo contrario, un lector puede observar un índice ya extraído.
Pregunta de seguimiento 6: ¿Cómo pruebas la distribución?
Ejecuta muchas pruebas en un conjunto fijo, cuenta cada valor, establece una tolerancia estadística y también verifica que cada valor devuelto siga presente.