DEV Community

SalahElhossiny
SalahElhossiny

Posted on

3 2

Topological Sort in Interviews

Topological Sort is used to find a linear ordering of elements that have dependencies on each other. For example, if event ‘B’ is dependent on event ‘A’, ‘A’ comes before ‘B’ in topological ordering.

This pattern defines an easy way to understand the technique for performing topological sorting of a set of elements.

The pattern works like this:

Initialization

a) Store the graph in adjacency lists by using a HashMap

b) To find all sources, use a HashMap to keep the count of in-degrees

Build the graph and find in-degrees of all vertices
a) Build the graph from the input and populate the in-degrees HashMap.

Image description

Find all sources
a) All vertices with ‘0’ in-degrees will be sources and are stored in a Queue.
Sort
a) For each source, do the following things:
—i) Add it to the sorted list.
 — ii)Get all of its children from the graph.
 — iii)Decrement the in-degree of each child by 1.  
— iv)If a child’s in-degree becomes ‘0’, add it to the sources Queue.

b) Repeat (a), until the source Queue is empty.
How to identify the Topological Sort pattern:

The problem will deal with graphs that have no directed cycles

If you’re asked to update all objects in a sorted order
If you have a class of objects that follow a particular order

Problems featuring the Topological Sort pattern:
Task scheduling
Minimum height of a tree

Top comments (0)

The Most Contextual AI Development Assistant

Pieces.app image

Our centralized storage agent works on-device, unifying various developer tools to proactively capture and enrich useful materials, streamline collaboration, and solve complex problems through a contextual understanding of your unique workflow.

👥 Ideal for solo developers, teams, and cross-company projects

Learn more

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay