Frontend School

Deployment Sequence Planner

DSA
medium

Deployment Sequence Planner

Medium
Graph
Topological Sort
Directed Acyclic Graph
Kahn's Algorithm
DFS

Overview

Tesla's vehicles and infrastructure rely on sophisticated software modules. Deploying updates to these modules requires careful orchestration due to intricate dependencies. If one module (Module A) depends on another (Module B), Module B must be deployed and fully operational before Module A can be deployed. Incorrect deployment order can lead to system failures or downtime.

This problem challenges you to determine a valid deployment sequence for a set of software modules, respecting all specified dependencies. This is crucial for ensuring seamless and reliable software updates across Tesla's diverse product ecosystem.

What you need to do / Task

Your task is to implement a function that takes the total number of modules and a list of their dependencies, then returns a valid deployment order. Specifically, you must:

  1. Model the module dependencies as a directed graph.
  2. Implement an algorithm to find a topological sort of this graph.
  3. If a valid deployment order exists, return any such order as an array of module IDs.
  4. If a circular dependency is detected (meaning no valid deployment order is possible), return an empty array [].

Input & output

Function Signature: function getDeploymentOrder(numModules: number, dependencies: number[][]): number[]

  • numModules: An integer representing the total number of software modules. Modules are identified by unique IDs from 0 to numModules - 1.
  • dependencies: An array of arrays, where each inner array [moduleA, moduleB] signifies that moduleA depends on moduleB. This means moduleB must be deployed before moduleA.

Return Value:

  • An array of numbers representing a valid topological order of module IDs for deployment. If multiple valid orders exist, any one is acceptable.
  • An empty array [] if a circular dependency is detected, indicating that no valid deployment order can be achieved.

Clarifications

  • Modules are represented by zero-indexed integers 0 through numModules - 1.
  • A module can have multiple dependencies, and multiple modules can depend on a single module.
  • The output order should contain all numModules if a valid order exists.

Examples

1

Example 1

Input:

numModules = 3, dependencies = [[0,1], [1,2]]

Output:

[2,1,0]

Note:

Module 0 depends on 1, and Module 1 depends on 2. So, 2 must be deployed first, then 1, then 0. A valid order is [2,1,0].

2

Example 2

Input:

numModules = 4, dependencies = [[1,0], [2,0], [3,1], [3,2]]

Output:

[0,1,2,3]

Note:

Module 0 has no dependencies. Modules 1 and 2 depend on 0. Module 3 depends on both 1 and 2. A valid deployment order is [0,1,2,3]. [0,2,1,3] would also be valid.

3

Example 3

Input:

numModules = 2, dependencies = [[0,1], [1,0]]

Output:

[]

Note:

Module 0 depends on 1, and Module 1 depends on 0, forming a circular dependency. No valid deployment order can be found.

Constraints

Constraints & assumptions

  • 1 <= numModules <= 10^5
  • 0 <= dependencies.length <= min(numModules * (numModules - 1) / 2, 10^5)
  • For each [moduleA, moduleB] in dependencies:
    • 0 <= moduleA, moduleB < numModules
    • moduleA != moduleB

Out of scope

  • Optimizing for a specific topological order (e.g., lexicographically smallest). Any valid order is sufficient.
  • Handling invalid input module IDs (assume all IDs are within 0 to numModules - 1).

What interviewers evaluate

  • Ability to correctly model graph relationships from problem description.
  • Proficiency in implementing a standard graph traversal algorithm (e.g., Kahn's algorithm or DFS-based topological sort).
  • Correctly identifying and handling cyclic dependencies.
  • Efficiency of the solution in terms of time and space complexity.

Loading editor...