Compilation Order

Try to solve the Compilation Order problem.

We'll cover the following

Statement#

There are a total of nn classes labeled with the English alphabet (AA, BB, CC, and so on). Some classes are dependent on other classes for compilation. For example, if class BB extends class AA, then BB has a dependency on AA. Therefore, AA must be compiled before BB.

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.
  • 0≤0 \leq dependencies.length ≤676\leq 676
  • dependencies[i].length =2= 2
  • All dependency pairs should be unique.

Examples#

Created with Fabric.js 3.6.6 [C, A] [B, A] [D, C] [E, B] [E, D] A B C E D Output A, B, C, D, E A, C, B, D, E A, C, D, B, E Sample example 1Input

1 of 2

Created with Fabric.js 3.6.6 Output Sample example 2Input [C, A] [B, A] [B, C] [D, C] [D, B] [E, B] [E, D] A, C, B, D, E A B C D E

2 of 2

In the above examples, the arrows represent the relationship between these classes. For example, the arrow A→CA \rightarrow C shows that CC extends AA, and therefore, CC is dependent on AA.

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

1

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]

A)

[A, B, C, D]

B)

[C, A, B, D]

C)

[C, B, D, A]

D)

[D, C, B, A]

Question 1 of 30 attempted

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.

Drag and drop the cards to rearrange them in the correct sequence.

Build the graph from the input using adjacency lists.

Store the in-degree of each vertex in a hash map.

Add the sources to a queue.

Pop from the queue and store the node in a list, let’s call it sortedsorted orderorder.

Decrement the in-degrees of the node’s children by 1. If the in-degree of a node becomes 0, add it to the source queue.

Repeat until all vertices have been visited. Return the sortedsorted orderorder list.

Try it yourself#

Implement your solution in main.py in the following coding playground. We have provided some useful code templates in the other file that you may build on to solve this problem.

Python
main.py
graph.py
Input #1
Compilation Order

Solution: Verifying an Alien Dictionary

Solution: Compilation Order