Solution: Compilation Order
Let's solve the Compilation Order problem using the Topological Sort pattern.
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 a character.
-
dependencies.length
dependencies[i].length
- All dependency pairs should be unique.
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
The naive approach is to generate all possible compilation orders for the given classes and then select the ones that satisfy the dependencies.
However, this would be very expensive since there would be an exponential number of possible orders ( , where is the number of classes) and only a handful of valid ones. The time complexity for this approach is . The space complexity is .
Optimized approach using topological sort
A more optimized solution to the above problem is topological ordering. Topological sort is used to find a linear ordering of elements that have dependencies on or priority over each other. For example, if is dependent on or if has priority over , is listed before in topological order. Since we’re looking for the order of compilation of classes, this problem lends itself naturally to the topological sort pattern.
For this problem, we find the topological order of the given classes using the list of class dependencies. The vertices in the graph represent the classes, and the directed edge represents the dependency relationship.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.