Entrevista técnica: ¿Cómo implementar un programador de tareas con prioridades y cancelable?

Prompt y alcance

Implementa un Scheduler de un solo nodo con schedule(taskId, runAt, priority, fn), cancel(taskId) y next(). Selecciona el runAt más próximo, luego la mayor priority y, por último, la secuencia de envío. Solo una versión de un taskId es válida. Una tarea cancelada no debe iniciarse; cuando no haya nada pendiente de ejecución inmediata, next() devuelve una indicación de espera o un resultado vacío. Explica la eliminación perezosa (lazy deletion), la concurrencia de workers, la elección del reloj y las condiciones de carrera en el apagado.

El material público de entrevistas presenta la programación de tareas como un problema combinado que involucra colas de prioridad, pools de workers, cancelación y manejo de fallos. Evalúa los contratos de ciclo de vida y concurrencia además de la estructura de datos del heap en sí.

Qué está evaluando el entrevistador

• Una máquina de estados para pending, running, cancelled y completed sin transiciones ilegales.
• Una clave determinista (runAt, -priority, sequence) que nunca compare objetos de tarea.
• Verificaciones de versión o eliminación perezosa para que el reemplazo y la cancelación no filtren trabajo obsoleto.
• Una distinción precisa entre cancelar trabajo en cola y detener una función en ejecución.
• Una demostración de que los límites de workers, el orden de apagado y la selección del reloj preservan el contrato.

Aclaraciones que conviene hacer primero

• ¿Es runAt un plazo relativo monotónico o tiempo de reloj de pared? Asume un reloj monotónico para las esperas.
• ¿Recibe fn la cancelación? Asume un AbortSignal, únicamente con detención cooperativa.
• ¿Un taskId duplicado reemplaza o falla? Esta versión reemplaza la versión anterior.
• ¿cancel detiene una función en ejecución de inmediato? No; evita una ejecución que aún no ha comenzado y envía una señal a una en ejecución.
• ¿close espera a que termine el trabajo en ejecución? Asume que rechaza nuevo trabajo y espera a que los workers terminen.

Respuesta de 30 segundos

Mantendría (runAt, -priority, sequence, taskId, version) en un min-heap y almacenaría la versión actual de cada ID de tarea en un mapa. Programar o cancelar actualiza el mapa e invalida las entradas antiguas del heap; next() valida repetidamente la versión y el estado antes de mover una tarea vencida a running. Un despachador utiliza un reloj monotónico para esperar al elemento superior del heap y luego entrega el trabajo a un pool de workers de tamaño fijo. La cancelación en cola es una garantía estricta; la cancelación de código en ejecución es cooperativa. El apagado rechaza nuevos envíos, despierta al despachador y espera a que se complete la limpieza.

Análisis detallado paso a paso

Paso 1: Definir la clave y los invariantes

Utiliza (runAt, -priority, sequence) como clave del heap. Una secuencia monotónica hace que marcas de tiempo y prioridades idénticas sean deterministas. current[taskId] almacena únicamente la versión más reciente. Las versiones obsoletas pueden permanecer temporalmente en el heap, pero nunca pueden pasar de pending a running.

Paso 2: Definir el reemplazo en schedule

Cada schedule crea una nueva versión, la almacena en el mapa y añade una nueva entrada al heap. No hay una búsqueda lineal a través del arreglo. Cuando se extrae una entrada, su versión se compara con la del mapa. La inserción es O(log n) y los identificadores duplicados no pueden producir dos ejecuciones válidas.

schedule(id, runAt, priority, fn):
    version = nextVersion(id)
    current[id] = {version, state: pending, fn, runAt, priority}
    heappush(heap, (runAt, -priority, nextSequence(), id, version))

Paso 3: Implementar cancel y la limpieza de la cabecera

La cancelación marca la tarea pendiente actual como cancelled y despierta a quien esté esperando. Cuando next() extrae la cabecera, verifica que el mapa aún apunte a la misma versión y que el estado sea pending. Las entradas obsoletas, canceladas y reemplazadas se descartan. La eliminación perezosa evita un escaneo O(n), pero las proporciones de entradas obsoletas deben monitorearse y reconstruirse periódicamente.

Paso 4: Controlar el trabajo vencido con un límite de workers

El despachador no debe entregar trabajo futuro a los workers. Calcula el retraso hasta la cabecera del heap con un reloj monotónico. Una vez cumplido el plazo, cambia atómicamente de pending a running y coloca la tarea en una cola de workers de tamaño fijo. El recuento de workers o un semáforo impone el límite de concurrencia.

Paso 5: Separar la cancelación de la finalización de la función

Si una tarea en cola se cancela antes de la transición de estado, fn nunca se invoca. Una tarea en ejecución solo puede recibir un AbortSignal; la función debe verificarlo o pasarlo a operaciones de E/S cancelables. Registra cancelRequested y no reportes la finalización hasta que la función haya retornado efectivamente.

Paso 6: Ordenar el cierre contra condiciones de carrera

close entra primero en closing y rechaza nuevas programaciones; luego cancela temporizadores y despierta al despachador. El despachador deja de reclamar nuevas tareas mientras los workers terminan el trabajo ya reclamado; solo entonces el programador pasa a closed. Si el trabajo en cola debe descartarse de inmediato, marca las entradas del mapa como canceladas en lugar de simplemente vaciar el heap.

Paso 7: Demostrar complejidad y límites de espacio

Un schedule normal es O(log n), cancel es una actualización de estado O(1) y next realiza un trabajo de heap de O(log n). Cada entrada obsoleta se extrae a lo sumo una vez, por lo que la limpieza se amortiza sobre la actualización o cancelación que la generó. Reconstruye a partir de las entradas actuales del mapa cuando el tamaño del heap supere un múltiplo fijo de tareas activas.

Paso 8: Probar los entrelazamientos importantes

Prueba el ordenamiento estable para claves iguales, el reemplazo antes de que la entrada antigua llegue a la cabecera, la cancelación inmediatamente antes y después de reclamar la tarea, una tarea más temprana que interrumpe una espera, el límite de workers, fallos en las funciones, el envío durante el cierre y saltos en el reloj monotónico. Realiza pruebas diferenciales de next() contra un modelo de referencia ordenado y registra el pico de workers activos.

Respuesta de ejemplo de alta calidad

Separaría el estado del heap: un mapa almacena la versión más reciente para cada taskId, mientras que un min-heap almacena (runAt, -priority, sequence, taskId, version). El reemplazo escribe una nueva versión y la cancelación marca el estado; ninguno de los dos muta el arreglo del heap. El despachador reclama únicamente tareas vencidas y las coloca en una cola de workers de tamaño fijo. La validación de versiones evita que se ejecuten entradas canceladas y obsoletas, mientras que AbortSignal proporciona cancelación cooperativa a las funciones en ejecución. El apagado rechaza nuevo trabajo, detiene las reclamaciones, despierta a los que esperan y aguarda a que finalice el trabajo reclamado. Las métricas rastrean las entradas activas frente al tamaño del heap para que la eliminación perezosa no crezca sin límite.

Errores comunes

• Ordenar únicamente por prioridad e ignorar que runAt todavía está en el futuro.
• Mutar una entrada del heap in situ y romper el invariante del heap.
• Eliminar solo del mapa y luego ejecutar una entrada antigua del heap.
• Tratar una llamada exitosa a cancel() como prueba de que el código en ejecución se ha detenido.
• Usar el tiempo de reloj de pared para las esperas y sufrir correcciones de reloj.
• Vaciar la cola en close dejando vivos temporizadores, despachadores o workers.
• Iniciar workers sin límite y convertir el programador en un lanzador ilimitado.

Preguntas de seguimiento y respuestas

¿Cómo evitas la inanición (starvation) del trabajo de baja prioridad?

Indica que la prioridad estricta es el comportamiento predeterminado y puede causar inanición en tareas de baja prioridad. Si se requiere equidad, aumenta la prioridad efectiva con el tiempo de espera o utiliza cuotas ponderadas. Ambas opciones modifican la clave de ordenamiento y la prueba de latencia, por lo que se deben añadir métricas y pruebas.

¿Cómo evitas ejecuciones superpuestas para una tarea recurrente?

Añade un bloqueo de ejecución o una generación al estado de la tarea. Si la siguiente activación llega mientras se está ejecutando, elige explícitamente omitir, consolidar una ejecución pendiente o encolar una nueva versión. Nunca envíes incondicionalmente cuando la superposición esté prohibida.

¿Cómo te recuperarías tras una caída del proceso?

Un heap en memoria solo cubre el ciclo de vida del proceso. Persiste la versión, el estado y el tiempo de la próxima ejecución, reconstruye el heap al iniciar y reclama las tareas con una actualización condicional o un lease. La recuperación normalmente proporciona ejecución al menos una vez (at-least-once), por lo que las funciones de las tareas deben ser idempotentes.

¿Cómo lo extenderías a múltiples nodos?

Reemplaza el heap local con una cola persistente indexada por tiempo y usa leases o escrituras condicionales para la propiedad. Permite que un lease vencido se vuelva reintentable tras el fallo de un nodo. Transporta las versiones a través de cancelaciones y reemplazos para que los consumidores rechacen el trabajo obsoleto, y utiliza el tiempo de almacenamiento o una ventana de tolerancia explícita entre nodos.