Planteamiento y contexto
Implemente un calendario donde book(start, end) retorne true y almacene el intervalo únicamente cuando no se solape con uno existente. Los intervalos son semiabiertos y requieren start < end; [10, 20) y [20, 30) son adyacentes. El problema evalúa estructuras ordenadas, límites, el momento de inserción y la complejidad.
Qué evalúa el entrevistador
La clave es una condición de solapamiento demostrable: con los inicios ordenados, solo es necesario verificar el predecesor y sucesor inmediatos. Una respuesta sólida compara un recorrido lineal (scan), un árbol balanceado y un arreglo ordenado, y luego señala que los servicios multiproceso o persistentes añaden requisitos de atomicidad y bloqueos.
Preguntas para clarificar
- ¿Los tiempos son enteros o marcas de tiempo (timestamps), y pueden ser negativos?
- ¿Se debe validar
start < end, y qué ocurre ante una entrada inválida? - ¿Los intervalos son estrictamente semiabiertos, permitiendo que extremos iguales se toquen?
- ¿Cuántas reservas y qué rango se manejan; se requieren cancelaciones o consultas?
- ¿Es una solución monohilo en memoria o un servicio persistente multiproceso?
Respuesta en 30 segundos
Usaría un mapa ordenado por inicio (start). Para [s, e), se busca el primer sucesor con inicio mayor o igual a s; si su inicio es menor que e, los intervalos se solapan. Luego se inspecciona el predecesor; si su fin es mayor que s, se solapan. Se inserta únicamente cuando ambas comprobaciones pasan. La semántica semiabierta permite que el fin del predecesor sea igual a s y que el inicio del sucesor sea igual a e. Un árbol balanceado ofrece búsqueda e inserción en O(log n) con espacio O(n).
Respuesta detallada paso a paso
Paso 1: Definir el solapamiento
Los intervalos semiabiertos [a, b) y [c, d) se solapan exactamente cuando a < d && c < b. Una vez ordenados los inicios, basta con el predecesor y sucesor directos, ya que los intervalos más lejanos terminan antes o comienzan después.
Paso 2: Elegir una estructura ordenada
Un árbol balanceado o TreeMap de Java proporciona búsqueda de predecesor y sucesor. Un arreglo ordenado tiene búsqueda O(log n) pero inserción O(n); un recorrido lineal es O(n). Ajuste la elección según el volumen de reservas y la mezcla de operaciones.
Paso 3: Comprobar antes de insertar
Inspeccione el sucesor, luego el predecesor, y escriba solo después de que ambos pasen. Insertar y revertir más tarde puede exponer un estado intermedio inválido.
boolean book(int start, int end) {
if (start >= end) return false;
var next = events.ceilingEntry(start);
if (next != null && next.getKey() < end) return false;
var prev = events.floorEntry(start);
if (prev != null && prev.getValue() > start) return false;
events.put(start, end);
return true;
}Paso 4: Demostrar el comportamiento en los límites
next.start == end y prev.end == start no se solapan. Inicios iguales no pueden reemplazar un intervalo antiguo que se intersecte porque la verificación del sucesor lo rechaza. Utilice tipos numéricos seguros si los timestamps pueden desbordarse.
Paso 5: Establecer la complejidad
El predecesor, sucesor y la inserción en un árbol balanceado son O(log n), con espacio O(n). Un arreglo ordenado busca en O(log n) pero inserta en O(n); un recorrido lineal es simple pero escala mal. Incluya las llamadas rechazadas en el análisis de complejidad.
Paso 6: Extender a concurrencia y persistencia
En una sola máquina, bloquee la comprobación y la inserción juntas. Entre múltiples procesos, use una transacción, una restricción única o un bloqueo de rango; una caché no puede ser la autoridad final de conflictos.
Compensaciones y límites
Intervalos semiabiertos frente a cerrados
Los intervalos semiabiertos expresan intervalos adyacentes de forma natural, tienen una longitud end - start y evitan la duplicación de límites. Un negocio con intervalos cerrados debe redefinir la granularidad de manera consistente.
TreeMap frente a un árbol de intervalos
El predecesor y el sucesor son suficientes cuando se rechaza todo solapamiento. Las consultas de solapamiento, cancelaciones o estadísticas de rangos pueden justificar un árbol de intervalos o un índice de rangos en base de datos.
Plan de implementación y evidencia
Matriz de pruebas
Cubra el primer intervalo, contención, solapamiento parcial, extremos que se tocan, inicios iguales, entrada vacía, valores grandes y solicitudes duplicadas. Después de cada reserva aceptada, asegure el invariante de orden.
Límite de producción
Para múltiples instancias, defina el aislamiento de transacciones, errores de conflicto, claves de idempotencia para reintentos y reglas de zona horaria. Pruebe la carga de la restricción persistente bajo reservas concurrentes.
Errores comunes y preguntas de seguimiento
Error: comprobar solo el sucesor
El nuevo intervalo puede solaparse con la parte final del predecesor, por lo que el fin del predecesor también debe verificarse.
Error: tratar extremos iguales como solapamiento
La semántica semiabierta permite que [10, 20) y [20, 30) se toquen; mantenga comparaciones estrictas.
Error: insertar antes de detectar el conflicto
La comprobación y la escritura deben ser un único paso lógico y atómico para preservar el invariante.
Seguimiento: permitir dos solapamientos
Mantenga conteos de intervalos activos o una línea de barrido (sweep line); la restricción se convierte en un problema de solapamiento máximo.
Seguimiento: reservas concurrentes
Bloquee en una sola máquina; use transacciones, bloqueos de rango o escrituras serializables entre instancias en lugar de memoria local del proceso.