Here's a curated list of topological sort problems frequently asked by FAANG companies, organized by difficulty and problem pattern.
Link: https://leetcode.com/problems/course-schedule/
Difficulty: Medium
Why FAANG Loves It: Classic cycle detection in directed graph - tests understanding of topological sort prerequisites
Companies: Amazon, Meta, Google, Microsoft
Link: https://leetcode.com/problems/course-schedule-ii/
Difficulty: Medium
Why FAANG Loves It: Extends Course Schedule - must actually return the topological order
Companies: Amazon, Meta, Google, Microsoft, Apple
Link: https://leetcode.com/problems/minimum-height-trees/
Difficulty: Medium
Why FAANG Loves It: Tests topological sort on undirected graphs + creative thinking
Companies: Google, Meta, Amazon
Link: https://leetcode.com/problems/alien-dictionary/ 🔒
Difficulty: Hard
Why FAANG Loves It: EXTREMELY POPULAR - combines graph construction + topological sort + edge case handling
Companies: Google (favorite), Meta, Amazon, Microsoft, Apple
Link: https://leetcode.com/problems/sequence-reconstruction/ 🔒
Difficulty: Medium
Why FAANG Loves It: Tests understanding of unique topological ordering
Companies: Google, Amazon
Link: https://leetcode.com/problems/course-schedule-iii/
Difficulty: Hard
Why FAANG Loves It: Combines greedy + topological thinking (though more greedy-focused)
Companies: Google, Meta
Link: https://leetcode.com/problems/parallel-courses/ 🔒
Difficulty: Medium
Why FAANG Loves It: Tests BFS-based topological sort with level tracking
Companies: Amazon, Google
Link: https://leetcode.com/problems/parallel-courses-ii/ 🔒
Difficulty: Hard
Why FAANG Loves It: Topological sort + dynamic programming/bitmask - very challenging
Companies: Google, Meta
Link: https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/
Difficulty: Hard
Why FAANG Loves It: Multi-level topological sort - separates senior candidates from others
Companies: Google, Amazon, Meta
Link: https://leetcode.com/problems/build-a-matrix-with-conditions/
Difficulty: Hard
Why FAANG Loves It: 2D topological sort - tests deep understanding
Companies: Google, Amazon
Link: https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/
Difficulty: Medium
Why FAANG Loves It: Disguised topological sort - tests pattern recognition
Companies: Amazon, Microsoft
Link: https://leetcode.com/problems/loud-and-rich/
Difficulty: Medium
Why FAANG Loves It: DFS/topological sort with memoization
Companies: Meta, Google
Link: https://leetcode.com/problems/strange-printer-ii/
Difficulty: Hard
Why FAANG Loves It: Non-obvious topological sort application
Companies: Google
- Master Course Schedule I & II
- Understand both BFS (Kahn's) and DFS approaches
- Practice explaining your approach out loud
- Alien Dictionary - practice 5+ times until fluent
- Parallel Courses - master level-by-level processing
- Minimum Height Trees - understand the "peeling" technique
- Sort Items by Groups - this will prepare you for anything
- Build a Matrix With Conditions - dual topological sort mastery
- Practice disguised problems to sharpen pattern recognition
- Cycle Detection (DFS with color marking)
- Kahn's Algorithm (BFS with in-degree counting)
- Multi-level Topological Sort (nested graph dependencies)
- Unique vs Multiple Valid Orders (checking uniqueness)
- Level-by-level Processing (parallel execution simulation)
🔥 Hot Topics:
- Google: Alien Dictionary, Sort Items by Groups, Multi-level sorts
- Amazon: Course Schedule variations, Parallel Courses, Recipe problems
- Meta: Alien Dictionary, Minimum Height Trees, Loud and Rich
- Microsoft: Course Schedule, Find All Recipes, Basic to Medium problems
Ready to tackle one? Pick a problem and let me know - I'll guide you through with hints! 🎯