Frontend School

Optimal Module Build Order

DSA
hard

Optimal Module Build Order

Hard
Graph
Topological Sort
Priority Queue

Overview

In large-scale software development, managing module dependencies is crucial for efficient build processes. A common challenge arises when multiple modules are ready to be built simultaneously, and the build system needs to decide which one to prioritize. This problem simulates a scenario where modules have dependencies, and each module is associated with a version number. Your task is to determine an optimal build order that respects all dependencies while prioritizing modules with higher version numbers when multiple choices are available.

What you need to do / Task

Implement the getOptimalBuildOrder function. This function should return a list of module IDs representing a valid topological build order. If at any point multiple modules are ready to be built (i.e., all their dependencies have been met), the module with the highest version number among them should be selected next. This greedy choice ensures the 'optimal' order as defined.

Input & output

Input:

  • numModules: An integer representing the total number of modules in the project. Modules are 0-indexed, from 0 to numModules - 1.
  • dependencies: An array of [from, to] pairs, where from and to are module IDs. A pair [from, to] indicates that module from must be built before module to.
  • moduleVersions: An array of integers, where moduleVersions[i] is the version number of module i. Higher numbers indicate higher versions.

Output:

  • An array of number representing the module IDs in the optimal build order. If no valid build order can be found (due to a cycle, though constraints guarantee no cycles), an empty array or an appropriate error handling mechanism should be considered (for this problem, assume valid input without cycles).

Clarifications

  • Module IDs are 0-indexed, from 0 to numModules - 1.
  • All modules will eventually be included in the build order, meaning the graph of dependencies is acyclic and covers all numModules.
  • If numModules is 0, an empty array should be returned.
  • If dependencies is empty, modules should be ordered by their version numbers in descending order.

Examples

1

Example 1

Input:

numModules = 4, dependencies = [[0, 1], [0, 2], [1, 3], [2, 3]], moduleVersions = [10, 20, 15, 5]

Output:

[0,1,2,3]

Note:

Module 0 has no dependencies. After 0, modules 1 (v20) and 2 (v15) are ready. Module 1 is picked due to higher version. Then module 2 is picked. Finally, module 3 becomes ready and is picked.

2

Example 2

Input:

numModules = 3, dependencies = [[0, 2], [1, 2]], moduleVersions = [100, 200, 50]

Output:

[1,0,2]

Note:

Modules 0 (v100) and 1 (v200) have no dependencies. Module 1 is picked first due to its higher version. Then module 0 is picked. Finally, module 2 becomes ready and is picked.

3

Example 3

Input:

numModules = 5, dependencies = [[0,1],[0,2],[1,3],[2,4]], moduleVersions = [50, 60, 70, 80, 90]

Output:

[0,2,1,4,3]

Note:

Module 0 (v50) has no dependencies. After 0, modules 1 (v60) and 2 (v70) are ready. Module 2 is picked due to its higher version. Then module 1 is picked. After 2, module 4 (v90) is ready. After 1, module 3 (v80) is ready. Module 4 is picked first due to higher version, then 3.

Constraints

Constraints & assumptions

  • 1 <= numModules <= 10^5
  • 0 <= dependencies.length <= 2 * 10^5
  • 0 <= from, to < numModules for all [from, to] in dependencies
  • 1 <= moduleVersions[i] <= 10^9 for all i
  • All module IDs in dependencies are valid and within [0, numModules - 1].
  • There are no cyclic dependencies in the input graph.
  • Each module has a unique version number (simplifies tie-breaking, but solution should ideally handle non-unique versions by stable sorting or arbitrary choice for equal versions; for this problem, assume uniqueness for simplicity in prioritization logic).

What interviewers evaluate

  • Algorithm Correctness: The solution must correctly implement a topological sort algorithm, consistently respecting all dependencies and applying the version-based prioritization rule.
  • Efficiency: The algorithm should achieve optimal time complexity, typically O(V + E log V) where V is the number of modules and E is the number of dependencies, and efficient space usage.
  • Edge Case Handling: The solution should gracefully handle edge cases such as an empty dependency list, a single module, or modules with no incoming dependencies.
  • Code Quality: Code should be clean, well-structured, readable, and demonstrate good programming practices.
  • Problem Solving & Adaptability: Demonstrates the ability to adapt a standard algorithm (Topological Sort) to a specific problem variant (prioritization with versions).

Loading editor...