Entrevista técnica: ¿Cómo implementar un Sparse Set con operaciones O(1)?

Problema y alcance

Dado un universo de enteros acotado [0, U), implemente un conjunto con insert(x), remove(x), contains(x), clear() e iteración sobre los miembros actuales. Las cuatro primeras operaciones deben ser O(1) en el peor de los casos; la iteración toma O(k) para k miembros actuales. Los duplicados se rechazan y eliminar un valor inexistente no realiza ninguna operación (no-op).

Los registros públicos de entrevistas incluyen esta forma de pregunta en una discusión de Pure Storage. La prueba central es el invariante de los arreglos denso/disperso, no memorizar una clase de biblioteca.

Qué está evaluando el entrevistador

• Si usted declara que se requiere un universo fijo; la afirmación de O(1) no se extiende gratuitamente a enteros arbitrarios.
• Si mantiene dense[sparse[x]] == x y lo utiliza para evitar falsos positivos por índices desactualizados.
• Si la eliminación intercambia con el último elemento, manteniendo el prefijo denso contiguo y la iteración en O(k).
• Si declara un espacio de O(U) y reconoce cuándo un conjunto hash o un mapa de bits es más apropiado.

Aclaraciones previas a la codificación

1. ¿Se conoce U y puede la solución asignar dos arreglos de longitud U? Esta es la precondición de recursos.
2. ¿Debe estar ordenado iterate()? Este diseño devuelve todos los miembros pero no promete ningún orden.
3. ¿Se requieren iteradores estables o acceso concurrente? Esos requisitos cambian la semántica de swap-delete y de sincronización.
4. ¿Debe clear() evitar escanear U? La consigna requiere tiempo constante, por lo que solo restablece size.

Respuesta de 30 segundos

“Mantengo un arreglo de índices disperso (sparse) de longitud U, un arreglo denso (dense) de longitud U y el size actual. Un elemento x está presente exactamente cuando sparse[x] < size y dense[sparse[x]] == x. Insert escribe x en dense[size] y registra el índice; remove sobrescribe su posición con el último elemento y corrige el índice de dicho elemento; clear únicamente establece size en cero. Las cuatro operaciones principales son O(1) en el peor de los casos, la iteración sobre el prefijo denso es O(k) y el espacio es O(U)”.

Análisis paso a paso en profundidad

Paso 1: Declarar el invariante.

dense[0..size) contiene cada miembro exactamente una vez. Para un miembro x, sparse[x] es su posición en dense y dense[sparse[x]] == x. Un no miembro puede retener un valor disperso antiguo, por lo que contains no puede verificar únicamente si el índice está dentro del rango.

Paso 2: Búsqueda e inserción.

contains(x) verifica 0 <= x < U, luego valida sparse[x] < size y el enlace inverso. Insert llama primero a contains; si está ausente, escribe x en dense[size], establece sparse[x] = size e incrementa size.

Paso 3: Swap-delete (Eliminación por intercambio).

Si x está en la posición i, sea last = dense[size - 1]. Escriba last en dense[i], actualice sparse[last] = i y decremente size. No es necesario limpiar sparse[x]: después de que el tamaño cambia, la verificación del enlace inverso invalida la entrada desactualizada. La eliminación del último elemento sigue la misma lógica.

Paso 4: Clear en tiempo constante e iteración lineal.

clear() establece size = 0; el contenido antiguo del arreglo ya no se lee como miembros. La iteración escanea únicamente de dense[0] a dense[size - 1], por lo que cuesta O(k), no O(U).

Paso 5: Complejidad y límites.

contains, insert, remove y clear son O(1) en el peor de los casos; la iteración es O(k); el espacio es O(U). GCC documenta esta representación como útil para un universo fijo y una enumeración amigable con la memoria caché (cache-friendly). Si el universo es desconocido, debe crecer o es demasiado grande para la memoria, un conjunto hash o un mapa de bits pueden ajustarse mejor.

Paso 6: Probar el invariante.

Compare cada operación aleatoria con un Set de referencia. Cubra un conjunto vacío, inserción de duplicados, eliminación de un valor inexistente, eliminación de un elemento intermedio y del último, reutilización después de clear y los valores 0 y U-1. Después de cada operación, verifique que el prefijo denso no tenga duplicados y que el enlace inverso de cada miembro sea válido.

Respuesta de muestra de alta calidad

“El universo acotado [0, U) me permite intercambiar dos arreglos por operaciones deterministas en tiempo constante. Dense almacena un prefijo compacto de los miembros actuales, mientras que sparse mapea un valor de vuelta a su índice en dense. La pertenencia debe verificar los límites, el índice < size y el enlace inverso; verificar únicamente el número disperso es inseguro. Remove intercambia el último elemento y actualiza su índice disperso, mientras que clear solo restablece el tamaño. Las actualizaciones y búsquedas son O(1) en el peor de los casos, la iteración es O(k) y el espacio es O(U). Si el universo no estuviera controlado, elegiría en su lugar un conjunto hash o un mapa de bits”.

Errores comunes

• Verificar solo sparse[x] < size → un valor inexistente puede conservar un índice plausible → verifique también dense[sparse[x]] == x.
• Desplazar todos los elementos posteriores en la eliminación → la eliminación se convierte en O(U) o O(k) → intercambie con el último elemento.
• Llenar arreglos durante clear → clear se convierte en O(U) → restablezca solo el tamaño.
• Ignorar el universo acotado → acceso fuera de límites o memoria inaceptable → confirme primero [0, U) y la capacidad.
• Llamar a la iteración O(1) → obtener una vista es en tiempo constante, pero consumir todos los miembros es O(k) → separe los dos costos.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Cómo soportaría enteros arbitrarios?

Comprima las coordenadas de los valores en [0, U) primero. Si el dominio de valores sigue creciendo o no se puede escanear de antemano, un conjunto hash es más natural, pero su garantía de tiempo constante es amortizada o esperada en lugar de la garantía del peor de los casos requerida en esta consigna.

Pregunta de seguimiento 2: ¿Cómo preservaría el orden de iteración?

Swap-delete altera el orden en dense. Preservar el orden de inserción requiere una lista enlazada adicional o un arreglo estable, lo que cambia los costos de eliminación y de espacio. Confirme si el orden es parte del contrato de la interfaz antes de agregarlo.

Pregunta de seguimiento 3: ¿Cuándo elegiría un mapa de bits?

Elija un mapa de bits cuando la pertenencia sea la única operación, el universo sea moderado y un bit por valor sea importante. Elija un sparse set cuando la enumeración rápida también sea importante; la elección correcta depende de U, la cardinalidad y los patrones de acceso.