When I interviewed at Microsoft last year, my first technical interview was about a classic dependency problem.
You’re given a set of tasks to do with their associated dependencies and you must write a script that tells you the order to resolve these tasks.
So, in this image Task D is required to be completed before Task C can be completed. Task C is required to be completed before Task B can be completed, and so forth.
Therefore, it’s safe to say that in order for Task A to be completed, you must first complete Task D.
In addition, this question required candidates to identify tasks that can not be completed:
Here, Task B requires Task C to be completed, Task C requires Task D, but Task D requires Task B to completed.
Notice how it’s impossible to complete this? B requires C, C requires D, D requires B. This is known as a cycle; there’s a ton of algorithms out there to be able to solve these (see here).
We could write our own code to solve this (which gets complicated and tough to understand very quickly), or rely on a hidden standard library gem: graphlib.TopologicalSorter.
» I seriously wish I had known about graphlib to begin with - maybe a future snack? Reply and let me know if you want a snack about graphlib.
What is topological sort?
Think of topological sort as an algorithm to be able to organize the path to completion for a given set of tasks - think of it as an ordered to-do list if every item in that list could have prerequisites.
» If you want to the crux of this stuff, check out this article on Kahn’s Algorithm.
Using graphlib’s TopologicalSorter
Instead of working with nodes and edges (which generally Python developers don’t work with), you’ll define your tasks and what your tasks depend on, then use TopologicalSorter to create your chain of dependencies:
from graphlib import TopologicalSorter
# Define dependencies here
# A depends on B, B depends on C, C depends on nothing
tasks = {
"task_a": {"task_b"},
"task_b": {"task_c"},
"task_c": set(),
}
# Call the sorting
sorter = TopologicalSorter(tasks)
print(list(sorter.static_order()))When ran, you’ll get ['task_c', 'task_b', 'task_a']. This tells us that you’ll do task_c first, then task_b, then task_a.
If you have a circular dependency (“cycle”; A depends on B, B depends on A), the sorter will flag it:
circular_tasks = {
"task_a": {"task_b"},
"task_b": {"task_a"},
}
sorter = TopologicalSorter(circular_tasks)
try:
sorter.prepare()
except CycleError as error:
print(f"Can't resolve: {error}")When ran, you’ll get the following error: Can't resolve: ('nodes are in a cycle', ['task_a', 'task_b', 'task_a'])
If you look at some of the solutions that are out there, you’ll see very quickly how difficult it is to write it yourself. Instead, TopologicalSorter makes it easy for you to write these kinds of graphs.
I don’t know about you, but I’m never going to write a topological sort by hand anymore.
Where does this show up outside of interviews?
Believe it or not, a lot of places. One of the places it shows up is in Django’s own migration system. If you’re running any kind of schema changes or data backfills with ordering requirements within their ecosystem, they leverage this logic heavily.
Happy coding!
📧 Join the Python Snacks Newsletter! 🐍
Want even more Python-related content that’s useful? Here’s 3 reasons why you should subscribe the Python Snacks newsletter:
Get Ahead in Python with bite-sized Python tips and tricks delivered straight to your inbox, like the one above.
Exclusive Subscriber Perks: Receive a curated selection of up to 6 high-impact Python resources, tips, and exclusive insights with each email.
Get Smarter with Python in under 5 minutes. Your next Python breakthrough could just an email away.
You can unsubscribe at any time.
Interested in starting a newsletter or a blog?
Do you have a wealth of knowledge and insights to share with the world? Starting your own newsletter or blog is an excellent way to establish yourself as an authority in your field, connect with a like-minded community, and open up new opportunities.
If TikTok, Twitter, Facebook, or other social media platforms were to get banned, you’d lose all your followers. This is why you should start a newsletter: you own your audience.
This article may contain affiliate links. Affiliate links come at no cost to you and support the costs of this blog. Should you purchase a product/service from an affiliate link, it will come at no additional cost to you.
