Scale AI Interview Questions

Background: Scale AI needs to manage and execute numerous tasks efficiently, especially with dependencies among them. Building a task scheduler that can handle these requirements is essential for optimizing workflows in data annotation and processing tasks.
Problem statement: You are to implement a basic task scheduler that can schedule tasks based on their dependencies. Each task can depend on several other tasks, and you must ensure that a task is executed only after all its dependencies have been completed. You should account for edge cases where there may be circular dependencies or tasks that cannot be completed.
Function/class signature:

• class TaskScheduler:

- def add_task(self, task_id: str, dependencies: List[str]) -> None: # Adds a new task with its dependencies.
- def schedule_tasks(self) -> List[str]: # Returns a list of tasks in the order they should be executed.Example 1:
Input:
add_task('A', [])
add_task('B', ['A'])
add_task('C', ['A'])
Output:
['A', 'B', 'C']
Explanation: Task 'A' has no dependencies, followed by 'B' and 'C' which depend on 'A'.Example 2:
Input:
add_task('D', ['E'])
add_task('E', [])
Output:
['E', 'D']
Explanation: 'E' is added first since 'D' depends on it.Constraints:

• Each task_id is a unique string.


• The maximum number of tasks is 10^4.


• The maximum number of dependencies per task is 10.


• Circular dependencies should raise an error.

Background: Scale AI requires efficient task scheduling to manage data processing pipelines, where tasks often depend on the completion of others. A robust task scheduler ensures optimal resource utilization and timely data processing.
Problem statement: Implement a basic task scheduler that can handle task dependencies. Given a list of tasks and their dependencies, your scheduler should execute the tasks in a sequence where dependencies are met. If a task has no dependencies, it can be executed first. You will provide a list of task IDs and a list of dependencies as pairs of task IDs.
Function/class signature:

• def schedule_tasks(tasks: List[str], dependencies: List[Tuple[str, str]]) -> List[str]:

Example 1:

• Input: tasks = ['A', 'B', 'C'], dependencies = [('A', 'B'), ('B', 'C')]


• Output: ['C', 'B', 'A']


• Explanation: Task 'C' has no dependencies, followed by 'B' which depends on 'A'.

Example 2:

• Input: tasks = ['A', 'B', 'C', 'D'], dependencies = [('A', 'B'), ('B', 'C'), ('D', 'B')]


• Output: ['D', 'C', 'B', 'A']


• Explanation: Task 'D' can execute first, then 'C' which depends on 'B', followed by 'B' and finally 'A'.

Constraints:

• 1 <= len(tasks) <= 100


• 0 <= len(dependencies) <= 100


• All tasks are unique strings.


• Dependencies are valid pairs, where the first element depends on the second.

Background: Scale AI's products often require managing numerous tasks that depend on one another, especially in data processing scenarios. A reliable scheduling system is essential to ensure that these tasks are executed in the correct order, particularly as the scale of operations increases.
Problem statement: Create a basic task scheduler that can manage and execute tasks based on their dependencies. Each task should be defined with a unique identifier as a string and a list of dependencies that represent tasks that must be completed before it can run. Implement methods to add tasks and execute them in the correct order based on their dependencies. The scheduler should handle cases where tasks have no dependencies, as well as cyclic dependencies that should raise an error.
Function/class signature:

• def add_task(self, task_id: str, dependencies: List[str]) -> None:


• def execute(self) -> List[str]:

Example 1:

• Input: scheduler.add_task('A', [])


• Input: scheduler.add_task('B', ['A'])


• Input: scheduler.execute()


• Output: ['A', 'B']


• Explanation: Task 'A' has no dependencies and runs first, followed by task 'B' which depends on 'A'.

Example 2:

• Input: scheduler.add_task('C', ['D'])


• Input: scheduler.add_task('D', [])


• Input: scheduler.add_task('A', ['C'])


• Input: scheduler.execute()


• Output: ['D', 'C', 'A']


• Explanation: Task 'D' runs first, then 'C', followed by 'A'.

Constraints:

• Each task_id is unique and a string with a length of 1 to 20 characters.


• Dependencies are a list of strings with a length of 0 to 10 characters.


• The number of tasks will not exceed 100.


• The implementation should detect circular dependencies and raise an error.

Background: At Scale AI, effectively managing task scheduling is crucial for executing jobs efficiently, especially in data processing pipelines. This involves not only scheduling tasks but also managing dependencies between them to ensure proper execution order.
Problem statement: You need to implement a basic task scheduler that can handle tasks with dependencies. Each task has a unique identifier and can have multiple dependent tasks that need to be completed before it can be executed. Implement a function that determines the order of task execution such that all dependencies are met. If it's impossible to complete all tasks (due to cycles in dependencies), return an empty list.
Function/class signature:

• def schedule_tasks(tasks: List[int], dependencies: List[Tuple[int, int]]) -> List[int]:

Example 1:

• Input: tasks = [1, 2, 3], dependencies = [(1, 2), (1, 3)]


• Output: [1, 2, 3]


• Explanation: Task 1 must be completed before tasks 2 and 3.

Example 2:

• Input: tasks = [1, 2, 3], dependencies = [(1, 2), (2, 1)]


• Output: []


• Explanation: There is a cycle in the dependencies between tasks 1 and 2, making it impossible to complete.

Constraints:

• 1 ≤ len(tasks) ≤ 1000


• 1 ≤ len(dependencies) ≤ 5000


• Task identifiers are distinct integers in the range [1, len(tasks)].

Background: Scale AI needs a robust task scheduling system to manage complex workflows with interdependencies efficiently. It is crucial for optimizing resource utilization and ensuring that tasks are executed in the correct order.
Problem statement: Given a list of tasks each represented by a unique identifier and its dependencies (tasks that must be completed before this task can start), design a function that returns the order in which tasks can be executed. If there is no valid order (due to cyclic dependencies), return an empty array. Use topological sorting to solve this problem.
Function/class signature:

• def task_scheduler(tasks: List[int], dependencies: List[Tuple[int, int]]) -> List[int]:

Example 1:

• Input: tasks = [1, 2, 3, 4], dependencies = [(1, 2), (1, 3), (3, 4)]


• Output: [1, 3, 4, 2] (possible output)


• Explanation: Task 1 must be completed before 2 and 3, and task 3 must be completed before task 4.

Example 2:

• Input: tasks = [1, 2, 3], dependencies = [(1, 2), (2, 1)]


• Output: []


• Explanation: There is a cycle between tasks 1 and 2, so no possible execution order.

Constraints:

• 1 ≤ tasks.length ≤ 1000


• 1 ≤ dependencies.length ≤ 1000


• Each task identifier is unique and between 1 to n, where n is the number of tasks.

Background: Scale AI manages large-scale data processing and needs an efficient system for scheduling tasks with dependencies, ensuring that tasks are processed in the right order.
Problem statement: Implement a class TaskScheduler that manages a list of tasks, each with a set of dependencies. You will need to create a method schedule_tasks that takes the list of tasks and their dependencies and returns an ordered list of tasks that can be executed respecting the dependencies. If there are circular dependencies, return an empty list.
Function/class signature:

• def schedule_tasks(tasks: List[str], dependencies: List[Tuple[str, str]]) -> List[str]:

Example 1:
Input:

tasks = ['A', 'B', 'C', 'D']  
dependencies = [('A', 'B'), ('B', 'C'), ('C', 'D')]

Output:

['D', 'C', 'B', 'A']

Explanation: Task D can be completed first as it has no dependencies, followed by C, B, and finally A.
Example 2:
Input:

tasks = ['A', 'B', 'C']  
dependencies = [('A', 'B'), ('B', 'A')]

Output:

[]

Explanation: There's a circular dependency between tasks A and B, making it impossible to schedule them.
Constraints:

• 1 <= len(tasks) <= 10^4


• 0 <= len(dependencies) <= 10^4


• Task names are unique strings with a length of up to 100 characters.