Compilation Order
Understand how to apply topological sort to arrange classes for compilation based on their dependencies. This lesson helps you identify and implement the correct order to compile classes when given dependency pairs, a common coding interview pattern involving directed acyclic graphs.
We'll cover the following...
Statement
There are a total of classes labeled with the English alphabet (, , , and so on). Some classes are dependent on other classes for compilation. For example, if class extends class , then has a dependency on . Therefore, must be compiled before .
Given a list of the dependency pairs, find the order in which the classes should be compiled.
Constraints:
- Class name should be an uppercase character.
-
dependencies.length dependencies[i].length- All dependency pairs should be unique.
Examples
In the above examples, the arrows represent the relationship between these classes. For example, the arrow shows that extends , and therefore, is dependent on .
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check if you’re solving the correct problem:
Compilation Order
Given the following list of dependencies, what is the order of compilation of classes?
Select all that apply.
dependencies = [A, B], [B, C], [A, D] Multi-select
[A, B, C, D]
[C, A, B, D]
[C, B, D, A]
[D, C, B, A]
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground:
import java.util.*;class CompilationOrder {public static List<Character> findCompilationOrder(ArrayList<ArrayList<Character>> dependencies) {// Replace this placeholder return statement with your codereturn new ArrayList<Character>();}}