Entrevista de código: ¿Cómo usarías una wavelet matrix para consultas de k-ésimo elemento en un rango?

Prompt y alcance

Dado un arreglo estático de enteros a, responde muchas consultas de rangos semiabiertos [l, r): devuelve el k-ésimo valor más pequeño, la frecuencia de x y el número de elementos en [lo, hi). El arreglo nunca cambia y los valores pueden ser grandes. Diseña y analiza una estructura más rápida que ordenar cada rango.

Una wavelet matrix particiona valores de forma estable por bits, desde el más significativo hasta el menos significativo, almacenando un bitvector y conteos de unos en prefijos en cada nivel. No necesita punteros de árbol explícitos; cada consulta mapea su intervalo al siguiente nivel. Especifica que k es basado en cero, maneja la compresión de coordenadas y duplicados, y proporciona los límites.

Qué evalúa el entrevistador

• Explicar por qué la partición estable, el inicio del bloque de ceros y el mapeo de rank preservan el orden.
• Seleccionar el k-ésimo valor sobre [l, r) y acumular bits correctamente.
• Manejar duplicados, rangos vacíos, k fuera de rango y valores con signo.
• Distinguir las rutas para conteos en el dominio de valores, frecuencia puntual y consultas de k-ésimo.
• Dar límites de O(B) para consulta, O(nB) para construcción y espacio compresible.
• Reconocer que la estructura estática no ofrece actualizaciones económicas y conocer alternativas.

Preguntas para clarificar

1. ¿Es r exclusivo, y es k basado en cero o en uno?
2. ¿Es el arreglo verdaderamente inmutable? Si no, ¿cuáles son las tasas de actualización y consulta?
3. ¿Tienen signo los valores y cuál es su ancho máximo? ¿Podemos aplicar compresión de coordenadas?
4. ¿Qué memoria hay disponible para rank, y se pueden agrupar en bloques o comprimir los bitvectors?
5. ¿Necesitamos solo k-ésimo, o también frecuencia, predecesor o suma en rango? Las operaciones influyen en la elección.

Respuesta de 30 segundos

Aplicaría compresión de coordenadas a los valores para obtener códigos no negativos con un ancho de bits B. Durante la construcción, particiono de forma estable la secuencia actual desde el bit más alto hacia abajo, almacenando el bitvector de cada nivel y los conteos prefijos de rank-one. Para el k-ésimo, mantengo [l,r), cuento los ceros en el nivel y mapeo al bloque de ceros o resto los ceros y mapeo al bloque de unos mientras establezco ese bit de la respuesta. La frecuencia usa dos recorridos de rank; un conteo en el dominio de valores es la diferencia de dos llamadas a countLess. Las consultas cuestan O(B) y la construcción cuesta O(nB).

Solución paso a paso

1. Codificar el dominio de valores

Para enteros con signo arbitrarios, ordena los valores distintos y mapéalos a 0..m-1, conservando un arreglo de código a valor. Luego B es ceil(log2(m)), con un caso explícito para m=1. Si el orden natural debe preservarse directamente, invierte el bit de signo antes de tratar los valores con signo como sin signo.

2. Construir un nivel estable

Inspecciona cur en bit, añade todos los valores con bit cero a next, luego todos los valores con bit uno, preservando el orden dentro de ambos grupos. bv[i] registra el bit en la posición original i, y zeroCount es la cantidad de ceros. La estabilidad mantiene los intervalos posteriores vinculados a los mismos elementos originales.

rank1(i) = number of ones in bv[0..i)
zeroCount = n - rank1(n)
for interval [l, r):
  zero interval = [l - rank1(l), r - rank1(r))
  one interval  = [zeroCount + rank1(l), zeroCount + rank1(r))

3. Consultar el k-ésimo valor en el rango

En cada nivel calcula zeros = (r-l) - (rank1(r)-rank1(l)). Cuando k es menor que la cantidad de ceros, mapea al intervalo de ceros. De lo contrario, resta los ceros, mapea al intervalo de unos y establece el bit de respuesta actual. Después de B niveles, decodifica el código a su valor original.

4. Consultar la frecuencia de un valor

Trata cada bit objetivo como una rama fija y mapea [l,r) de la misma manera. Un objetivo con cero sigue el intervalo de ceros; un objetivo con uno sigue el intervalo de unos usando zeroCount. Después de B niveles, la longitud del intervalo es la frecuencia. Un objetivo ausente en el diccionario comprimido devuelve cero.

5. Consultar un rango de valores

Define countLess(x, l, r) como el número de valores menores que x en [l,r). En un nivel donde x tiene el bit uno, cada rama de ceros es menor, por lo que se suma zeros y se continúa en la rama de unos. Para un bit cero, continúa únicamente en la rama de ceros. El conteo en [lo, hi) es countLess(hi)-countLess(lo).

6. Límites y verificación

Define el comportamiento para un rango vacío o cuando el extremo izquierdo no es menor que el derecho; nunca indexes arreglos de rank fuera de sus límites. Exige que k caiga dentro de la longitud del rango actual. Prueba casos con todos los elementos iguales, ordenados, duplicados intercalados, valores negativos, rangos de un solo elemento, ancho máximo de bits y valores ausentes en el diccionario, comparando cada resultado con una ordenación o conteo por fuerza bruta.

7. Complejidad y compensaciones

Con conteos de prefijos ordinarios, cada nivel almacena O(n) contadores, por lo que el espacio y la construcción son O(nB) y cada operación es O(B). Un bitvector comprimido con soporte de rank reduce el espacio y las constantes. La estructura se adapta a cargas de trabajo inmutables y con muchas consultas. Para actualizaciones, considera reconstrucciones por bloques, bitvectors dinámicos, un segment tree de conjuntos ordenados o procesamiento offline y reevalúa los costos de memoria y actualización.

Ejemplo de respuesta sólida

Comenzaría indicando que los rangos son semiabiertos, k está basado en cero y el arreglo es inmutable. Aplicaría compresión de coordenadas a los valores y usaría B bits. La construcción particiona de forma estable desde el bit más alto hacia abajo, reteniendo conteos prefijos de rank-one y longitudes de bloques de ceros en cada nivel.

Para el k-ésimo, cada nivel cuenta los ceros en el intervalo actual. Si k pertenece a los ceros, se mapea con l-rank1(l) y r-rank1(r); de lo contrario, se restan los ceros, se mapea con zeroCount+rank1(l) y zeroCount+rank1(r), y se establece el bit de respuesta. La frecuencia sigue una ruta de valor fija, mientras que el conteo en el dominio de valores son dos llamadas a countLess. La construcción es O(nB) y cada consulta O(B), con errores explícitos o cero para rangos inválidos y códigos ausentes.

Errores comunes

• Mezclar rangos cerrados y semiabiertos → rank se desplaza en uno → usa [l,r) de forma consistente y escribe el mapeo.
• Olvidar la partición estable → los intervalos posteriores ya no identifican a los mismos elementos → preserva el orden en ambos bloques.
• Entrar al bloque de unos sin restar los ceros → los k-ésimos valores son demasiado grandes → resta antes de mapear.
• Comparar valores con signo como bits sin signo → los negativos quedan mal ordenados → comprime o invierte el bit de signo.
• Asumir que las actualizaciones son económicas → las actualizaciones invalidan las permutaciones de los niveles → declara la precondición estática y las alternativas.
• Probar solo con valores distintos → los errores con duplicados y límites permanecen ocultos → prueba casos con elementos iguales, intercalados, vacíos e inválidos.

Preguntas de seguimiento y respuestas

¿Por qué no ordenar cada rango?

Ordenar un rango cuesta O((r-l) log(r-l)) y repite trabajo en cada consulta. La matriz precalcula información de bifurcación, por lo que una consulta solo visita B niveles y se adapta a cargas estáticas y con alto volumen de consultas.

¿Por qué rank1 mapea intervalos?

El rank de prefijo indica cuántos unos ocurren antes de cada extremo, lo que da las posiciones relativas del intervalo en los bloques de ceros y unos. La partición estable asegura que esas posiciones representen a los mismos elementos.

¿Cómo respondes el k-ésimo mayor?

Conviértelo al k-ésimo menor con length - 1 - k, o prefiere la rama de unos en cada nivel mientras restas su conteo. Ambos siguen siendo O(B).

¿Qué pasa si el dominio de valores es mucho mayor que n?

Aplica compresión de coordenadas a los valores observados y retén el mapa inverso. Para un valor de consulta no visto, haz una búsqueda binaria de su límite de inserción o devuelve frecuencia cero.

¿Qué pasa si se requieren actualizaciones?

Una wavelet matrix básica no es amigable con las actualizaciones. Utiliza reconstrucción por bloques, bitvectors dinámicos, un segment tree de estructuras ordenadas o procesamiento offline según las proporciones de actualización/consulta, los objetivos de latencia y la memoria.