Entrevista técnica: Implementar un módulo de rangos mutable

Planteamiento y alcance

Implementa tres operaciones sobre intervalos semiabiertos [left, right): agregar cobertura, comprobar si una consulta está totalmente cubierta y eliminar cobertura. Asume 1 <= left < right <= 10^9 y hasta 10^4 llamadas, coincidiendo con el problema público de Range Module. Especifica qué sucede cuando left >= right si tu API acepta entradas de manera defensiva.

Qué está evaluando el entrevistador

La prueba principal es si puedes elegir y preservar un invariante de estructura de datos mientras se insertan, eliminan y consultan intervalos. La representación esperada es una colección canónica ordenada de intervalos disjuntos; LeetCode lista un conjunto ordenado y un árbol de segmentos (segment tree) como enfoques relevantes. Magicsheet etiqueta el problema como difícil y lo categoriza con conjuntos ordenados y árboles de segmentos. La pregunta también evalúa la disciplina con límites semiabiertos, la seguridad de los iteradores y el cálculo de la complejidad.

Preguntas de clarificación para hacer

1. ¿Los extremos son inclusivos? Esta respuesta utiliza [left, right).
2. ¿Deben fusionarse los rangos adyacentes que se tocan, como [1,3) y [3,5)? Esta respuesta los fusiona en un único intervalo canónico.
3. ¿Se conocen todos los extremos antes de la ejecución? El diseño base es online, por lo que no se conocen.
4. ¿Qué debe hacer una entrada inválida con left >= right? Retornar sin cambiar el estado o rechazarla explícitamente.
5. ¿El dominio es lo suficientemente acotado y estático como para justificar un árbol de segmentos? Eso afecta el diseño alternativo.

Solución paso a paso

1. Elegir la representación y el invariante

Utiliza un mapa ordenado del inicio al final del intervalo. std::map mantiene las claves ordenadas y garantiza búsqueda, inserción y eliminación logarítmicas; la iteración ascendente permite que el algoritmo recorra únicamente los intervalos cercanos. Normaliza la cobertura adyacente, de modo que después de cada operación el mapa no contenga ningún par con previousEnd >= nextStart.

2. Agregar cobertura

Comienza en el primer intervalo cuyo final sea al menos left (o el primer intervalo después del predecesor). Mientras el inicio actual sea a lo sumo el right en crecimiento, expande left y right para incluir dicho intervalo y luego márcalo para ser borrado. Borra el rango contiguo marcado e inserta el intervalo fusionado. El estado vacío y un rango disjunto de ambos vecinos no necesitan ninguna estructura especial.

3. Eliminar cobertura y consultar cobertura

Para la eliminación, visita los intervalos con start < right y end > left. Para cada superposición, conserva [oldStart,left) cuando oldStart < left, y conserva [right,oldEnd) cuando right < oldEnd; borra el original antes de insertar los fragmentos. Para una consulta, inspecciona el intervalo cuyo inicio sea el mayor inicio que no supere a left; retorna true únicamente si existe y su final es al menos right. Con extremos semiabiertos, [1,3) no cubre a [3,4).

Corrección y complejidad

El invariante demuestra la corrección por inducción. La adición reemplaza cada intervalo conectado al nuevo rango por su unión, de modo que no se pierde ningún punto cubierto y el resultado es canónico. La eliminación reemplaza cada superposición exactamente por las partes que quedan fuera del rango eliminado. Consultar el predecesor es suficiente porque los intervalos disjuntos y ordenados garantizan que cualquier intervalo anterior termine no más tarde, y cualquier intervalo posterior con inicio mayor a left no pueda contener a left.

Sea n el número de intervalos almacenados y k el número de intervalos afectados por una actualización. Una consulta es O(log n). Una actualización realiza O(log n) búsquedas más O(k) de recorrido y borrado de iteradores; las implementaciones que vuelven a buscar cada clave pueden ser en cambio O(k log n). El espacio es O(n). Un árbol de segmentos es razonable para un universo de coordenadas acotado y conocido, mientras que la compresión de coordenadas requiere todos los extremos de forma offline y no es adecuada para llamadas online arbitrarias.

Respuesta modelo

“Implementaría un mapa ordenado normalizado de intervalos semiabiertos, ordenados y disjuntos. Add localiza y fusiona todos los intervalos que se superponen o se tocan, remove elimina las superposiciones y conserva a lo sumo dos fragmentos en los límites, y query comprueba el predecesor del inicio solicitado. La obligación clave de demostración es que cada operación preserva la unión canónica. Query cuesta O(log n); una actualización cuesta O(log n + k) al borrar un rango contiguo de iteradores y utiliza O(n) de espacio. Compararía este mapa online con un árbol de segmentos solo después de confirmar el dominio de coordenadas y si se conocen todos los extremos”.

Errores comunes

• Tratar los extremos como cerrados → los rangos adyacentes parecen superponerse incorrectamente → define primero [left,right).
• Dejar intervalos adyacentes separados → las consultas y actualizaciones posteriores encuentran duplicados evitables → normaliza la adyacencia.
• Eliminar mientras se incrementa un iterador invalidado → omite nodos o accede a almacenamiento liberado → guarda el siguiente iterador o borra un rango conocido.
• Dividir sin preservar ambos lados → la cobertura desaparece en un límite → prueba la eliminación en el medio y la contención total.
• Afirmar que cada actualización es O(log n) → una operación puede afectar a muchos intervalos → incluye k en la cota.
• Usar compresión de coordenadas de forma online → los extremos no vistos invalidan los índices → usa una estructura ordenada o reconstruye desde un conjunto offline completo.

Preguntas de seguimiento y extensiones

¿Qué casos límite deben probarse?

Prueba un módulo vacío, adiciones repetidas, una consulta exactamente en un extremo, adiciones adyacentes [1,3) y luego [3,5), eliminación de una sección intermedia, eliminación que cubra un intervalo completo, eliminación sin superposición, rangos anidados y extremos 0 y 10^9 cuando la API los permita.

¿Cómo probarías el invariante?

Después de cada operación aleatoria, verifica mediante aserciones que los inicios estén ordenados, end > start y previousEnd < nextStart. Compara los resultados de las consultas con un arreglo booleano pequeño o un modelo de unión por fuerza bruta sobre un dominio de coordenadas diminuto. Esto detecta errores de tipo off-by-one y pérdida de fragmentos.

¿Cuándo resultaría superior un árbol de segmentos?

Elige un árbol de segmentos cuando el universo de coordenadas esté acotado o sea comprimible y la agregación de rangos o la propagación perezosa (lazy propagation) sean importantes. Proporciona operaciones logarítmicas predecibles, pero añade complejidad de nodos y de estado perezoso; el mapa ordenado es más simple para intervalos dispersos y online.