Determine task order with prerequisites
AdobeSoftware Engineer · Technical ScreenLast updated
This question evaluates a candidate's proficiency with graph-theoretic concepts like dependency modeling and cycle detection, and their ability to produce valid task orderings under constraints within the Coding & Algorithms domain.
You are given n tasks labeled 0..n−1 and a list of prerequisite pairs (a, b) meaning task b must be completed before task a. Determine one valid order in which to complete all tasks, or report that it is impossible if dependencies contain a cycle. Describe the algorithm, data structures, and complexity, and explain how you would detect cycles and handle multiple valid orders.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.