Entrevista de código: ¿Cómo construirías un programador de tareas consciente de dependencias?

Enunciado y alcance

Implementa un TaskScheduler en memoria. El invocador envía un ID de tarea, IDs de dependencias y una función. El programador solo puede tomar una tarea después de que todas sus dependencias hayan tenido éxito. Expón operaciones como submit, ready, complete, fail y cancel, y reporta los ciclos de dependencias que nunca podrán ejecutarse. Explica los envíos duplicados, la propagación de fallos, los límites de concurrencia, el apagado y los límites de reinicio.

Este problema combina el recorrido de grafos con una máquina de estados activa. Una respuesta sólida clarifica la semántica de estados y de fallos antes de elegir las estructuras de datos, y luego mantiene los grados de entrada (indegrees), las aristas inversas y una cola de listos (ready queue). El TopologicalSorter de Python trata los nodos sin predecesores pendientes como procesables y expone los ciclos detectados como datos de diagnóstico. Dicha semántica ayuda a definir el contrato, pero un ordenamiento topológico estático por sí solo es insuficiente, ya que las tareas se completan, fallan y se cancelan con el tiempo.

Lo que evalúa el entrevistador

• Distinguir entre pending, ready, running, succeeded, failed, blocked y cancelled.
• Mantener invariantes de grado de entrada y de adyacencia inversa en lugar de reexaminar cada tarea.
• Liberar únicamente los dependientes afectados cuando una dependencia se completa.
• Definir la propagación de ciclos, fallos y cancelaciones antes de elegir las API.
• Limitar los workers, garantizar un solo reclamo por versión de tarea y manejar envíos duplicados.
• Proporcionar cotas de complejidad y pruebas para intercalaciones adversarias.

Preguntas de clarificación

• ¿El grafo es estático o se pueden añadir tareas dinámicamente? Asume que todas las tareas referenciadas se envían antes de que comience la programación; solo se puede enviar una nueva versión mientras está en ejecución.
• ¿Qué les ocurre a los descendientes después de que falla una dependencia? Esta respuesta los marca como blocked; el reintento requiere una nueva generación explícita.
• ¿La cancelación se propaga en cascada a todos los descendientes? Asume que solo cancela esa tarea; los descendientes pasan a ser blocked cuando una dependencia obligatoria se cancela.
• ¿Los fallos se reintentan automáticamente? No. El invocador envía una nueva generación y es responsable de la idempotencia de los efectos secundarios.
• ¿ready() devuelve una sola tarea o un lote? Devuelve como máximo maxConcurrency - running tareas en orden determinista.

Respuesta de treinta segundos

Almacena el estado de cada tarea, el conteo de dependencias sin terminar y la lista de adyacencia inversa. Antes de programar, ejecuta el algoritmo de Kahn o un DFS de tres colores y devuelve una ruta del ciclo si existe alguno. Coloca las tareas con grado de entrada cero en una cola de listos estable. Bajo un único bloqueo (lock), toma tareas cambiando ready a running; ante el éxito, decrementa el conteo de cada dependiente y encola aquellos que lleguen a cero. El fallo y la cancelación marcan a los descendientes afectados como blocked. Cada callback incluye una generación para que workers obsoletos no liberen dependientes dos veces. Un grupo fijo de workers o un semáforo impone la concurrencia.

Solución paso a paso

Paso 1: Definir estados y límites

Los estados avanzan hacia adelante: de pending a ready, luego a running, y finalmente a succeeded o failed. La cancelación puede ocurrir mientras esté en pending o ready; la cancelación de una función en ejecución es cooperativa. blocked significa que la función no se ejecutó porque una dependencia obligatoria ya no puede tener éxito. Los estados terminales nunca regresan a ready, lo que previene ejecuciones duplicadas.

Almacena un generation por cada ID de tarea. Un envío duplicado puede rechazarse o crear una nueva generación; esta solución opta por el reemplazo únicamente mientras la versión antigua no esté en ejecución. Una versión en ejecución no puede sobrescribirse de forma silenciosa; devuelve un conflicto o espera su callback terminal.

Paso 2: Construir grados de entrada y aristas inversas

La tabla de tareas almacena remainingDeps; un mapa inverso almacena dependents[dependencyId]. Registra cada arista una sola vez. Las tareas con grado de entrada cero entran a la cola de listos durante la inicialización, y los cambios posteriores solo actualizan los conteos afectados.

Task:
  id, generation, dependencies, dependents
  remainingDeps, state, fn, error

submit(task):
  validateUniqueDependencies(task)
  registerEdges(task)
  if task.remainingDeps == 0:
      task.state = READY
      readyQueue.push(task.id)

Una dependencia desconocida no debe tratarse como si ya estuviera completa. Mantenla en estado waiting hasta que sea enviada, o recházala con un error UnknownDependency si el contrato exige un grafo cerrado.

Paso 3: Reportar ciclos antes de la ejecución

Para un grafo estático, el algoritmo de Kahn copia los grados de entrada, procesa los nodos con grado de entrada cero y elimina sus aristas salientes. Si se procesan menos nodos que el total, el resto contiene un ciclo. Devuelve una ruta concreta como A → B → C → A, no solo un booleano.

Alternativamente, un DFS blanco-gris-negro encuentra una arista de gris a gris y reconstruye el ciclo mediante punteros a padres. Ejecuta la detección antes de que cualquier tarea pase a running. Prohíbe añadir aristas después de que comience la ejecución a menos que el contrato cree una nueva versión del grafo.

Paso 4: Tomar tareas y aplicar límites de concurrencia

ready() calcula los slots disponibles, extrae tareas en un orden de envío estable y cambia cada estado a running dentro de la misma sección crítica. Una vez devuelta, otro invocador no puede tomar la tarea. complete(id, generation) valida tanto la generación como el estado; un callback tardío de un worker antiguo devuelve un conflicto y no puede liberar dependientes.

Usa una cantidad fija de workers o un semáforo para el límite de concurrencia. La longitud de la cola no es el conteo de tareas activas: solo las tareas en running consumen slots. Si un lote solicitado excede los slots disponibles, devuelve la cantidad disponible o CapacityExceeded en lugar de aumentar la concurrencia silenciosamente.

Paso 5: Propagar éxito, fallo y cancelación

Ante el éxito, recorre los dependientes directos. Decrementa remainingDeps únicamente para las versiones que aún estén pendientes; encola un nodo cuando el conteo llegue a cero. Ante un fallo, este contrato marca a los descendientes directos y transitivos como blocked y registra la primera causa de bloqueo. Una política de dependencias alternativas solo es válida si se especifica explícitamente.

La cancelación afecta a las versiones que no han comenzado. Una función en ejecución puede recibir un AbortSignal, pero solo la función puede confirmar una salida cooperativa. Los descendientes se convierten en blocked cuando una dependencia obligatoria falla o se cancela; nunca simulan que dicha dependencia tuvo éxito.

Paso 6: Hacer que los envíos y los callbacks sean idempotentes

Usa (taskId, generation) como clave de idempotencia. Llamadas repetidas a complete, fail o cancel devuelven el estado terminal conocido y no decrementan a los dependientes dos veces. Al reemplazar una versión pendiente, elimina sus aristas inversas antiguas antes de registrar las nuevas; sobrescribir el objeto por sí solo deja aristas obsoletas y puede hacer que un dependiente espere indefinidamente.

Si las actualizaciones no son necesarias, rechazar IDs duplicados es más simple. Explica la compensación: un constructor estático puede rechazar duplicados, mientras que un flujo de trabajo de larga duración generalmente necesita generaciones, registros de auditoría y versiones de reintento explícitas.

Paso 7: Apagado, reintento y recuperación

close() rechaza nuevos envíos, evita que ready() tome más trabajo y espera los callbacks en ejecución o un tiempo de expiración definido. Las tareas en cola se cancelan o se retienen según el contrato; limpiar la memoria sin registrar un motivo ocasiona pérdida de información. Un reintento crea una nueva generación y vuelve a verificar la instantánea de dependencias en lugar de cambiar failed de vuelta a ready.

Un programador en memoria no puede recuperarse tras una caída del proceso. La persistencia requiere almacenar tareas, versiones, estados, dependencias y leases (arrendamientos). Los workers de recuperación toman tareas mediante escrituras condicionales, y las funciones de tarea deben ser idempotentes. La recuperación puede ofrecer una ejecución de al menos una vez (at-least-once), no efectos secundarios de exactamente una vez (exactly-once).

Paso 8: Complejidad y pruebas

La inicialización del grafo es O(V + E). Cada finalización examina únicamente las aristas salientes, por lo que un pase completo de propagación se mantiene en O(V + E); una cola de listos basada en heap realiza reclamos en O(log V). El espacio es O(V + E).

Prueba un grafo vacío, ramas independientes, una cadena larga, ciclos, dependencias desconocidas, dos dependencias que se completan al mismo tiempo, propagación de fallos, cancelación de descendientes, callbacks duplicados, envíos duplicados, capacidad cero, condiciones de carrera durante el apagado y callbacks tardíos de generaciones antiguas. Un modelo de estados pequeño puede comparar cada conjunto de tareas listas y asegurar a lo sumo una transición a pending → running por versión.

Respuesta modelo

Primero congelaría el grafo y luego almacenaría el estado, la generación, el conteo de dependencias restantes y la adyacencia inversa de cada tarea. El algoritmo de Kahn junto con punteros a padres reporta un ciclo concreto. Las tareas sin dependencias entran en una cola de listos estable. ready() toma tareas hasta agotar los slots de concurrencia restantes bajo un único bloqueo y las marca inmediatamente como running. Un callback de finalización debe coincidir con la generación y solo puede transicionar una vez; el éxito decrementa los conteos aguas abajo y encola los nodos que llegan a cero. El fallo y la cancelación producen descendientes en estado blocked en lugar de simular un éxito. Los callbacks duplicados son idempotentes, los reintentos crean una nueva generación y el apagado rechaza nuevo trabajo antes de vaciar los callbacks en ejecución. El pase es O(V + E) y las pruebas cubren los límites de concurrencia y efectos secundarios.

Errores comunes

• Realizar un solo ordenamiento topológico sin definir transiciones dinámicas de finalización y fallo.
• Examinar todos los nodos en busca de disponibilidad tras cada finalización en lugar de usar aristas inversas.
• Devolver únicamente un booleano para indicar ciclos, sin una ruta de diagnóstico.
• Omitir la generación en los callbacks de finalización, permitiendo que workers obsoletos liberen dependientes.
• Tratar el fallo de una dependencia como un éxito y ejecutar trabajo aguas abajo sin cumplir los prerrequisitos.
• Afirmar que cancelar una función en ejecución es forzoso sin un contrato de señalización cooperativa.
• Incrementar la cantidad de workers para ocultar el trabajo acumulado (backlog) y agotar la capacidad aguas abajo.
• Reutilizar un estado fallido para reintentos sin semántica de idempotencia, efectos secundarios o leases.

Preguntas de seguimiento

¿Cómo manejarías un grafo demasiado grande para la memoria?

Almacena los metadatos de las tareas y las aristas de forma duradera, y carga solo una ventana activa por tenant o partición. Mantén un cursor en memoria. Los reclamos utilizan escrituras condicionales o leases cortos, y la finalización continúa verificando la generación. Explica dependencias entre particiones, consistencia de paginación y ejecución duplicada tras la expiración del lease.

¿Cómo puede continuar una rama fallida mientras los nodos dependientes se detienen?

Etiqueta las aristas como obligatorias u opcionales. Una tarea pasa a estar lista solo después de que todas las dependencias obligatorias tengan éxito y las opcionales alcancen un estado terminal. Registra los fallos opcionales en el resumen de entrada y en las métricas en lugar de descartarlos silenciosamente; esto amplía la máquina de estados y las pruebas.

¿Cómo añadirías dependencias dinámicamente?

Permite nuevas aristas solo mientras una tarea esté en pending, incrementando el grado de entrada dentro de la misma sección crítica. Rechaza cambios en tareas que estén en ready o running. Si se requieren cambios en ejecución, crea una nueva generación y ejecútala sobre el nuevo grafo una vez que la versión antigua alcance un estado terminal.

¿Cómo cancelas una dependencia compartida sin afectar ramas no relacionadas?

Cambia únicamente el estado terminal de esa dependencia y luego inspecciona las relaciones de aristas obligatorias a lo largo de las aristas inversas. Las ramas sin esa dependencia continúan; cada tarea aguas abajo que la requiera pasa a ser blocked. Audita quién la canceló, cuándo y a lo largo de qué ruta de propagación.

¿Cómo evitan la doble ejecución múltiples procesos worker?

Toma las tareas con una actualización atómica en base de datos o un lease, e incluye la generación en la condición. Un lease puede expirar y permitir otro reclamo, por lo que la función debe ser idempotente o compensable. Un bloqueo en memoria protege únicamente a un solo proceso.

¿Qué señales de observabilidad son importantes?

Monitorea el conteo de ciclos, el conteo de bloqueos, el tiempo de espera en estado listo, la duración de ejecución, los conflictos de reclamo, la expiración de leases, los callbacks duplicados y la latencia de propagación por arista. Segmenta por tipo de tarea y tenant para que los promedios no oculten la acumulación de colas, y distingue los errores de configuración del grafo de los fallos de funciones.

¿Cómo demostrarías que una tarea no se toma dos veces?

Coloca la verificación de estado, el decremento de slots y la escritura de running en una sola sección crítica o actualización condicional atómica, e incluye la generación en los callbacks. Una prueba de modelo puede intercalar dos llamadas a ready() y asegurar a lo sumo una transición a pending → running por versión; una finalización duplicada devuelve el estado terminal conocido.