Frontend School

Curated Production Pipeline

DSA
hard

Curated Production Pipeline

Hard
Graph
Topological Sort
Kahn's Algorithm

Overview

Spotify's content pipeline involves numerous steps from initial recording to final release. To ensure a smooth and efficient workflow, and to meet crucial deadlines for high-priority tracks, it's essential to properly sequence these production tasks. This problem simulates a simplified version of such a pipeline, where tasks have dependencies and some are critical with specific completion deadlines.

What you need to do / Task

You are given a set of production tasks, their dependencies, and a list of critical tasks with associated deadlines. Your goal is to determine a valid ordering of tasks such that all dependencies are met, and all critical tasks are completed by their respective deadlines.

Input & output

  • numTasks: An integer representing the total number of unique production tasks, labeled from 0 to numTasks - 1.
  • dependencies: An array of pairs [fromTask, toTask], where fromTask must be completed before toTask can begin.
  • criticalTasks: An array of pairs [taskId, maxPosition], where taskId is a critical task that must appear at an index <= maxPosition in the final ordered sequence (0-indexed).

Return: An array of numbers representing any valid topological order of tasks that satisfies all dependencies and critical task deadlines. If no such order exists (due to a cycle or an unmet critical deadline), return an empty array [].

Clarifications

  • Task IDs are 0-indexed, from 0 to numTasks - 1.
  • If multiple valid task orders exist, any one of them is acceptable.
  • If dependencies is empty, tasks can be ordered arbitrarily, subject to criticalTasks constraints.
  • If criticalTasks is empty, only dependency constraints need to be satisfied.
  • The maxPosition for critical tasks is 0-indexed. So, a maxPosition of 0 means the task must be the very first task in the sequence.

Examples

1

Example 1

Input:

numTasks = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]], criticalTasks = [[0, 3]]

Output:

[3,1,2,0]

Note:

A valid order is [3, 1, 2, 0]. Task 0 is critical and must be at position <= 3. It's at position 3, which satisfies the condition. Another valid output could be [3,2,1,0].

2

Example 2

Input:

numTasks = 3, dependencies = [[0, 1], [1, 2], [2, 0]], criticalTasks = []

Output:

[]

Note:

The dependencies form a cycle (0 -> 1 -> 2 -> 0), so no valid topological order can exist. An empty array is returned.

3

Example 3

Input:

numTasks = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]], criticalTasks = [[0, 1]]

Output:

[]

Note:

In any valid topological order, tasks 1 and 2 must come before task 0, and task 3 must come before tasks 1 and 2. This means task 0 will always be at position 2 or 3 (e.g., [3,1,2,0] or [3,2,1,0]). Since task 0 is critical and must be at position <= 1, its deadline cannot be met. An empty array is returned.

4

Example 4

Input:

numTasks = 2, dependencies = [], criticalTasks = [[0, 0], [1, 1]]

Output:

[0,1]

Note:

No dependencies, so tasks can be ordered freely. Task 0 must be at position 0, Task 1 must be at position <= 1. The order [0, 1] satisfies both. The order [1, 0] would violate Task 0's critical deadline (1 <= 0 is false), so [0, 1] is the only valid sequence.

Constraints

Constraints & assumptions

  • 1 <= numTasks <= 10^5
  • 0 <= dependencies.length <= 2 * 10^5
  • 0 <= criticalTasks.length <= numTasks
  • All taskIds in dependencies and criticalTasks are valid: 0 <= taskId < numTasks.
  • 0 <= maxPosition < numTasks for all critical tasks.
  • Dependencies do not contain self-loops (e.g., [A, A]).
  • The graph formed by dependencies is not necessarily connected.

Out of scope

  • Finding the lexicographically smallest or any other "optimal" topological sort. Any valid sort is sufficient.
  • Input validation beyond the specified constraints (e.g., handling non-integer inputs).

What interviewers evaluate

  • Correctness: The solution must correctly identify cycles and unmet critical task deadlines, returning an empty array in such cases, and a valid sequence otherwise.
  • Algorithm Efficiency: The chosen algorithm should be efficient enough to handle large numbers of tasks and dependencies (optimal O(V+E) complexity).
  • Graph Representation: Effective use of data structures (e.g., adjacency lists, in-degree arrays) for graph representation.
  • Code Structure & Readability: Clean, well-organized code with appropriate variable names and comments where necessary.

Loading editor...