Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Compilation Order

Explore how to find the proper order to compile classes with dependencies by applying topological sort. This lesson helps you understand how to handle class dependency pairs to resolve compilation sequences efficiently, building skills to apply graph theory concepts in coding interviews.

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

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] Multi-select

A.

[A, B, C, D]

B.

[C, A, B, D]

C.

[C, B, D, A]

D.

[D, C, B, A]

1 / 3

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.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5
6

Try it yourself

Implement your solution in the following coding playground.

Python
usercode > main.py
from collections import deque



def find_compilation_order(dependencies):



  # Replace this placeholder return statement with your code

  return []
Compilation Order