Planteamiento y alcance
Implementa un conjunto de intervalos con add([l,r)), remove([l,r)), contains(x) y overlaps([l,r)). Los intervalos adyacentes o superpuestos deben fusionarse automáticamente, mientras que la eliminación puede dividir un intervalo. Explica los límites abiertos y cerrados, los rangos vacíos y la complejidad.
Esto evalúa colecciones ordenadas, invariantes y el manejo de casos límite. La documentación de bisect de Python señala que la bisección encuentra un punto de inserción, mientras que la inserción en una lista aún puede ser O(n). Especifica la suposición sobre el tamaño de los datos y si se necesita un árbol en lugar de afirmar que cada operación es O(log n).
Qué está evaluando el entrevistador
Primero, ¿puedes definir la semántica semiabierta y manejar la adyacencia? Segundo, ¿pueden la inserción y la eliminación examinar solo los vecinos potencialmente intersecantes en lugar de cada intervalo? Tercero, ¿puedes elegir un arreglo, un árbol balanceado o un árbol de intervalos según la escala y demostrar el invariante?
Preguntas para aclarar antes de responder
- ¿Son los intervalos cerrados, abiertos o semiabiertos? Asume
[l,r), de modo que[0,1)y[1,2)no se intersecan. - ¿Son los puntos finales números de punto flotante? Asume enteros comparables; define reglas de precisión y NaN en caso contrario.
- ¿Deben fusionarse los intervalos adyacentes? Asume que sí, para mantener una representación normalizada.
- ¿Cuáles son la escala y la proporción de lectura/escritura? Los conjuntos pequeños pueden usar un arreglo ordenado; los conjuntos grandes pueden requerir un árbol balanceado o un árbol de intervalos.
- ¿Qué sucede al eliminar un rango que no existe? Asume que es idempotente y conserva solo la porción que existe.
Un marco de respuesta de 30 segundos
“Usaría intervalos semiabiertos y los mantendría ordenados, disjuntos y no adyacentes. add utiliza búsqueda binaria para encontrar la primera intersección posible y luego recorre hacia la derecha para fusionar entradas superpuestas o adyacentes. remove examina las intersecciones y preserva los remanentes izquierdo y derecho no vacíos. contains verifica el intervalo predecesor; overlaps comprueba el primer intervalo cuyo final supera el inicio de la consulta. Un arreglo tiene una búsqueda O(log n) pero desplazamientos O(n); para conjuntos más grandes, usaría un árbol balanceado o un árbol de intervalos.”
Análisis detallado paso a paso
Paso 1: Definir el invariante normalizado
Almacena intervalos semiabiertos ordenados, disjuntos y no adyacentes [l,r) con l < r; los intervalos vacíos nunca se ingresan. Tras la normalización, un punto pertenece a lo sumo a un intervalo, por lo que las actualizaciones pueden enfocarse en los vecinos locales.
Paso 2: Elegir el almacenamiento
Para unos pocos miles de intervalos y pocas escrituras, un arreglo ordenado es simple y confiable; la búsqueda binaria localiza una posición mientras que la inserción y la eliminación desplazan elementos. Para un alto volumen de escrituras y consultas, utiliza un árbol balanceado de claves ordenadas. Agrega un árbol de intervalos aumentado solo cuando se requieran conteos de cobertura o la profundidad máxima de superposición.
Paso 3: Localizar los vecinos de inserción
Usa bisect_left para encontrar el primer inicio no menor que l, luego inspecciona un predecesor porque puede extenderse a través de l. Recorre hacia la derecha mientras el siguiente inicio sea a lo sumo el final fusionado actual; los intervalos adyacentes se incluyen en la fusión.
add(l, r):
i = first index with start >= l, then i = max(0, i - 1)
while i < len(intervals) and intervals[i].end >= l:
l = min(l, intervals[i].start)
r = max(r, intervals[i].end)
delete intervals[i]
insert [l, r) at iPaso 4: Implementar la eliminación y división
Encuentra el primer intervalo que pueda intersecar [l,r) y procesa hasta que el siguiente inicio sea al menos r. Para cada intervalo, conserva las porciones no vacías de [start,l) y [r,end). Como la entrada está normalizada, la eliminación no crea rangos adyacentes que necesiten otra fusión.
Paso 5: Implementar consultas de punto y de rango
Para contains(x), encuentra el último intervalo con start <= x y verifica x < end. Para overlaps([l,r)), encuentra el primer intervalo con end > l; se superpone si start < r. Un rango de consulta vacío devuelve false. Cada comparación sigue la semántica semiabierta.
Paso 6: Demostrar la corrección
El bucle de inserción elimina únicamente los rangos que se superponen o tocan el nuevo rango y reemplaza su unión con un solo intervalo, por lo que la cobertura se preserva. La eliminación suprime únicamente la intersección y conserva las dos diferencias. El ordenamiento y la no adyacencia se restauran después de cada operación, y cada consulta requiere solo un candidato predecesor o sucesor.
Paso 7: Analizar la complejidad
La localización en un arreglo es O(log n), pero desplazar y eliminar entradas fusionadas puede ser O(n), donde n es el número de intervalos. Recorrer k intervalos vecinos añade O(k). Un árbol balanceado puede proporcionar actualizaciones locales en O(log n + k) a cambio de un mayor costo de implementación y memoria. No confundas el costo de la búsqueda binaria con el costo de la operación completa.
Paso 8: Diseñar pruebas de casos límite
Prueba un conjunto vacío, rango vacío, fusión adyacente, contención total, superposición parcial, abarcar varios intervalos, eliminación en el medio, eliminación en extremos, números negativos, operaciones repetidas y un rango de consulta grande. Realiza pruebas diferenciales de operaciones aleatorias contra un modelo de arreglo booleano punto por punto.
Compensaciones y límites
Compensación 1: Intervalos semiabiertos o cerrados
Los rangos semiabiertos se componen de forma natural, tienen una longitud r-l y se adaptan a casos de uso de tiempo e índices de arreglos. Una lógica de negocio con intervalos cerrados debe modificar de forma consistente las reglas de adyacencia, longitud y desbordamiento de enteros; cambiar únicamente los operadores de comparación no es seguro.
Compensación 2: Arreglo o árbol balanceado
Los arreglos son compactos y amigables con la memoria caché para conjuntos pequeños o medianos con muchas lecturas. Los árboles manejan muchas inserciones y eliminaciones, pero requieren claves ordenadas y reglas de invalidación de iteradores. Elige según el n real, la proporción de escrituras y el presupuesto de latencia.
Compensación 3: Fusionar rangos adyacentes o preservar la procedencia
La fusión reduce los elementos y simplifica las consultas. Si los intervalos representan permisos, reservas o períodos contables cuyos límites originales importan, conserva los metadatos de origen o utiliza una representación que no descarte segmentos.
Simulacros de fallas y plan de evolución
Simulacro 1: Muchas inserciones adyacentes
Inserta 10,000 intervalos adyacentes en orden inverso. Verifica que quede un único intervalo normalizado sin ningún extremo faltante, luego mide los desplazamientos en el arreglo para decidir si se necesita un árbol.
Simulacro 2: Inserción y eliminación aleatorias
Genera operaciones aleatorias de add, remove, contains y overlaps y compáralas con un modelo punto por punto. Comprueba especialmente que eliminar el medio de un intervalo y luego insertarlo fusione correctamente ambos lados.
Simulacro 3: Límites y entradas inválidas
Prueba l == r, l > r, enteros muy grandes y NaN. Define si los rangos vacíos retornan, si los rangos invertidos generan un error o se intercambian, y si se rechazan las entradas de punto flotante.
Errores comunes y preguntas de seguimiento
Error 1: Confundir adyacente con superpuesto
Los rangos semiabiertos [0,1) y [1,2) no se intersecan, aunque un conjunto normalizado aún puede fusionarlos. Define las condiciones de intersección y de fusión por separado.
Error 2: Comprobar solo el vecino derecho
El predecesor puede cruzar el nuevo extremo izquierdo. Inspecciona un predecesor después de la búsqueda binaria.
Error 3: Dejar intervalos vacíos tras la eliminación
Filtra cada diferencia con start >= end, o contains puede reportar una coincidencia fantasma.
Error 4: Afirmar que bisect hace que la inserción sea O(log n)
Python señala explícitamente que los desplazamientos por inserción en una lista son O(n). Especifica los costos de búsqueda, desplazamiento y recorrido por separado.
Error 5: Ignorar los límites de punto flotante
NaN no sigue el ordenamiento normal y la igualdad aproximada hace que la adyacencia sea inestable. Define la normalización de precisión antes de permitir números flotantes.
Error 6: Perder la procedencia
Si los intervalos representan permisos, reservas o períodos contables, una unión puede perder el significado de origen. Conserva los metadatos o no fusiones dichos segmentos.