Entrevista técnica de código: Implementar un árbol de intervalos para consultas de superposición

Planteamiento y casos de uso

Los árboles de intervalos se adaptan a rangos de tiempo dinámicos, reservas y ocupación de recursos. La idea central es un árbol balanceado ordenado por el punto final inferior, aumentado con el punto final superior máximo de cada subárbol para omitir ramas imposibles.

Qué evalúa el entrevistador

• Si los límites de los intervalos cerrados y la superposición son correctos.
• Si maxEnd se define y mantiene con precisión.
• Si la aumentación poda trabajo en lugar de escanear cada nodo.
• Si la inserción, la eliminación y las rotaciones actualizan la aumentación.
• Si se manejan los duplicados, un árbol vacío y las eliminaciones inexistentes.
• Si la complejidad toma en cuenta el número de intervalos reportados.

Aclaraciones antes de responder

• ¿Los intervalos son cerrados, abiertos o semiabiertos?
• ¿Los puntos finales son enteros, de punto flotante o marcas de tiempo?
• ¿Se permiten intervalos duplicados y la eliminación utiliza un ID o los puntos finales?
• ¿Una consulta debe devolver todas las superposiciones o solo una?
• ¿Se requieren inserción, eliminación y auto-balanceo en línea?
• ¿Los resultados deben ordenarse por el punto final inferior?

Estructura de respuesta en 30 segundos

“Clasificaría un árbol balanceado por el punto final inferior y almacenaría el punto final superior más el maxEnd máximo del subárbol. Una consulta reporta la superposición actual, entra al subárbol izquierdo solo cuando su maxEnd puede alcanzar el límite inferior de la consulta y entra al lado derecho solo mientras el punto final inferior actual esté dentro del límite superior de la consulta. La inserción y la eliminación utilizan operaciones de árbol balanceado y actualizan maxEnd a lo largo del camino, recalculando los nodos afectados después de las rotaciones.”

Análisis detallado paso a paso

Paso 1: Definir la superposición. Los [a,b] y [c,d] cerrados se superponen exactamente cuando a <= d y c <= b; rechace a > b primero.

Paso 2: Definir un nodo. Almacene low, high, un ID único, hijos y maxEnd; ordene por (low, id) para que los puntos finales iguales permanezcan diferenciados.

Paso 3: Podar consultas. Reporte el nodo actual cuando se superponga. Realice recursión a la izquierda solo cuando left.maxEnd >= query.low, y realice recursión a la derecha solo cuando el low <= query.high actual.

Paso 4: Mantener la aumentación. maxEnd es el máximo entre el high del nodo y los valores de ambos hijos. Recalcule solo los caminos afectados después de actualizaciones y rotaciones.

Paso 5: Eliminar de forma segura. Localice por ID, realice la eliminación de árbol balanceado y actualice maxEnd hacia arriba desde el camino de reemplazo; devuelva un resultado explícito para un ID no encontrado.

Paso 6: Probar casos límite. Cubra puntos finales que se tocan, contención, duplicados, negativos, intervalos de un solo punto, un árbol vacío y una salida que contenga todos los intervalos.

Paso 7: Establecer la complejidad. Un árbol balanceado tiene altura logarítmica; una consulta es O(log n + k) para k intervalos reportados, una actualización es O(log n) y el espacio es O(n).

Respuesta modelo de alta calidad

“Utilizaría un árbol red-black ordenado por (low, id), con cada nodo almacenando high y el maxEnd del subárbol. Para [q1,q2], reporte cuando low <= q2 y high >= q1; entre al hijo izquierdo solo cuando left.maxEnd >= q1, y al hijo derecho solo cuando el low <= q2 actual. La inserción y la eliminación actualizan los máximos en el camino, y las rotaciones recalculan los nodos rotados y el padre. Los IDs distinguen duplicados. Pruebo puntos finales cerrados y salidas donde todo coincide. La consulta es O(log n + k) y la actualización es O(log n).”

Errores comunes

• Usar low < q2 para superposición → los puntos finales que se tocan desaparecen → haga coincidir el tipo de intervalo elegido.
• Almacenar únicamente el high de cada nodo → la poda es imposible → mantenga el maxEnd del subárbol.
• Omitir la aumentación después de una rotación → las consultas posteriores se vuelven incorrectas → recalcule los nodos afectados.
• Afirmar una consulta O(log n) → falta el costo de salida → establezca O(log n + k).
• Sobrescribir puntos finales iguales → la eliminación y la salida se vuelven inestables → use un ID único o una clave compuesta.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Qué pasa si las consultas son únicamente puntos?

Use [x,x] y la misma poda de maxEnd. Si los puntos finales son enteros pequeños y estáticos, evalúe una estructura discreta especializada.

Pregunta de seguimiento 2: ¿Por qué no escanear una lista?

Con muchos intervalos y actualizaciones intercaladas, un escaneo toca todos los nodos. El árbol limita la búsqueda a un camino logarítmico más la salida reportada.

Pregunta de seguimiento 3: ¿Por qué las rotaciones preservan maxEnd?

Solo cambian subárboles locales; recalcular los nodos afectados de abajo hacia arriba restaura la definición del campo.

Pregunta de seguimiento 4: ¿Cómo se eliminan intervalos duplicados?

Asigne un ID en la inserción, use la clave (low, ID) y elimine por ID para que permanezcan otros intervalos con puntos finales iguales.

Pregunta de seguimiento 5: ¿Qué sucede con los puntos finales de punto flotante?

Defina la semántica de NaN, precisión e igualdad. Cuando sea posible, convierta a ticks enteros o unidades de tiempo.

Pregunta de seguimiento 6: ¿Cómo se garantiza una salida ordenada?

El recorrido in-order proporciona el orden por punto final inferior; si la poda cambia el orden de visita, recopile y ordene, indicando el costo adicional.

Pregunta de seguimiento 7: ¿Por qué es segura la poda?

Si el punto final máximo de un subárbol izquierdo está por debajo del límite inferior de la consulta, todos los intervalos allí terminan demasiado temprano para superponerse, por lo que omitirlo es seguro.