Compilation Order
Explore how to apply topological sorting to find the correct order for compiling classes with dependencies. This lesson helps you understand managing dependencies in coding problems, a common pattern needed to solve questions involving task ordering in technical interviews.
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:
#include <iostream>vector<char> FindCompilationOrder(vector<vector<char>> dependencies){// Replace this placeholder return statement with your codereturn dependencies[0];}